標籤：

4個相同/不同的蘋果放到3個相同/不同的盤子，有幾种放法？

02-01

4個相同的蘋果，放到3個相同的盤子，有幾种放法？
4個不同的蘋果，放到3個相同的盤子，有幾种放法？
4個不同的蘋果，放到3個不同的盤子，有幾种放法？

請說明具體的思路

還有4個相同的蘋果放到三個不同的盤子里。這四類問題難度各自不同，可以說是組合中比較經典的問題了，或者可以推廣到N個蘋果放進M個盤子里。

最簡單的是4個不同的蘋果放到3個不同的盤子里，每個蘋果顯然有3種不同的方法，所以總數是 $M^N$

其次是4個相同的蘋果放到3個不同的盤子里，這等效於三個未知數的不定方程解法數量的問題，解決的方法是用隔板法，將4個蘋果與2個隔板進行組合，兩個隔板將4個蘋果分成了三堆，對應三個盤子。所以答案是 $C_{N+M-1}^{M-1}$

再其次是4個相同的蘋果放到3個相同的盤子里，這個感覺起來是要難一些，但是可以歸類到前面的問題中，我們將第二種情況中的三個盤子中蘋果的數量按順序排列起來，這樣就可以變成第三個問題，也就是：要求x + y + z = 4，且滿足x &<= y &<= z的解的數量。

我們做一下變數代換， $t_1 = x, t_2 = y - x, t_3 = z - y$ ，這樣可以改寫成

$3t_1 + 2t_2 + t_3 = 4$

或者更一般地

$Mt_1 + (M-1)t_2 + ... + 2t_{M-1} + t_M = N$

的非負整數解的個數。

把這個數寫成 $f(M,N)$ ，則顯然有

$f(M,N) = f(M-1, N) + f(M-1, N-M) + f(M-1, N-2M)...$

$f(M, 0) = 1$

$f(1, N) = 1$

$f(M, k) = 0 (k < 0)$

由於

$f(M, N+M) - f(M, N) = f(M-1, N+M)$

也可以改寫成

$f(M,N) = f(M, N-M) + f(M-1, N)$

可以算出：

$f(3, 4) = f(3, 1) + f(2,4) = f(1,1) + f(2,2) + f(1,4) = 2 + f(2,0) + f(1,2) = 4$

這個特殊計數序列實際上是分拆數，雖然一般定義的分拆數是前述不定方程滿足x &<= y &<= z &< ... 的正整數解的數量，但顯然它對應到

$Mt_1 + (M-1)t_2 + ... + 2t_{M-1} + t_M = N - M$

的非負解的數量，所以僅僅是N的大小不同而已。

最後是4個不同的蘋果放到3個相同的盤子中，這可以藉助一類特殊計數序列即第二類stirling數來表示，第二類stirling數相當於將N個蘋果放到M個盤子中，且每個盤子非空的解的數量。它滿足遞推關係：

$s(N,M) = s(N-1,M-1) + Ms(N-1, M)$

$s(0,0) = 1$

$s(0, M) = 0 (M > 0)$

$s(N, 0) = 0 (N > 0)$

邊界條件也可以改寫為：

$S(N, N) = 1$

$S(N, 1) = 1$

這是由於：考慮最後一個蘋果，它要麼放進一個原來為空的盤子里，對應第一項；要麼放進已經有蘋果的M個盤子之一，對應第二項。

而我們要求的結果中，盤子可以是空的，只需要將所有可能的m加起來就可以了：

$sum_{m = 1}^M s(N, m)$

我就要放到一個盤子里！

推薦閱讀：

※世界上沒有百分百的事情，可是每個人都會死這就是百分百的事但這個問題又恰恰反證了世界上沒有百分百的事情？
※集合 X 有 n 個元素，從集合 X 中隨機選取 A、B 兩個子集。A 是 B 的子集的概率是多少？
※如果未來生女孩的概率是95%這個世界會怎樣？
※每架次航班上至少有一個醫生的概率有多大？
※兩根長度 1 的線段完全落入單位正方形內，求相交概率？

TAG:邏輯 | 概率 |