二项式系数

定义

\(\binom{n}{k}\) 计数 \(n\) 元素集合的 \(k\) 子集个数。

如果 \(k>n\) ,则 \(\binom{n}{k}\) = 0，对所有的 \(n\) ，\(\binom{n}{0}=1\)。
如果 \(n\) 是一个正整数，且，则 \(\binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n(n-1)\dots(n-k+1)}{k(k-1)\dots1}\)

显然，其满足对称性，即 \(\binom{n}{k}=\binom{n}{n-k}\)

推论

1.帕斯卡定理

对于所有满足 \(1 \leq k \leq n\) 的正整数 \(k\)，有 \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\)

证法1：

\(\binom{n-1}{k-1}+\binom{n-1}{k}=\frac{(n-1)!}{k!(n-k-1)!}+\frac{(n-1)!}{(k-1)!(n-k)!}=\frac{(n-1)!(n-k)}{k!(n-k)!}+\frac{(n-1)!k}{k!(n-k)!}=\frac{(n-1)!(n-k+k)}{k!(n-k)!}=\frac{n!}{k!(n-k)!}=\binom{n}{k}\)

证法2：

假设有 \(n\) 个字母，1个 \(A\)，其余为 \(B\) 。
考虑选择 \(k\) 个字母的方案数，显然为 \(\binom{n}{k}\)。第二种选法，考虑分字母种类讨论，有两大类：①选 \(A\) : 则还需选 \((k-1)\) 个 \(B\) ,共 \(\binom{n-1}{k-1}\) 种选法; ②不选 \(A\) ，则需选 \(k\) 个 \(B\) ,共 \(\binom{n-1}{k}\) 种选法。则一共为 \(\binom{n-1}{k-1}+\binom{n-1}{k}\) 种。所以有 \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\)

2.\(\sum_{k=0}^{n} \binom{n}{k}=2^n\)

显然，两边分别为 \(n\) 集合的子集个数的一种枚举方式。

3.对于方程 \(x_1+x_2+\dots+x_k=r\) 的非负整数解的个数为 \(\binom{r+k-1}{k-1}\)

构造一个长为 \(k+r-1\) 的序列 \(a_i\) ,且 \(a_i=0\)，对于 \(i\in[1,k+r)\)。
选择其中的 \(k-1\) 个数赋为 \(1\) ，则这 \(k-1\) 个 \(1\) 把序列分为了 \(k\) 段零串（串可为空），每一段的 \(0\) 的个数就对应了一个 \(x\) 的取值，又共有 \(\binom{r+k-1}{k-1}\) 种选法，所以此方程非负整数解的个数也就为 \(\binom{r+k-1}{k-1}\)。

4.范德蒙卷积

\(\sum_{k=0}^n \binom{m_1}{k}\binom{m_2}{n-k}=\binom{m_1+m_2}{n}\)

两个集合 \(A\) 和 \(B\) ，大小分别为 \(m_1\)、\(m_2\)。现从两集合中选出n个数，则方案数为 \(\binom{m_1+m_2}{n}\) 。考虑枚举从 \(A\) 中选择的元素个数，记为 \(k\)，从 \(B\) 中选 \(n-k\) 个元素，则方案数为 \(\binom{m_1}{k}\binom{m_2}{n-k}\)，所以共 \(\sum_{k=0}^n \binom{m_1}{k}\binom{m_2}{n-k}\) 种方案数，
则上式成立。

5. \(k\binom{n}{k}=n\binom{n-1}{k-1}\)

左式为从 \(n\) 个人中选 \(k\) 个人组成小队，再在小队中选一个人当队长的方案数。右式为从 \(n\) 个人中选一人当队长，再在剩下的 \(n-1\) 个人中选 \(k-1\) 个人组成小队的方案数。

显然两式等价。

6.\(\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}\)

由 5 可得，\(\sum_{k=0}^{n}k\binom{n}{k}=\sum_{k=0}^{n}n\binom{n-1}{k-1}=n\sum_{k=0}^{n}\binom{n-1}{k-1}=n2^{n-1}\)

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

\(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\binom{n-2}{k}\)

\(=\binom{0}{k}+\binom{0}{k-1}+\binom{1}{k-1}+\dots+\binom{n-2}{k-1}+\binom{n-1}{k-1}\)

又 \(\binom{0}{k}=0\)，则 \(\binom{n+1}{k+1}=\binom{0}{k}+\binom{1}{k}+\dots+\binom{n-1}{k}+\binom{n}{k}=\sum_{j=0}^n\binom{j}{k}\)

二项式定理

\(n\) 为非负整数，对于所有的 \(x\)、\(y\) 有 \((x+y)^n=\sum_{k=0}^{n} \binom{n}{k}x^{n-k}y^k\)

证明

证法1

\((x+y)^n=(x+y)(x+y)\dots(x+y)\)

对于每一项 \((x+y)\) 都可选择一个 \(x\) 或 \(y\) 相乘，组成 \(x^ky^{n-k}\)。即需从这 \(n\) 个 \((x+y)\) 选 \(k\) 个 \(x\) ,其余选 \(y\),则方案数为 \(\binom{n}{k}\)，即 \(x^ky^{n-k}\) 项的系数为 \(\binom{n}{k}\)。
所以 \((x+y)^n=\sum_{k=0}^{n} \binom{n}{k}x^{n-k}y^k\)

证法2

对于 \(n=1\) ，\((x+y)^1=\sum_{k=0}^{1} \binom{n}{k} x^ky^{n-k}=x^1y^0+x^0y^1=x+y\)

对于 \(n>1\)，\((x+y)^{n+1}=(x+y)(x+y)^n=(x+y)\sum_{k=0}^{n} \binom{n}{k} x^ky^{n-k}\)

\(=\sum_{k=0}^{n} \binom{n}{k} x^{k+1}y^{n-k}+\sum_{k=0}^n \binom{n}{k} x^ky^{n-k+1}\)

\(=\binom{n}{n}x^{n+1}+\sum_{k=0}^{n-1}\binom{n}{k} x^{k+1}y^{n-k}+\binom{1}{0}y^{n+1}+\sum_{k=1}^n\binom{n}{k}x^ky^{n+1-k}\)

\(=\binom{n}{n}x^{n+1}+\sum_{k=1}^{n}\binom{n}{k-1} x^{k}y^{n-k+1}+\binom{1}{0}y^{n+1}+\sum_{k=1}^n\binom{n}{k}x^ky^{n+1-k}\)

\(=\binom{1}{0}y^{n+1}+\sum_{k=1}^{n} [\binom{n}{k-1}+\binom{n}{k}]x^ky^{n+1-k}+\binom{n}{n}x^{n+1}\)

\(=y^{n+1}+\sum_{k=1}^n \binom{n+1}{k} x^ky^{n+1-k}+x^{n+1}\)

\(=\sum_{k=0}^{n+1}\binom{n+1}{k} x^ky^{n+1-k}=(x+y)^{n+1}\)

根据归纳法，此定理成立。

推论

奇偶讨论

对于 \(\sum_{k=0}^{n} \binom{n}{k} x^kx^{n-k}=(x+y)^n\)，\(x=1\)，\(y=-1\) 时，有

\((1-1)^n=\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\dots+(-1)^n\binom{n}{n}=0\)

移项得 \(\binom{n}{0}+\binom{n}{2}+\dots=\binom{n}{1}+\binom{n}{3}+\dots\)

又有 \(\sum_{k=0}^{n} \binom{n}{k}=2^n\)

则 \(\begin{cases} \binom{n}{0}+\binom{n}{2}+\dots=2^{n-1} \\ \binom{n}{1}+\binom{n}{3}+\dots=2^{n-1} \end{cases}\)

牛顿二项式定理

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

其中， \(\alpha\) 为实数， \(0<=|x|<|y|\)。

牛顿二项式系数

\(\binom{\alpha}{k}= \begin{cases} \frac{\alpha(\alpha-1)\dots(\alpha-k+1)}{k!} ， k>0 \\ 1 ，k=0 \\ 0 ，k<0 \end{cases}\)

推论

设 \(z=\frac{x}{y}\)，则 \(|z|<1\) , \((x+y)^{\alpha}=y^{\alpha}(\frac{x}{y}+1)^{\alpha}=y^{\alpha}(1+z)^{\alpha}=y^{\alpha}\sum_{k=0}^{\infty} \binom{\alpha}{k} z^k\)

所以 \((1+z)^{\alpha}=\sum_{k=0}^{\infty} \binom{\alpha}{k} z^k\)

令 \(\alpha\) 等于负整数 \(-n\) ，则

\(\binom{\alpha}{k}=\binom{-n}{k}=\frac{-n(-n-1)\dots(-n-k+1)}{k!}=(-1)^k\frac{n(n+1)\dots(n+k-1)}{k!}=(-1)^k\binom{n+k-1}{k}\)

\((1+z)^{\alpha}=(1+z)^{-n}=\sum_{k=0}^{\infty} (-1)^k\binom{n+k-1}{k} z^k\)

用 \(z\) 代替 \(-z\) ，得到 \((1-z)^{-n}=\frac{1}{(1-z)^n}=\sum_{k=0}^{\infty} \binom{n+k-1}{k} z^k\)

再令 \(n=1\) ,则 \(\frac{1}{1+z}=\sum_{k=0}^{\infty} (-1)^kz^k\)，\(\frac{1}{1-z}=\sum_{k=0}^{\infty} z^k\)

求根

对于 \(\binom{\alpha}{0}=1\),

\(\binom{\alpha}{k}=\binom{\frac{1}{2}}{k}=\frac{\frac{1}{2}(\frac{1}{2}-1)\dots(\frac{1}{2}-k+1)}{k!}=\frac{(-1)^{k-1}}{2^k}\frac{1*3*\dots*(2k-3)}{k!}=\frac{(-1)^{k-1}}{2^k}\frac{(2k-2)!}{2^{k-1}(k-1)!k!}=\frac{(-1)^{k-1}}{k2^{2k-1}}\frac{(2k-2)!}{(k-1)!}=\frac{(-1)^{k-1}}{k2^{2k-1}}\binom{2k-2}{k-1}\)

所以对于 \(|z|<1\) ,有
\(\sqrt{1+z}=(1+z)^{\frac{1}{2}}=1+\sum_{k=1}^{\infty} \frac{(-1)^{k-1}}{k2^{2k-1}}\binom{2k-2}{k-1} z^k\)

多项式定理

\(\binom{n}{n_1 n_2 \dots n_t}=\frac{n!}{n_1!n_2!\dots n_t!}\) 为 \((x_1+x_2+\dots+x_t)^n\) 中的系数，其中 \(n_1+n_2+\dots+n_t=n\)

一般地，\((x_1+x_2+\dots+x_t)^n=\sum\binom{n}{n_1 n_2 \dots n_t}x_1^{n_1}x_2^{n_2}\dots x_t^{n_t}\)

帕斯卡公式

\(\binom{n}{n_1 n_2 \dots n_t}=\sum_{k=1}^t \binom{n-1}{n_1 \dots (n_k-1)\dots n_t}\)