排列組合

引入

排列組合是組合數學中的基礎。排列就是指從給定個數的元素中取出指定個數的元素進行排序；組合則是指從給定個數的元素中僅僅取出指定個數的元素，不考慮排序。排列組合的中心問題是研究給定要求的排列和組合可能出現的情況總數。排列組合與古典概率論關係密切。

在高中初等數學中，排列組合多是利用列表、枚舉等方法解題。

加法 & 乘法原理

加法原理

完成一個工程可以有 \(n\) 類辦法，\(a_i(1 \le i \le n)\) 代表第 \(i\) 類方法的數目。那麼完成這件事共有 \(S=a_1+a_2+\cdots +a_n\) 種不同的方法。

乘法原理

完成一個工程需要分 \(n\) 個步驟，\(a_i(1 \le i \le n)\) 代表第 \(i\) 個步驟的不同方法數目。那麼完成這件事共有 \(S = a_1 \times a_2 \times \cdots \times a_n\) 種不同的方法。

排列與組合基礎

排列數

從 \(n\) 個不同元素中，任取 \(m\)（\(m\leq n\)，\(m\) 與 \(n\) 均為自然數，下同）個元素按照一定的順序排成一列，叫做從 \(n\) 個不同元素中取出 \(m\) 個元素的一個排列；從 \(n\) 個不同元素中取出 \(m\)(\(m\leq n\)) 個元素的所有排列的個數，叫做從 \(n\) 個不同元素中取出 \(m\) 個元素的排列數，用符號 \(\mathrm A_n^m\)（或者是 \(\mathrm P_n^m\)）表示。

排列的計算公式如下：

\[ \mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} \]

\(n!\) 代表 \(n\) 的階乘，即 \(6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6\)。

公式可以這樣理解：\(n\) 個人選 \(m\) 個來排隊 (\(m \le n\))。第一個位置可以選 \(n\) 個，第二位置可以選 \(n-1\) 個，以此類推，第 \(m\) 個（最後一個）可以選 \(n-m+1\) 個，得：

\[ \mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} \]

全排列：\(n\) 個人全部來排隊，隊長為 \(n\)。第一個位置可以選 \(n\) 個，第二位置可以選 \(n-1\) 個，以此類推得：

\[ \mathrm A_n^n = n(n-1)(n-2) \cdots 3 \times 2 \times 1 = n! \]

全排列是排列數的一個特殊情況。

組合數

從 \(n\) 個不同元素中，任取 \(m \leq n\) 個元素組成一個集合，叫做從 \(n\) 個不同元素中取出 \(m\) 個元素的一個組合；從 \(n\) 個不同元素中取出 \(m \leq n\) 個元素的所有組合的個數，叫做從 \(n\) 個不同元素中取出 \(m\) 個元素的組合數，用符號 \(\dbinom{n}{m}\) 來表示，讀作「\(n\) 選 \(m\)」。

組合數計算公式

\[ \dbinom{n}{m} = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!} \]

如何理解上述公式？我們考慮 \(n\) 個人選 \(m\) 個出來（\(m \le n\)），不排隊，不在乎順序。如果在乎順序那麼就是 \(\mathrm A_n^m\)，如果不在乎那麼就要除掉重複，那麼重複了多少？同樣選出來的 \(m\) 個人，他們還要「全排」得 \(m!\)，所以得：

\[ \begin{aligned} \dbinom{n}{m} \times m! &= \mathrm A_n^m\\ \dbinom{n}{m} &= \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n-m)!} \end{aligned} \]

組合數也常用 \(\mathrm C_n^m\) 表示，即 \(\displaystyle \mathrm C_n^m=\binom{n}{m}\)。現在數學界普遍採用 \(\dbinom{n}{m}\) 的記號而非 \(\mathrm C_n^m\)。

組合數也被稱為「二項式係數」，下文二項式定理將會闡述其中的聯繫。

特別地，規定當 \(m>n\) 時，\(\mathrm A_n^m=\dbinom{n}{m}=0\)。

插板法

插板法（Stars and bars）是用於求一類給相同元素分組的方案數的一種技巧，也可以用於求一類線性不定方程的解的組數。

正整數和的數目

問題一：現有 \(n\) 個 完全相同 的元素，要求將其分為 \(k\) 組，保證每組至少有一個元素，一共有多少種分法？

考慮拿 \(k - 1\) 塊板子插入到 \(n\) 個元素兩兩形成的 \(n - 1\) 個空裏面。

因為元素是完全相同的，所以答案就是 \(\dbinom{n - 1}{k - 1}\)。

本質是求 \(x_1+x_2+\cdots+x_k=n\) 的正整數解的組數。

非負整數和的數目

問題二：如果問題變化一下，每組允許為空呢？

顯然此時沒法直接插板了，因為有可能出現很多塊板子插到一個空裏面的情況，非常不好計算。

我們考慮創造條件轉化成有限制的問題一，先借 \(k\) 個元素過來，在這 \(n + k\) 個元素形成的 \(n + k - 1\) 個空裏面插板，答案為

\[ \binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n} \]

雖然不是直接求的原問題，但這個式子就是原問題的答案，可以這麼理解：

開頭我們借來了 \(k\) 個元素，用於保證每組至少有一個元素，插完板之後再把這 \(k\) 個借來的元素從 \(k\) 組裏面拿走。因為元素是相同的，所以轉化過的情況和轉化前的情況可以一一對應，答案也就是相等的。

由此可以推導出插板法的公式：\(\dbinom{n + k - 1}{n}\)。

本質是求 \(x_1+x_2+\cdots+x_k=n\) 的非負整數解的組數（即要求 \(x_i \ge 0\)）。

不同下界整數和的數目

問題三：如果再擴展一步，要求對於第 \(i\) 組，至少要分到 \(a_i,\sum a_i \le n\) 個元素呢？

本質是求 \(x_1+x_2+\cdots+x_k=n\) 的解的數目，其中 \(x_i \ge a_i\)。

類比無限制的情況，我們借 \(\sum a_i\) 個元素過來，保證第 \(i\) 組至少能分到 \(a_i\) 個。也就是令

\[ x_i^{\prime}=x_i-a_i \]

得到新方程：

\[ \begin{aligned} (x_1^{\prime}+a_1)+(x_2^{\prime}+a_2)+\cdots+(x_k^{\prime}+a_k)&=n\\ x_1^{\prime}+x_2^{\prime}+\cdots+x_k^{\prime}&=n-a_1-a_2-\cdots-a_k\\ x_1^{\prime}+x_2^{\prime}+\cdots+x_k^{\prime}&=n-\sum a_i \end{aligned} \]

其中

\[ x_i^{\prime}\ge 0 \]

然後問題三就轉化成了問題二，直接用插板法公式得到答案為

\[ \binom{n - \sum a_i + k - 1}{n - \sum a_i} \]

不相鄰的排列

\(1 \sim n\) 這 \(n\) 個自然數中選 \(k\) 個，這 \(k\) 個數中任何兩個數都不相鄰的組合有 \(\dbinom {n-k+1}{k}\) 種。

二項式定理

在進入排列組合進階篇之前，我們先介紹一個與組合數密切相關的定理——二項式定理。

二項式定理闡明瞭一個展開式的係數：

\[ (a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i \]

證明可以採用數學歸納法，利用 \(\dbinom{n}{k}+\dbinom{n}{k-1}=\dbinom{n+1}{k}\) 做歸納。

二項式定理也可以很容易擴展為多項式的形式：

設 \(n\) 為正整數，\(x_i\) 為實數，

\[ (x_1 + x_2 + \cdots + x_t)^n = \sum_{滿足 n_1 + \cdots + n_t=n 的非負整數解} \binom{n}{n_1,n_2,\cdots,n_t} x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t} \]

其中的 \(\dbinom{n}{n_1,n_2,\cdots,n_t}\) 是多項式係數，它的性質也很相似：

\[ \sum{\binom{n}{n_1,n_2,\cdots,n_t}} = t^n \]

排列與組合進階篇

接下來我們介紹一些排列組合的變種。

多重集的排列數 | 多重組合數

請大家一定要區分 多重組合數 與 多重集的組合數！兩者是完全不同的概念！

多重集是指包含重複元素的廣義集合。設 \(S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}\) 表示由 \(n_1\) 個 \(a_1\)，\(n_2\) 個 \(a_2\)，…，\(n_k\) 個 \(a_k\) 組成的多重集，\(S\) 的全排列個數為

\[ \frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!} \]

相當於把相同元素的排列數除掉了。具體地，你可以認為你有 \(k\) 種不一樣的球，每種球的個數分別是 \(n_1,n_2,\cdots,n_k\)，且 \(n=n_1+n_2+\ldots+n_k\)。這 \(n\) 個球的全排列數就是 多重集的排列數。多重集的排列數常被稱作 多重組合數。我們可以用多重組合數的符號表示上式：

\[ \binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^kn_i!} \]

可以看出，\(\dbinom{n}{m}\) 等價於 \(\dbinom{n}{m,n-m}\)，只不過後者較為繁瑣，因而不採用。

多重集的組合數 1

設 \(S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}\) 表示由 \(n_1\) 個 \(a_1\)，\(n_2\) 個 \(a_2\)，…，\(n_k\) 個 \(a_k\) 組成的多重集。那麼對於整數 \(r(r<n_i,\forall i\in[1,k])\)，從 \(S\) 中選擇 \(r\) 個元素組成一個多重集的方案數就是 多重集的組合數。這個問題等價於 \(x_1+x_2+\cdots+x_k=r\) 的非負整數解的數目，可以用插板法解決，答案為

\[ \binom{r+k-1}{k-1} \]

多重集的組合數 2

考慮這個問題：設 \(S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}\) 表示由 \(n_1\) 個 \(a_1\)，\(n_2\) 個 \(a_2\)，…，\(n_k\) 個 \(a_k\) 組成的多重集。那麼對於正整數 \(r\)，從 \(S\) 中選擇 \(r\) 個元素組成一個多重集的方案數。

這樣就限制了每種元素的取的個數。同樣的，我們可以把這個問題轉化為帶限制的線性方程求解：

\[ \forall i\in [1,k],\ x_i\le n_i,\ \sum_{i=1}^kx_i=r \]

於是很自然地想到了容斥原理。容斥的模型如下：

全集：\(\displaystyle \sum_{i=1}^kx_i=r\) 的非負整數解。
屬性：\(x_i\le n_i\)。

於是設滿足屬性 \(i\) 的集合是 \(S_i\)，\(\overline{S_i}\) 表示不滿足屬性 \(i\) 的集合，即滿足 \(x_i\ge n_i+1\) 的集合（轉化為上面插板法的問題三）。那麼答案即為

\[ \left|\bigcap_{i=1}^kS_i\right|=|U|-\left|\bigcup_{i=1}^k\overline{S_i}\right| \]

根據容斥原理，有：

\[ \begin{aligned} \left|\bigcup_{i=1}^k\overline{S_i}\right| =&\sum_i\left|\overline{S_i}\right| -\sum_{i,j}\left|\overline{S_i}\cap\overline{S_j}\right| +\sum_{i,j,k}\left|\overline{S_i}\cap\overline{S_j}\cap\overline{S_k}\right| -\cdots\\ &+(-1)^{k-1}\left|\bigcap_{i=1}^k\overline{S_i}\right|\\ =&\sum_i\binom{k+r-n_i-2}{k-1} -\sum_{i,j}\binom{k+r-n_i-n_j-3}{k-1}+\sum_{i,j,k}\binom{k+r-n_i-n_j-n_k-4}{k-1} -\cdots\\ &+(-1)^{k-1}\binom{k+r-\sum_{i=1}^kn_i-k-1}{k-1} \end{aligned} \]

拿全集 \(\displaystyle |U|=\binom{k+r-1}{k-1}\) 減去上式，得到多重集的組合數

\[ Ans=\sum_{p=0}^k(-1)^p\sum_{A}\binom{k+r-1-\sum_{A} n_{A_i}-p}{k-1} \]

其中 A 是充當枚舉子集的作用，滿足 \(|A|=p,\ A_i<A_{i+1}\)。

圓排列

\(n\) 個人全部來圍成一圈，所有的排列數記為 \(\mathrm Q_n^n\)。考慮其中已經排好的一圈，從不同位置斷開，又變成不同的隊列。所以有

\[ \mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)! \]

由此可知部分圓排列的公式：

\[ \mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!} \]

組合數性質 | 二項式推論

由於組合數在 OI 中十分重要，因此在此介紹一些組合數的性質。

\[ \binom{n}{m}=\binom{n}{n-m}\tag{1} \]

相當於將選出的集合對全集取補集，故數值不變。（對稱性）

\[ \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}\tag{2} \]

由定義導出的遞推式。

\[ \binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\tag{3} \]

組合數的遞推式（楊輝三角的公式表達）。我們可以利用這個式子，在 \(O(n^2)\) 的複雜度下推導組合數。

\[ \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}=2^n\tag{4} \]

這是二項式定理的特殊情況。取 \(a=b=1\) 就得到上式。

\[ \sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]\tag{5} \]

二項式定理的另一種特殊情況，可取 \(a=1, b=-1\)。式子的特殊情況是取 \(n=0\) 時答案為 \(1\)。

\[ \sum_{i=0}^m \binom{n}{i}\binom{m}{m-i} = \binom{m+n}{m}\ \ \ (n \geq m)\tag{6} \]

拆組合數的式子，在處理某些數據結構題時會用到。

\[ \sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}\tag{7} \]

這是 \((6)\) 的特殊情況，取 \(n=m\) 即可。

\[ \sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\tag{8} \]

帶權和的一個式子，通過對 \((3)\) 對應的多項式函數求導可以得證。

\[ \sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2}\tag{9} \]

與上式類似，可以通過對多項式函數求導證明。

\[ \sum_{l=0}^n\binom{l}{k} = \binom{n+1}{k+1}\tag{10} \]

通過組合分析一一考慮 \(S=\{a_1, a_2, \cdots, a_{n+1}\}\) 的 \(k+1\) 子集數可以得證，在恆等式證明中比較常用。

\[ \binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\tag{11} \]

通過定義可以證明。

\[ \sum_{i=0}^n\binom{n-i}{i}=F_{n+1}\tag{12} \]

其中 \(F\) 是斐波那契數列。

二項式反演

記 \(f_n\) 表示恰好使用 \(n\) 個不同元素形成特定結構的方案數，\(g_n\) 表示從 \(n\) 個不同元素中選出 \(i \geq 0\) 個元素形成特定結構的總方案數。

若已知 \(f_n\) 求 \(g_n\)，那麼顯然有：

\[ g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i \]

若已知 \(g_n\) 求 \(f_n\)，那麼：

\[ f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i \]

上述已知 \(g_n\) 求 \(f_n\) 的過程，就稱為 二項式反演。

證明

將反演公式的 \(g_i\) 展開得到：

\[ \begin{aligned} f_n &= \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} \left[\sum_{j = 0}^{i} \binom{i}{j} f_j\right] \\ &= \sum_{i = 0}^{n}\sum_{j = 0}^{i}\binom{n}{i}\binom{i}{j} (-1)^{n-i}f_j \end{aligned} \]

先枚舉 \(j\)，再枚舉 \(i\)，得到：

\[ \begin{aligned} f_n &= \sum_{j = 0}^{n}\sum_{i = j}^{n}\binom{n}{i}\binom{i}{j} (-1)^{n-i}f_j \\ &= \sum_{j = 0}^{n}f_j\sum_{i = j}^{n}\binom{n}{i}\binom{i}{j} (-1)^{n-i} \end{aligned} \]

使用「組合數性質 | 二項式推論」的公式 (11) 得到：

\[ \begin{aligned} f_n &= \sum_{j = 0}^{n}f_j\sum_{i = j}^{n}\binom{n}{j}\binom{n - j}{i - j} (-1)^{n-i} \\ &= \sum_{j = 0}^{n}\binom{n}{j}f_j\sum_{i = j}^{n}\binom{n - j}{i - j} (-1)^{n-i} \end{aligned} \]

令 \(k = i - j\)。則 \(i = k + j\)，上式轉換為：

\[ f_n = \sum_{j = 0}^{n}\binom{n}{j}f_j\sum_{k = 0}^{n - j}\binom{n - j}{k} (-1)^{n-j-k}1^{k} \]

使用「組合數性質 | 二項式推論」的公式 (5) 得到：

\[ f_n = \sum_{j = 0}^{n}\binom{n}{j}f_j[n = j] = f_n \]

證畢。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用