ti.htm

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

 <param name=BGColor value="">
 <param name=SWRemote value="">
 <param name=Stacking value=below>
</object><o:p></o:p></span></p>

<p><span style='font-size:10.0pt'>可看作是格路问题：左边第<span lang=EN-US>i项为从点C到点(-1,i)直接经过(0,i)的路径,再到点B的所有路径数。左边所有项的和就是从点C到B的所有路径数即为右边的意义。
<o:p></o:p></span></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>16.给出<img width=271 height=48
id="_x0000_i1041" src="1\image012.gif" align=middle>的组合意义。<br>
解：C(n+1,r+1)是指从n+1个元素a<sub>1</sub>, a<sub>2</sub>,…,a<sub>n+1</sub>中任取r+1个进行组合的方案数。<br>
左边：若一定要选a<sub>n+1</sub>,则方案数为C(n,r).若不选a<sub>n+1</sub>,一定要选a<sub>n</sub>,则方案数为C(n-1,r).若不选a<sub>n+1</sub>,a<sub>n</sub>,…a<sub>r+2</sub>,则方案数为C(r,r).
所有这些可能性相加就得到了总方案数。 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>17.证明:<img width=417 height=48
id="_x0000_i1042" src="1\image014.gif" align=middle><br>
证：组合意义,右边：m个球,从中取n个,放入两个盒子,n个球中每个球都有两种放法,得到可能的方案数。左边：第i项的意义是一个盒子中放i个,另一个盒子放n-i个,所有的方案数相加应该等于右边。<br>
<img width=217 height=261 id="_x0000_i1043" src="ans1\image026.gif"
align=middle><br>
证毕。 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>18.从n个人中选r个围成一圆圈，问有多少种不同的方案？<o:p></o:p></span></p>

<p><span style='font-size:10.0pt'>解：圆排列<span lang=EN-US>:共有P(n,r)/r种不同的方案。<o:p></o:p></span></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>19.分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法。(解略)
<o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>20.(a)按照第19题的要求，写出邻位对换法(排列的生成算法之二)的相应算法。<br>
(b)写出按照邻位对换法由给定排列生成其下一个排列的算法。(解略) <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>21.对于给定的正整数n,证明当<img width=180
height=88 id="_x0000_i1044" src="1\image016.gif" align=middle>时，C(n,k)是最大值。<br>
证：取C(n,k)和C(n,k-1)进行比较。C(n,k)/C(n,k-1)=(n-k+1)/k。<br>
当k&gt;n/2时,(n-k+1)/k&lt;1,即C(n,k)&lt;C(n,k-1)<br>
当k&gt;n/2时,(n-k+1)/k&gt;1,即C(n,k)&gt;C(n,k-1)得到当k为最接近n/2的数时，C(n,k)取到最大值。 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>22.(a)用组合方法证明<img width=36
height=40 id="_x0000_i1045" src="1\image018.gif" align=middle>和<img width=48
height=40 id="_x0000_i1046" src="1\image020.gif" align=middle>都是整数. (b)证明<img
width=48 height=51 id="_x0000_i1047" src="1\image022.gif" align=middle>是整数. <br>
证：(a)设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。对2n个球进行排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2
次。得到2n个不同球放入n个不同的盒子里，每盒两个的方案数(2n)!/2 若有3n个不同的球,放入n个不同盒子,故同理得(3n)!/(3!)是整数。<br>
(b)有n个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n<sup>2</sup>)!/(n!)<sup>n</sup>是整数。另外由于n个盒子相同，放入不同的盒子是没有区别的，应该把n个盒子的排列数n!除去。<br>
因此得到(n<sup>2</sup>)!/(n!)<sup>n+1</sup>是整数。 <span style="mso-spacerun:
yes">&nbsp;</span><o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>23.(a)在2n个球中,有n个相同,求从这2n个球中选取n个的方案数。<br>
(b)在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数.<br>
解：(a) 相当于从n个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。<br>
共有方案： C(n,0)+C(n,1)+…+C(n,n)=2<sup>n</sup>种。<br>
(b)相当于从2n+1个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。<br>
共有方案： C(2n+1,0)+C(2n+1,1)+…+C(2n+1,n) = 4<sup>n</sup>种。 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>24.证明在由字母表{0,1,2}生成的长度为n的字符串中.<br>
(a)0出现偶数次的字符串有<img width=43 height=44 id="_x0000_i1048" src="1\image024.gif"
align=middle>个； <br>
(b)<img width=256 height=48 id="_x0000_i1049" src="1\image026.gif"
align=middle>，其中<img width=64 height=44 id="_x0000_i1050" src="1\image028.gif"
align=middle>. <br>
证：(a)归纳法：当n=1时,0出现偶数次的字符串有(3<sup>1</sup>+1)/2=2个(即1,2),成立。<br>
假设当n=k时,0出现偶数次的字符串有(3<sup>k</sup>+1)/2种。总的字符串有3种。0出现奇数次的字符串有(3<sup>k</sup>-1)/2种。<br>
当n=k+1时，0出现偶数次的字符串包括两部分：<br>
n=k时,0出现偶数次再增加一位不是0的，共有2(3<sup>k</sup>+1)/2种，0出现奇数次再增加一位0,共有(3<sup>k</sup>-1)/2种。<br>
所以共有2(3<sup>k</sup>+1)/2+(3<sup>k</sup>-1)/2=(3<sup>k+1</sup>+1)/2种，证毕。<o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>(b) 等式左边第m项是0出现m次的字符串数，总和就是0出现偶数次的字符串数，右边由(a)得是0出现偶数次的字符串数，两边显然相等。
<o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>25. 5台教学机器m个学生使用，使用第1台和第2台的人数相等，有多少种分配方案？<br>
解：当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)(m-2n)<sup>3</sup>。<br>
所以总的方案数为<img width=193 height=48 id="_x0000_i1051" src="ans1\image028.gif"
align=middle><o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>26.在由n个0及n个1构成的字符串中，任意前k个字符中，0的个数不少于1的个数的字符串有多少？<br>
解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1). <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>27.在1到n的自然数中选取不同且互不相邻的k个数，有多少种选取方案？<br>
解法一：设从1~n中选取互不相邻的k个数的方案数为g(n,k),若选n，则方案数为g(n-2,k-1),若不选n则方案数为g(n-1,k)。<br>
显然，g(n,k)=g(n-2,k-1)+g(n-1,k).且只有当n≥2k-1时，g(n,k)&gt;0,否则g(n,k)=0.<br>
可给定初始值g(2k-1,k)=1,g(2k-2,k)=0。 <o:p></o:p></span></p>

<p><span style='font-size:10.0pt'>解法二：我们可以把所选数看作挡板，它们之间各有<span lang=EN-US><span
style='mso-text-raise:-6.0pt'><!--[if gte vml 1]><v:shape id="_x0000_i1105"
 type="#_x0000_t75" style='width:58.8pt;height:18pt' o:ole="">
 <v:imagedata src="./ti.files/image011.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=78 height=24
src="./ti.files/image012.gif" v:shapes="_x0000_i1105"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1105"
  DrawAspect="Content" ObjectID="_1069567295">
 </o:OLEObject>
</xml><![endif]-->个数，第一个数之前和第k个数之后各有<span style='mso-text-raise:-6.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1108" type="#_x0000_t75" style='width:37.2pt;height:18pt' o:ole="">
 <v:imagedata src="./ti.files/image013.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=49 height=24
src="./ti.files/image014.gif" v:shapes="_x0000_i1108"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1108"
  DrawAspect="Content" ObjectID="_1069567296">
 </o:OLEObject>
</xml><![endif]-->个数，那么就有<o:p></o:p></span></span></p>

<p><span lang=EN-US style='font-size:10.0pt'><span style='mso-text-raise:-6.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1113" type="#_x0000_t75" style='width:103.2pt;height:18pt' o:ole="">
 <v:imagedata src="./ti.files/image015.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=138 height=24
src="./ti.files/image016.gif" v:shapes="_x0000_i1113"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1113"
  DrawAspect="Content" ObjectID="_1069567297">
 </o:OLEObject>
</xml><![endif]-->，<span style='mso-text-raise:-6.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1117" type="#_x0000_t75" style='width:76.2pt;height:18pt' o:ole="">
 <v:imagedata src="./ti.files/image017.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=102 height=24
src="./ti.files/image018.gif" v:shapes="_x0000_i1117"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1117"
  DrawAspect="Content" ObjectID="_1069567298">
 </o:OLEObject>
</xml><![endif]-->，<span style='mso-text-raise:-6.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1122" type="#_x0000_t75" style='width:55.8pt;height:18pt' o:ole="">
 <v:imagedata src="./ti.files/image019.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=75 height=24
src="./ti.files/image020.gif" v:shapes="_x0000_i1122"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1122"
  DrawAspect="Content" ObjectID="_1069567299">
 </o:OLEObject>
</xml><![endif]--><o:p></o:p></span></p>

<p><span style='font-size:10.0pt'>做变换：<span lang=EN-US><span style='mso-text-raise:
-16.0pt'><!--[if gte vml 1]><v:shape id="_x0000_i1129" type="#_x0000_t75"
 style='width:118.8pt;height:37.8pt' o:ole="">
 <v:imagedata src="./ti.files/image021.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=159 height=51
src="./ti.files/image022.gif" v:shapes="_x0000_i1129"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1129"
  DrawAspect="Content" ObjectID="_1069567300">
 </o:OLEObject>
</xml><![endif]-->，则<span style='mso-text-raise:-6.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1134" type="#_x0000_t75" style='width:121.8pt;height:18pt' o:ole="">
 <v:imagedata src="./ti.files/image023.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=162 height=24
src="./ti.files/image024.gif" v:shapes="_x0000_i1134"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1134"
  DrawAspect="Content" ObjectID="_1069567301">
 </o:OLEObject>
</xml><![endif]-->，它的自然数解数为C(n-k+1,k)，这就是答案。<o:p></o:p></span></span></p>

<p><span style='font-size:10.0pt'>解法三：从中选出的<span lang=EN-US>k个数分别是<span
style='mso-text-raise:-6.0pt'><!--[if gte vml 1]><v:shape id="_x0000_i1138"
 type="#_x0000_t75" style='width:58.2pt;height:18pt' o:ole="">
 <v:imagedata src="./ti.files/image025.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=78 height=24
src="./ti.files/image026.gif" v:shapes="_x0000_i1138"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1138"
  DrawAspect="Content" ObjectID="_1069567302">
 </o:OLEObject>
</xml><![endif]-->，令<span style='mso-text-raise:-6.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1142" type="#_x0000_t75" style='width:69pt;height:18pt' o:ole="">
 <v:imagedata src="./ti.files/image027.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=92 height=24
src="./ti.files/image028.gif" v:shapes="_x0000_i1142"><![endif]></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1142"
  DrawAspect="Content" ObjectID="_1069567303">
 </o:OLEObject>
</xml><![endif]-->，那么这k个数是1,2,…,n-k+1中的k个，和我们要求的数列是一一对应的，<o:p></o:p></span></span></p>

<p><span style='font-size:10.0pt'>所以答案是<span lang=EN-US>C(n-k+1,k)。<o:p></o:p></span></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>28.(a)在5个0，4个1组成的字符串中，出现01或10的总次数为4的，有多少个?<br>
(b)在m个0，n个1组成的字符串中,出现01或10的总次数为k的，有多少个？<br>
解：(a)先将5个0排成一列：00000，1若插在两个0中间，“010”，则出现2个“01”或“10”;若插在两端，则出现1个“01”或“10”;要使出现“01”,“10”总次数为4，有两种办法：<br>
(1)把两个1插入0得空当内，剩下的1插入1的前面。<br>
(2)把1个1插入0得空当内，再取两个1分别插入两端，剩下的1插入1的前面。<br>
故总方案数为C(4,2)·2+C(4,1)·3=36. <br>
(b)m个0产生m-1个空当，<br>
若k为奇数,则必有且只有1个“1”插入头或尾,总方案数为<img width=191 height=45 id="_x0000_i1052"
src="ans1\image030.gif" align=middle><br>
若k为偶数,总方案数为<img width=311 height=44 id="_x0000_i1053" src="ans1\image032.gif"
align=middle><o:p></o:p></span></p>

</div>

</body>

</html>