2_8.htm

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

<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image184.gif" width="96" height="112"></p>
<p>得&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image186.gif" width="67" height="133"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image188.gif" width="317" height="41"></p>
<p>&nbsp;&nbsp;&nbsp; 例10：求n位的2进制数中最后三位才第一次出现010图象的数的个数。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 即求对n位2进制数 从左而右扫描，第一次在最后三位出现010图象的数的个数。自然，最后三位除外任取连续三个都不会是010的。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 设a<sub>n</sub>表满足条件的n位数个数，和前例类似，最后三位是010的n位2进制数共2<sup>n-3</sup> 
个， 
 
对这2<sup>n-3</sup>个数分析如下。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; （a）包含了在最后三位第1次出现010图象的个数，其个数为a<sub>n</sub>，排除了在第n-4到第n-2位第1次出现010图象的可能。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; （b）包含了在第n-4到第n-2位第1次出现010图象的数，其个数为a<sub>n-2</sub></p>
<p>&nbsp;&nbsp;&nbsp;<sub>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </sub><img border="0" src="2_8.pic/image200.gif" width="529" height="55"></p>
<p>&nbsp;&nbsp;&nbsp;<sub> </sub>（c）包含了在第(n-5)位到第(n-3)位第1次出现010图象的数，其个数是a<sub>n-3</sub></p>
<p>&nbsp;&nbsp;&nbsp;<sub>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image204.gif" width="529" height="55"></sub></p>
<p>&nbsp;&nbsp;&nbsp;<sub> </sub>（d）包含了在第(n-6)位到第(n-4)位第1次出现010图象的数，其个数是2a<sub>n-4</sub> 
，因在第n-3位（打*号的格）可以取0或1两种状态。</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image209.gif" width="529" height="56"></p>
<p>&nbsp;&nbsp;&nbsp; 一般可以归纳为对k>=3，从第(n-k-2)位到第n-k位第一次出现010图象的数，其数目为2<sup>k-3</sup>a<sub>n-k</sub> 
。从第n-k位到第n-3位中间的k-3位可以取0，1两种值，故有2<sup>k-3</sup>种状态。</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image215.gif" width="541" height="58"></p>
<p>&nbsp;故得递推关系如下：&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image217.gif" width="317" height="51"></p>
<p>&nbsp;&nbsp;&nbsp; n=5时有下面几种状态：&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 00010,10010,11010</p>
<p>排除了01010，因从左而右扫描时01010属于前三位出现010图象的。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 请注意，递推关系(2-8-7)式不是常系数递推关系。</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image221.gif" width="145" height="24"></p>
<p>故n=6时有：&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image223.gif" width="256" height="25"></p>
<p>n=7时有&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image225.gif" width="320" height="25"></p>
<p>其它依此类推。 
 
令&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image227.gif" width="237" height="25"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image229.gif" width="211" height="77"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image231.gif" width="277" height="25"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image233.gif" width="275" height="51"></p>
<p>整理得&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image235.gif" width="349" height="132"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image237.gif" width="283" height="137"></p>
<p>&nbsp;&nbsp;&nbsp; 例11：解图（2-8-5）电路网络中的v<sub>j</sub>,j=0,1,2,<sup>...</sup>,n 
设其中v(t)=v&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image360.gif" width="742" height="225"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
<img border="0" src="2_8.pic/image361.gif" width="374" height="277"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
图（2－8－5）</p>
<p>

 

 
 
 

 

 

 

 

 

 

 

 

 

 



图（2－8－5）根据欧姆定律有&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image260.gif" width="113" height="51"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image262.gif" width="261" height="85"></p>
<p>由于各点的电流代数和为零，&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image264.gif" width="236" height="41"></p>
<p>（2－8－8）代入（2－8－9）得递推关系&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image266.gif" width="267" height="41">&nbsp;</p>
<p>或&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image268.gif" width="249" height="25"></p>
<p>由v<sub>0</sub>点的电流代数和为零，可得&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image272.gif" width="113" height="67"></p>
<p>特征方程是x<sup>2</sup>-4x+1=0</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image276.gif" width="71" height="24"></p>
<p>设&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image278.gif" width="193" height="27"></p>
<p>解方程组&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image280.gif" width="193" height="53"></p>
<p>得&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image282.gif" width="248" height="165"></p>
<p>&nbsp;&nbsp;&nbsp; 例12：求图2-8-6所示的n级网络的等效电阻R<sub>n</sub> 
。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 所谓等效电路，相当于图2-8-6中虚线所包围的块用一电阻R<sub>n</sub>取代，使在两端点n和&ntilde;之间的效果一样。R<sub>n</sub>可以作为由R<sub>n-1</sub>等效电阻如图（2－8－7）所示的方式串并联构成的.&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image293.gif" width="602" height="223"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
<img border="0" src="2_8.pic/image299.gif" width="184" height="233"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image301.gif" width="264" height="93"></p>
<p>得递推关系如下&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image303.gif" width="236" height="88"></p>
<p>令&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image305.gif" width="155" height="45"></p>
<p>因此&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image307.gif" width="241" height="88"></p>
<p>令&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image309.gif" width="247" height="53"></p>
<p>将&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image311.gif" width="112" height="24"></p>
<p>代入&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image313.gif" width="136" height="25"></p>
<p>得到&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image315.gif" width="245" height="76"></p>
<p>特征方程是x<sup>2</sup>-4R+R<sup>2</sup>=0&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image319.gif" width="244" height="53"></p>
<p>解方程组&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image321.gif" width="195" height="53"></p>
<p>得&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image323.gif" width="95" height="93"></p>
<p>&nbsp;&nbsp;&nbsp; 例13：设有地址从1到n的单元，用以纪录一组信息。这个信息的每个元素都占用两个单元，而且存放的地址是完全随机的，因而可能出现两个存放信息单元之间留下一个空单元无法存放其他信息，求这n各单元留下空单元的平均数。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp; 设这个平均数为a<sub>n</sub> 。&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image331.gif" width="535" height="55"></p>
<p>&nbsp;&nbsp;&nbsp; 存储单元如上图，设某一信息占用了第i+1，i+2两个单元，把这组单元分割成两个部分，一是从1到i，另一从i+3到n。由于用相邻两个单元的几率相等，&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image333.gif" width="239" height="67">&nbsp;&nbsp;</p>
<p><img border="0" src="2_8.pic/image335.gif" width="264" height="45"></p>
<p>（2-8-13）式是变系数递推关系，可改为&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image337.gif" width="213" height="48"></p>
<p>设&nbsp;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image339.gif" width="227" height="51"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image341.gif" width="161" height="99"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image343.gif" width="183" height="7"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image345.gif" width="124" height="21"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image347.gif" width="131" height="21"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image349.gif" width="151" height="41"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image351.gif" width="179" height="24"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image353.gif" width="113" height="24"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image355.gif" width="140" height="27"></p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image357.gif" width="211" height="112">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</p>
<p>一般有</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_8.pic/image359.gif" width="260" height="137"></p>