圖論/二項式係數的雜耍

簡介

熟練掌握二項式係數對於關於圖的組合論證非常有幫助。你應該像熟練運用普通代數方程一樣熟練地運用二項式係數。

技巧

• 在一般方程中代入特定值，例如在以下方程中仔細選擇 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}}$

應用

• 找到排列中特定長度的迴圈的機率。