指数型母函数(下)

指数型母函数(下) 母函数 九、指数型母函数(下) [例19] 证明 n111,,kk C(,1)1，，？，,,•.,,,nkn2,,,1k 1证明 令经过组合变换(100)得 a,0•,a•,,•,••(k,1,•2•,•？)0kk n1,,kkb,0,b,(,1),••••C,,,0nnk,,k,1 n1kk,1••••••••••••,(,1)C•,••(n,1•,•2•,•？),nkk,1 由习题一第11题得知 11b， ,1，，？，nn2 于是利用反转公式(101)，即得 n111,,kk C(,1)1，，？，,,•.,,,nkn2,,,1k 这就是要证明的. 如果不用这里的互逆公式，要直接证明这个等式是颇不容易的. 看一个具体的指数型母函数的例子. r从n个相异物体中任取r个作排列，其所有可能的排列数记为，则 An rr. A,n(n,1)？(n,r，1),r!•Cnn 所以数列 rn010 A•,•A•,•？•,•A•,•？,•A•,•0,•0•,•？••(A,1)•nnnnn的指数型母函数是 n2AAn012nn，，，？，xA••Axxnn2!n!•• nn122,1，Cx，Cx，？，Cx nnn n,(1，x)•. n这说明函数不仅是组合数列 (1，x) 01nC•,•C•,•？•,•C•,•0•,•0•,•？ nnn 的普通母函数，而且还是排列数列 01n A•,•A•,•？•,•A•,•0,•0•,•？••nnn的指数型母函数. 从这个例子来看，似乎指数型母函数和排列问题有关，下一节我们就要仔细讨论这个问 题. 习题九 1(确定下列数列的指数型母函数: nn(i)1，-1，1，-1，…，，…，; a,(,1)(,1)n(ii)0～，1～，2～，…，n～，…，; a,n•!n nn2(iii)0～，2?～，2?2～，…，， …，. a,2n•!2,n•!n2(利用组合变换的互逆公式证明 kn(,1)1,1km. C(C),,，nmkm，k，1m，n，1,0k 解答 111((i);(ii);(iii). e(,x)1,x1,2x 1a,2(令，由习题一第12题知，经组合变换后得 akkm，k，1 nn1!m!n••kkkk， b,(,1)Cak,(,1)C,,,nnnm，k，1(n，m，1)!,,00kk 于是由反变换公式得 nn!m!k••kkkk,(,1),(,1) aCbC,,nnkn(k，m，1)!,,00kk kn1(,1),1km此即 ,C(C),，nmkm，n，1m，k，1,0k