与(14.4)比较!的系数郎得(1.4.12)的第一式.(1412)的第 二式由第一式中换n为2n,换m为n而得到。 在(1.4.4)中换t为-t, (1-t) 习(-y( (148) 饣 两端对E求微商, l一t 代=1人内即得(1.4.13) (1418)的两节对4求r次微商 (-1)(n)(1-m)-∑(-1)()(" 两节再除以r!, (-1)(") 代=1入内即得(1.4.14) 现在用(14.10)来证(14.15).当n=0时,(1.4.15)是平凡 的:其左节为空和,右节为零.当n>0时, (-1)1 7+ k十 1≤k≤ n+1(k+1 十1 ∑( 十12≤力+t n十1 十(n十 (1415)还可证明如下:由(14.18)两节对4求原函数
是1 +(1-1)+=∑( /+1·(14,19) 代r=0人上式,得 (1.4. 代(1120)和x=1入(14.19), 1 A十 1 +1\k 由此立得(14.15). 现在利用(145)和数学归纳法来证明(1416),当n=1 时,(14.16)显然成立.设(1416)对n成立,那末, (-1)-1/n+ k 饣 -++xx=《2)+(1 (-1) 十 十 1 1≤走≤n }+,k+ )+,x+1++1() n+1 十1
故(1.16)成立.至此,定证毕 利用母函数还可给出 (124)的第五个证明.由定理142得知,可重组合的计 数母函数是 (:+:+2+…)?-(1-r), 其 Taylor展式为 (-n)(-n-1)…( (1421) 故有(124).证毕 定理144. 1.n元集A的r可重组合要求A的每个元至少出现一次,这 样的组合数是 (14.22) 1 2.有组合恒等式 +;-1)-∑(-1)("+ 十R (4.23) k 证明.1.符合这里的条件的组合的计数母函数为 (t+t2+…)”〓r(1一t) 由(14.21), (4+
比较的系数即得(1.42) 2.由 (1-r2)-"=(1-t)-(1+t)”, 两节按 Taylor级数展开, ((<- 故有 (X,) 十5一-1 十1-1 比较两节!的系数 若2|5, 若2 由此立得(1423).证毕. 这里自然会产生一个问题:对于排列,有无类似的工具?回 答这个问题就是下节的任务 §15排列的母函数 先看一个简单的例子 由(144) (+功)
这就是说,在(1+n)的展式中,项的系数就是集[1,n]的 i无重排列数.这个简单的情况提供了下面的启示:排列的计数 母函数采用形如 的幂级数较为有利,这种类型的幂级数很象指数函数c的展开 式,故名为指数型母函数简称为指母函数.有时为了强调上节的 母函数与指母函数的区别,叫前者为普通型母函数简称为普母函 数或母函数 现在来证明较一般的结臭 定理1.51.集[1,n]的λ-排列,其中数码i(1≤i≤n) 允许出现的次数组成的集为S,那末,这样的排列数的指母函数为 l I (.51) 证明.展开(1.51), λ (1.52) 由定理1.3.2,对于固定的一组数λ1,…,λ,符合所述条件的 (λ1十∴十λn)-排列数是 (1 λ-) (1.53) 3!…·λn! 因此,(152)中项的系数恰好是对一切可能的选取(λ1 十n一t,↓1∈S(1≤≤n) 符合条件的↓排列的总数,证毕