(x1+…+x"一(x1+…十x)…(x1+…十x 1.3,.8) 的展式中,项x1…x(自然有如十∴…+b·n)可由n个因 子(x1+…十x)中选出b个(1≤讠≤,对这b个因子都 取x来参与乘积而得出.这种选法数就是V(b1,…,b.所以, (13.8)的展式中项x1…x的系数就是V(b1…,b), 定理132所讨论的问题允许集中一些元素相同。一般地说 集A的一个分类,又称为集A的一个规格是b好…b’指的 是A有q个不同的元素类,每个类中的元素相同,不同类中的元 索互异,且恰有b;个元素的类的个数是q,1≤i≤了,q= 十…+q如果|An,A中恰有k个讠元类,这种分类 又记为 (1,k2,……k),k≥0(1≤i≤n) 有关这种分类的一些问题,以后还会遇到 §14组合的母函数 母函数是处理组合论课题的一个重要工具,有关它的一般介 绍将在下章进行.这节和下节只就最简单情形的组合问题,用母 函数作工具来处理,为今后的讨论寞定一个直觉的基础,并把排列 组合问题的研究推向深入 先看一个例子.设A口{x,x,x3}.把x3,x2,x当作不 定元添加到整数环Z上,就得到多项式环Z[x1,x2,x3],简记为 ZA].在环ZA1上再添加另一个不定元t,又得到一个新的多 项式环zA儿[,简记为z4;.在Z[A;1]中作乘积 (1+x1)(1十x2)(1十x}), 展开后按的升幂写出,得 1+(x1+x2+x3)x+(x1x2+x2x3+xx1)x2+x1x2xy 1+a2t2+ 这里Gσ(,x3)(1≤讠≤3)为元x1,1,x3的初等对称
多项式.易见,的三个项正好是A的1-无重组合的全部,02的 三个项正好是A的2-重组合的全部,3的唯一一项正好是A的 唯一的3-无重组合,因此在a中,把x1=x2=x3=1代入,就 得到A的无重组合数: (+t)=2a(1,1,1) 对更一般的情形,有类似的结果 定理141.设d={x1,x2,…,#},则在环Z[x ;]中,有 I(1+x;t)2o )t,(14.1) 其中σ(x1,…,xn)是x1,x,…,xn的第讠个初等对称多项式 (x1, ox1,……,x)∑x1…x;(1≤i≤n).(142) 因而 a(1,…,1)→C(0≤≤n), (14.3) 且 (1+ 证明.对n行数学归纳法,当n=1付,有 1+x1t=a+t,因a=,叽=x I十 1 可 故定理为真.设n-1时定理成立,那么对n,有 I(+x;1)=ⅡI(+x;(1+ ≤i≤-1 24·
tO x n-1 +(x1,…,xn-1) ( F:t ) 0≤ 这里用到了 ;(x1 )+ x 在(14,2)中令x1 xn≌1,考虑到符合条件 L≤n<…<j≤ 的i1…,j正好是l,n]的i无重组含,故(142)右节的项 数为C{.由此立得(1.4.3).再由(14.1),便得(144) (144)的第二个证明.在乘积 1+t)”〓(1+t)…(1+t) 中,项是从#个因子1+t中选取i个,在这;个1+z里都 选t,从余下的n一i个因子1+中都选1作乘积来得到的 因此p的系数为上述选法的个数,即组合数 证毕 公式(144)就是著名的牛顿二项式定理.出于(144)的缘 故组合数(;)又叫项式系数 定理1.41可推广为
定理142.设A={x1,……,xn}.在集A的r可重组合 中,元x的允许重复的次数所组成的集若记为MA(1≤≤n), 则这样的组合的全部由 只.x (14.5) 的展式中项的系数8(x1……,xn)的全部单项式给出:所以这样 的组合数为 (146) 且 8(1 (147) 证明.展开(145), (148) ≤A≤r∈M i1+n→ 1≤火<界 ∈M(1≤k≤n 其中r的系数 ih∈Mh(≤≤组) 中的各项 Mk十…十 正好是满足定理条件的全部组合,因而这样的组合数为8(1,… 在(14.8)中令x x=1,则得(1.4.7).证毕 由于(14.1)和(145)中r的系数的全部项正好是某类组合 的全部,所以这种类型的函数叫做相应的组合的陈列母函数.由 于(144)和(147)中t的系数正好是某类组合数,所以这种类 型的函数叫做相应的组合的计数母函数.或称为组合数的母函 数,又简称为母函数 组合数的母函数在组合数的计算及组合数之间的关系等问题
的处理中,起着十分置要的作用.下面略举数例以明其意 定瑆143 ( 0 (149) raD 5 -∑(-y()-0,n>0,(141 ←r< (14.11) 2012r+1 7- (!412) A≥0 (14.13) k (14.14) k+1 n≥0 十1 (-1) (14.16 1上≤ 证明,在(144)中令=1即得(149);令 得(14.10).由(149)和(14.10)相加、相减,则得(14.11).由 (1+1)”=(1+t)?m(]+t) 2””,=)(141 27