组合数学讲义及答案-2章-母函数

《组合数学》第二章母函数1/49第二章母函数及其应用问题：对于不尽相异元素的部分排列和组合，用第一章的方法是比较麻烦的（参见表2.0.1）。新方法：母函数方法。表2.0.1条件组合方案数排列方案数对应的集合相异元素，不重复!!!rnrnCrn!!rnnPrnneeeS,,,21相异元素，可重复rrnC1rnS＝{,,21eene,}不尽相异元素（有限重复）特例r＝n1!!!!21mnnnnS＝{11en，22en，…，mmen},n1＋n2＋…＋nm＝n，nk≥1,(k＝1,2,…,m)r＝1mm所有kn≥rrrmC1rm至少有一个kn满足1≤knr基本思想：把离散的数列同多项式或幂级数一一对应起来，从而把离散数列间的结合关系转化为多项式或幂级数之间的运算。2.1母函数（一）母函数（1）定义【定义2.1.1】对于数列na，称无穷级数0nnnxaxG为该数列的（普通型）母函数，简称普母函数或母函数。《组合数学》第二章母函数2/49（2）例【例2.1.1】有限数列rnC（r＝0,1,2,…,n）的普母函数是。xG＝nnnnnnxCxCxCC2210＝nx1【例2.1.2】无限数列{1，1，…，1，…}的普母函数是xG＝nxxx21＝x11（3）说明●na可以为有限个或无限个；●数列na与母函数一一对应；例如，无限数列{0，1，1，…，1，…}的普母函数是nxxx20＝xx1●将母函数只看作一个形式函数，目的是利用其有关运算性质完成计数问题，故不考虑“收敛问题”，而且始终认为它是可“逐项微分”和“逐项积分”的。（4）常用母函数{ak}，k＝0,1,…G(x){ak}，k＝0,1,…G(x)ak＝1x11ak＝akax11ak＝k21xxak＝k＋1211xak＝k(k＋1)312xxak＝k2311xxxak＝k(k＋1)(k＋2)416xxak＝k，任意x1a0＝0，ak＝kak-ln(1-ax)ak＝!kk，任意xe《组合数学》第二章母函数3/49ak＝!21kkxcosak＝!121kkxxsin1ak＝121kkxxarctan1ak＝kkn11nx（二）组合问题（1）组合的母函数定理2.1.1组合的母函数：设mmenenenS,,,2211,且n1＋n2＋…＋nm＝n，则S的r可重组合的母函数为xG＝minjjix10＝nrrrxa0(2.1.1)其中，r可重组合数为rx之系数ra，r＝0,1,2,…,n.理论依据：多项式的任何一项与组合结果一一对应（见例2.1.3）定理2.1.1的优点：●将无重组合与重复组合统一起来处理；●使处理可重组合的枚举问题变得非常简单。（2）特例推论1neeeS,,,21，则r无重组合的母函数为G(x)＝(1＋x)n(2.1.2)组合数为rx之系数rnC。推论2neeeS,,,21，则r无限可重组合的母函数为G(x)＝nnjjxx110(2.1.3)《组合数学》第二章母函数4/49组合数为xr之系数rrn1C。推论3neeeS,,,21，每个元素至少取一个，则r可重组合（r≥n）的母函数为G(x)＝nnjjxxx11(2.1.4)组合数为xr之系数11Cnr。推论4neeeS,,,21，每个元素出现非负偶数次，则r可重组合的母函数为G(x)＝nnxxx2421＝nx211(2.1.5)组合数为xr之系数ra=为偶数当为奇数当rrrnr,2,12C,0推论5neeeS,,,21，每个元素出现奇数次，则r可重组合的母函数为G(x)＝nnxxxx1253＝nxx21(2.1.6)组合数为xr之系数为偶数当为奇数当nrnrnrnnrar,2,12C,0推论6设S=mmenenen,,,2211,且n1＋n2＋…＋nm＝n，要求元素ie至少出现ik次，则S的r可重组合的母函数为G(x)＝minkjjiix1＝nkrrrxa(2.1.7)其中，r可重组合数为rx之系数ra，r＝k,k＋1,…,n，k＝k1＋《组合数学》第二章母函数5/49k2＋…＋km。（3）一般情形：设S={20.a，30.b，∞.c}，并设元素a只能出现1～5，10，13，16次，b只允许出现奇数次，c至少出现5次且必须出现偶数次，求S的r可重组合的母函数。G(x)＝16131052xxxxxx2953xxxx86xx（三）应用【例2.1.3】设有2个红球，1个黑球，1个白球，问（1）共有多少种不同的选取方法，试加以枚举？（2）若每次从中任取3个，有多少种不同的取法？解（1）设想用x，y，z分别代表红、黑、白三种球，两个红球的取法与x0，x1，x2对应起来，即红球的可能取法与1＋x＋x2中x的各次幂一一对应，亦即x0＝1表示不取，x表示取1个红球，x2表示取两个。对其它球，依此类推。则母函数G(x,y,z)＝(1＋x＋x2)(1＋y)(1＋z)＝1＋(x＋y＋z)＋(x2＋xy＋xz＋yz)＋(x2y＋x2z＋xyz)＋(x2yz)共有5种情况，即①数字1表示一个球也不取的情况，共有1种方案；②取1个球的方案有3种，分别为红、黑、白三种球只取1个；③取2个球的方案有4种，即2红、1红1黑、1红1白、1黑1白；④取3个球的方案有3种，即2红1黑、2红1白、三色球各一；《组合数学》第二章母函数6/49⑤取4个球的方案有1种，即全取。若令x＝y＝z＝1，就得所有不同的选取方案总数为G(1,1,1)＝1＋3＋4＋3＋1＝12（2）若只考虑每次取3个的方案数，而不需枚举，则令y＝x，z＝x，便有G(x)＝(1＋x＋x2)(1＋x)(1＋x)＝1＋3x＋4x2＋3x3＋x4由x3的系数即得所求方案数为3。【例2.1.4】有18张戏票分给甲、乙、丙、丁4个班（不考虑座位号），其中甲、乙两班最少1张，甲班最多5张，乙班最多6张，丙班最少2张，最多7张，丁班最少4张，最多10张，问有多少种不同的分配方案？解（1）问题分析：这实质上是由甲、乙、丙、丁四类共28个元素中可重复地取18个元素的组合问题。其中432110,7,6,5eeeeS，m＝4，n＝n1＋n2＋n3＋n4＝5＋6＋7＋10＝28，k＝4321kkkk＝1＋1＋2＋4＝8，r＝18。（2）求解：由推论6知相应的母函数为G(x)＝104726151iiiiiiiixxxx＝x8＋…＋140x18＋…＋x28所以，共有140种分配方案。（3）特殊情况处理：若将戏票数改为r＝4张，各班所分戏票的下限数ik＝0（i＝1,2,3,4），这时G1(x)＝100706050iiiiiiiixxxx＝2843541xxx与《组合数学》第二章母函数7/49G2(x)＝40iix＝411x＝28444953541xxx中4x的系数是一样的，因为将50iix扩展为0iix并不影响4x的系数，故用G2(x)计算要比用G1(x)方便得多。同理，当r＝6时，可以用G3(x)＝3050jjiixx＝3501xxii来代替G1(x)求6x的系数。【例2.1.5】从n双互相不同的鞋中取出r只（nr），要求其中没有任何两只是成对的，问共有多少种不同的取法？解解法一：用母函数方法。即视为neeeS2,,2,221，但同类中的两个ie不一样，即S应为2122211211,,,,,,nneeeeeeS故其r重组合的母函数为G(x)＝(1＋2x)n＝nrrrxrn02即不同的取法共有rrrna2种。由于每类元素最多只能出现一次，故G(x)＝nx21中不能有2x项，再由同双的两只鞋子有区别知，x的系数应为2。解法二：用排列组合。先从n双鞋中选取r双，共有rn种选法，再从此r双中每双抽取一只，有r2种取法，由乘法原理，即得结果同上。解法三：仍用排列组合。先取出k只左脚的鞋，再在其余kn《组合数学》第二章母函数8/49双鞋中取出kr只右脚的鞋rk,,2,1,0，即得取法数为ra=02221110rnrnrnnrnnrnn由此得组合恒等式02221110rnrnrnnrnnrnn＝rrn2此类问题的一般提法是：设集合S中共有m类元素，其中第i类有in个，且同类的元素也互不相同，即S＝mmnmmnneeeeeeeee,,,,,,,,,21222211121121；；；。现从中取出r个，若规定第i类元素不能少于ik个，则S的r组合的母函数为G(x)＝minkjjiiixjn1例如，把5本相同的书分给甲、乙、丙3个班，再发到个人手上，每人最多发一本。考虑将分给某班的某本书发给该班的同学A与将其发给同学B被认为是不同的分法（每个同学最多一本），而且甲、乙两班最少1本，甲班最多5本，乙班最多6本，丙班最少2本，最多9本，问有多少种不同的分配方案？这时，S＝393231262221151211,,,,,,,,,eeeeeeeee；；，3m，n＝321nnn＝5＋6＋9＝20，k＝321kkk＝1＋1＋2＝4，r＝5。故r组合母函数为，G(x)＝926151965iiiiiixixixi＝4291615x＋5291625292615391615x＋…《组合数学》第二章母函数9/49＋20996655x＝10804x＋73805x＋…＋20x所以，共有7380种分配方案。说明：这里不能认为此问题等价于从20个相异元素中不重复地抽取5个元素，那么，答案应为520＝15,504了。【例2.1.6】甲、乙、丙3人把n（n≥3）本相同的书搬到办公室，要求甲和乙搬的本数一样多，问共有多少种分配的方法？（解）（1）分析：组合问题：从集合321,,eeeS中可重复地选取n个元素，但要求1e与2e的个数一样多，求不同的选取方案数。核心：限制盒子之间的关系。（2）特例：n＝1，1种分法，甲和乙都分0本（丙1本）。n＝2，2种分法：甲和乙分0本（丙2本）或甲和乙1本（丙0本）。当n＝3时，分法2种。当n＝4或5，3种分法：甲和乙都分0本、