范数(norm)是在向量空间上定义的一个实值函数：V->R，一般用记号||x||表示，它满足以下三个性质：
(1) ||x||≥0, ||x||=0 ‹=› x=0
(2) ||ax||=|a|•||x|| (a为数域F中的数)
(3)||x+y||≤||x||+||y|| 
对于实数p≥1，定义p-范数

1-范数又被称为“出租车范数”。这个名字很形象，指一个出租车沿着”水平”和”竖直”的街道从向量x起点开到终点所走过的路程。
2-范数又被称为“欧几里德范数”。在欧式空间里，它表示两点间的距离(向量x的模长)。所以性质(3)在欧式空间里就是我们熟知的“两点之间线段最短”
此外，定义∞-范数为：

当看到这个定义时，我们很自然的产生疑问：为什么如此定义∞-范数？它和p-范数有什么关系？
实际上，它们之间是有关系的。p-范数的定义中，令p->∞便得到∞-范数，也即

证明：令
Read the rest of this entry »

当两个连续函数都趋于无穷时，我们常用洛必达法则来比较它们趋向无穷的快慢。函数的阶越高，它趋向无穷的速度就越快。在定义在正整数域上的函数中，n!趋向于正无穷的速度非常快，所以在算法设计中如果出现这样的时间复杂度就太糟糕了。logn趋向无穷的速度则非常慢。
今天你将看到一个增长速度比n!快的多的函数和一个比logn慢的多的函数，它们都源于一个函数–’Ackerman Function’。
并非一切的递归函数都有通项公式，Ackerman函数就是这么一个例子。它是一个双递归函数，有两个自变量(独立)。定义如下： 
 
Read the rest of this entry »

在图书馆里面看到了一本很有意思的书《数学的奥妙》，作者是伊库纳契夫【俄】。它是一本数学科普书，里面有很多趣味的数序题和游戏。给大家推荐一下。我把其中的一些有意思的题写在这里（其实是前几页的，因为我还没看完）：
[1]分子比分母小的分数，能和分子比分母大的分数相等么？
[2]每天中午，轮船由法国的哈弗尔港启航，经由大西洋驶往纽约。同一时刻，同一家公司的轮船从纽约出发驶向哈弗尔港。两艘船的航行日期都需要7日。请问：从哈弗尔经纽约的轮船在抵达纽约时，共和几艘同一家公司反方向的轮船相会？
[3]有位农妇提一篮苹果到市场去卖，第一个客人买走全部苹果的一半加上1/2个，第二个客人买走剩下苹果的一半再加上1/2个，第三个客人再买走剩下的一半又1/2个……第六个客人也买了剩下苹果的一半加1/2个，这时农妇的苹果刚好卖完，而这6个客人所买的苹果都不曾切为两半，请问农妇带了多少苹果到市场去卖？
[4]某一个整数的个位数是2，把2移至最前方，数字立即变为原来的两倍，求原数。
[5]有3个骑士各带着一名随从在河边会合，想渡河到对岸。碰巧发现一艘可以容纳2人的小船。因为随从们都表示不愿意和自己主人以外的骑士在一起，而且无论如何威胁利诱，都没有任何效果，那三个胆怯的随从始终坚持他们的意见。但最后6个人还是凭那艘只能容纳2人的小船平安无事过了河，请问他们是如何做到的呢？ Read the rest of this entry »

骰子是许多娱乐必不可少的工具之一，比如麻将等。不知为何，人们都不约而同的喜欢上了这个小东西。于是各种和其相关的产品都出来了，比如骰子摄像头，骰子笔筒，骰子打火机，骰子坐垫，骰子牙签盒……
我们传统的骰子是六个面，每个面上是1~6中的一个数字。我们投掷一对骰子，并记下两个骰子上的数字之和。出现2的方式只有一种(1+1),出现3的方式有两种(1+2,2+1),…….,出现12的方式有一种(6+6)。
问题来了，我们要找这样的一对骰子(当然也是6个面)，使得：
1 每个骰子上面的点数不能和普通骰子一样，即不能是{1,2,3,4,5,6}
2 每个面上至少有一个点
3 掷这对骰子出现的数字之和n的方式种数和上述普通骰子一样
这里，我们要用一种漂亮的方法解决这个问题。构造一个生成函数：f(x) = x¹ + x² + x³ + x⁴ + x⁵ + x⁶这里xⁿ的指数表示骰子的一个面上点数，xⁿ前面的系数表示形成n的方式种数。当然对于投掷一个普通骰子来说，生成各个数字的种数都是1，所以前面的系数都是1。投掷两个骰子时所能形成的点数之和与形成这个点数的方式种数可以用它们函数的积来表示：
(x¹ + x² + x³ + x⁴ + x⁵ + x⁶)² = x² + 2x³ + 3x⁴ + 4x⁵ + 5x⁶ + 6x⁷ + 5x⁸ + 4x⁹ + 3x¹⁰ + 2x¹¹ + x¹²
你可以验证一下，每个系数正表示了对应数字出现的方式种数。
对于我们要构造的骰子，两个“骰子函数”的积应该正好是上面的多项式。这也就是要把(f(x))²因式分解为两个因式。由于
f(x) = x¹ + x² + x³ + x⁴ + x⁵ + x⁶=x(1+x+x² + x³ + x⁴ + x⁵ )=x(x+1)(x² - x+1)(x²+x+1)
所以
(f(x))² = x²(x + 1)²(x² − x + 1)²(x² + x + 1)²
我们还有两个限制： Read the rest of this entry »

预备知识
排列的定义：
1,2,3…,n排列成一个有序n元数组称为一个n元排列
逆序的定义：
对给定的n元排列p1,p2,…,pn，如果一对数前后位置和它们的大小顺序相反(即左边数大于右边数)，则它们就称为一个逆序
逆序数：n元排列中逆序的个数
容易证明下面这个命题：
设在n元排列p1,p2,…,pn中，用t(pi)表示排列在pi左边但大于pi的数的个数，那么这个n元排列的逆序数 t = t(p1)+t(p2)+…+t(pn)

问题
对于一个固定的n元排列，它的逆序数存在且唯一。那么反过来，已知一个n元排列的逆序数为m，这样的n元排列有多少种？
我们用f(n,m)表示逆序数为m的n元排列的个数,则求满足条件的排列个数问题就转化为求f(n,m)的值的问题。
为了得到最终结果，我们先研究f(n,m)的性质。可以得到以下几个定理： Read the rest of this entry »