「Note」二项式定理与组合恒等式

二项式定理

定理$1$: $(x+y)^n=\sum_{k=0}^n(^n_k)x^ky^{n - k}$

证明$1$:
$$ 当n=1时,公式显然成立.假设公式对于n成立\\ (x+y)^{n+1} = (x + y)^n \times (x+y)\\ =(x+y) \times \sum_{k=0}^n \dbinom {n}{k} x^ky^{n - k}\\ =x\sum_{k=0}^n \dbinom {n}{k} x^ky^{n - k} + y\sum_{k=0}^n \dbinom {n}{k} x^ky^{n - k}\\ =\sum_{k=0}^n \dbinom {n}{k} x^{k + 1}y^{n - k} + \sum_{k=0}^n \dbinom {n}{k} x^ky^{n - k + 1}\\ =\sum_{k=1}^{n+1} \dbinom {n}{k} x^ky^{n - k + 1} + \sum_{k=0}^n \dbinom {n}{k} x^ky^{n - k + 1}\\ =\sum_{k=1}^n \dbinom {n}{k} x^ky^{n - k+1} + x^{n+1}+y^{n+1} \\ =\sum_{k=0}^{n + 1} \dbinom {n}{k} x^ky^{n+ 1 - k} \\ 即公式对n+1成立 $$

组合恒等式

定理$1$: $\dbinom{n}{k}=\dbinom{n}{n-k}$

证明$1$:从组合意义证明，$\dbinom{n}{k}$表示从$n$个物品中留下$k$个的方案数，$\dbinom{n}{n - k}$表示从$n$个物品中拿走$n-k$个的方案数，两者是等价的。

---

定理$2$:$\dbinom{n}{k}=\frac{n}{k}\dbinom{n-1}{k-1}$

证明$2$:可以用公式法。$\dbinom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n}{k}\times \frac{(n - 1)!}{(k-1)![(n - 1) - (k - 1)]!} = \frac{n}{k}\dbinom{n-1}{k-1}$

---

定理$3$:$\dbinom{n}{k}=\dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}$

证明$3$:从组合意义证明，$\dbinom{n}{k}$表示从$n$个物品中选$k$个的方案数，考虑当前的物品，有选它与不选两种情况，如果选它，就等价于从$n - 1$个物品中选$k - 1$的方案数$\dbinom{n - 1}{k}$；如果不选，就等价于从$n - 1$个物品中选$k$个的方案数$\dbinom{n - 1}{k - 1}$，相加即是总方案数。

---

定理$4$: $\sum_{k = 0} ^ {n} \dbinom{n}{k} = 2^n$

证明$4$:从组合意义证明，$\sum_{k = 0} ^ {n} \dbinom{n}{k}$表示从$n$个物品中任意选任意个的方案数，考虑每个物品，有选与不选两种情况，一共就有$2^n$种方案数。

---

定理$5$: $\sum_{k = 0} ^ {n} (-1) ^k \dbinom{n}{k} = 0$

证明$5$:因为$\dbinom{n}{k}=\dbinom{n}{n-k}$,且$$\dbinom{n}{k}$$ 和$\dbinom{n}{n-k}$必定反号，所以等于$0$.

---

定理$6$:$\sum_{k = 0} ^ {n} k \dbinom{n}{k} = n 2 ^ {n - 1}$

证明$6$:因为$\dbinom{n}{k}=\frac{n}{k}\dbinom{n-1}{k-1}$，$\sum_{k = 0} ^ {n} k \dbinom{n}{k} = \sum_0^n n \dbinom{n - 1}{k - 1}=n\sum_0^n\dbinom{n - 1}{k - 1} = n2^{n - 1}$

---

定理$7$:$\sum_{l=0}^n\dbinom{l}{k} = \dbinom{n + 1}{k + 1} n, k \in \mathrm{N}$

证明$7$:从组合意义证明，依次考虑每个元素$A_i$是否包含在集合$\mathrm{S}|\mathrm{S} \in \mathrm{A},|\mathrm{S}|=k+1$中,含$A_1$，方案数为$\dbinom{n}{k}$,不含$A_1$,含$A_2$,方案数为$\dbinom{n - 1}{k}$,$\dots$,不含$A_1, A_2, \dots, A_{n}$,含$A_{n+1}$，方案数为$\dbinom{0}{k}$。转换为变下项求和。