📄 2_8.htm
字号:
<head><title>组合数学</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><h1>§2.8 母函数和递推关系应用举例 </h1><p> 例1：下图是一逻辑回路，符号D是一延迟装置，即在时间t输入一个信号给延迟装置D，在t+1时刻D将输出同样的信号，符号<span style="font-size:10.5pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-bidi-font-family:"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">⊕</span>表示加法装置 </p><p> <img border="0" src="2_8.pic/image005.gif" width="772" height="226"></p><p> 若在t=0，1，2，3，…时刻，输入信号u<sub>0</sub>,u<sub>1</sub>,<sup>...</sup>求相同时刻的输出信号v<sub>0</sub>,v<sub>1</sub>,<sup>...</sup>。 显然，v<sub>0=</sub>u<sub>0</sub>,v<sub>1=</sub>u<sub>1</sub>+u<sub>0</sub>,<sup>...</sup> </p><p> 一般的有v<sub>n=</sub>u<sub>n</sub>+u<sub>n-1</sub>+u<sub>n-3</sub>, n>=3</p><p> 若信号输入的序列u<sub>0</sub>,u<sub>1</sub>,<sup>...</sup>的母函数为U(x)，输出的信号序列v<sub>0</sub>,v<sub>1</sub>,<sup>...</sup>的母函数为V(x)，则</p><p> <img border="0" src="2_8.pic/image021.gif" width="229" height="24"></p><p>其中P(x)=1+x+x<sup>3</sup> 被装置（图 2-8-1）的特性所确定，可以看作是该装置的传递函数，如图2-8-2 </p><p> <img border="0" src="2_8.pic/image027.gif" width="443" height="41"></p><p> 例2：由红球两个，白球、黄球各一个，试求有多少种不同的组合方案。 </p><p> 设r，w，y分别代表红球，白球，黄球。 </p><p> <img border="0" src="2_8.pic/image029.gif" width="236" height="101"></p><p>由此可见，出一个球也不取的情况外，有： </p><p> （a）取一个球的组合数为三，即分别取红，白，黄，三种。 </p><p> （b）取两个球的组合数为四，即两个红的，一红一黄，一红一白，一白一黄。 </p><p> （c）取三个球的组合数为三，即两红一黄，两红一白，一红一黄一白。 </p><p> （d）取四个球的组合数为一，即两红一黄一白。 </p><p> 令取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>的母函数为 </p><p> <img border="0" src="2_8.pic/image035.gif" width="187" height="48"></p><p>共有1+3+4+3+1=12种组合方式。 </p><p> 例3：n个完全一样的球放到m个有标志的盒子中，不允许有空盒，问共有多少种不同的方案？其中n>=m。 </p><p> 由于不允许有空盒，令n个球放到m个有标志的盒子的方案数为a<sub>n</sub>，序列{a<sub>n</sub>}对应的母函数为G(x)。则 </p><p> <img border="0" src="2_8.pic/image041.gif" width="300" height="72"></p><p>因 </p><p> <img border="0" src="2_8.pic/image043.gif" width="227" height="85"></p><p>故二项式(1-x)-<sup>m</sup> 中x<sup>n-m</sup> 项系数为 </p><p> <img border="0" src="2_8.pic/image049.gif" width="297" height="47"></p><p>即 </p><p> <img border="0" src="2_8.pic/image051.gif" width="263" height="45"></p><p> 例4：某单位有8个男同志，5个女同志，现要组织一个有数目为偶数的男同志和数目不少于2的女同志组成的小组，试求有多少种组成方式。 </p><p> 令a<sub>n</sub>为从8位男同志中抽取出n个的允许组合数。由于要男同志的数目必须是偶数，故 </p><p> <img border="0" src="2_8.pic/image054.gif" width="287" height="24"><img border="0" src="2_8.pic/image056.gif" width="259" height="24"> 。 </p><p>故数列a<sub>0</sub>,a<sub>1</sub>,<sup>...</sup>,a<sub>8</sub>对应一母函数 </p><p> <img border="0" src="2_8.pic/image060.gif" width="220" height="24"></p><p> 类似的方法可得女同志的允许组合数对应的母函数位 </p><p> <img border="0" src="2_8.pic/image062.gif" width="189" height="24"></p><p> <img border="0" src="2_8.pic/image064.gif" width="281" height="149"></p><p>C(x)中x<sup>k</sup> 项的系数c<sub>k</sub> 为符合要求的k个人组成的小组的数目，总的组成方式数目为 </p><p> <img border="0" src="2_8.pic/image070.gif" width="236" height="43"></p><p> 例5：10个数字（0到9）和4个四则运算符(+,-,×,÷) 组成的14个元素。求由其中的n个元素的排列构成一算术表达式的个数。 </p><p> 因所求的n个元素的排列是算术表达式，故从左向右的最后一个符号必然是数字。而第n-1位有两种可能，一是数字，一是运算符。如若第n-1位是十个数字之一，则前n-1位必然构成一算术表达式。 </p><p> 如若不然，即第n-1位是4个运算符之一，则前n-2位必然是算术表达式。根据以上分析，令a<sub>n</sub> 表n个元素排列成算术表达式的个数。则 </p><p> <img border="0" src="2_8.pic/image075.gif" width="233" height="48"></p><p>a<sub>2</sub>=120指的是从0到99的100个数，以及<span style="font-size:10.5pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-bidi-font-family:"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">±0,</span><span style="font-size:10.5pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-bidi-font-family:"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">±1,<sup>...</sup>,</span><span style="font-size:10.5pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-bidi-font-family:"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">±9,</span></p><p> <span style="font-size: 10.5pt; mso-bidi-font-size: 12.0pt; font-family: 宋体; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"> </span>利用递推关系(2-8-1)，得a<sub>0</sub>=1/2</p><p> 特征多项式x<sup>2</sup>-10x-40 。它的根是 </p><p> <img border="0" src="2_8.pic/image087.gif" width="211" height="53"></p><p>解方程 </p><p> <img border="0" src="2_8.pic/image089.gif" width="203" height="72"></p><p>得 </p><p> <img border="0" src="2_8.pic/image091.gif" width="164" height="56"></p><p> <img border="0" src="2_8.pic/image094.gif" width="237" height="72"></p><p> 例6：设有n条封闭的曲线，两两相交于两点， 任意三条封闭曲线不相交于一点。求这样的n条曲 线把平面分割成几个部分？ </p><p> <img border="0" src="2_8.pic/image092.gif" width="179" height="272"></p><p> 设满足条件的n条封闭曲线所分割成的域的数目为a<sub>n</sub> ，其中n-1条封闭曲线所分割成的域的数目为a<sub>n-1</sub>第n条封闭曲线和这些曲线相交于2(n-1)个点，这2(n-1)个点把第n条封闭曲线截成2(n-1)条弧，每条弧把2(n-1)个域中的每个域一分为二。故新增加的域数为2(n-1) </p><p> <img border="0" src="2_8.pic/image099.gif" width="248" height="24"></p><p> 利用递推关系(2-8-2得a<sub>0</sub>=2 设 </p><p> <img border="0" src="2_8.pic/image103.gif" width="172" height="173"></p><p> 另解：利用欧拉公式：点数+域数-边数=2 </p><p>点数= </p><p> <img border="0" src="2_8.pic/image105.gif" width="36" height="48"></p><p>边数=2×点数 </p><p> 域数= </p><p> <img border="0" src="2_8.pic/image115.gif" width="176" height="48"> </p><p> 例7：平面上有一点P，它是n个域D<sub>1</sub>,D<sub>2</sub>,<sup>...</sup>,D<sub>n</sub> 的共同交界点，见图2-8-4现 取k种颜色对这n个域进行着色， 要求相邻两个域着的颜色不同。 试求着色的方案数。 </p><p> <img border="0" src="2_8.pic/image113.gif" width="226" height="334"></p><p> 令a<sub>n</sub> 表示这n个域的着色 方案数。无非有两种情况 </p><p> （1）D<sub>1</sub>和D<sub>n-1</sub>有相同的颜色；</p><p> （2）D<sub>1</sub> 和D<sub>n-1</sub>所着颜色不同。</p><p> 第一种情形，域有k-1种颜色可用，即D<sub>1</sub>D<sub>n-1</sub>域所用颜色除外；而且从D<sub>1</sub>到D<sub>n-2</sub>的着色方案，和n-2个域的着色方案一一对应。后一种D<sub>n</sub>域有k-2种颜色可供使用；而且从D<sub>1</sub> 到D<sub>n-1</sub>的每一个着色方案和n-1个域的着色方案一一对应。 </p><p> <img border="0" src="2_8.pic/image137.gif" width="272" height="48"></p><p>利用(2-8-3)得a<sub>1</sub>=0,a<sub>0</sub>=k ，(2-8-3)的特征方程为 </p><p> <img border="0" src="2_8.pic/image141.gif" width="164" height="75"></p><p> 例8：求下列行列式（n行n列） </p><p> <img border="0" src="2_8.pic/image143.gif" width="217" height="123"></p><p> 利用行列式展开法，沿第一行展开得 </p><p> <img border="0" src="2_8.pic/image145.gif" width="288" height="24"></p><p>利用(2-8-5)式得d<sub>0</sub>=1</p><p>特征方程是x<sup>2</sup>-x+1=0</p><p>解方程，得 </p><p> <img border="0" src="2_8.pic/image151.gif" width="119" height="45"></p><p> 设 </p><p> <img border="0" src="2_8.pic/image153.gif" width="172" height="41"></p><p>解方程 </p><p> <img border="0" src="2_8.pic/image155.gif" width="192" height="91"></p><p>得 </p><p> <img border="0" src="2_8.pic/image157.gif" width="267" height="117"></p><p> 例9：求n位2进制最后三位出现010图象的数的个数。 </p><p> 对于n位2进制数b<sub>1</sub>,b<sub>2</sub>,<sup>...</sup>,b<sub>n</sub>从左而右进行扫描，一当出现010图象，便从这图象后面一位从头开始扫描，例如对11位2进制数00101001010从左而右的扫描结果应该是2-4，7-9位出现010图象，即 </p><p> <img border="0" src="2_8.pic/image161.gif" width="89" height="23"></p><p>而不是4-6，7-9位出现的010图象，即不是 </p><p> <img border="0" src="2_8.pic/image163.gif" width="91" height="23"></p><p>为了区别于前者起见，我们说4-6，9-11位是010，但不是“出现010图象”，这作为约定。 </p><p> 为了找出关于数列a<sub>n</sub>的第推关系，需对满足条件的数的结构进行分析。由于n位中除了最后三位是010已确定，其余n-3位可取0或1： </p><p> <img border="0" src="2_8.pic/image167.gif" width="610" height="63"></p><p> 故最后3位是010的n位2进制数的个数是2<sup>n-3</sup>。其中包含最后3位出现010图象的以及在n-4位到第n-2位出现010图象，而在最后3位并不出现010图象的两类数，后一种数为xx<sup>...</sup>x01010,故有 </p><p> <img border="0" src="2_8.pic/image176.gif" width="155" height="51"></p><p>利用(2-9-6)推得a<sub>2</sub>=0,a<sub>1</sub>=0,a<sub>0</sub>=1/2 </p><p>特征方程为 </p><p> <img border="0" src="2_8.pic/image180.gif" width="123" height="64"></p><p>设 </p><p> <img border="0" src="2_8.pic/image182.gif" width="248" height="41"></p><p>解方程组 </p>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -