学习笔记-二项式系数

本文整理了《组合数学》中二项式系数的主要内容，包括二项式系数，二项式定理，多项式定理，牛顿二项式定理与常用的组合计数恒等式。

(请刷新以获取数学公式)

二项式系数及扩展

对任意实数$n$，整数$k$，定义二项式系数

由定义易证：

1、(帕斯卡公式)

$$\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}$$

2、(吸收公式)

$$k\dbinom{n}{k}=n\dbinom{n-1}{k-1}$$

二项式定理

1、（二项式定理）设$n$是正整数，对于所有的$x$和$y$，有

$$(x+y)^n=\sum_{k=0}^{n}\dbinom{n}{k}x^{n-k}y^k$$

证明见高中教科书。

2、令$x=y=1$，即得：

$$\dbinom{n}{0}+\dbinom{n}{1}+...+\dbinom{n}{n}=2^n$$

3、令$x=1,y=-1$，即得：

$$\dbinom{n}{0}-\dbinom{n}{1}+\dbinom{n}{2}-...+(-1)^n\dbinom{n}{n}=0$$

这说明在大小为$n$的集合$S$中，有偶数个元素的子集和有奇数个元素的子集均有$2^{n-1}个$

4、对任意正整数$n$，有恒等式:

$$1\dbinom{n}{1}+2\dbinom{n}{2}+...+n\dbinom{n}{n}=n2^{n-1}$$

下面给出证明：

$$令 S=0\dbinom{n}{0}+1\dbinom{n}{1}+...+n\dbinom{n}{n} \\ 又S=0\dbinom{n}{n}+1\dbinom{n}{n-1}+...+n\dbinom{n}{0} \\ \therefore 2S=n\left[\dbinom{n}{0}+\dbinom{n}{1}+...+\dbinom{n}{n}\right] \\ 即S=n2^{n-1}$$

5、对任意整数$n>=1$，有恒等式

$$n(n+1)2^{n-2}=\sum_{k=1}^{n}k^2\dbinom{n}{k}$$

可以用组合推理的形式给出证明：

假设现在要在$n$个人中选出$k$人做班委，并在其中选出一个班长和一个团委（可以兼任），这个方案数显然是$\sum_{k=1}^{n}k^2\tbinom{n}{k}$

如果班长和团委是一个人，有$n2^{n-1}$种方案；如果是两个人，有$n(n-1)2^{n-2}$种方案，共有$n(n+1)2^{n-2}$种方案

两种计数方式的结果显然是相同的，这就证明了上面的恒等式。

6、对任意整数$n>1$，有恒等式

$$\dbinom{n}{1}-2\dbinom{n}{2}+3\dbinom{n}{3}+...+(-1)^{n-1}n\dbinom{n}{n}=0$$

下面给出证明：

$$\because (x-1)^n=\dbinom{n}{0}-\dbinom{n}{1}x+\dbinom{n}{2}x^2...+ (-1)^n\dbinom{n}{n}x^n$$

两边对$x$求导得：

$$n(x-1)^{n-1}=-\dbinom{n}{1}+2\dbinom{n}{2}x-3\dbinom{n}{3}x^2+...+(-1)^nn\dbinom{n}{n}x^{n-1}$$

代入$x=1$知等式成立

7、对任意整数$n>=1$，有恒等式

$$1+\frac{1}{2}\dbinom{n}{1}+\frac{1}{3}\dbinom{n}{2}+...+\frac{1}{n+1}\dbinom{n}{n}=\frac{2^{n+1}-1}{n+1}$$

下面给出证明：

$$(x+1)^n=\dbinom{n}{0}+\dbinom{n}{1}x+\dbinom{n}{2}x^2+...+\dbinom{n}{n}x^n$$

求两边在$[0,1]$内的定积分即得上述等式。

8、（范德蒙卷积公式）对所有的正整数$m_1$,$m_2$和$n$，有恒等式

$$\sum_{k=0}^{n}\dbinom{m_1}{k}\dbinom{m_2}{n-k}=\dbinom{m_1+m_2}{n}$$

作为特殊形式，有恒等式

$$\sum_{k=0}^{n}\dbinom{n}{k}\dbinom{n}{n-k}=\dbinom{2n}{n}$$

下面给出证明：

考虑$(1+x)^{m_1+m_2}$ 的 $x^n$项，它的系数为$\tbinom{m_1+m_2}{n}$

考虑$(1+x)^{m_1}(1+x)^{m_2}$ 的 $x^n$项，是对于所有$k≤n$，第一个式子的$x^k$项与第二个式子的 $x^{n-k}$项的乘积，它的系数为$\sum_{k=0}^{n}\dbinom{m_1}{k}\dbinom{m_2}{n-k}$ 两者显然相等，故等式成立。

多项式定理

对正整数$n$和非负整数$n_1 ,n_2,...n_t$定义多项式系数

$$\dbinom{n}{n_1,n_2,...,n_t}=\frac{n!}{n_1!n_2!...n_t!}$$

可以帕斯卡公式扩展到多项式系数：

$$\dbinom{n}{n_1,n_2,...,n_t}=\dbinom{n-1}{n_1-1,n_2,...,n_t}+\dbinom{n-1}{n_1,n_2-1,...,n_t}+...+\dbinom{n-1}{n_1,n_2,...,n_t-1}$$

将二项式定理推广到多项式定理：

$$(x_1+x_2+...+x_t)^n=\sum_{n_1+n_2+...+n_t=n}\dbinom{n}{n_1,n_2,...,n_t}x_1^{n_1}x_2^{n_2}...x_t^{n_t}$$

证明都和二项的情况相同。

牛顿二项式定理

设$\alpha$是实数。假设$abs(x)$ < $abs(y)$,对于所有$x$和$y$，有

$$(x+y)^{\alpha}=\sum_{k=0}^{\infty}\dbinom{\alpha}{k}x^ky^{\alpha-k}$$

其中

$$\dbinom{\alpha}{k}=\frac{\alpha(\alpha-1)...(\alpha-k+1)}{k!}$$

设$z=x/y$，易知$abs(z)$ < 1，于是有

$$(1+z)^{\alpha}=\sum_{k=0}^{\infty}\dbinom{\alpha}{k}z^k$$

设$n$是正整数，令$\alpha=-n$，则有

$$\dbinom{\alpha}{k}=\dbinom{-n}{k}=\frac{-n(-n-1)...(-n-k+1)}{k!}\\ =(-1)^k\frac{n(n+1)...(n+k-1)}{k!}=(-1)^k\dbinom{n+k-1}{k}$$

因此当$abs(z)$ < 1有

$$\frac{1}{(1+z)^n}=\sum_{k=0}^{\infty}(-1)^k\dbinom{n+k-1}{k}$$

用$-z$代替$z$，于是有

$$\frac{1}{(1-z)^n}=\sum_{k=0}^{\infty}\dbinom{n+k-1}{k}$$

作为特殊情况，当$n=1$时有

$$\frac{1}{1+z}=\sum_{k=0}^{\infty}(-1)^kz^k \\ \frac{1}{1-z}=\sum_{k=0}^{\infty}z^k$$

重要的二项式系数恒等式

1、（阶乘展开式）对整数$n>=k>=0$有

$$\dbinom{n}{k}=\frac{n!}{k!(n-k)!}$$

2、（对称恒等式）对整数$n>=0$，$k$是整数有

$$\dbinom{n}{k}=\dbinom{n}{n-k}$$

3、（吸收恒等式）对整数$k≠0$有

$$k\dbinom{r}{k}=r\dbinom{r-1}{k-1}$$

4、（帕斯卡公式）对整数$k$有

$$\dbinom{r}{k}=\dbinom{r-1}{k}+\dbinom{r-1}{k-1}$$

5、（上指标反转）对整数$k$有

$$\dbinom{r}{k}=(-1)^k\dbinom{k-r-1}{k}$$

6、（三项式版恒等式）对整数$m,k$有

$$\dbinom{r}{m}\dbinom{m}{k}=\dbinom{r}{k}\dbinom{r-k}{m-k}$$

7、（牛顿二项式定理）当$abs(x)$ < $abs(y)$或$\alpha$为整数有

$$(x+y)^{\alpha}=\sum_{k=0}^{\infty}\dbinom{\alpha}{k}x^ky^{\alpha-k}$$

8、（平行求和法）对整数$n$有

$$\sum_{k=0}^{n}\dbinom{r+k}{k}=\dbinom{r+n+1}{n}$$

9、（上指标求和法）对整数$n,m>=0$有

$$\sum_{k=0}^{n}\dbinom{k}{m}=\dbinom{n+1}{m+1}$$

10、（范德蒙卷积公式）对整数$n$有

$$\sum_{k=0}^{n}\dbinom{r}{k}\dbinom{s}{n-k}=\dbinom{r+s}{n}$$