組合學/二項式定理

二項式定理

二項式定理確定了不同和的冪的展開式；寫出來，它就是

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

這裡，${\tbinom {n}{i}}$ 是n 和i 的二項式係數，它在上一章中被定義為一個計數從n 個元素的集合中選擇i 個元素的方法的數量，讀作“從n 個元素中選擇i 個”，它的值可以計算為

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

因此，$(x+2)^{2}=1x^{2}+2x^{1}2^{1}+2^{2}=x^{2}+4x+4\,$

以及 $(x+y)^{5}=x^{5}+5x^{4}y+10x^{3}y^{2}+10x^{2}y^{3}+5xy^{4}+y^{5}\,$

展開式中的係數是帕斯卡三角形中一行中的項。即 $(x+y)^{5}$ 給出了帕斯卡三角形第五行的係數。

組合證明

二項式定理有很多可能的證明。組合證明如下

考慮兩邊 $x^{n-k}y^{k}\,$ 的係數，其中k為固定值。左邊即 $(x+y)^{n}=(x+y)(x+y)\cdots (x+y)$ 展開後，只有 $x^{n-i}y^{i}\,$ 型別項，其中i從0到n。 $x^{n-k}y^{k}\,$ 出現的次數恰好等於從n個數中選出k個數的方法數。這是因為，從每個因子 (x+y) 中，總共有n個因子，我們需要選擇k個y（剩下的就是x）。因此，左邊 $x^{n-k}y^{k}\,$ 的係數將是 ${n \choose k}$。這與右邊係數相符，證明完成。證明應該是邏輯性的，不是陳述句。

推論

二項式定理有許多推論。

首先，在定理中令x = y = 1，我們得到 $2^{n}=\sum _{i=0}^{n}{n \choose i}$。這意味著，一個包含n個元素的集合的子集總數（即 $2^{n}$，我們已經得到了這個結果）等於從n個元素中選擇i個有序集合的方法數的總和，對所有i來說。

其次，在定理中令x = 1，y = -1，我們得到 $0=\sum _{k=0}^{n}(-1)^{k}{n \choose k}$。等價地，這意味著，

$\sum _{k\ odd}{n \choose k}=\sum _{k\ even}{n \choose k}$,

也就是說，對於任何n階集合，其奇數階子集的數量等於其偶數階子集的數量。

第三，透過比較 $x^{k}$ 在 $(1+x)^{m+n}$ 中的係數，我們得到了範德蒙德恆等式。

${\begin{aligned}\sum _{k=0}^{m+n}{m+n \choose k}x^{k}&=(1+x)^{m+n}\\&=(1+x)^{m}(1+x)^{n}\\&={\biggl (}\sum _{k=0}^{m}{m \choose k}x^{k}{\biggr )}{\biggl (}\sum _{k=0}^{n}{n \choose k}x^{k}{\biggr )}\\&=\sum _{k=0}^{m+n}{\biggl (}\sum _{i=0}^{k}{m \choose i}{n \choose k-i}{\biggr )}x^{k},\end{aligned}}$

注意，這裡我們使用的是兩個多項式相乘的定義，它們的次數分別為 *m* 和 *n*，即

${\biggl (}\sum _{i=0}^{m}a_{i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}b_{j}x^{j}{\biggr )}=\sum _{r=0}^{m+n}{\biggl (}\sum _{k=0}^{r}a_{k}b_{r-k}{\biggr )}x^{r},$

其中我們使用約定 *a_s* = 0 對於所有整數 *s* > *m* 和 *b_t* = 0 對於所有整數 *t* > *n*。

比較 $x^{k}$ 的係數，我們得到了範德蒙恆等式

${m+n \choose k}=\sum _{i=0}^{k}{m \choose i}{n \choose k-i},\qquad m,n,k\in \mathbb {N}$

注意，在範德蒙恆等式中將 m 設為 1，我們可以得到上一章中討論的帕斯卡關係，儘管形式略有不同

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

範德蒙德恆等式也有一個組合證明。二項式係數 ${m+n \choose k}$ 代表從 m + n 個元素的集合 $A\bigcup B$ 中選取 k 個子集的個數，其中 $A=\{1,2\cdots m\}$ 和 $B=\{m+1,m+2\cdots m+n\}$。包含 i 個 A 中元素的 k-子集的個數將是 ${m \choose i}{n \choose k-i}$（從 A 中選取 i 個元素，並且從 B 中選取剩下的 k-i 個元素）。求和 $\sum _{i=0}^{k}{m \choose i}{n \choose k-i}$ 計算了所有 i 的這些子集。

範德蒙德恆等式另一個有用的結果是在恆等式中令 m = k = n。這將得到：

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

讓我們看看另一個結果，第四個結果。考慮$(1+x)^{m+n+1}=(1+x)\cdots (1+x)$，其中有$m+n+1$ 個 $(1+x)$ 項在等式右邊。左側 $x^{n+1}$ 的係數是 ${m+n+1 \choose n+1}$。在等式右側，該係數可以透過檢視從 m+n+1 個 (1+x) 型別的項中挑選出 n+1 個 x 和剩下的 1 的方法數量來獲得，這與我們在二項式定理證明中所做的方法類似。假設最右邊的 x 來自第 n+i+1 項，其中 i 顯然從 0 變化到 m。這給了我們從剩下的 n+i 項中選擇 n 個 x 的選擇，這可以在 ${n+i \choose n}$ 種方法中完成。方法總數顯然可以透過對所有可能的 i 求和來獲得。所以 $x^{n+1}$ 的係數將是 $\sum _{i=0}^{m}{n+i \choose n}$，因此我們有關係

${m+n+1 \choose n+1}=\sum _{i=0}^{m}{n+i \choose n}$

與範德蒙德恆等式一樣，該恆等式也可以用組合方法證明。左側表示從 m+n+1 個集合中選擇 n+1 個有序集合的方法數，比如 $\{1,2,\cdots m+n+1\}$。假設對於任何給定的 n+1 個有序集合，最大元素在 n+i+1 中，其中 i 從 0 變化到 m。那麼剩下的 n 個元素必須從 n+i 個元素中選擇，並且這樣做的選擇方法數正好是 ${n+i \choose n}$。對所有 i 求和，我們得到了方法總數，該總數已被確定為左側。只需要將這兩個項等同起來。

在上述恆等式中改變變數，我們得到

${n+1 \choose k+1}=\sum _{i=k}^{n}{i \choose k}$

這也意味著

${n+1 \choose k+1}-{m+1 \choose k+1}=\sum _{i=m+1}^{n}{i \choose k}$