2_11.htm

组合数学 清华大学研究生课程课件 呵呵

<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image074.gif" width="228" height="99"></p>
<p>3.母函数方法&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 设&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image076.gif" width="177" height="25"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image078.gif" width="207" height="77"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image080.gif" width="243" height="25"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image082.gif" width="217" height="131"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image084.gif" width="151" height="24"></p>
<p>即&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image086.gif" width="104" height="21"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image088.gif" width="107" height="45"></p>
<p>后面将看到只能取</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image090.gif" width="103" height="45"></p>
<p>才有意义.&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 由二项式定理&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image092.gif" width="203" height="60"><img border="0" src="2_11.pic/image094.gif" width="168" height="60"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image096.gif" width="299" height="85">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</p>
<p>即(1-4x)<sup>1/2</sup>中x<sup>n+l</sup>项的系数为&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image102.gif" width="255" height="143"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image104.gif" width="171" height="48"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image106.gif" width="141" height="45"></p>
<p>的系数为正，而且得&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image108.gif" width="113" height="48"></p>
<p>从递推关系&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image110.gif" width="165" height="24"></p>
<p>同样可推出&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image112.gif" width="121" height="45"></p>
<p>令&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image114.gif" width="244" height="51"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image116.gif" width="263" height="129"></p>
<p>用&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image118.gif" width="73" height="49"></p>
<p>乘等式两端得&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image120.gif" width="264" height="148"></p>
<p>即&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image122.gif" width="215" height="176"></p>
<p>4.举例&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image123.gif" width="404" height="202"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image124.gif" width="389" height="244"></p>
<p>&nbsp;&nbsp;&nbsp; 例1.&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image126.gif" width="100" height="48"> 
,</p>
<p>见图2-11-4&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 例2.P=a<sub>1</sub>a<sub>2</sub>a<sub>3</sub><sup>...</sup>a<sub>n</sub>为n个数a<sub>1</sub>a<sub>2</sub>a<sub>3</sub><sup>...</sup>a<sub>n</sub>的乘积,依据乘法的结合率,不改变其顺序,只用括号表示成对的乘积.试问有几种不同的乘法方案?&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 令P<sub>n</sub> 表示n个数乘积的n-1对括号插入的不同方案数.&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image134.gif" width="296" height="24"></p>
<p>令&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image136.gif" width="161" height="24"></p>
<p>故得&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image138.gif" width="243" height="24"></p>
<p>而且h<sub>n+1</sub>=h<sub>n</sub>=1 故P<sub>n</sub> 即为Catalan数h<sub>n+1</sub></p>
<p>&nbsp;&nbsp;&nbsp;<sub> </sub>以n-4为例&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image145.gif" width="129" height="48"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image147.gif" width="284" height="48"></p>
<p>P<sub>4</sub>=Catalan数h<sub>5</sub> ，下面建立（2－11－4）式中不同的乘法顺序和一个5边形不同拆分的一一对应关系，如图2－11－6&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image167.gif" width="474" height="199"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image168.gif" width="458" height="125"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image171.gif" width="444" height="181"></p>
<p>a×b运算用二分树表示，两片叶子分别表乘数和被乘数，分支点为运算符×，如图2－11－5&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image175.gif" width="134" height="142"></p>
<p>&nbsp;&nbsp;&nbsp; 例3. n个1和n个0组成一2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？</p> 
<p>&nbsp;&nbsp;&nbsp; 下面介绍两种算法。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 解法1. 设P<sub>2n</sub>为这样所得的数的个数。在2n位上填入n个1的方案数为&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image179.gif" width="36" height="48">，</p>
<p>不填1的其余n位自动填以数0。从&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image181.gif" width="36" height="48"></p>
<p>中减去不符合要求的方案数即为所求。不合要求的数指的是从左而右扫描，出现0的累计数超过1的累计数的数。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 不合要求的数的特征是从左而右扫描时，必然在某一奇数2m+1位上首先出现m+1个0的累计数，和m个1的累计数。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 此后的2（n－m）－1位上有n－m个1，n－m－1个0。如若把后面这部分2（n－m）－1位，0与1交换，使之成为n－m个0，n－m－1个1，结果得1个由n＋1个0和n－1个1组成的2n位数，即一个不合要求的数对应于一个由n－1个0和n＋1个1组成的一个排列。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 反过来，任何一个由n＋1个0，n－1个1组成的2n位数，由于0的个数多2个，2n是偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面的部分，令0和1互换，使之成为由n个0和n个1组成的2n位数。即n＋1个0和n－1个1组成的2n位数，必对应于一个不合要求的数。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 用上述方法建立了由n＋1个0和n－1个1组成的2n位数，与由n个0和n个1组成的2n位数中从左向右扫描出现0的累计数超过1的累计数的数一一对应。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 例如&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image183.gif" width="65" height="29"></p>
<p>是由4个0和4个1组成的8位2进制数。但从左而右扫描在第5位（打*号）出现0的累计数3超过1的累计数2，它对应于由3个1，5个0组成的10100010。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 反过来&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image187.gif" width="67" height="29"></p>
<p>对应于&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image189.gif" width="65" height="19">。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 因而不合要求的2n位数与n＋1个0，n－1个1组成的排列一一对应，故有&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image191.gif" width="321" height="48"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image193.gif" width="267" height="99"></p>
<p>&nbsp;&nbsp;&nbsp; 解法2.这个问题可以一一对应于图2－11－7中从原点（0，0）到（n，n）点的路径要求中途所经过的点（a，b）满足关系 
a&lt;=b&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 对应的办法是从（0，0）出发，对2n位数从左而右扫描，若遇到1便沿y轴正方向走一格；若遇到0便沿x轴正方向走一格。由于有n个0，n个1，故对应一条从（0，0）点到达（n，n）点的路径，由于要求1的累计数不少于0的累计数，故可以途经对角线OA上的点，但不允许穿越过对角线。反过来，满足这条件的路径对应一满足要求的2n位2进制数。见图&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image205.gif" width="769" height="294"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 图   2-11-8 
  
图   2-11-7&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 问题导致求从（0，0）出发，途经对角线及对角线上方的点到达（n，n）点的路径数。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 从一点到另一点的路径数的讨论见第1章§3例1。见图2－11－7，从O点出发经过OA及OA上方的点到达A点的路径对应一条从 
O'A'点出发经过O'A'及O'A'上方的点到达O'点的路径，这是显而易见的。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 从O'点出发途经A 上的点到达A'点的路径，故对应一点从O点出发穿越OA到达A'点的路径，故对应一从O 
点出发穿越OA到达 A点的路径。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 所以从O点出发经过OA 及OA以上的点最后到达A点的路径树，等于从O'点出发到达A'点的所有路径数，减去从O'点出发路径 
OA上的点到达A'点的路径数。即&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image239.gif" width="321" height="48"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image241.gif" width="267" height="99"></p>
<p>&nbsp;&nbsp;&nbsp; 例4. 由n个1，n个0组成的2n位二进制数，要求从左向右扫描前2n－1位时1的累计数大于0的累计数，求满足这样条件的数的个数。此问题可归结为图2－11－7中从O点出发只经过对角线OA上方的点抵达A点，求这样的路径数。相当于求从O'(0,1)点不经过对角线OA，抵达A'(n-1,n)点的路径数，于是便转换为例3的问题。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 根据例3的结果。从O'(0,1)点通过O'A'的点，以及O'A'上方的点到达A'(n-1,n)的路径数为</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image256.gif" width="289" height="96"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_11.pic/image258.gif" width="125" height="48"></p>