timu.htm

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

 id="_x0000_i1460" type="#_x0000_t75" style='width:19.2pt;height:31.2pt' o:ole="">
 <v:imagedata src="./timu.files/image017.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=26 height=42
src="./timu.files/image018.gif" v:shapes="_x0000_i1460"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1460"
  DrawAspect="Content" ObjectID="_1069585688">
 </o:OLEObject>
</xml><![endif]-->x<sup>10</sup>系数即为所求。或是用枚举，</span><span lang=EN-US
style='font-family:Wingdings;mso-ascii-font-family:宋体;mso-hansi-font-family:
宋体;mso-char-type:symbol;mso-symbol-font-family:Wingdings'><span
style='mso-char-type:symbol;mso-symbol-font-family:Wingdings'>J</span></span><span
lang=EN-US>.<span style="mso-spacerun: yes">&nbsp; </span>答案是678。</span></p>

<p><span lang=EN-US>4.求由A,B,C,D组成的允许重复的排列中 AB至少出现一次的排列数目。&nbsp;</span></p>

<p>解：<span lang=EN-US>A、B、C、D组成的全排列数为 p=n<sup>4</sup> , 不出现AB的字符串的排列数为&nbsp;a<sub>n
</sub>, AB至少出现一次的排列数目是b<sub>n </sub>,</span></p>

<p>那么<span lang=EN-US>a<sub>n </sub>+ b<sub>n</sub> = n<sup>4</sup>. a<sub>n</sub>递推关系为：&nbsp;a<sub>n+2
</sub>= 4a<sub>n+1</sub>-a<sub>n</sub> ,初值：&nbsp;a<sub>1</sub> = 4 , a<sub>2</sub>
= 15。所以<span style='mso-text-raise:-14.0pt'><!--[if gte vml 1]><v:shape id="_x0000_i1285"
 type="#_x0000_t75" style='width:145.8pt;height:37.8pt' o:ole="">
 <v:imagedata src="./timu.files/image019.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=194 height=51
src="./timu.files/image020.gif" v:shapes="_x0000_i1285"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1285"
  DrawAspect="Content" ObjectID="_1069585689">
 </o:OLEObject>
</xml><![endif]-->，</span></p>

<p>故答案是<span lang=EN-US>b<sub>n </sub><span style="mso-spacerun:
yes">&nbsp;</span>= 4<sup>n</sup> - a<sub>n </sub><span style="mso-spacerun:
yes">&nbsp;</span>， 即：<span style='mso-text-raise:-14.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1289" type="#_x0000_t75" style='width:145.8pt;height:37.8pt'
 o:ole="">
 <v:imagedata src="./timu.files/image021.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=194 height=50
src="./timu.files/image022.gif" v:shapes="_x0000_i1289"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1289"
  DrawAspect="Content" ObjectID="_1069585690">
 </o:OLEObject>
</xml><![endif]-->。</span></p>

<p><span lang=EN-US>5.求n位四进制数中2和3必须出现偶次的 数目。&nbsp;</span></p>

<p>解：假设<span lang=EN-US>2出现k次，3出现了m次，那么有<span style='mso-text-raise:-15.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1300" type="#_x0000_t75" style='width:106.8pt;height:36pt' o:ole="">
 <v:imagedata src="./timu.files/image023.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=142 height=48
src="./timu.files/image024.gif" v:shapes="_x0000_i1300"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1300"
  DrawAspect="Content" ObjectID="_1069585691">
 </o:OLEObject>
</xml><![endif]--> 中方案，</span></p>

<p>所以最后的答案就是<span lang=EN-US><span style='mso-text-raise:-15.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1317" type="#_x0000_t75" style='width:615pt;height:36pt' o:ole="">
 <v:imagedata src="./timu.files/image025.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=820 height=48
src="./timu.files/image026.gif" v:shapes="_x0000_i1317"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1317"
  DrawAspect="Content" ObjectID="_1069585692">
 </o:OLEObject>
</xml><![endif]--></span></p>

<p><span lang=EN-US>6.试求由a,b,c三个文字组成的n位符号串 中不出现aa图像的符号串的数目。&nbsp;</span></p>

<p>解法一：设不出现<span lang=EN-US>aa的字符串中以a结尾的有a<sub>n</sub> 个，不以a结尾的有b<sub>n</sub>个，那么题目要求的是c<sub>n</sub>=a<sub>n</sub>+b<sub>n</sub>
.</span></p>

<p>显然我们有<span lang=EN-US> a<sub>n+1 </sub>= b<sub>n</sub> , b<sub>n+1 </sub>= 2c<sub>n</sub>
,所以c<sub>n+2 </sub>= 2c<sub>n+1</sub>+2c<sub>n</sub></span></p>

<p>最后可以得到：<span lang=EN-US>c<sub>n </sub>= <span style='mso-text-raise:-12.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1345" type="#_x0000_t75" style='width:201pt;height:34.2pt' o:ole="">
 <v:imagedata src="./timu.files/image027.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=268 height=46
src="./timu.files/image028.gif" v:shapes="_x0000_i1345"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1345"
  DrawAspect="Content" ObjectID="_1069585693">
 </o:OLEObject>
</xml><![endif]--></span></p>

<p>解法二：设<span lang=EN-US>a出现了k次，那么所有的a不能相邻。在1…n中去k个不相邻的数有C(n-k+1,k)中取法（参见第一章-习题27）</span></p>

<p>那么我们最后的答案就是<span lang=EN-US><span style='mso-text-raise:-15.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1324" type="#_x0000_t75" style='width:90pt;height:46.2pt' o:ole="">
 <v:imagedata src="./timu.files/image029.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=120 height=62
src="./timu.files/image030.gif" v:shapes="_x0000_i1324"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1324"
  DrawAspect="Content" ObjectID="_1069585694">
 </o:OLEObject>
</xml><![endif]-->。</span></p>

<p>注： 比较解法一、二中的答案我们知道：<span lang=EN-US><span style='mso-text-raise:-15.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1351" type="#_x0000_t75" style='width:90pt;height:46.2pt' o:ole="">
 <v:imagedata src="./timu.files/image029.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=120 height=62
src="./timu.files/image031.gif" v:shapes="_x0000_i1351"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1351"
  DrawAspect="Content" ObjectID="_1069585695">
 </o:OLEObject>
</xml><![endif]--> = <span style='mso-text-raise:-12.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1350" type="#_x0000_t75" style='width:201pt;height:34.2pt' o:ole="">
 <v:imagedata src="./timu.files/image027.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=268 height=46
src="./timu.files/image032.gif" v:shapes="_x0000_i1350"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1350"
  DrawAspect="Content" ObjectID="_1069585696">
 </o:OLEObject>
</xml><![endif]--></span></p>

<p style='text-indent:36.0pt;mso-char-indent-count:3.0;mso-char-indent-size:
12.0pt'>怎么直接证明这个恒等式？可以思考一下。</p>

<p><span lang=EN-US>7.证明序列&nbsp; C(n,n),C(n+1,n),C(n+2,n),<sup>... </sup>的母函数为&nbsp;<span
style='mso-text-raise:-5.0pt'><!--[if gte vml 1]><v:shape id="_x0000_i1358"
 type="#_x0000_t75" style='width:55.8pt;height:19.2pt' o:ole="">
 <v:imagedata src="./timu.files/image033.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=74 height=26
src="./timu.files/image034.gif" v:shapes="_x0000_i1358"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1358"
  DrawAspect="Content" ObjectID="_1069585697">
 </o:OLEObject>
</xml><![endif]--></span></p>

<p>证明：（利用归纳法）</p>

<p>当<span lang=EN-US>n = 0,1的时候是显然的。</span></p>

<p>假设对<span lang=EN-US>n = k成立，那么当n = k + 1 时，我们有</span></p>

<p style='text-indent:21.0pt'><span lang=EN-US><span style='mso-text-raise:
-15.0pt'><!--[if gte vml 1]><v:shape id="_x0000_i1372" type="#_x0000_t75"
 style='width:262.8pt;height:36pt' o:ole="">
 <v:imagedata src="./timu.files/image035.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=350 height=48
src="./timu.files/image036.gif" v:shapes="_x0000_i1372"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1372"
  DrawAspect="Content" ObjectID="_1069585698">
 </o:OLEObject>
</xml><![endif]--></span></p>

<p style='text-indent:21.0pt'>计算右边<span lang=EN-US><span style='mso-text-raise:
-3.0pt'><!--[if gte vml 1]><v:shape id="_x0000_i1380" type="#_x0000_t75"
 style='width:16.8pt;height:16.2pt' o:ole="">
 <v:imagedata src="./timu.files/image037.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=22 height=21
src="./timu.files/image038.gif" v:shapes="_x0000_i1380"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1380"
  DrawAspect="Content" ObjectID="_1069585699">
 </o:OLEObject>
</xml><![endif]-->的系数为<span style='mso-text-raise:-15.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1379" type="#_x0000_t75" style='width:58.2pt;height:36pt' o:ole="">
 <v:imagedata src="./timu.files/image039.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=78 height=48
src="./timu.files/image040.gif" v:shapes="_x0000_i1379"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1379"
  DrawAspect="Content" ObjectID="_1069585700">
 </o:OLEObject>
</xml><![endif]-->，故得证。</span></p>

<p><span lang=EN-US>8.证明&nbsp;C(n,n)+C(n+1,n)+…+C(n+m,n) = C(n+m+1,n+1)</span></p>

<p>证明： 等式的右端相当于从<span lang=EN-US>n+m+1个球中取n+1个球的组合。 把这n+m+1个球编号:</span></p>

<p>如果取出的<span lang=EN-US>n+1个球中最小编号是1，则得到 C(n+m,n);</span></p>

<p>如果最小编号是<span lang=EN-US>2则得到C(n+m-1,n)；</span></p>

<p><span lang=EN-US>……</span></p>

<p>如果最小编号是<span lang=EN-US>m则得到C(n,n)。&nbsp;</span></p>

<p>于是就有<span lang=EN-US>C(n,n)+C(n+1,n)+…+C(n+m,n) = C(n+m+1,n+1)</span></p>

<p><span lang=EN-US>9.利用&nbsp;<span style='mso-text-raise:-14.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1394" type="#_x0000_t75" style='width:61.2pt;height:34.8pt' o:ole="">
 <v:imagedata src="./timu.files/image041.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=82 height=46
src="./timu.files/image042.gif" v:shapes="_x0000_i1394"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1394"
  DrawAspect="Content" ObjectID="_1069585701">
 </o:OLEObject>
</xml><![endif]-->，改善 §4(2) 的p<sub>n</sub>估计式。&nbsp;</span></p>

<p>解：由于<span lang=EN-US><span style='mso-text-raise:-12.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1399" type="#_x0000_t75" style='width:91.8pt;height:33pt' o:ole="">
 <v:imagedata src="./timu.files/image043.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=122 height=44
src="./timu.files/image044.gif" v:shapes="_x0000_i1399"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1399"
  DrawAspect="Content" ObjectID="_1069585703">
 </o:OLEObject>
</xml><![endif]-->，知道<span style='mso-text-raise:-12.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1413" type="#_x0000_t75" style='width:225pt;height:33pt' o:ole="">
 <v:imagedata src="./timu.files/image045.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=300 height=44
src="./timu.files/image046.gif" v:shapes="_x0000_i1413"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1413"
  DrawAspect="Content" ObjectID="_1069585704">
 </o:OLEObject>
</xml><![endif]-->，<span style='mso-text-raise:-5.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1412" type="#_x0000_t75" style='width:49.8pt;height:16.2pt' o:ole="">
 <v:imagedata src="./timu.files/image047.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=66 height=21
src="./timu.files/image048.gif" v:shapes="_x0000_i1412"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1412"
  DrawAspect="Content" ObjectID="_1069585705">
 </o:OLEObject>
</xml><![endif]--></span></p>

<p>所以<span lang=EN-US><span style='mso-text-raise:-13.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1425" type="#_x0000_t75" style='width:178.8pt;height:36pt' o:ole="">
 <v:imagedata src="./timu.files/image049.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=238 height=48
src="./timu.files/image050.gif" v:shapes="_x0000_i1425"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1425"
  DrawAspect="Content" ObjectID="_1069585706">
 </o:OLEObject>
</xml><![endif]-->，所以<span style='mso-text-raise:-6.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1426" type="#_x0000_t75" style='width:52.8pt;height:30pt' o:ole="">
 <v:imagedata src="./timu.files/image051.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=71 height=40
src="./timu.files/image052.gif" v:shapes="_x0000_i1426"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1426"
  DrawAspect="Content" ObjectID="_1069585707">
 </o:OLEObject>
</xml><![endif]--></span></p>

<p><span lang=EN-US>10. 8台计算机分给3个单位，第1单位的分配量不超过3台，第2单位的分配量不超过4台，第3个单位不超过5台，问共有几种分配方案？&nbsp;</span></p>

<p>解：利用母函数<span lang=EN-US><span style='mso-text-raise:-5.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1454" type="#_x0000_t75" style='width:319.2pt;height:18pt' o:ole="">
 <v:imagedata src="./timu.files/image053.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=426 height=24
src="./timu.files/image054.gif" v:shapes="_x0000_i1454"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1454"
  DrawAspect="Content" ObjectID="_1069585708">
 </o:OLEObject>
</xml><![endif]-->　，项x<sup>8</sup>的系数即为答案。</span></p>

<p><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>答案是14。</span></p>