ti.htm

随着各行各业的发展和生产需要

  (b)Bose-Einstein假定：r个质点完全相同，每一个盒子可以放任意数个. <br>
  (c)Fermi-Dirac假定：r个质点都完全相同，每盒不超过一个.<br>
  解：(a) 每个质点放入盒子都有n种选择，r个质点共有r<sup>n</sup>种不同的图案。<br>
  (b) 可重组合，共有C(n+r-1,r)种图案。<br>
  (c) 一般组合问题，共有C(n,r)种图案。 </p>
<p>14.从26个英文字母中取出6个字母组成一字，若其中有2或3个母音，问分别可构成多少个字(不允许重复)？<br>
  解：其中有2个母音可构成C(21,4)C(5,2)6!个字。 其中有3个母音可构成C(21,3)C(5,3)6!个字。 </p>
<p>15.给出<img width=493 height=48
src="./1/image010.gif" align="middle">的组合意义.<br>
  解：如图：</p>
<p><object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0" width="300" height="200">
    <param name=movie value="ans1/1.swf">
    <param name=quality value=high>
    <embed src="ans1/1.swf" quality=high pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" type="application/x-shockwave-flash" width="300" height="200">
    </embed> 
  </object></p>
<p>可看作是格路问题：左边第i项为从点C到点(-1,i)直接经过(0,i)的路径,再到点B的所有路径数。左边所有项的和就是从点C到B的所有路径数即为右边的意义。 
</p>
<p>16.给出<img width=271 height=48
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). 
  所有这些可能性相加就得到了总方案数。 </p>
<p>17.证明:<img width=417 height=48
src="./1/image014.gif" align="middle"><br>
  证：组合意义,右边：m个球,从中取n个,放入两个盒子,n个球中每个球都有两种放法,得到可能的方案数。左边：第i项的意义是一个盒子中放i个,另一个盒子放n-i个,所有的方案数相加应该等于右边。<br><img width=217 height=261
src="./ans1/image026.gif" align="middle"><br>证毕。 
</p>
<p>18.从n个人中选r个围成一圆圈，问有多少种不同的方案？</p>
<p>解：圆排列:共有P(n,r)/r种不同的方案。<br>
</p>
<p>19.分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法。(解略) <br>
</p>
<p>20.(a)按照第19题的要求，写出邻位对换法(排列的生成算法之二)的相应算法。<br>
  (b)写出按照邻位对换法由给定排列生成其下一个排列的算法。(解略) <br>
</p>
<p>21.对于给定的正整数n,证明当<img width=180 height=88
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>n/2时,(n-k+1)/k<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)取到最大值。 </p>
<p>22.(a)用组合方法证明<img width=36 height=41
src="./1/image018.gif" align="middle">和<img width=48 height=41
src="./1/image020.gif" align="middle">都是整数. (b)证明<img width=49 height=51
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>是整数。 </p>
<p>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)种。 
</p>
<p>24.证明在由字母表{0,1,2}生成的长度为n的字符串中.<br>
  (a)0出现偶数次的字符串有<img width=43 height=44
src="./1/image024.gif" align="middle">个； <br>
  (b)<img width=256 height=48
src="./1/image026.gif" align="middle">，其中<img width=64 height=45
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种，证毕。<br>
  (b) 等式左边第m项是0出现m次的字符串数，总和就是0出现偶数次的字符串数，右边由(a)得是0出现偶数次的字符串数，两边显然相等。 </p>
<p>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=47
src="./ans1/image028.gif" align="middle"></p>
<p>26.在由n个0及n个1构成的字符串中，任意前k个字符中，0的个数不少于1的个数的字符串有多少？<br>
  解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1). </p>
<p>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)>0,否则g(n,k)=0.<br>
  可给定初始值g(2k-1,k)=1,g(2k-2,k)=0。 </p>
<p>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
src="./ans1/image030.gif" align="middle"><br>
  若k为偶数,总方案数为<img width=311 height=45
src="./ans1/image032.gif" align="middle"></p>
</body>
</html>