| 三明治问题的解析方法。。。 |
| 送交者: 括号 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) 生成函数将组合问题表示成解析问题，通过解析变换（比如级数展开等）进行研究。。。。 |
|
|
|
|
 |
 |
| 实用资讯 | |
