图论/二项式系数的杂耍

简介

熟练掌握二项式系数对于关于图的组合论证非常有帮助。你应该像熟练运用普通代数方程一样熟练地运用二项式系数。

技巧

• 在一般方程中代入特定值，例如在以下方程中仔细选择 x 和 y：

$(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}.$

• 使用递归公式的“大锤”证明。你可能会发现通过帕斯卡三角形的图“跟踪”二项式系数很有帮助。
• 对先前恒等式进行微分以得到新的恒等式。
• 关于排列和组合的组合论证。

实例

示例：2n 要得到 $\sum _{k=0}^{n}{\tbinom {n}{k}}=2^{n}$ 在 $(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}.$

恒等式

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

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

${\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.$

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

$\displaystyle \sum _{k=0}^{n}{\tbinom {n}{k}}^{2}={\tbinom {2n}{n}}.$

$\displaystyle \sum _{k=0}^{n}{\tbinom {n}{k}}{\tbinom {n}{n-k}}={\tbinom {2n}{n}}.$

$\sum _{k=0}^{n}k{\tbinom {n}{k}}=n2^{n-1}$

$\sum _{k=0}^{n}k^{2}{\tbinom {n}{k}}=(n+n^{2})2^{n-2}$

$\sum _{m=0}^{n}{\tbinom {m}{j}}{\tbinom {n-m}{k-j}}={\tbinom {n+1}{k+1}}$

$\sum _{m=0}^{n}{\tbinom {m}{k}}={\tbinom {n+1}{k+1}}\,.$

$\sum _{k=0}^{\lfloor {\frac {n}{2}}\rfloor }{\tbinom {n-k}{k}}=F(n+1)$

其中，F(n) 表示第 n 个 斐波那契数。

$\sum _{j=k}^{n}{\tbinom {j}{k}}={\tbinom {n+1}{k+1}}$

$\sum _{j=0}^{k}(-1)^{j}{\tbinom {n}{j}}=(-1)^{k}{\tbinom {n-1}{k}}$

$\sum _{j=0}^{n}(-1)^{j}{\tbinom {n}{j}}=0$

$\sum _{i=0}^{n}{i{\binom {n}{i}}^{2}}={\frac {n}{2}}{\binom {2n}{n}}$

$\sum _{i=0}^{n}{i^{2}{\binom {n}{i}}^{2}}=n^{2}{\binom {2n-2}{n-1}}$.

$\sum _{k=q}^{n}{\tbinom {n}{k}}{\tbinom {k}{q}}=2^{n-q}{\tbinom {n}{q}}$

应用

• 找到排列中特定长度的循环的概率。