排列與組合學(xué)習(xí)筆記

collegiate · 2025-01-05 00:07:56 · 算法·理論

本文章將會(huì)向你講解排列與組合的基本知識(shí)和綜合運(yùn)用。

會(huì)從定義、問題導(dǎo)入、解決方法、經(jīng)典例題、總結(jié)等方面講解。

加法計(jì)數(shù)原理和乘法計(jì)數(shù)原理會(huì)在附錄進(jìn)行講解。

排列的定義為：從給定的 n 個(gè)不同元素中，取出指定個(gè)數(shù)為 m(m \le n) 的元素進(jìn)行排序。

排列的重點(diǎn)在于要進(jìn)行排序，與元素順序有關(guān)。

排列相當(dāng)于是選擇后再排序。

排列數(shù)的定義為從給定的 n 個(gè)不同元素中，取出指定個(gè)數(shù)為 m(m \le n) 的元素所有排列的個(gè)數(shù)。

我們用 A_n^m 表示如上定義。

現(xiàn)在有 5 個(gè)元素，分別為 a,b,c,d,e。要求從這 5 個(gè)元素中任取兩個(gè)排成列的所有可能的個(gè)數(shù)。

我們之前可能通過暴力枚舉來(lái)解決問題：

其中 (x,y) 表示排列所構(gòu)成的二元組，可以發(fā)現(xiàn)，一共有 20 種可能。

但是我們也可以通過乘法計(jì)數(shù)原理解決：

我們分 2 次選擇，第一次顯然有 5 種選法，第二次時(shí)，由于第一次選擇了一個(gè)，所以第二次只有 5 - 1 = 4 種選法了。

然后由乘法計(jì)數(shù)原理得出，一共有 5 \times 4 = 20 種不同的選法。

這樣子以來(lái)，我們就可以用 A_5^2 = 20 來(lái)表示這個(gè)結(jié)果。

如果這道題變成要求從這 5 個(gè)元素中任取三個(gè)排成列的所有可能的個(gè)數(shù)該怎么做呢？

我們還是可以通過暴力枚舉，但是畫圖太麻煩了，但也可以得出一共有 60 種，這種辦法并不適用于數(shù)據(jù)大的排列。

然后再嘗試通過乘法計(jì)數(shù)原理解決：

我們第一次可以選 5 個(gè)，但是第二次選的時(shí)候只能選 5 - 1 = 4 個(gè)，第三次選的時(shí)候只能選 4 - 1 = 3 個(gè)，然后總共就有 5 \times 4 \times 3 = 60 種。

我們用 A_5^3 = 60 來(lái)表示上述結(jié)果。

對(duì)于 A_n^m 來(lái)說(shuō)，我們將它抽象成選元素，即從 n 個(gè)元素種選 m 個(gè)所有排列的個(gè)數(shù)。

我們第一次可以選 n 個(gè)，第二次可以選 n-1 個(gè)，第三次可以選 n-2 個(gè)，以此類推。然后根據(jù)乘法計(jì)數(shù)原理就可以得出以下公式：

那么我們變換再化簡(jiǎn)一下，也就得到了：

我們就得出了求 A_n^m 的公式。

組合的定義為：從給定的 n 個(gè)不同元素中，取出指定個(gè)數(shù)為 m(m \le n) 的元素不進(jìn)行排序。

組合的重點(diǎn)在于要不進(jìn)行排序，與元素順序無(wú)關(guān)。

組合相當(dāng)于是選擇的結(jié)果。

組合數(shù)的定義為從給定的 n 個(gè)不同元素中，取出指定個(gè)數(shù)為 m(m \le n) 的元素所有組合的個(gè)數(shù)。

我們用 C_n^m 表示如上定義。

現(xiàn)在有 5 個(gè)元素，分別為 a,b,c,d,e。要求從這 5 個(gè)元素中任取兩個(gè)組合的所有可能的個(gè)數(shù)。

注意到，剛才是排列，現(xiàn)在是組合，我們先把剛才的暴力枚舉的表拿出來(lái)：

可以發(fā)現(xiàn)，有些二元組對(duì)于組合來(lái)說(shuō)是重復(fù)了的。

例如 (a,b) 和 (b,a) 就是相同的，也就是說(shuō)，每一組數(shù)對(duì)于組合來(lái)說(shuō)重復(fù)了 2 次。

首先，我們用 C_5^2 來(lái)表示上述的答案，那么怎么求呢？

我們剛才知道，每個(gè)數(shù)對(duì)于組合來(lái)說(shuō)重復(fù)了 2 次，所以我們就可以得到：

如果這道題變成要求從這 5 個(gè)元素中任取三個(gè)組合的所有可能的個(gè)數(shù)該怎么做呢？

我們從上文知道，要求排列數(shù)，就是 A_5^3 = 60 即可，但是如何求組合呢？

我們就要看每組數(shù)對(duì)于組合來(lái)說(shuō)重復(fù)了幾次，也就是求這個(gè)三元組可以組成多少種排列，即 A_3^3。

所以對(duì)于 C_5^3 來(lái)說(shuō)，答案就為：

我們首先了解全排列：

對(duì)于 A_n^m 來(lái)說(shuō)，若 n = m 則這個(gè)排列數(shù)就是全排列。

要求組合數(shù)，最重要的就是知道對(duì)于組合來(lái)說(shuō)重復(fù)的個(gè)數(shù)。

若取出 m 個(gè)元素，那么重復(fù)的次數(shù)就是這 m 個(gè)元素所組成的排列數(shù)，也就是 A_m^m。不難發(fā)現(xiàn)，重復(fù)的次數(shù)就是 m 的全排列。

所以就可以得到以下公式:

再將它展開和化簡(jiǎn)，就可以得到最后的公式了：

這就是我們想要的公式了。

我們已經(jīng)了解了排列與組合的基本知識(shí)，現(xiàn)在讓我們來(lái)做一些題，鞏固一下知識(shí)吧！

我們要了解在什么時(shí)候用排列，在什么時(shí)候用組合。

有序的安排我們使用排列；無(wú)序的選擇我們使用組合。因?yàn)榕帕惺怯行虻模M合是無(wú)序的。

從 8 名學(xué)生中挑選 1 人搬東西，挑選 1 人幫老師接水，挑選 1 人接送老師，共有幾種不同方案？

看到挑選，也就是選擇，我們使用組合。

挑選 1 人搬東西，也就是從 8 個(gè)人中選擇 1 個(gè)人，即 C_8^1 為答案。

挑選 1 人幫老師接水，也就是從 7 個(gè)人中選擇 1 人，因?yàn)閯偛胚x走了一個(gè)人，所以現(xiàn)在只有 7 個(gè)。即 C_7^1 為答案。

挑選 1 人接送老師，也就是從 6 個(gè)人中選擇 1 人，因?yàn)閯偛胚x走了兩個(gè)人，所以現(xiàn)在只有 6 個(gè)。即 C_6^1 為答案。

然后根據(jù)乘法計(jì)數(shù)原理計(jì)算最終答案：

但是這一道題就不可以用排列嗎？當(dāng)然可以！

我們將題看成將 8 名學(xué)生安排到 3 個(gè)任務(wù)里面去，這不就是 A_8^3 嗎？

我們通過計(jì)算可以得出這和剛才的答案是一樣的！

有 3 個(gè)蘋果和 3 個(gè)香蕉，現(xiàn)在選擇 2 個(gè)蘋果和 2 個(gè)香蕉，每天吃一個(gè)水果，問有多少種安排方法。

我們一步一步看問題，看到先選擇，就用組合。

從 3 個(gè)蘋果中選 2 個(gè)，也就是 C_3^2；從 3 個(gè)香蕉中選 2 個(gè)，也是 C_3^2。

然后我們看見安排方法，就用排列。

我們將問題抽象為，將這 4 個(gè)水果安排進(jìn) 4 天的位置里面，也就是 A_4^4。

最后就可以運(yùn)用乘法計(jì)數(shù)原理求出答案：

從 3 名社恐和 5 名社牛中挑選 1 人搬東西，挑選 1 人幫老師接水，挑選 1 人接送老師，要求至少要有 1 名社恐，共有幾種不同方案？

這一題相比前面的題多了一個(gè)要求，考慮解決這個(gè)要求。

我們采用排列的思想，也就是將問題抽象成：將 8 個(gè)人放進(jìn) 3 個(gè)任務(wù)里面，要求至少 1 名社恐。

但是如何解決這個(gè)要求呢？我們正面思考的話，對(duì)于這個(gè)要求來(lái)說(shuō)，可能會(huì)有 1 個(gè)或 2 個(gè)或 3 個(gè)社恐，非常麻煩。所以我們考慮逆向思考。

要求至少有 1 名社恐，逆向思考就是沒有社恐唄，也就是全是社牛。也就是 A_5^3

而我們只用拿全部排列數(shù)減去全是社牛的排列數(shù)，不就是有社恐的排列數(shù)嗎？

總共的排列數(shù)可以求出來(lái)，即 A_8^3 為答案；而全是社牛的排列數(shù)已經(jīng)求了出來(lái)，所以這題的答案就出來(lái)了：

有 6 個(gè)人甲、乙、丙、丁、戊、己排成一橫排，最左方只能是甲或者是乙，且最右端不能是甲，問有多少種排列方法。

這一題除了要求排列方法，還有要求，并且甲的事最多，所以從甲入手。

由題可得，甲只能在 1 號(hào)位至 5 號(hào)位之間，但是當(dāng)甲再 1 號(hào)位的時(shí)候與再 2 至 5 號(hào)位時(shí)是不同的，所以對(duì)甲進(jìn)行分類討論。

當(dāng)甲在 1 號(hào)位時(shí)，就可以將問題抽象為將乙、丙、丁、戊、己放進(jìn)后面的 5 個(gè)位置，即 A_5^5 為答案。

當(dāng)甲不在 1 號(hào)位時(shí)，即在 2 至 5 號(hào)位時(shí)，可以抽象為將甲安排進(jìn)這 4 個(gè)位置，即 A_4^1 為答案。

因?yàn)榧撞辉?1 號(hào)位上，所以乙就必須在 1 號(hào)位上，這樣才滿足條件。

然后就是將丙、丁、戊、己放進(jìn)剩余的 4 個(gè)位置，也就是 A_4^4 為答案。

最后的甲不在 1 號(hào)位的總方案數(shù)就為 A_4^1 \times A_4^4。

那么最后只要將兩種情況加起來(lái)就是總方案數(shù)了：

有 5 個(gè)人甲、乙、丙、丁、戊排成一橫排，甲不能站在兩端，丙要和丁相鄰，問有多少種不同的排列方法。

這一題除了有位置要求之外，丙還要和丁相鄰，我們可以先處理這個(gè)條件。

我們將丙和丁看成一個(gè)元素，再和甲、乙和戊排隊(duì)，所以只剩下了 4 個(gè)位置。

但是計(jì)算之前，我們發(fā)現(xiàn)丙和丁是可以交換位置的，因?yàn)楸投≈g也要排隊(duì)，所以事先要求出 A_2^2 的值。

我們?cè)賮?lái)看另一個(gè)條件，也就是甲不能在兩端，那么說(shuō)明甲只能在 2 號(hào)位或者 3 號(hào)位，因?yàn)橐还簿?4 個(gè)位置。那么甲要在這兩個(gè)位置之中選擇一個(gè)，也就是 C_2^1。

然后就只剩下了戊、丙丁和乙，也就是將這 3 個(gè)元素（我們將丙丁看作了一個(gè)元素）安排進(jìn)這 3 個(gè)位置里面，即 A_3^3。

最后我們通過乘法計(jì)數(shù)原理求出答案即可：

有 6 個(gè)人甲、乙、丙、丁、戊、己排成一橫排，甲乙必須相鄰，丙丁不能相鄰，問有多少種不同的排列方法。

這一題除了有捆綁問題還有不相鄰的要求，我們想考慮捆綁。

我們將甲和乙看作一個(gè)元素，那么就有 A_2^2 種排列方法。

再和戊和己排隊(duì)，也就是將 3 個(gè)元素放進(jìn) 3 個(gè)位置里面，也就是 A_3^3 種排列方式。

我們?cè)賮?lái)考慮不相鄰的要求，我們假設(shè)甲乙、戊、己排隊(duì)之后是下面的樣子：

那么要使丙丁不相鄰，那么他們兩個(gè)就只能在畫橫線的空位上面，這樣就不會(huì)相鄰了。

這里共有 4 個(gè)橫線，也就是將兩個(gè)人安排進(jìn) 4 個(gè)位置，即 A_4^2 為答案。

最后運(yùn)用乘法計(jì)數(shù)原理求出答案即可：

現(xiàn)有 6 個(gè)數(shù)字從 0 到 5，問這 6 個(gè)數(shù)字能組成的不相同的四位偶數(shù)的個(gè)數(shù)。

看見這道題之后，發(fā)現(xiàn)這和前面的題都不一樣，但是先別慌。

看見了四位偶數(shù)，可以得到 2 個(gè)信息：

那么這道題不就變成了排隊(duì)類型的問題嗎？看見數(shù)字 0 的事情最多，所以從 0 入手。

我們類比上面的位置問題，分類討論數(shù)字 0 的位置在末尾和不在末尾的兩種情況。

若數(shù)字 0 在末尾的位置，那么現(xiàn)在就是將其余的 5 個(gè)數(shù)字放進(jìn)還剩的 3 個(gè)位置里面，即 A_5^3。

若數(shù)字 0 不在末尾的位置，也就是末尾是 2 或 4 的情況。那么我們就要將 2 或 4 安排進(jìn) 1 個(gè)位置里面，也就是 A_2^1 了。

我們還注意到首位不能是 0 這個(gè)數(shù)字，所以也就是將 5-1=4 個(gè)數(shù)安排進(jìn) 1 個(gè)位置，即 A_4^1 了。注意這 4 個(gè)數(shù)中不含數(shù)字 0。

最后就只剩了 2 個(gè)位置，也就是將剩下的 4 個(gè)數(shù)放進(jìn) 2 個(gè)位置里面，即 A_4^2 了。

然后運(yùn)用乘法計(jì)數(shù)原理求出這種情況的答案，也就是 A_2^1 \times A_4^1 \times A_4^2 這個(gè)值。

最后的答案就是將這兩種情況加起來(lái)即可：

排列與組合其實(shí)說(shuō)簡(jiǎn)單也不簡(jiǎn)單，說(shuō)難其實(shí)也難，所以多做題有助于提升對(duì)這類題型的敏感度，所以這里有一些課后思考題：

求方程 x_1+x_2+x_3+x_4=8 的正整數(shù)解的個(gè)數(shù)

現(xiàn)有 6 個(gè)數(shù)字從 0 到 5，問這 6 個(gè)數(shù)字能組成的不相同的五位奇數(shù)的個(gè)數(shù)