📄 2_7.htm
字号:
<head><title>组合数学</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><h1>§2.7 指数型母函数 </h1><p> §2.7.1 问题提出 </p><p> 设有n个元素，其中元素a<sub>1</sub>重复了n<sub>1</sub> 次，元素a<sub>2</sub> 重复了n<sub>2</sub> 次，…，a<sub>k</sub> 重复了n<sub>k</sub> 次，n=n<sub>1</sub>+n<sub>2</sub>+<sup>...</sup>+n<sub>k</sub>从中取r个排列，求不同的排列数 </p><p> 如果n<sub>1</sub>=n<sub>2</sub>=<sup>...</sup>=n<sub>k</sub>=1，则是一般的排列问题。 </p><p> 现在由于出现重复，故不同的排列计数便比较复杂。先考虑n个元素的全排列，若n个元素没有完全一样的元素，则应有n!种排列。若考虑n<sub>i</sub> 个元素a<sub>i</sub>的全排列数为n<sub>i</sub>! ，则真正不同的排列数为 </p><p> <img border="0" src="2_7.pic/image024.gif" width="76" height="45"></p><p>§2.7.2 解的分析 </p><p> 先讨论一个具体问题：若有8个元素，其中设a<sub>1</sub>重复3次，a<sub>2</sub>重复2次，a<sub>3</sub>重复3次。从中取r个组合，其组合数为c<sub>r</sub>，则序列 c<sub>0</sub>,c<sub>1</sub>,c<sub>2</sub>,c<sub>3</sub>,c<sub>4</sub>,c<sub>5</sub>,c<sub>6</sub>,c<sub>7</sub>的母函数为</p><p> <img border="0" src="2_7.pic/image035.gif" width="315" height="73"></p><p> 从x<sup>4</sup> 的系数可知，这8个元素中取4个组合，其组合数为10。这10个组合可从下面展开式中得到 </p><p> <img border="0" src="2_7.pic/image039.gif" width="312" height="236"></p><p>其中4次方项有 </p><p> <img border="0" src="2_7.pic/image041.gif" width="304" height="51"></p><p>(2-7-2)表达了从8个元素(a<sub>1</sub>a<sub>3</sub>各3个,a<sub>2</sub>2个)中取4个的组合。例如x<sub>1</sub>x<sub>3</sub><sup>3</sup>为一个a<sub>1</sub>，3个a<sub>3</sub>的组合，x<sub>1</sub><sup>2</sup>x<sub>3</sub><sup>2</sup>为两个a<sub>1</sub>，两个a<sub>3</sub>的组合，以此类推。 </p><p> 若研究从中取4个的不同排列总数，以x<sub>1</sub><sup>2</sup>x<sub>3</sub><sup>3</sup>对应的两个两个的不同排列为例，其不同排列数为 </p><p> <img border="0" src="2_7.pic/image055.gif" width="52" height="41"></p><p>即 </p><p> <img border="0" src="2_7.pic/image057.gif" width="60" height="24"><img border="0" src="2_7.pic/image059.gif" width="60" height="24"><img border="0" src="2_7.pic/image061.gif" width="60" height="24"><img border="0" src="2_7.pic/image063.gif" width="60" height="24"><img border="0" src="2_7.pic/image065.gif" width="60" height="24"><img border="0" src="2_7.pic/image067.gif" width="60" height="24"></p><p>六种。同样，1个a<sub>1</sub>3个a<sub>3</sub>的不同排列数为 </p><p> <img border="0" src="2_7.pic/image071.gif" width="43" height="41"></p><p>即 </p><p> <img border="0" src="2_7.pic/image073.gif" width="61" height="24"><img border="0" src="2_7.pic/image075.gif" width="61" height="24"><img border="0" src="2_7.pic/image077.gif" width="61" height="24"><img border="0" src="2_7.pic/image079.gif" width="61" height="24"></p><p>以此类推。故从(2-7-2)式可得问题的解，其不同的排列数为 </p><p> <img border="0" src="2_7.pic/image081.gif" width="272" height="149"></p><p>§2.7.3 指数型母函数 为了便于计算，利用上述特点，形式地引进函数 </p><p> <img border="0" src="2_7.pic/image083.gif" width="236" height="88"></p><p> <img border="0" src="2_7.pic/image085.gif" width="317" height="171"></p><p> 从(2-7-3)式计算结果可以得出：取一个的排列数为3，取两个的排列数为2*9/2=9，取3个的排列数为3!*14/3=28，取4个的排列数为4!*35/12=70，如此等等。把(2-7-3)式改写成下面形式便一目了然了。 </p><p> <img border="0" src="2_7.pic/image087.gif" width="301" height="85"></p><p> 定义：对于序列a<sub>0</sub>a<sub>1</sub>a<sub>2</sub><sup>...</sup>函数 </p><p> <img border="0" src="2_7.pic/image091.gif" width="207" height="85"></p><p>称为是序列a<sub>0</sub>a<sub>1</sub>a<sub>2</sub><sup>...</sup>的指数型母函数 </p><p> 综合上述可得如下两个结论： </p><p> (a) 若元素a<sub>1</sub>有n<sub>1</sub>个，元素a<sub>2</sub>有n<sub>2</sub>个，…，元素a<sub>k</sub>有n<sub>k</sub>个，由此；组成的n个元素的排列，不同的排列总数为 </p><p> <img border="0" src="2_7.pic/image104.gif" width="76" height="45"></p><p>其中n=n<sub>1</sub>+n<sub>2</sub>+<sup>...</sup>+n<sub>k</sub></p><p> <sub> </sub>(b) 若元素a<sub>1</sub> 有n<sub>1</sub> 个，元素a<sub>2</sub> 有n<sub>2</sub> 个，…，元素a<sub>k</sub> 有n<sub>k</sub>个，由此；组成的n个元素中取r个排列，设其不同的排列数为p<sub>r</sub> 。则序列p<sub>r</sub>,p<sub>1</sub>,<sup>...</sup>,p<sub>n</sub>的指数型母函数为 </p><p> <img border="0" src="2_7.pic/image118.gif" width="308" height="96"> </p><p>与(2)中所用的方法相比，可以看出指数型母函数在解决有重复元素的排列时的优越性。 </p><p>§2.7.4 举例 </p><p> 例1：求由两个a，1个b，2个c组成的不同排列总数。 </p><p> 根据结论一，不同的排列总数为 </p><p> <img border="0" src="2_7.pic/image120.gif" width="92" height="41"></p><p> 例2：由1，2，3，4四个数字组成的五位数中，要求数1出现次数不超过2次，但不能不出现； 2出现次数不超过1次； 3出现次数可达3次，也可以不出现；4出现次数为偶数。求满足上述条件的数的个数。 </p><p> 设满足上述条件的r位数为 ，序列 的指数型母函数为 </p><p> <img border="0" src="2_7.pic/image126.gif" width="264" height="176"></p><p> <img border="0" src="2_7.pic/image128.gif" width="244" height="109"></p><p> <img border="0" src="2_7.pic/image130.gif" width="283" height="88"></p><p>由此可见满足条件的5位数共215个。 </p><p> 例3: 求1，3，5，7，9五个数字组成的n位数的个数，要求其中3，7出现的次数为偶数，其他1，5，9出现次数不加限制。</p> <p> 设满足条件的r位的个数为 ，则序列 对应的指数型母函数为 </p><p> <img border="0" src="2_7.pic/image135.gif" width="303" height="44"></p><p>由于</p><p> <img border="0" src="2_7.pic/image137.gif" width="241" height="173"></p><p> <img border="0" src="2_7.pic/image139.gif" width="221" height="179"></p>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -