| 三明治問題的解析方法。。。 |
| 送交者: 括號 2011年12月20日18:39:11 於 [靈機一動] 發送悄悄話 |
|
原來說過要寫個生成函數的科普貼。但發現網上這方面的好貼太多了，再寫難免成了狗尾續貂。但三明治這種題既是使用也是學習理解生成函數的很好的例子。所以就題論題引申一下。。。。 三明治的問題可以簡單表述為在A，B，C，D，E這5種三明治中選4個（可以有重複）的組合問題。 首先看如下5個一元多項式的乘積展開： g(x) = (1+Ax+AA*xx+AAA*xxx+....)(1+Bx+BBxx+BBB*xxx+....)*.... = 1 + (A+B+C+D+E)*x + (AA+BB+CC+DD+EE+AB+AC+AD+AE+...)*xx + (AAA+BBB+...+ABC)*xxx + .... 不難看出，展開前(等式左邊)每個多項式x^n項的係數中三明治名稱的指數(n)與該種三明治被選出來的個數對應。展開後，x^n項的係數列出了從這5種三明治中選擇n個的所有組合。因此，由上面這個多項式的乘積函數g(x)，可以生成5種三明治中選n個(n = 0,1,2,3,4,5,6,.....)的所有組合。g(x)就是這個組合問題的所謂生成函數。 比如，三明治問題中n=4（在這5種三明治中選4個），的所有組合就是g(x)展開式中x^4項的係數。 更進一步，三明治問題並不關心具體組合的一一羅列，而只關心n等於某一數值（比如4）時的組合總數。不難看出，在g(x)中令A=B=C=D=E=1，則展開式中x^n的係數就對應了這個所需要的總數。這時，g(x)化簡為5個相同等比級數的乘積: g(x) = (1+x + xx + xxx + x^4+....)^5 = (1/1-x)^5 推而廣之，k種三明治選擇n個的生成函數就是k個相同等比級數的乘積: g(x) = (1/1-x)^k 對g(x)求n次導數並讓x=0，得到g(x)級數展開式中x^n項的係數Cn滿足關係式 Cn*n! = k*(k+1)*(k+2)*....*(k+n-1) = (k + n - 1)!/(k-1)! 從而得到k種三明治選擇n個的組合總數: Cn = (k + n - 1)!/(k-1)!n! = (k + n -1, n) 生成函數將組合問題表示成解析問題，通過解析變換（比如級數展開等）進行研究。。。。 |
|
|
|
|
 |
 |
| 實用資訊 | |
