组合数学笔记之二——“二项式系数”

数学 组合数学

---

主页地址 ：月光森林

---

Pascal公式

对于满足 $1 \leq k \leq n - 1$ 的所有整数 $k$ 和 $n$，都有

$$C(n, k) = C(n - 1, k - 1) + C(n - 1, k)$$

pascal三角形 ：

n\k	0	1	2	3	4	5	6	7	8	...
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1
8	1	8	28	56	70	56	28	8	1
...	...	...	...	...	...	...	...	...	...	...

该三角形中的每一项，但不是出现在左边和右边倾斜上等于1的项，通过把上一行的两项加在一起而得到：一项在其直接上方而另一项位于其左边。这和上面的pascal公式是对应的。由此还能得到

1. 对称关系： $C(n ,k) = C(n, n - k)$；
2. 二项式系数恒等式： $C(n, 0) + C(n, 1) + ... + C(n, n) = 2^n$；
3. 
   
   • 在 $k = 1$ 一列上 $C(n, 1) = n$ 是计数数
   • 在 $k = 2$ 一列上的数 $C(n, 2) = n(n - 1) / 2$ 是所谓的三角形数
   • 在 $k = 3$ 一列上的数 $C(n, 3) = n(n - 1)(n - 2) / 3!$ 是所谓的四面体数。

可以对Pascal三角形做出另一种解释。令n是一个非负整数，并令k为满足 $0 \leq k \leq n$ 的整数。定义 $p(n, k)$ 为从左上顶点(项C(0, 0) = 1)到项C(n, k)的路径数，其中，在每一条路径，从一项移动到该项下一行在其直接下方的项或其直接右下方的项。于是Pascal三角形的项C(n, k)的值代表从左上角到这项的路径的条数。

二项式定理

定理一： 令n是一个正整数。于是，对所有的x和y,

$$(x + y)^n = x^n + C(n, 1)x^{n-1}y + C(n, 2)x^{n -2}y^2 + ... + C(n, n - 1)xy^{n-1} + C(n, n)y^n$$ 用求和记号写出，即： $$(x + y)^n = \sum C(n, k)x^{n - k}y^k$$
二项式定理还有几种等价形式： $$(x + y)^n = \sum C(n, n - k)x^{n-k}y^k$$ $$(x+y)^n = \sum C(n, n-k)x^ky^{n-k}$$ $$(s + y)^n = \sum C(n, k)x^ky^{n-k}$$
定理二： 令n是一个正整数。则对所有的x，有 $$(1 + x)^n = \sum C(n, k)x^k = \sum C(n, n - k)x^k$$

一些恒等式

1. $$kC(n, k) = nC(n-1, k - 1) \qquad (n, k \in Z^+)$$
2. $$\sum_{j = 0}^{n} C(n, j) = 2^n \qquad (n ≥ 0)$$
3. $$\sum_{j = 0}^{n}(-1)^jC(n, j) = 0$$
   或者可以写成 $$C(n, 0) + C(n, 2) + ... + = C(n, 1) + C(n, 3) + ... = 2^{n-1}$$
4. $$\sum_{j = 1}^{n}jC(n, j) = n2^{n-1}$$

5. $$\sum_{j = 0}^nC^2(n, j) = C(2n, n)$$

6. $$\sum_{j = 0}^k C(r, j) = C(r + k + 1, k)$$

7. $$\sum_{j = 0}^n C(j, k) = C(n + 1, k + 1)$$

二项式系数的单峰性

令n是正整数，二项式序列$C(n, 0), C(n, 1), C(n, 2), ... , C(n, n)$是单峰序列。更精确地说 :

1. n为偶数时，

   $$C(n, 0) < C(n, 1) < C(n, 2) < ... < C(n, n/2), C(n, n/2) > ... > C(n, n -1) > C(n, n)$$
   1. n为奇数时， $$C(n, 0) < C(n, 1) < C(n, 2) < ... < C(n, (n-1)/2) = C(n, n/2+1), C(n, (n+1)/2) > ... > C(n, n -1) > C(n, n)$$