《组合数学》教案-2章(母函数)

第二章母函数及其应用1.普母函数及其在组合问题中的应用2.指母函数及其在排列问题中的应用3.正整数的分拆及其组合意义和应用问题：对于不尽相异元素的部分排列和组合，用第一章的方法比较麻烦（参见表2.0.1）。新方法：母函数方法。表2.0.1条件组合方案数排列方案数对应的集合相异元素，不重复!!!Crnrnrn!!PrnnrnneeeS,,,21相异元素，可重复rrn1CrnS＝{,,21eene,}不尽相异元素（有限重复）特例r＝n1!!!!21mnnnnS＝{11en，22en，…，mmen},n1＋n2＋…＋nm＝n，nk≥1,（k＝1,2,…,m）r＝1mm所有kn≥rrrm1Crm至少有一个kn满足rnk1基本思想：把离散的数列同多项式或幂级数一一对应起来，从而把离散数列间的结合关系转化为多项式或幂级数之间的运算。2.1母函数（一）母函数（1）定义《组合数学》第二章母函数2/46【定义2.1.1】对于数列na，称无穷级数0nnnxaxG为该数列的（普通型）母函数，简称普母函数或母函数。（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《组合数学》第二章母函数3/46ak＝k(k＋1)(k＋2)416xxak＝k，任意x1a0＝0，ak＝kak-ln(1-ax)ak＝!kk，任意xeak＝!21kkxcosak＝!121kkxxsin1ak＝121kkxxarctan1ak＝kkn11nx（二）组合问题（1）组合的母函数【定理2.1.1】组合的母函数：设mmenenenS,,,2211,且n1＋n2＋…＋nm＝n，则S的r可重组合的母函数为xG＝minjjix10＝nrrrxa0其中，r可重组合数为rx之系数ra，r＝0,1,2,…,n。理论依据：多项式的任何一项与组合结果一一对应。优点：将无重组合与重复组合统一起来处理；使处理可重组合的枚举问题变得非常简单。（2）特例【推论1】neeeS,,,21，则r无重组合的母函数为G(x)＝(1＋x)n组合数为rx之系数rnC。《组合数学》第二章母函数4/46【推论2】neeeS,,,21，则r无限可重组合的母函数为G(x)＝nnjjxx110组合数为rx之系数rrn1C。【推论3】neeeS,,,21，每个元素至少选一个：母函数G(x)＝nnjjxxx11组合数11Cnr【推论4】neeeS,,,21，每个元素选非负偶数个：母函数G(x)＝nnxxx2421＝nx211组合数ra＝为偶数当为奇数当rrrnr,2,12C,0。【推论5】neeeS,,,21，每个元素选奇数个：母函数G(x)＝nnxxxx1253＝nxx21组合数为偶数当为奇数当nrnrnrnnrar,2,12C,0【推论6】S＝mmenenen,,,2211，且n1＋n2＋…＋nm＝n，元素ie至少出现ik次：为《组合数学》第二章母函数5/46母函数G(x)＝minkjjiix1＝nkrrrxa组合数rar＝k,k＋1,…,n，k＝k1＋k2＋…＋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红、黑、白球），元素的个数以符号的指数区分。母函数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/46⑤取4个球的方案有1种，即全取。令x＝y＝z＝1，得方案总数G(1,1,1)＝1＋3＋4＋3＋1＝12（2）只考虑每次取3个的方案数，不需枚举令y＝x，z＝xG(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）求解：母函数G(x)＝104726151iiiiiiiixxxx＝x8＋…＋140x18＋…＋x28（3）特殊情况处理：戏票数r＝4，ik＝0（i＝1,2,3,4）G1(x)＝100706050iiiiiiiixxxx＝2843541xxxG2(x)＝40iix＝411x＝28444953541xxx《组合数学》第二章母函数7/464x系数相同，用G2(x)计算要比用G1(x)方便得多（因为将50iix扩展为0iix不影响4x的系数）同理，r＝6，可用G3(x)＝3050jjiixx＝3501xxii代替G1(x)求6x的系数。【例2.1.5】从n双互相不同的鞋中取出r只（nr），要求其中没有任何两只是成对的，问共有多少种不同的取法？（解）解法一：母函数法。视为neeeS2,,2,221，但同类中的两个ie不一样，即2122211211,,,,,,nneeeeeeS故其r重组合的母函数为G(x)＝(1＋2x)n＝nrrrxrn02不同的取法共有rrrna2种。本质：每类元素最多只能出现一次，但同类元素互换后方案不同。故G(x)＝nxC121中不能有2x项，再由同双的两只鞋子有区别知，x的系数应为2。解法二：排列组合。先从n双鞋中选取r双，共有rn种选法，再从此r双中每双抽取一只，有r2种取法。解法三：排列组合。先取出k只左脚的鞋，再在其余kn双鞋中取出kr只右脚的鞋rk,,2,1,0：《组合数学》第二章母函数8/46ra＝02221110rnrnrnnrnnrnn得组合恒等式02221110rnrnrnnrnnrnn＝rrn2一般提法：S＝mmnmmnneeeeeeeee,,,,,,,,,21222211121121；；；从中取出r个，第i类元素最少ik个，最多it个，母函数：G(x)＝mitkjjiiixjn1举例，把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。母函数G(x)＝926151965iiiiiixixixi＝4291615x＋5291625292615391615x＋…[phone]x＝10804x＋73805x＋…＋20x共有7380种分配方案。说明：与问题“从20个相异元素中不重复地抽取5个元素”《组合数学》第二章母函数9/46不等价（答案为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本、1本或2本。（3）一般情形：视为2个大盒子A、B，且A又分为2个小盒子。分两步分配：第一步：A盒子分偶数本，B盒子分任意本；第二步：将分给A盒的书再给甲、乙各分一半。A（2k本）B（n－2k本）甲（k本）乙（k本）丙（n－2k本）xG＝kxxx2421kxxx21＝xx1112＝2112111411141xxx＝0141nnnx＋041nnx＋0121nnxnn＝041121nnnxn《组合数学》第二章母函数10/46＝021nnxn不同的分配方法共有21n种。x——上整数函数。即不小于x的最小整数。（待定系数法