资源描述：
《《组合数学》教案2章(母函数)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章母函数及其应用1.普母函数及其在组合问题中的应用2.指母函数及其在排列问题中的应用3.正整数的分拆及其组合意义和应用问题：对于不尽相异元素的部分排列和组合，用第一章的方法比较麻烦（参见表2.0.1）。新方法：母函数方法。表2.0.1条件组合方案数排列方案数对应的集合相异元素，不重复相异元素，可重复S＝{}不尽相异元素（有限重复）特例r＝n1S＝{，，…，},n1＋n2＋…＋nm＝n，nk≥1,（k＝1,2,…,m）r＝1mm所有≥r至少有一个满足基本思想：把离散的数列同多项式或幂级数一一对应起来，从而把离散数列间的结合关系转化为多项式或
2、幂级数之间的运算。2.1母函数（一）母函数（1）定义【定义2.1.1】对于数列，称无穷级数为该数列的（普通型）母函数，简称普母函数或母函数。（2）例【例2.1.1】有限数列（r＝0,1,2,…,n）的普母函数是：＝＝【例2.1.2】无限数列{1,1.…,1,…}的普母函数是＝＝（3）说明●可以为有限个或无限个。●数列与母函数一一对应。{0,1,1,…,1,…}＝●将母函数视为形式函数，目的是利用其有关运算性质完成计数问题，故不考虑“收敛问题”，而且始终认为它是可“逐项微分”和“逐项积分”的。（4）常用母函数{ak}，k＝0,1,…G(x){a
3、k}，k＝0,1,…G(x)ak＝1ak＝akak＝kak＝k＋1ak＝k(k＋1)ak＝k2ak＝k(k＋1)(k＋2)ak＝，任意a0＝0，ak＝-ln(1-ax)ak＝，任意ak＝ak＝ak＝ak＝（一）组合问题（1）组合的母函数【定理2.1.1】组合的母函数：设,且n1＋n2＋…＋nm＝n，则S的r可重组合的母函数为＝＝其中，r可重组合数为之系数，r＝0,1,2,…,n。理论依据：多项式的任何一项与组合结果一一对应。优点：l将无重组合与重复组合统一起来处理；l使处理可重组合的枚举问题变得非常简单。（2）特例【推论1】，则r无重组合的母
4、函数为G(x)＝(1＋x)n组合数为之系数。【推论2】，则r无限可重组合的母函数为G(x)＝组合数为之系数。【推论3】，每个元素至少选一个：母函数G(x)＝组合数【推论4】，每个元素选非负偶数个：母函数G(x)＝＝组合数＝。【推论5】，每个元素选奇数个：母函数G(x)＝＝组合数【推论6】S＝，且n1＋n2＋…＋nm＝n，元素至少出现次：为母函数G(x)＝＝组合数r＝k,k＋1,…,n，k＝k1＋k2＋…＋km。（3）一般情形：设S＝{20.a，30.b，∞.c}，并设元素a只能出现1～5，10，13，16次，b只允许出现奇数次，c至少出现5次
5、且必须出现偶数次，求S的r可重组合的母函数。G(x)＝（一）应用【例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
6、个球的方案有4种，即2红、1红1黑、1红1白、1黑1白；④取3个球的方案有3种，即2红1黑、2红1白、三色球各一；⑤取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张，最多1
7、0张，问有多少种不同的分配方案？（解）（1）分析：实质为甲、乙、丙、丁四类共28个元素中可重复地取18个元素的组合问题。，m＝4，n＝n1＋n2＋n3＋n4＝5＋6＋7＋10＝28，k＝＝1＋1＋2＋4＝8，r＝18。（2）求解：母函数G(x)＝＝x8＋…＋140x18＋…＋x28（3）特殊情况处理：戏票数r＝4，＝0（i＝1,2,3,4）G1(x)＝＝G2(x)＝＝＝系数相同，用G2(x)计算要比用G1(x)方便得多（因为将扩展为不影响的系数）同理，r＝6，可用G3(x)＝＝代替G1(x)求的系数。【例2.1.5】从n双互相不同的鞋中取出r
8、只（），要求其中没有任何两只是成对的，问共有多少种不同的取法？（解）解法一：母函数法。视为，但同类中的两个不一样，即故其r重组合的母函数为G(x)＝(1＋2x)n＝
