首頁>Club>
6
回覆列表
  • 1 # 使用者4607844662782

    還有4個相同的蘋果放到三個不同的盤子裡。這四類問題難度各自不同,可以說是組合中比較經典的問題了,或者可以推廣到N個蘋果放進M個盤子裡。最簡單的是4個不同的蘋果放到3個不同的盤子裡,每個蘋果顯然有3種不同的方法,所以總數是其次是4個相同的蘋果放到3個不同的盤子裡,這等效於三個未知數的不定方程解法數量的問題,解決的方法是用隔板法,將4個蘋果與2個隔板進行組合,兩個隔板將4個蘋果分成了三堆,對應三個盤子。所以答案是再其次是4個相同的蘋果放到3個相同的盤子裡,這個感覺起來是要難一些,但是可以歸類到前面的問題中,我們將第二種情況中的三個盤子中蘋果的數量按順序排列起來,這樣就可以變成第三個問題,也就是:要求x + y + z = 4,且滿足x <= y <= z的解的數量。我們做一下變數代換,,這樣可以改寫成或者更一般地的非負整數解的個數。把這個數寫成,則顯然有由於也可以改寫成可以算出:這個特殊計數序列實際上是分拆數,雖然一般定義的分拆數是前述不定方程滿足x <= y <= z < ... 的正整數解的數量,但顯然它對應到的非負解的數量,所以僅僅是N的大小不同而已。最後是4個不同的蘋果放到3個相同的盤子中,這可以藉助一類特殊計數序列即第二類stirling數來表示,第二類stirling數相當於將N個蘋果放到M個盤子中,且每個盤子非空的解的數量。它滿足遞推關係:邊界條件也可以改寫為:這是由於:考慮最後一個蘋果,它要麼放進一個原來為空的盤子裡,對應第一項;要麼放進已經有蘋果的M個盤子之一,對應第二項。而我們要求的結果中,盤子可以是空的,只需要將所有可能的m加起來就可以了:

  • 中秋節和大豐收的關聯?
  • 為什麼很多人在不瞭解TF boys的情況下一個勁的黑他們?