組合計數（四） 應用

要講理論誰都會講，但是如果理論不能應用於現實的問題上那也只會淪於紙上談兵。



要算 C 要算 P 有什麼困難的，公式都丟給你了基本上有數字都算得出來。真正難的是如何把一串文字轉換成正確的算式，因為沒有一道題目會好心到告訴你這裡要用錯排列或單射的 f。提到錯排列，是時候該來看看這個東西了。

Q：abcde 五人互相交換名片，在不拿到自己名片的前提下，有幾種交換方式？

首先來看看我們真正要求的是什麼：

其中 A 代表 a 不拿到自己名片的交換方式的集合，BCDE 以此類推。我們對於集合的交集實在是沒輒，不過至少我們還有狄摩根定理：

其中 U 是所有可能的交換的集合，元素數量是 5! = 120。現在我們有了集合的聯集了，就可以使用排容原理了：

再加上 ABCDE 五個集合的大小都一樣，我們只要算不同數量集合的交集各有多少個再乘上交集的大小就夠了。

A：44種。

Q ：五種不同的酒倒入三個相同的酒杯，每個酒杯限倒一種酒，酒沒有限次數，則有幾種倒法？

噢，老天，是我最愛的倒酒問題。有在高中的排列組合打滾過的都應該知道，另外還有幾種這個類似的問題，但是一開始的判斷都是一樣的。很顯然地我們有兩個集合：一個有五種不同的酒、另一個有三個相同的酒杯。因為每個酒杯最多只能裝一種酒，所以我們可以安心地假設從含有酒杯的集合出發的函數（不會有一個酒杯對應到兩種酒的情形）。

因此這是任意 f。Sx: X → Y 的情況，該用重複組合 。要是限制每種酒只能倒一次，那就得用組合 C 了（單射：不同元素不能映射到同一元素）。

A：35種。

Q：ABCDEF 六個字母排列，但 DE 兩字母不能靠在一起，則有幾種排法？

經典的排列問題。當然這問題可以用全部減去 DE 靠在一起的狀況，或著是陪我玩一下：

我們假設在 ABCF 週圍的五個空隙有 DE 和三個「空白」在排列。ABCF 的排列有 4! = 24 種，DE 和三個空白的排列有 5! / 3! = 20 種。

現在透過乘法原理將兩者合併起來，並將空白省略，就可以得到我們想要的結果：480種。

A：480種。

Q：7張相同的明信片和5個相同的信封分給4個人，每人至少1張明信片和1個信封，則有多少種分法？

在這裡因為一定會有人有超過一張明信片或一個信封，所以 f: X → Y 的 X 絕對不是人而應該是明信片或信封的集合。因為明信片和信封的分發是獨立的，故兩者可以最後透過乘法原理結合。題目的條件剛好符合滿射的敘述，因此我們要使用的是滿射 f ⸰ Sx : X → Y：

有趣的是：

A：80種。