【学习笔记】组合数学 第5章

lyc 比较菜，写出来的东西难免会有锅，可以的话请在下面 Gitalk 里指出。谢谢了qwq

0x00 一些约定

$\binom{n}{k}$ 即 $C_n^k$ ，组合数或二项式系数，表示在 $n$ 元集合中取互不相同的 $k$ 子集的方案数，$\LaTeX$ 是 \binom{n}{k}。

相应地，我们也有 多项式系数 ：

$\binom{n}{n_1\ n_2\dots n_t} = \frac{n!}{n_1!n_2! \dots n_t!}$

一个集合的 $k$ 子集 指的是大小为 $k$ 的子集。

$\binom{n}{0}=1$

0x01 一些定理

也可能说不上是定理

总之是成立的恒等式（

0 组合数的定义

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

1 一些相对显然的东西

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

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

2 二项式定理

$(x+y)^n=\sum\limits_{k=0}^n \binom{n}{k}x^{n-k}y^k$

3 由二项式定理推出来的一些东西

$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\dots+\binom{n}{n}=2^n$

Proof ：用二项式定理展开 $(1+1)^n$ 即得证

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

Proof ：展开 $(1-1)^n$ 即得证

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

Proof ：读者自证不难

4 范德蒙卷积公式

$\sum\limits_{k=0}^{n}\binom{m_1}{k}\binom{m_2}{n-k}=\binom{m_1+m_2}{n}$

作为特殊形式，有

$\sum\limits_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$

Proof ：见习题 25

5 多项式定理

$(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}$

Proof ：读者自证不难

6 牛顿二项式定理

懒得写了（

总之是对于 $(x+y)^a$ （$a$ 为任意实数）的定理（

0x02 习题选讲

1-6. 略

1. 对任意实数 $r$ 求和：

   $\sum\limits_{k=0}^{n} \binom{n}{k}r^k$

   $\begin{aligned} \sum\limits_{k=0}^{n} \binom{n}{k}r^k &= \sum\limits_{k=0}^{n} \binom{n}{k}r^k1^{n-k}\\ &= (r+1)^n \end{aligned}$

2. 用二项式定理证明：

   $2^n=\sum\limits_{k=0}^n (-1)^k \binom{n}{k} 3^{n-k}$

   $\text{原式} =(3-1)^n=2^n$

3. 求和：

   $\sum\limits_{k=0}^n (-1)^k \binom{n}{k} 10^k$

   $\text{原式}= \begin{cases} \sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} 10^k = (10-1)^n=9^n & n\text{为偶数}\\ -\sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} 10^k =-(10-1)^n=-9^n & n\text{为奇数} \end{cases}\\[5mm] \text{故原式}=(-1)^n9^n$

4. 使用 组合推理 证明：

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

   设大小为 $n$ 的有限集合 $S$ ，则等式左右的组合意义为：在 $S$ 中选择一个 $k$ 子集 $S'$，再从 $S'$ 中任选一个元素的方案数

5. 使用 组合推理 证明：

   $\binom{n}{k}-\binom{n-3}{k}=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\binom{n-3}{k-1}$

   设大小为 $n$ 的有限集合 $S$ ，有三个互不相同的元素 $a,b,c\in S$ 。则等式左右的组合意义为：在 $S$ 中选择一个 不同时包含 $a,b,c$ 的 $k$ 子集的方案数。

6. 设 $n$ 是正整数。证明：

   $\sum\limits_{k=0}^{n} (-1)^k \binom{n}{k}^2 = \begin{cases} 0 & \text {若 n 是奇数}\\[5mm] (-1)^m \binom{2m}{m} & \text{若 }n=2m \end{cases}$

   不会（

7. 求出等于下列表达式的二项式系数：

   $\binom{n}{k}+3\binom{n}{k-1}+3\binom{n}{k-2}+\binom{n}{k-3}$

   反复运用 帕斯卡公式 $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ 得

   $\text{原式} = \binom{n+3}{k}$

8. 证明

   $\binom{r}{k}=\frac{r}{r-k}\binom{r-1}{k}$

   其中 $r$ 为 实数， $k$ 是整数且 $r\ne k$ 。

   直接展开即得证

9. 证明：对于每一个整数 $n>1$ ，有

   $\binom{n}{1}-2\binom{n}{2}+3\binom{n}{3}+\dots + (-1)^{n-1} n \binom{n}{n}$

   $\begin{aligned} \text{原式} &= n\binom{n-1}{0}-n\binom{n-1}{1}+n\binom{n-1}{2}+\dots +(-1)^{n-1}n\binom{n-1}{n-1}\\[5mm] &=n\left(\binom{n-1}{0}-\binom{n-1}{1}+\binom{n-1}{2}+\dots +(-1)^{n-1}n\binom{n-1}{n-1} \right)\\[5mm] &=0 \end{aligned}$

10. 证明：对正整数 $n$ ，有

    $1+\frac{1}{2}\binom{n}{1}+ \frac{1}{3}\binom{n}{2}+\dots+ \frac{1}{n+1}\binom{n}{n} = \frac{2^{n+1}-1}{n+1}$

    $\binom{n+1}{0}+\binom{n+1}{1}+\binom{n+1}{2}+\dots+\binom{n+1}{n+1}=2^{n+1}\\[5mm] \binom{n+1}{1}+\binom{n+1}{2}+\dots+\binom{n+1}{n+1}=2^{n+1}-1\\[5mm] 1\binom{n+1}{1}+\frac{1}{2}\times 2 \binom{n+1}{2}+\dots+\frac{1}{n+1} (n+1) \binom{n+1}{n+1}=2^{n+1}-1\\[5mm] (n+1)\binom{n}{0}+\frac{1}{2}(n+1) \binom{n}{1}+\dots+\frac{1}{n+1}(n+1) \binom{n}{n}=2^{n+1}-1\\[5mm] \binom{n}{0}+\frac{1}{2}\binom{n}{1}+\dots+\frac{1}{n+1}\binom{n}{n}=\frac{2^{n+1}-1}{n+1}\\[5mm] 1+\frac{1}{2}\binom{n}{1}+ \frac{1}{3}\binom{n}{2}+\dots+ \frac{1}{n+1}\binom{n}{n} = \frac{2^{n+1}-1}{n+1}$

    证毕

11. 由于不会微积分所以上面两题都是用组合数学的方法证的，所以这题没了。

12. 过程和 16 题几乎一模一样，把初始的式子换成 $(1-1)^{n+1}$ 的展开式就好了。

13. 通过先证明下面的结果并利用恒等式 (5.19) ，求级数 $1^2+2^2+3^2+\dots+n^2$ 的和

    $m^2=2\binom{m}{2}+\binom{m}{1}$

    证明 $m^2=2\binom{m}{2}+\binom{m}{1}$ ：

    使用组合推理：设大小为 $m$ 的集合 $S$ 。等式两边的组合意义为：在 $S$ 中依次选出两个元素（可以相同）的方案数。

    求和：

    $\begin{aligned} \text{原式} &= 2\binom{1}{2}+\binom{1}{1}+2\binom{2}{2}+\binom{2}{1}+\dots+2\binom{n}{2}+\binom{n}{1}\\[5mm] &= 2\binom{n+1}{3}+\binom{n+1}{2} \end{aligned}$

14. 求整数 $a,b,c$ ，使得对所有的 $m$ 有

    $m^3 = a\binom{m}{3}+b\binom{m}{2}+c\binom{m}{1}$

    然后求级数 $1^3+2^3+3^3+\dots+n^3$ 的和

    使用组合推理：设有大小为 $m$ 的集合 $S$ ，则 $m^3$ 的组合意义为：在 $S$ 中依次取 $3$ 个元素 $x,y,z$ （可以相同）的方案数。

    $\binom{m}3{}$ 表示 $x,y,z$ 互不相同的方案数， $\binom{m}{2}$ 表示 $x,y,z$ 中有两个相同的方案数，以此类推。

    $x,y,z$ 可以交换位置，故 $a=3!=6 ,\ b=2!=2,\ c=1!=1$。

    数学证明：直接暴力展开（

    求和：略

15. 暴力展开它不香吗

16. 暴力展开它不香吗

17. (a) $\binom{24}{14}$

    (b) $\binom{9}{4}\binom{15}{6}$

    (c) 草 这个题好无聊 不写了（

18. $\binom{45}{10}\binom{35}{15}$

19. 应用 组合推理 的方法证明二项式系数的 范德蒙卷积公式 ：对于所有的正整数 $m_1,m_2,n$ ，有

    $\sum\limits_{k=0}^{n}\binom{m_1}{k}\binom{m_2}{n-k}=\binom{m_1+m_2}{n}$

    设有 $m_1$ 元集合 $S_1$ ，$m_2$ 元集合 $S_2$ ，且 $S_1\bigcap S_2=\varnothing$ ，则显然右式的组合意义为 $S_1+S_2$ 的 $n$ 子集个数。而左式刚好遍历了每一种选择方案。

21. 设 $n,k$ 是整数且满足 $1\le k \le n$ 。证明：

    $\sum\limits_{k=1}^n k \binom{n}{k}^2 = n \binom{2n-1}{n-1}$

    $\sum\limits_{k=1}^n k \binom{n}{k}^2 = n \binom{2n-1}{n-1} \\[5mm] \sum\limits_{k=1}^n n\binom{n-1}{k-1} \binom{n}{k}=n \binom{2n-1}{n-1} \\[5mm] \sum\limits_{k=1}^n \binom{n-1}{k-1} \binom{n}{k}= \binom{2n-1}{n-1} \\[5mm] \sum\limits_{k=0}^{n-1} \binom{n-1}{k} \binom{n}{k+1}= \binom{2n-1}{n-1} \\[5mm] \sum\limits_{k=0}^n \binom{n-1}{k} \binom{n}{n-k-1}= \binom{2n-1}{n-1}$

    套用范德蒙卷积公式即得证。

还有几题没写 = =
咕咕咕