4.1 二項式係數與展開

先計數，再展開

二項式定理常被記成公式，但公式背後其實是計數。展開 $(x+y)^n$ 時，每個乘積都來自於在 $n$ 個括號中各選一個 $x$ 或 $y$。不同的選擇可以產生同一個單項式，而它的係數正是產生這個單項式的選法數。因此，必須區分乘法過程中得到的乘積與合併同類項後留下的項。

核心問題是：有多少種方法可以選出提供 $y$ 的括號？這些括號的位置很重要，但列舉這些位置時的先後次序並不重要。階乘、排列與組合使這個區別變得精確，也說明了為甚麼二項式係數是整數，以及為甚麼尋找一個係數時不必寫出整個展開式。

階乘、排列、組合

定義

階乘

對正整數 $n$，

$$n! = n(n-1)(n-2)\cdots 2\cdot 1.$$

約定 $0! = 1$。

把 $n$ 個不同物件不重複地排成一列，第一位置有 $n$ 種選擇，第二位置剩下 $n-1$ 種，依此類推。把各步的選擇數相乘，就得到階乘。這是逐步計數的乘法原理：每個已經完成的部分排列，都有相同數目的下一步選擇。零的階乘取一，對應唯一的空排列，而不是沒有排列。

定義

排列

設 $n,k$ 為整數且 $0 ≤ k ≤ n$。從 $n$ 個不同物件中不重複地取出 $k$ 個，並排成有次序的一列，稱為一個 $k$-排列。其數量為

$$P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.$$

當 $k=0$ 時，乘積沒有因子，稱為空積，其值為 $1$。

乘積中恰好有 $k$ 個因子：最後一步已經用去 $k-1$ 個物件，所以還剩 $n-(k-1)=n-k+1$ 種選擇。階乘的商只是約去從 $n-k$ 到 $1$ 的未用因子，並沒有增加一次選擇。特別地，$P(n,n)=n!$ 計算全部物件的排列，而 $P(n,0)=1$ 計算唯一的空有序選擇。

無序選擇只說明選中了哪些物件；有序選擇還要說明它們的位置；排列一個已經選定的集合，則只決定內部次序。例如，從字母 $A,B,C,D,E$ 中依次選出三個不同字母，共有 $P(5,3)=5\cdot4\cdot3=60$ 個結果。序列 $A,B,C$ 與 $C,B,A$ 是不同的有序結果，卻對應同一個三元素集合。使用計數公式前，應先判斷題目是否區分這樣的兩個結果。

定義

二項式係數

對滿足 $0 ≤ k ≤ n$ 的整數 $n,k$，定義

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

它計算一個 $n$ 元素集合的 $k$ 元素子集數，也稱為 $k$-組合數。記號 $C(n,k)$ 表示同一個數。

每個固定的 $k$ 元素選擇，都恰好有 $k!$ 種內部排列。因此，可以把有序選擇分成大小相同的組：包含相同物件的有序選擇屬於同一組。按組計數得到

$$P(n,k)=\binom{n}{k}k!, \qquad \binom{n}{k}=\frac{P(n,k)}{k!}.$$

這既解釋了為甚麼要除以階乘，也說明所得的商一定是整數。在五個字母的例子中，每組有 $3!=6$ 種次序，所以無序選擇共有 $60/6=10$ 種。這裏能除以同一個數，是因為物件互不相同，每個選擇都有同樣多的內部次序。組合數已經消去了這些次序，不能再重複除一次。

例題

帶限制的座位安排

有 $m$ 個不同的女生與 $n$ 個不同的男生排成一列，假設 $m\gt n$，且不允許兩個男生相鄰。我們區分每個人，因此交換兩個女生或兩個男生都會得到不同的座位安排。

先排列女生，共有 $m!$ 種方法。對每個固定的女生次序，都有 $m+1$ 個空隙：最前面一個，相鄰女生之間各一個，最後面一個。每個空隙最多放一個男生；若同一空隙放入兩個男生，他們就會相鄰。

先從這些空隙中選出 $n$ 個，共有 $\binom{m+1}{n}$ 種選法；再把 $n$ 個男生安排到選定的空隙中，共有 $n!$ 種方法。空隙本身已有從左到右的次序，需要安排的是男生。因此，

$$\binom{m+1}{n}n!=P(m+1,n)=\frac{(m+1)!}{(m+1-n)!}.$$

再乘以女生的排列數，得到

$$m!\binom{m+1}{n}n!=m!P(m+1,n) =m!\frac{(m+1)!}{(m+1-n)!}.$$

這個過程沒有重複計數：每個最終座位安排都唯一決定女生次序、被佔用的空隙，以及各空隙中的男生；反過來，每組這樣的選擇都會給出合法安排。原假設 $m\gt n$ 保證空隙足夠，但同一論證實際上適用於滿足 $n ≤ m+1$ 的非負整數。當 $m=0$ 時，把空的一列視為一個空隙。當 $n=m+1$ 時，所有空隙都被佔用；當 $n\gt m+1$ 時，不可能避免男生相鄰，答案為零，此時不能套用上面的階乘商。

Pascal 恆等式

定理

基本二項式係數恆等式

設 $n$ 為非負整數。對滿足 $0 ≤ k ≤ n$ 的整數 $k$，

$$\binom{n}{0}=\binom{n}{n}=1, \qquad \binom{n}{k}=\binom{n}{n-k}.$$

對滿足 $0 ≤ k ≤ n-1$ 的整數 $k$，

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

空子集只有一個，包含全部物件的子集也只有一個，所以兩端的係數都是一。這也包括原集合為空時的 $\binom00=1$。對稱性則來自取補集：每個選中的 $k$ 元素子集，都唯一對應未選中的 $n-k$ 元素子集；再取一次補集，就返回原來的選擇。因此兩種選擇的數目相同。在階乘公式中，這個對稱性表現為分母中兩個因子的交換。

最後一條是 Pascal 恆等式。上標增加一，是因為可供選擇的物件增加了一個。要數 $n+1$ 個不同物件的 $k+1$ 元素子集，可先指定其中一個物件，再分成兩種情況。包含指定物件的子集，還須從其餘 $n$ 個中選 $k$ 個，有 $\binom nk$ 個；不包含指定物件的子集，則須從其餘物件中選齊 $k+1$ 個，有 $\binom n{k+1}$ 個。這兩類互不重疊，又涵蓋所有可能，因此計數相加。指標範圍保證兩種選擇都在上述階乘定義的範圍內。

證明

Pascal 恆等式的代數證明

對滿足 $0 ≤ k ≤ n-1$ 的整數 $k$，計算

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

取公分母 $(k+1)!(n-k)!$。第一項的分子須乘 $k+1$，第二項的分子須乘 $n-k$，所以分子之和為

$$n!(k+1)+n!(n-k)=n!(n+1).$$

因此

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

最後一個階乘的指標正確，因為 $(n+1)-(k+1)=n-k$。核對這個差，可以避免最後寫出的上下標相差一位。

Pascal 三角形從第零行開始，把 $\binom nk$ 放在第 $n$ 行，$k$ 從零到 $n$。前五行為

$$\begin{array}{c} 1\\ 1\quad1\\ 1\quad2\quad1\\ 1\quad3\quad3\quad1\\ 1\quad4\quad6\quad4\quad1 \end{array}$$

每行的首尾都是一，每個內部數字等於上方相鄰兩個數字之和；補集對稱性還使每行左右對稱。這些規律都由計數恆等式解釋，不需要把它們當成互不相關的口訣。

例題

格點路徑

若每一步只能向右或向上走一格，從 $(0,0)$ 到 $(5,3)$ 有多少條路徑？

每條路徑都需要 $8$ 步，其中 $5$ 步向右、$3$ 步向上。選出八個位置中哪五個是向右的步，剩下的步就全部確定，從而整條路徑也確定。反過來，每個這樣的選擇都會到達目標。因此路徑數是

$$\binom{8}{5}=\binom{8}{3}=56.$$

這裏不再乘 $5!$ 或 $3!$：向右的步沒有各自的標籤，交換兩步向右的移動，不會改變路徑。一般地，到達 $(k,n-k)$ 的路徑數為 $\binom nk$。

這也給出 Pascal 恆等式的幾何解釋。到達 $(k+1,n-k)$ 的路徑，最後一步要麼從 $(k,n-k)$ 向右走，要麼從 $(k+1,n-k-1)$ 向上走。按最後一步分類計數，便得到 $\binom nk+\binom n{k+1}=\binom{n+1}{k+1}$，其中 $0 ≤ k ≤ n-1$。

二項式定理

定理

二項式定理

對每個正整數 $n$，

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

概念視角組合

一個子集對應展開中的一組選擇

設 $n\ge1$、$0\le k\le n$ 為整數，並把 $x,y$ 視為可交換的變量。 給 $(x+y)^n$ 的 $n$ 個因子標上 $1,\ldots,n$。

選擇觀點。 標籤的 $k$ 元素子集 $S$ 恰好指定哪些因子提供 $y$，其餘因子均提供 $x$。 改變列舉 $S$ 中元素的次序不會改變選擇，所以計數為 $\binom nk$，無需再乘 $k!$。

代數觀點。 分配律讓每組選擇貢獻一個乘積；交換律使選取 $k$ 個 $y$ 的乘積 都成為同一單項式 $x^{n-k}y^k$。反過來，產生這些形式指數的每組選擇都確定唯一的上述子集。 合併貢獻後，係數便是 $\binom nk$。該係數恆等式隨後適用於所有實數代入，包括零。

這裏 $k$ 數的是 $y$ 的選擇數；若改數 $x$，指標便換成 $n-k$。 端點子集 $S=\varnothing$ 與 $S=\{1,\ldots,n\}$ 各給出一種選擇。 遍歷所有子集大小，合併前共有 $2^n$ 個乘積。

每個乘積的總次數都是 $n$，即兩個指數之和為 $n$。當 $k$ 從零增加到 $n$ 時，$x$ 的指數逐漸減少，$y$ 的指數逐漸增加，合併後共有 $n+1$ 個單項式位置。兩端是 $x^n$ 和 $y^n$，係數均為一。若改為記錄提供 $x$ 的因子數，就得到另一種等價寫法：

$$(x+y)^n=\sum_{k=0}^n\binom nk x^k y^{n-k}.$$

兩種約定都正確，但同一次計算必須始終使用所選的約定。把求和次序倒過來時，補集對稱性保證對應的係數相同。

Pascal 恆等式也解釋了歸納步驟。把 $n$ 次方的展開式乘以 $x+y$，內部項 $x^{n+1-j}y^j$ 有兩個來源：原來指標為 $j$ 的項乘 $x$，以及原來指標為 $j-1$ 的項乘 $y$。當 $1 ≤ j ≤ n$ 時，合併係數得到 $\binom nj+\binom n{j-1}=\binom{n+1}j$。兩端的項則各出現一次。從一次方開始，就能逐行推出所有正整數次方的公式。

例題

展開小次方

當 $n=3$，

$$(x+y)^3=x^3+3x^2y+3xy^2+y^3.$$

$x^2y$ 的係數三，數的是乘積 $yxx$、$xyx$、$xxy$：三個因子中恰好一個提供 $y$。同樣，選擇兩個位置提供 $y$，得到貢獻給 $xy^2$ 的三個乘積。不選任何 $y$ 或全部選擇 $y$，則得到兩端的項。因此，合併前的 $8$ 個乘積變成 $4$ 個單項式，係數為 $1,3,3,1$，而係數之和仍然數盡全部八種選擇。

代入特定數值，可以把這個觀察推廣。取 $x=y=1$，每個單項式都變成一，所以係數之和為 $2^n$；取 $x=1$、$y=-1$，各項交替帶正負號，總和為零。對正整數 $n$，即

$$\sum_{k=0}^n\binom nk=2^n, \qquad \sum_{k=0}^n(-1)^k\binom nk=0.$$

第二個等式表示偶數元素子集與奇數元素子集的數目相等。這裏正整數條件不能忽略：若 $n=0$，交錯和只含一個值一。兩次代入都直接使用已經證明的有限二項式定理。

抽取係數

只尋找某一項時，二項式定理尤其方便。先寫一般項，把原括號中的每個完整加數看作一個整體，再把組合數、數值因子、正負號與變數指數分開處理。指數幫助我們確定指標，卻不會單獨給出係數。

對於 $(ax^p+bx^q)^n$，其中 $a,b$ 是數值常數，$p,q$ 是整數指數，代入有限二項式定理得到

$$T_k=\binom nk (ax^p)^{n-k}(bx^q)^k =\binom nk a^{n-k}b^k x^{p(n-k)+qk}, \qquad k=0,1,\ldots,n.$$

若出現負指數，須有 $x\ne0$。要求 $x^r$ 的係數，就解方程 $p(n-k)+qk=r$，只保留滿足 $0 ≤ k ≤ n$ 的整數指標。對每個合法指標，計算 $\binom nk a^{n-k}b^k$，包括常數帶來的正負號。沒有合法指標時，係數為零。當 $p\ne q$ 時，至多只有一個指標符合；若多項具有同一指數，就必須把它們的係數相加。

例題

尋找常數項

找出

$$\left(x^3-\frac{1}{x}\right)^9, \qquad x\ne0$$

的常數項。

第二個加數是完整的 $-1/x$，所以選擇它 $k$ 次，既會產生 $(-1)^k$，也會產生 $x^{-k}$。一般項為

$$\binom{9}{k}(x^3)^{9-k}\left(-\frac1x\right)^k =\binom{9}{k}(-1)^k x^{27-4k}.$$

常數項的指數為零。方程 $27-4k=0$ 給出 $k=27/4$，不是整數。因此展開式沒有常數項，即常數項係數為零。把指標四捨五入，會選中另一個次方，並不能得到所謂近似的常數項。

比較相近的表達式 $(x^2-1/x)^9$，仍取 $x\ne0$。第一個加數的指數改變後，一般項成為

$$\binom9k(x^2)^{9-k}\left(-\frac1x\right)^k =\binom9k(-1)^k x^{18-3k}.$$

此時 $18-3k=0$ 給出 $k=6$，是範圍內的整數，所以常數項為 $\binom96(-1)^6=84$。選了六個負因子，故符號為正。這兩個表達式說明，每次都必須重新計算指數，並檢驗解是否為合法指標。

尋找指定係數時，可依照以下步驟：

1. 寫出一般項，並說明指標記錄哪一種選擇。
2. 化簡變數指數，同時保留所有數值因子的次方與正負號。
3. 令指數等於題目要求的次方。
4. 檢查每個解是否為滿足 $0 ≤ k ≤ n$ 的整數。
5. 把合法指標代入數值係數；若有多個貢獻屬於同一次方，則相加。

常見錯誤

二項式索引必須是範圍內的整數

指標記錄被選中的因子數，所以不能是分數、負數，或大於因子的總數。不合法的指標意味著所求的項沒有出現。即使指標合法，係數通常也不只是組合數：兩個加數中的數值因子及其正負號仍須計算。常數項是指數為零的項，不是把變數代入零；當原式含倒數次方時，代入零尤其沒有意義。

快速檢查

思考檢查

為甚麼 $C(n,k)$ 要除以 $k!$，但 $P(n,k)$ 不需要？

比較有序與無序。

解答 · 答案

$P(n,k)$ 計算有次序排列；$C(n,k)$ 計算無次序選擇，所以要除去每個已選集合內部的 $k!$ 種排列。物件互不相同，保證每個選定集合恰好都有這麼多種次序。

思考檢查

從 $(0,0)$ 到 $(4,2)$，每步只可向右或向上，共有多少條路徑？

數向右步的位置。

解答 · 答案

總共 $6$ 步，其中 $4$ 步向右，所以共有 $\binom64=15$ 條。改選兩步向上的位置，由補集對稱性得到相同答案。

思考檢查

設整數 $n ≥ 2$，$(x+y)^n$ 中 $x^{n-2}y^2$ 的係數是甚麼？

使用二項式定理。

解答 · 答案

係數是 $\binom n2$：恰好選出兩個因子提供 $y$，其餘因子全部提供 $x$。

練習

1. 計算 $\binom{7}{3}$，並說明其計數意思。
2. 用階乘公式證明 $\binom{n}{k}=\binom{n}{n-k}$。
3. 求 $(2x-3)^6$ 中 $x^4$ 的係數。
4. 求 $(x^2+1/x)^6$ 中 $x^0$ 的係數，其中 $x\ne0$。

引導解答

解答 · 參考解答 1

$\binom73=7!/(3!4!)=(7\cdot6\cdot5)/(3\cdot2\cdot1)=35$，代表七元素集合的三元素子集數。每個子集對應六個有序選擇，除法消去了這些內部次序。

解答 · 參考解答 2

對整數 $0 ≤ k ≤ n$，代入公式：$\binom{n}{n-k}=n!/((n-k)!(n-(n-k))!)=n!/((n-k)!k!)=\binom nk$。由 $0!=1$，兩個表達式在端點也都有定義。

解答 · 參考解答 3

一般項為 $\binom6k(2x)^{6-k}(-3)^k$。令 $6-k=4$，得合法整數指標 $k=2$。係數為 $\binom62 2^4(-3)^2=15\cdot16\cdot9=2160$。兩個數值因子的次方都不能遺漏，負數的偶次方使這一項的係數為正。

解答 · 參考解答 4

一般項為 $\binom6k(x^2)^{6-k}x^{-k}=\binom6k x^{12-3k}$。令 $12-3k=0$，得合法整數指標 $k=4$，係數為 $\binom64=15$。兩個加數的數值係數均為正，所以沒有額外負號；這一次，指數方程確實有合法解。