2022年《组合数学》教案2章

1、第 二 章 母 函 数 及 其 应 用1. 普母函数及其在组合问题中的应用 2. 指母函数及其在排列问题中的应用 3. 正整数的分拆及其组合意义和应用问题：对于不尽相异元素的部分排列和组合,用第一章的方法 比较麻烦（参见表 2.0.1）；新方法：母函数方法；表 2.0.1 条件C组合方案数r.排列方案数对应的集合相异元素,不重复rn.r P nnn.r.Se 1,e 2,ennr.n相异元素,可重复Crr1nrSe 1,e 2,n,e n 不尽特例rn1 n.Sn1e 1,n2e 2,n 1.n2.nm.相异m m ,n me m, 元素全部r1 n 1n2 nmn,（有nrCrr1mrnk1

2、, 限重m（k1,2, , m）复）至少有一个nk满意1nkr基本 思想：把离散的数列同多项式或幂级数一一对应起来,从而把离散数列间的结合关系转化为多项式或幂级数之间的运 算；2.1 母 函 数（一） 母函数（1）定义【定义 2.1.1】对于数列an,称无穷级数Gxn0anxn为该数列的（一般型）母函数,简称（2）例普母函数 或母函数 ；【例 2.1.1】有限数列 C （r0, 1, 2, , n）的普母函数是：n rG xC n 0 C n 1 x C n 2 x 2 C n n x n1 x n【例 2.1.2】无限数列 1, 1. , 1, 的普母函数是Gx1xx2xn11x（3）说明a

3、 可以为有限个或无限个；nx2xn1xx 数列an与母函数一一对应；0, 1, 1, , 1, 0 x 将母函数视为形式函数,目的是利用其有关运算性质完成计数问题,故不考虑“ 收敛问题”微分” 和“ 逐项积分” 的；（4）常用母函数,而且始终认为它是可“ 逐项 ak ,k0,1, Gx2 ak ,k0,1, Gx ak1 1ak ak11x1axakk xakk1 11x21xakkk 1 2x3ak k2x1x1x31xak kk 1k6xxak k,任11xx11x42 意a0 0,ak ak-ln1- a x k任1exak .k,k意ak 1kak 2 k1k.cosx1.sinx2

4、kak2k1k1 xarctanak nkkxn1（二） 组合问题（1）组合的母函数【定理 2.1.1】组合的母函数：设Sn 1e 1,n2e 2,n me m,且 n1n2 nmn,就 S 的 r 可重组合的母函数为Gxmnixjnarxr其中, r 可重组合数为i1j0r0 x 之系数 rra ,r0, 1, 2, , n；理论依据：多项式的任何一项与组合结果一一对应；优点：将无重组合与重复组合统一起来处理；使处理可重组合的枚举问题变得特别简洁；（2）特例【推论 1】Se 1,e 2,e n,就 r 无重组合的母函数为Gx 1xn组合数为r x 之系数C ；n r【推论 2】Se 1,e

5、2,e n,就 r 无限可重组合的母函数为Gxxjn11xnj0组合数为r x 之系数Cr nr1；e n,每个元素至少选一个：【推论 3】Se 1,e 2,nxn母函数Gxj1xj1x组合数Cn r1 1e n,每个元素选非负偶数个：【推论 4】Se 1,e 2,母函数Gx1x2x4x2nn11nx20,当r为奇数当r为偶数；组合数ra Cnr1,r,22【推论 5】Se 1,e 2,e n,每个元素选奇数个：母函数Gxxx3x5x2n1n1x2nx0,当rn 为奇数2n,当rn为偶数组合数arCnr2n1,r【推论 6】Sn 1e 1,n2e 2,nme m,且 n1n2 nmn,元素ie

6、 至少显现ik 次：为母函数Gximjniixjrnkarxr组合数1karrk, k1, , n,kk1k2 km；（3）一般情形：设S20.a,30.b,.c,并设元素a只能显现 15,10,13,16 次,b 只答应显现奇数次, c 至少显现 5 次且必需显现偶数次,求S的 r 可重组合的母函数；Gxxx2x5x5x10 xx13x8x16xx3x296（三） 应用【例 2.1.3】设有 2 个红球, 1 个黑球, 1 个白球,问（1） 共有多少种不同的选取方法,试加以枚举？（2） 如每次从中任取3 个,有多少种不同的取法？（解）（1）元素符号化（ x,y,z 红、黑、白球）,元素 的个

7、数以符号的指数区分；母函数Gx, y, z 1xx2 1y 1z 1xyzx2xyxzyzx2yx2zxyz x2yz 5 种情形： 数字 1 表示一个球也不取的情形,共有 1 种方案； 取 1 个球的方案有 3 种,即红、黑、白三种球只取 1 个； 取 2 个球的方案有 4 种,即 2 红、1 红 1 黑、1 红 1 白、1 黑 1 白； 取 3 个球的方案有 3 种,即 2 红 1 黑、2 红 1 白、三色球各一； 取 4 个球的方案有 1 种,即全取；令 xyz1,得方案总数G1,1,1 1343112 （2）只考虑每次取 令 yx,zx 3 个的方案数,不需枚举Gx1xx2 1x 1x

8、13x4 x23 x3x4由 x3的系数即得所求方案数为 3；【例 2.1.4】有 18 张戏票分给甲、乙、丙、丁 4 个班（不考虑座位号）,其中甲、乙两班最少 1 张,甲班最多 5 张,乙班最多 6 张,丙班最少 2 张,最多 7 张,丁班最少 4 张,最多 10 张,问有多少种不同的安排方案？（解）（1）分析： 实质为甲、乙、丙、丁四类共 28 个元素中可重复地取 18 个元素的组合问题；S 5 e 1 , 6 e 2 , 7 e 3 , 10 e 4,m 4 , n n1 n2 n3 n4 5 6 7 10 28 , k k 1 k 2 k 3 k 4 11248,r18；（2）求解：母

9、函数5 6 7 10Gxx i x i x i x ii 1 i 1 i 2 i 4x8 140 x18 x28 （3）特别情形处理 ：戏票数 r4,ik 0（i1, 2, 3, 4）5 6 7 10G1xx i x i x i x ii 0 i 0 i 0 i 01 4 x 35 x 4x 284G 2xix14i 0 1 x4 281 4 x 35 x 4495 x4 x 系数相同,用 G2x运算要比用 G1x便利得多（由于将i50i x 扩展为i x 不影响x 的系数）4i0同理, r6,可用G3x5xixj35xi1x3i0j0i0r 只（rn）,要求其代替 G1x求6 x 的系数；【

10、例 2.1.5】从 n 双相互不同的鞋中取出中没有任何两只是成对的,问共有多少种不同的取法？（解）解法一 ：母函数法；视为,S,2e 1,2e 2, 2e n,但同类中的两个ie 不一样,即e ne n2Se 11,e 12,e 21,e 22故其 r 重组合的母函数为不同的取法共有aGx12xnrn0n2r xrrrn2 种；r本质：每类元素最多只能显现一次,但同类元素互换后方案不同；故 Gx1C1xn中不能有x 项,再由同双的两只鞋子 22有区分知, x 的系数应为 2；解法二 ：排列组合；先从n 双鞋中选取 r 双,共有n 种选 r法,再从今 r 双中每双抽取一只,有2 种取法；r解法三

11、 ：排列组合；先取出k 只左脚的鞋,再在其余nk双鞋中取出rk只右脚的鞋k01,2,r：ra nnnn1nn2nn0r0r1r12r2r得组合恒等式nnnn1nn2nn0rn2r0r1r12r2rr一般提法 ：Se 11 , e 12 , , e 1 n 1；e 21 , e 22 , , e 2 n 2；e m 1 , e m 2 , , e mn m从中取出 r 个,第 i 类元素最少 ik 个,最多 it 个,母函数：m t i n i jGxxi 1 j k i j举例, 把 5 本相同的书分给甲、乙、丙 3 个班,再发到个人手上,每人最多发一本；考虑将分给某班的某本书发给该班的同学

12、A 与将其发给同学B 被认为是不同的分法,而且甲、乙两班最少 1 本,甲班最多5 本,乙班最多6 本,丙班最少2 本,最多 9本,问有多少种不同的安排方案？nSe 11,e 12,e 15；e 21,e 22,e 26；e 31,e 32,k3,e 39,m3,n1n2n356920,kk1k21124,r5；母函数5 5 i 6 6 i 9 9 iGxx x xi 1 i i 1 i i 2 i5 6 9x 41 1 25 6 9 5 6 9 5 6 9x 51 1 3 1 2 2 2 1 25 6 9x 205 6 91080 x 7380 4 x x 20共有 7380 种安排方案；说明

13、：与问题“ 从 20 个相异元素中不重复地抽取 5 个元素”不等价（答案为20 15,504）；5【例 2.1.6】甲、乙、丙 3 人把 n（n3）本相同的书搬到办公室,要求甲和乙搬的本数一样多,问共有多少种安排的方法？（解）（1）分析：组合问题：从集合 S e 1 , e 2 , e 3中可重复地选取 n 个元素,要求 1e 与 e 的个数一样多,求不同的 2选取方案数；特点：限制盒子之间的关系；（2）特例：n1,1 种分法,甲和乙都分 0 本（丙 1 本）；n2,2 种分法：甲和乙分 0 本（丙 2 本）或甲和乙 1 本（丙0 本）；当 n3 时,分法 2 种；当 n4 或 5,3 种分法

14、：甲和乙都分0 本、 1 本或 2 本；（3）一般情形 ：视为 2 个大盒子 A、B,且 A 又分为 2 个小 盒子；分两步安排：第一步： A 盒子分偶数本, B 盒子分任意本；其次步：将分给 A 盒的书再给甲、乙各分一半；GA （2k 本）B（n2k 本）甲（k 本）乙（k 本）丙（n2k 本）x1x2x4x2k1xx2xk211x21x11111141x41x21x1n01n x 1n0 xn1n0nn1xn442n0n21141nxnn0n21xnn21种；不同的安排方法共有x 上整数函数；即不小于（待定系数法：分解有理多项式：1111xx11x2x2x1A1BC2x1xx 的最小整数；

15、A1x2B1xx1xx2C1x,112ABx2xABC12ACx1x2BC1A比较同次幂系数得方程组AAC0,B0解之得 AB1/4,C1/2）【例 2.1.7】证明组合等式（1）n2n3nnnnnnn 211n 22nmm,123n（2）n22n32n2nnn123n（ 3）nmnmmnm m001122mnm（证）（1）二项式1xnnnxnx2nxn012n两端求导n1xn1n2nx3nx2nnxn1（* ）123n令 x1 即可；（2）（* ）式两端同乘以 x 后求导nn1xn13nn1x1xn2xn122nx2nx2n2n123n令 x1；（3）1xn11mxm1xmnx两边绽开nn0

16、 xn 2x21nnxnmx101mnmm1.01x2x2mxmxmmnmnxm2n21mnxmmnxmmmn比较两边的常数项；2.2 母 函 数 的 性 质母函数与生成数列一一对应如两个母函数之间存在某种关系,就对应的生成数列之间也必定存在相应的关系；反之亦然；设：数列 a k、b k、c k的母函数分别为 Ax、Bx、Cx,且都可逐项微分和积分；【性质1】 如b k0,rkrrr（即akb kr）,就Bxak,kxrAx；b r1xr1b rxrb r1xr1（证） Bxb 0b 1xb 2x2000b rxrb r1xr1r个向右移 r 个位置且前面补0 a0 xra1xr1xrAx分析

17、 ：a ka 0,a 1,ar1,a r,00 ,0 ,a 0a 1,b kb 0,b 1,b r1,b r,b r1,【性质 2】如b ka kr,就1aixixrBxAxi0（证） Bxb0b1 xb2 x 2 arar 1 x ar 2x 2分析 ：a k,x 1 ar x rar1 x r 1 ar 2x r2 rrAxa0a1xa2x2ar1xr1xa 0,a 1,a k,向左移 r 个位置且前面舍掉b kb 0b 1,b k,ar,ar1,akr,【性质 3】如bkiik0ai,就 BxAx；xn1x（证）等式b kkai两端乘以k x 对 k 求和：k0:b 0 x00a0k1:

18、b 1xa 0 xa 1xk2:b 2x2a0 x2a 1x2a2x2kn:b nxna 0 xna 1xna 2xna n b nxnnxnxinxnaninxiain0n0i0即 Bxa 0 xia 1xia2i0i1xii2axia0 xia1xi0i0i0a0aa 1xxa2x2anxn11x1x1x1x0a1a2x2anxn1 Ax x1x例,已知Ax1xx 2 x n 11x,（a 1）kx x1令b kaik1 i0Bx12x3x 2 k0k1xkA11x2或Bxk0kxkk0 xkk0 xkk0 xk11213x同理,令 ckkib12 k1,可得i0Cx13x6x 210 x

19、315x4k0k1k2xk1132x1CxBxAx12x3x 2 1xx 2 x类推：DxCx Ax13x6x 210 x3 1xx 2 0k1k2k3ixk1146xk【性质 4】如iia 收敛,且 b kkia ,就0BxA11xAxx（证）第一由条件知b k 存在,按定义b0a0a1a2 A1 b1a1a2a3 A1a0 bkakak 1ak 2 A1a0a1a2 ak-1 给 bk 对应的等式两端都乘以左端k0b kxkBx xk并分别按左右求和,得右 端 A1 xA1a1a0 x 2A1a0a1 x 3A1a02aA11xx 2 a0 x1xx 2 a1x2 1xx 2 A1 x1

20、xxa 0a 1xa2x2x1 AxAx1Ax 1xA1x1x1【性质 5】如 bkkak,就 BxxA x ；（证） Bx k1b kxk0kakxkxk1kakxk1k0 xakxkxka kxkk1xAx a0 xAx 【性质 6】如 b kakk,就 Bx1xAxdxdx1x0（证 ）Bx k0b kxkk01akkxkk0a k1xxkx01xk0akxkdx1xAxdxx0 x0【性质 7】如 c kkaib ki,就 CxAx Bx ；i0（证）c0a0b0 c1a0b1a1b0 c2a0b2a1b1a2b0 cna0bna1bn-1 anb0给 ck 对应的等式两端都乘以xk后

21、左右两边分别求和,得Cxa0b0a0b1a1b0 xa0b2a1b1a2b0 x2 a0bna1bn-1 anb0 xna0 b0b1xb2 x2 a1xb0b1xb2 x2 a2x2b0b1xb2 x2 a0a1xa2 x2 b0b1xb2 x2 Ax Bx 2.3 指 数 型 母 函 数回忆：一般型母函数较好地解决了各种组合的计数问题；分析：组合数数列的母函数在解决计数问题和证明组合恒等式时之有用的缘由：具有有限封闭形式；启示：对排列问题也采纳母函数方式；特别是 n 个不尽相异元素中取 r 个的排列问题；困难：对于排列数数列 Pn,r ,采纳一般型母函数特别不便；缘由：它不能表为初等函数形

22、式；改进：n 集的 r 无重排列数和 r 无重组合数之间的关系：Cn,r P n , rr .1xnnC n , r x rnP n , r x rr 0 r 0 r .x r总结：在1xn的绽开式中,项 的系数恰好是排列数；启示：r .x k排列数数列的母函数为k 0 a k k .；（一） 数列的指母函数（1）定义数【定义 2.3.1】对于数列 a a 0,a 1,a 2, ,把形式幂级G e xn 0 a n xn n.a 0a1 . x a2 x2 2. an xn n.称为数列 a k 的指数型母函数 ,简称为 指母函数 ,而数列 a k 就称为指母函数Gex的生成序列 ；（2）例1

23、a 1 ,Gex r0r x r .e ；x2a P n k,Gexn0r xP n rr .1xn r（3）说明1a 可以为有限个或无限个；nxnex12数列an指母函数；例0,1,1, ,1, 0 xx2.1.2n .3将母函数视为形式函数,且始终是收敛的；4同一数列数列 a ,一般 Gx Gex；例 a 1 的普母函数为 Gx1x,指母函数为 Gexx e ；1例外：当a 0 时（ k2）,a 1x .1Gex Gxa0a 1xa05对同一函数fx,令k0ax k kk1x4i3.fxGex.或fxGxk0bkxk就一般akbk；例外fxa0a1x；sinxxx3x5x7x4i1.1.3

24、.5.7,04i1 .4i3视sinxGx为普母函数,就1,0 ,b n0,1,0 ,1,.1.3.5.7视sinxGex为指母函数,就,0,1,0,1a n,0,1,0,1（二） 排列问题【 定 理 2.3.1 】 设 重 集 S n 1 e 1 , n 2 e 2 , , n me m , 且n 1 n 2 n m n n1n2 nmn,就 S 的 r 可重排列的指母函数为Gexi m1 j n i0 xj . jr n0 a r r x. r其中, r 可重排列数为 xr .r 之系数 ra ,r0,1,2, ,n ；【例 2.3.1】盒中有 3 个红球, 2 个黄球, 3 个篮球,从中

25、取 4个球,排成一列,问共有多少种不同排列方案？（解） m3,n 3,n 2,n 3,r4 xx2x3Gex1xx2x31xx211.2.3.1.2.12.3.13x9 x 28 x 1 x 872 7213 x 335 x 1217x 1235 x 7213x 1 .9x226x370 x4170 x52.4.5.3350 x6560 x7560 x86.78.取 4 个球的排列方案数为70；枚举：令Ger,y,b 1rr2r31yy21bb2b31.2.3.1.2.1.2.3.1Ger,y,b1r y.11 r 2 y 2 b 2 2 ry.21 r 3 b 3 3 r 2 y 3 r.3

26、3 y 2 b ryb2b3yb22 rb2ybb3ry 23rb 2 560r3y2 b38.1 个；具体枚举：取 1 个球的 3 种排列方案为红、黄、蓝各分别取取 2 个球的 9 种排列方案为：红红、黄黄、蓝蓝、红黄、黄红、红蓝、蓝红、黄蓝、蓝黄；说明：（1）利用普母函数能枚举到每一种组合情形,但指母 函数做不到,只能对排列进行分类枚举；（2）一个问题的普目函数和指目函数可以相互转换；例：在Ger,y,b令每一项系数为 1,即得普母函数；（3）已知问题的普母函数Gr,y ,b,可利用其生成指母函数；.3.0r3.0.3.0b3.3r2y.3r2 b.1.3ry2.3 .0.3.2 .1 0

27、 .2 . .1.0.2.0.1.3rb2.0.3y2b.3yb2.3ryb.0.2.2 .10 .1.2.1 .1.1（三） 特例【推论 1】Se 1,e 2,e nrxr指母函数Gex1xnrn0P n r r xr.1.排列数为xr之系数P ；n r.r【推论 2】Se 1,e 2,e n指母函数Gexj0 xjnenxr0nrxrj.r.排列数为nr【特例】每个元素至少选一个（即rn）ex1nnCne inix1inCi1innr.i0i0r0r0in01iCinirxrnr.ki 个（ki方案数in1iCi nnir；0【推论 3】Sn1e 1,n2e 2,nme m,ei 至少取0

28、）指母函数Gexn1im,jn ixj,nme m,rn,全排列数1kij.【推论 4】Se 1n2e 2,n .n 1.n2.n m.（四） 应用【例 2.3.2】五个数字 1,1,2,2,3 能组成多少个四位数？（解）用 ra 表示组成 r 位数的个数, ra 的指母函数为x x 2 x x 2 xG e x 1 1 11 . 2 . 1 . 2 . .11 3 x 4 x 2 3 x 3 5x 4 1x 54 413 x 8 x 218 x 330 x 430 x 51 . 2 . 3 . 4 . 5 .能组成 30 个四位数；【例 2.3.3】求 1,3,5,7,9 五个数字组成的 n

29、 位数的个数（每个数字可重复显现）,要求其中 3,7 显现的次数为偶数, 1,5,9显现的次数不加限制；（解）设满意条件的n 位数的个数为a ,nan3指母函数：Gex1x2x421xx2x32.4.1.2.3.ex2ex2e3x1e5x52e3xexnxnn0 xn14nxn321n0.4n .nnn0n23n5nn5n1xn4n .2301an4【例 2.3.4】把上例的条件改为要求 5 和 9 显现的次数不加限制；求这样的1、3、7 显现的次数一样多,n 位数的个数；（解）设满意条件的数有b 个,类似例 2.1.6 .1x5Gex11.3 .1.x32.6 .2.x61.3 .2.6 .

30、1xx2x321.2.3.11.x31.2.x62.2 ex1.2 .11.x31 .2.x62.1.2.12x22x223x31.2.3.12x22x2231 .31.x31.2.1.3.2421.41.x425221.51.4.21 .5.26231.61.2.62.x6.31.2.6.1 2 x4 x 214 x 364 x 4272 x 51114 x 61 . 2 . 3 . 4 . 5 . 6 .即：b 1,b 2, 2 b 4, 3 b 14, 4 b 64, 5 b 272, 6 b 1114 一般情形,当 n3 k i 时 i 0,2；k 0,n 3 n 6 ib n 2 n

31、 2 n . 2 n . 2 n .n 3 . 1 . 1 . 1 . n 6 . 2 . 2 . 2 . i . k . k . k .懂得（按排列）：【例 2.3.5】在例 2.1.5 中,如把所取出的 r 只鞋再排成一列,问共有多少种结果？（解）即从集合 S e 11 , e 12 , e 21 , e 22 , , e ne n 2 的 n 类共 2n 个元素中不重复地取出 r 个元素排成一列, 且同一类元素 ie ,ie 不能同时显现（ 1in）；指母函数：Ge x1 P 2 1x nn n2 r x rn n2 r r . x rr 0 r r 0 r r .不同的排列数为 n2

32、r r .P 2 ；n r rr与例 2.1.5 类似,本问题的排列数也可以从排列的角度懂得为：先从 n 双鞋子中不重复地选出 r 双排成一列,共有 P 种排列情形,n r再从所选的每双鞋中抽取一只,有 2 种取法；由乘法原理,即得 r所求结果；安排问题 ：将 r 个不同的球放入n 个不同的盒子,每个盒子最多放一个球,而且每个盒子中有两个相异的格子,故仍需要进 行二次安排；假如某个盒子中放进一个球,那么,二次安排时有 两种可选的方案；一般提法 ：集合 S 中有 m 类元素,第 i 类元素有 in 个,且同 一类元素也互不相同,从 S 中取出 r 个元素排成一列,问共有多 少种排列结果？其中要求

33、第 i 类元素最少 ik ,最多 it 个,就此排列 问题的指母函数为GeximjtiP n jixjrn0ax r rr1kj.即得问题的答案ra （r0,1, , n）；2.4 正 整 数 的 分 拆 问题：将一个正整数分拆成如干个正整数之和；关联问题：安排问题、一次方程整数解的个数问题；（一） 概念【定义 2.4.1】nin1,n2,12 ,nk,k1n1i,k称该分解是 n 的一个 k 分拆,并称（二） 分类有序分拆考虑in 间的次序；n 为重量（或分项）；例 521111211无序分拆 不考虑次序（可把分项按大小排序） ；例 52111323112.4.1 有 序 分 拆求 n 的

34、k 有序分拆的个数 的组数；求一次不定方程全体正整数解可对每个重量in 加以条件限制： 1in ir （ i 1, 2, , k）；【定理 2.4.1】n 的 k 有序分拆分拆数列qknnn1n2i1 ,n k,k11niri;2 ,k的母函数：k r ix j x x 2 x r 1x x 2 x r 2i 1 j 1x x 2x kr组合意义（安排问题）：把 n 个相同的球放入 k 个不同的盒子里,第 i 个盒的容量为 ir （ i 1,2, ,k）,且使每盒非空；【推论】如对 n 的 k 有序分拆的各重量in 没有限制, 就其 k 有序分拆数列qkn的母函数是1xxk,且qknCk1；n

35、12.4.2 无 序 分 拆（一） 问题nn1n2nnk,k1n1n2pknk1简称分拆,分拆数记作,n 称为 最大分项 ；1问题转换：将 n 分拆为 k 项（每一项的大小不受限制）的分拆数等于将 n 分拆为最大分项为k（分项个数不限）的分拆数；设满意后一种条件的k 分拆数也为pkn；（二） 最大分项n k 的分拆 1分拆数不定方程整数解的组数1x12x2i1,kxk,kn1,xk1xi0,2,即整数 n 由 1,2, , k 答应重复且 k 至少显现一次的全部组合 数；母函数：1xx21x2xxx22xk3n1nx3x32k2xk1x1xk1knp kxx2k（三） 最大分项 n k 的分拆

36、 1分拆数不定方程整数解的组数1 x 1 2 x 2 kx k nx i 0 ; i 1 , 2 , , k分拆数列 rk n 的母函数：1 x x 2 1 x 2 x 2 21 x 3 x 3 21 x k x k 2x k 31 x 1 x 12 1 x kn k r k n x n2.4.3 Ferrers 图（一） 定义一个从上而下的 k 层格子,设 m 为第 i 层的格子数,当 i m im i 1（ i 1,2, ,n-1）,即上层的格子数不少于下层的格子数时,称为 Ferrers 图；（a）（b）（二） 性质（1）每一层至少有一个格子（2）Ferrers 图与 无序分拆对应关系：

37、 第 1 层的格子数对应分项 分项 n , ；n ,第 2 层的格子数对应 1图（a）2075521 （3）“ 转置” 的图仍为Ferrers 图,称为原 Ferrers 图的共轭图,或者说这两个图是 一对共轭的 Ferrers 图；如某个 Ferrers 图与其共轭图外形相同,就称其是 自共轭 的；共轭图对应的分拆叫做 共轭分拆图（ b）共轭分拆 205433311 （三） 应用【定理 2.4.2】（1）n 的全部 k 分拆的个数等于把n 分拆成最大分项等于k的全部分拆数；（2）把 n 分拆成最多不超过k 个数之和的分拆数等于把n 分拆成最大分项不超过k 的全部分拆数；（证）两种分拆一一对应

38、关系；【推论】正整数 n 分拆成互不相同的如干个奇数的和的分拆数,与 n 分拆成有自共轭的Ferrers 图的分拆数相等；（证）建立一一对应关系；设n2n 112 n212nkk1,n1n2nkFerrers 图特点：第 i 行、第 i 列元素为n1个；是自共轭的；反之亦然；17953 2.4.4 分 拆 数 的 估 计令 pnn 的全部无序分拆数（称作 npnk1p k nn 的分拆数 ）【定理 2.4.3】正整数 n 的全部分拆总数数列pn的母函数是Pxn0pnxn1x1x11xk2当 n 较大时,运算 pn是特别困难的；p11,p57,p1042,p15176, p20627,p2519

39、58,p20039729990293884 万亿pn的渐进公式和估值不等式：【例 2.4.4】关于pn的运算,有2n,n（1）pne20n3（2）pn13e34 n（3）2npnn3n,n2. 利用二元递归函数运算 pn的算法：【定理 2.4.5】令 Q n , m正整数 n 的最大分项 n1m 的全部分拆数：Qn,m1,n,n,n1,nm,mm1 或n1Qmn1Qn,mnQn,m1Q,1mn实质上是函数 Qn,m的一种递归定义；pnQn ,n；明显有 Q1,n Qm,11；12 由于最大重量 n1 实际上不能大于 Qn,n；n,故 m n 时,Qn,m3 由于在 n 的全部分拆中, 其 1

40、分拆只有一个, 即 nn1,而其它的分拆都是 n1n- 1；4 N 的最大分项为 m 的分拆数分为两部分：以 m 作为第一分项,其余分项之和等于nm,且最大分项 n2 不超过 m 的分拆数 Qn- m,m；最大分项 n1m- 1 的分拆数 Q n,m- 1；2.4.5 应 用【例 2.4.1】（各分项不同,即不重复 ）设有 1 克、2 克、3 克、4 克的砝码各一枚,如要求各砝码只能放在天平的一边；问能称出 那几种重量？有哪几种可能方案？（解）典型的正整数分拆问题；例：6 克物品 32142 分拆条件：最大分项不超过 4 时,6 的无序不重复分拆有两种 一般条件：将整数 n 分拆为最大分项不超

41、过 4,且各分项最多 只能显现一次的分拆；母函数：1x1x21x31x48x9x101xx22x32x42x52x62x7x结论：可称出从1 克到 10 克共 10 种重量,幂n x 的系数即为称出 n 克重量的方案数；枚举：分拆数的母函数：2 3 41 x 1 y 1 z 1 w 1 x y2xy2 z3xz3w4xy 2 z 3 y 2 w 4xw 4 y 2 z 3xy 2 w 4 z 3 w 4xz 3w 4 y2z3w4xy2z3w4规律：如 x n 1 y n 2 z n 3 w n 4（in 0 或 i ）中各因子的指数之和为n,就单项式 x n 1 y n 2 z n 3 w

42、n 4 对应一种称 n 克重量的方案；例：z 3w 4对应称 7 克重量的方案之一,而且用的是 3 克和 4克的砝码；另一方案为 xy 2w 4xy2w4对应的用 1 克、2 克和 4 克的砝码；说明：a 取 12324,重量相同, 元素个数不同, 对应所取元素个数不同的组合方案；b 如取两个元素,如 235,347,元素个数相同,但重量不同,是不同的整数的分拆方案；c 组合关怀的是元素的个数, 分拆关怀的是元素的加权和 （每个元素给予肯定的权值） ；对于组合而言,其母函数应为1 x 1 y 1 z 1 w1xyzwxyxzxwyzywzw xyzxywxzwyzwxyzw 【例 2.4.2】

43、（各分项无限重复 ）求用 1 分、2 分、3 分的邮票贴出不同面值的方案数；（解）分项可（无限）重复的无序分拆；母函数：Gx1xx2 1x2x4 1x3x6 1 1 11 x 1 x 2 1 x 33 14 5 61 x x x x x1 x 2 x 23 x 34 x 45 x 57 x 6例：x 系数为 4,贴出 4 分面值的方案有 4 种,即 441111,4211,422,431 说明：此题是根据邮票总面值的不同来区分并统计方案数的；如将邮票贴成一行, 不同面值的邮票互换位置后算作另一种方案,就问题将成为有序分拆；【例 2.4.3】（有序分拆 ）在例 2.4.2 中,根据有序分拆,贴成

44、总面值等于 4 分的方案数是多少？（解）例：无序分拆方案 4211、431 分别对应 3个和 2 个有序分拆方案（总的方案数为 7）：4211121112,43113 求解：利用有序分拆求方案数（分类运算）：4 的 1 有序分拆数为 q 1 4C4- 1,1-11,即 44 分拆为自身；4 的 2 有序分拆数为q24C4- 1,2- 13,即 4311322；4 的 3 有序分拆数q34C4- 1,3- 13,即 4211121112；4 的 4 有序分拆数 q 4 4C4- 1,4- 11,即 41111；各项 iq 4 求和,即得 4 的全部有序分拆数为 8,但此题中无 4分面值的邮票,故

45、不算 q 1 4,恰为 7 种方案；困难性：不能一次运算到位；【例 2.4.4】（各分项有限不重复 ）如有 1 克的砝码 3 枚,2 克的4 枚, 4 克的 2 枚,问能称出多少种重量？各有几种方案？（解）分析：无序分拆中处于不重复分拆（例 2.4.1）和无限重 复分拆（例 2.4.2）之间的有限重复分拆问题；母函数Gx1xx2x31x2x4x6x81x4x81x2x22x33 x43x54x64x75x85x95x105 x114 x124 x133 x143 x152 x162 x17x18x19 结果：共能称出 19 种重量 例：称 8 克重量（即 8 的分项为 1、2、4 的无序分拆）

46、8444224211222222211 扩展：如将 1 克的砝码改为 4 枚,方案增加 841111221111 【例 2.4.5】（扩展） 在例 2.4.4 中,如砝码可以放在天平的两边,但两边不能同时有同样重量的砝码,请给出问题的母函数；问要 秤出 2 克重的物体,有多少种不同的秤法？并给出每一种秤法；（解）分析：物体一边的砝码抵消了天平另一边砝码重量；Gx1111xx2x3x x3x2x11111x2x4x6x8x8x6x4x2111x4x8x8x4x11x102x92x83x73x64x53x44x33x24x134 x 3x 434 x 45 x 36 x 3x728 x 29 x

47、x10 x11x8x41x4x8x19x19 1317 x 132 x 163 x 结果：秤 2 克重物体的不同秤法有13 种；枚举：用不同符号x、y、z 代表不同砝码：Gxx3x2x11xx2x362y8y8y6y4y21y2y4yz8z414 z8 z2y64 z 4 zy xy 24 z x3y8z8（x2y68 z y88 z xy6zx2x2y 1 x2y2x24y4z4y2z4y8z8x2y6z8） （x2y48 z y68 z x2y88 z x24 z y624 z x2y4z 4y 8yx2y y x x2z4z4x2y8z8）x2y4z4 x3y8z 8例：称 2 克的重量

48、,有 13 种方法（负数表示砝码放在左边,正数表示砝码放在右边）2 x 11 y 2 x x y2y - 1- 122 24z - 1- 14 24z - 24 x2y44z 11- 2- 24y6z4222- 4x2y4z41122- 4x x y2y48z - 1- 1- 2- 244 2y8z4-1-12222- 468z- 2- 2- 244 x 2 y 8 8z 11- 2- 2- 2- 244 x 2 y 8 z 8112222- 4- 4 反例：用上边的母函数反映不出来的称法（即天平两边放有 同一重量的砝码,使得相同砝码抵消）2- 112 - 1- 2122- 1- 214 -

49、4114 - 424 - 1- 1- 4224 - 2- 4224 - 1- 1- 2- 42224 - 1- 1- 2- 2- 2244 【例 2.4.6】投掷 3 个骰子,点数之和为 有多少种？骰子的情形如下：（1）3 个骰子相异；（2）3 个骰子相同；n（3n18）,其方案（解）（1）3 个骰子不同（ 3 个骰子分别为红、兰、黄色） ,问题等价于 n 的每个分项都有限制的特别有序nn1n2n33-分拆；即1ni6,i1 ,2,3由定理 2.4.1 知,相应的母函数为Gxxx2x63x33x46x510 x61315x71421x825x 27 9 x 106 x 1631727x1125

50、x1221x15x10 x15x18n 的投掷方案个数就是xn的系数骰子的点数之和等于2n18；例如点数之和等于15 的方案有 10 种,即663636366654645564546465456555 原理：假设和式中的第一个加数为红色骰子的点数,后两个加数分别为兰色和黄色骰子的点数,而这也恰好反映了15 的每个分项值不超过 6 的全部有序 3 分拆；（2）3 个骰子相同,问题等价于 殊性表达在对每个重量的值都限制在n 的特别无序 3-分拆；其特 16 之间,即nn1n2n313,且6n1n2n3利用 Ferrers 图,问题又可转化为求n 的最大分项等于项数不超过 6 的分拆数,即求方程11

51、x10 ,2x23x33nx 1x2x36xx20 ,x,1的非负整数解的个数；母函数Gxx51xx2x3x4x21xx2x3x221x1x25x321xx2x221xx41xx2x3x1xx231x24x321xx221x23x331xx2x31xx2x21xx21xx21x22x341x1x2x35x 6x 6x106x111x36x 2x 3x 4x 5x 6x125x134x143x152x x17x18x 的系数（ 3n18）；其中点数之和等于n 的方案数就是例如点数之和等于10 的方案有 6 种,即10631622541 532442433 这也是 10 的每个分项值不超过6 的无

52、序 3 分拆数；习题二（1）基此题： 1,3,69,1315,18 （2）加强题： 2,5,1011 （3）提高题： 4,12,16,17 1.求以下数列的母函数（ n0,1,2, ）：nn0 xn（1）1nn；（2） n5 （3） nn1 ；（4） nn2 （解）（1）Gxn01nxnn0 xn1xnn（2）Gxn5xnn1xn4xnn0n0n0n0 xn114xn0 xn114x11x114x11214xx54x1x2（3）Gxn0nn1xn00 x2n2nn1xn2x2n2n1xnx2xn2n0n0 x2n0 xn2x21x2x2x231x（4）Gxn0nn2xnn0n1n2xnn0n1

53、xn0 xn2n0 xn111xx n 2 x n 1 1n 0 n 0 1 xx 2 x 11 x 1 x 1 x1 2x 31 1x 2 1 1x31 xx x3 22. 证明序列 Cn,n,Cn1,n,Cn2,n, 的母函数1为 n 11 x（证）已知集合 S e 1,e 2,e n 的 r-组合的母函数为1 n r 11 x nr 0 r x r所以序列 C n , n,C n ,1 n,C n 2 , n, 的母函数为G xnx 0 n 1x 1 n 2x 2 n rx rn n n nn rx rr 0 rn 1 r 1rxr 0 r11 x n 13. 设 Se 1 , e 2

54、, e 3 , e 4,求序列 a n 的母函数,其中 an是 S 的满意以下条件的 n 组合数：（1） S 的每个元素都显现奇数次；（2） S 的每个元素显现 3 的倍数次；（3） e1不显现, e2 至多显现一次；（4） e1只显现 1、3 或 11 次,e2 只显现 2、4 或 5 次；（5） S 的每个元素至少显现 10 次；4（解）（1）G xx x 3x 5 4x2 4；1 x（2）G x1 x 3 x 6 x 9 413 4；1 x（3）G x1 x 1 x x 2x 3 21 x2；1 x（4）G xx x 3x 11x 2x 4x 51 x x 2x 3 2x 3 2 x 5

55、 x 6 x 7 x 82 x 13 x 15 x 16；1 x（5）G xx 10 x 11x 12 4x 404；1 x4. 投掷两个骰子,点数之和为 r（2r12）,其组合数是多少？（解）相应的母函数为Gx1xx2x5x2n1xx2x3x4x221xx2x3x231xx2x241xx25x26x2x32x42x53x63x73x8293x10 x11x12其中点数之和为 n 的方案数就是x 的系数；5.居民小区组织义务活动,号召每家出一到两个人参与；设该小区共有 n 个家庭,现从中选出r 人,问：（1）设每个家庭都是3 口之家,有多少种不同的选法？当50 时,选法有多少种？（2）设 n

56、个家庭中两家有 4 口人,其余家庭都是 3 口人,有多少种选法？6.把 n 个相同的小球放入编号为1 ,2,m的 m 个盒子中,使得每个盒子内的球数不小于它的编号数；已知 n m 2 m,求不同2的放球方法数 g n , m；7. 红、黄、蓝三色的球各 8 个,从中取出 9 个,要求每种颜色的球至少一个,问有多少种不同的取法？（解）设从中取 r 个的不同取法有a 种,那么,数列a 的母函数为Gx2x2x2x37xx83997x1010 x16x242x33x488xxx3xxx3x8828x35x3x46x521x因此所求方案数为a 28 9a,8b,8c中取出 9 个元另法：原问题等价于从集

57、合S8素,且每个元素至少取一个；现在先把元素a、b、c 各取一个,然后再随便选出 6 个,就问题转变为从集合S 7a,7b ,7c中取出 6 个元素,且每个元素个数不限,求重复组合的方案数；又由于每个元素的个数大于 6,故从 S 中取 6 个元素与从集合 S a , b , c 中取出 6 个元素的组合数一样多, 从而知不同的取法为8.C661C22838将币值为 2 角的人民币,兑换成硬币（壹分、贰分和伍分）可有多少种兑换方法？（解）这是求正整数n 的分项只能等于1、2、5 的分拆数；设 n 的分拆数为a ,就a 的母函数为x5x10Gx1xx21x2x4121xn1x2x22x33x43x

58、5n1x5x101 x 2 x 22 x 33 x 44 x 529 x 20所以,共有 a 2029 种兑换方法；9. 有 1 克重砝码 2 枚,2 克重砝码 3 枚,5 克重砝码 3 枚,要求这 8 个砝码只许放在天平的一端；能称几种重量的物品？有多少种不同的称法？（解）设秤r 克重的物体有a 种秤法,那么数列 ra的母函数是Gx1xx21x2x4x61x5x10 x14绽开后得Gx112x22x23x32x42x5163x6173x7x2x8192x9x2x10213x113xx13x142x154x2x318x220 xx22因此,能称 122 克共 22 种重量的物品,全部不同的称法总数为G 13 4 448 10. 证明不定方程 x 1 x 2 x n r 的正整数解组的个数为 C r 1 n 1；（证）问题可以视为将 r 个相同的 1 放入 n 个盒子；由于将 ix之间的