ti.htm

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

src="ans1\image002.gif" align=middle>，其中a<sub>k</sub>≤k-1,<img width=105
height=45 id="_x0000_i1027" src="ans1\image004.gif" align=middle>，命题成立。<br>
再证表示的唯一性： <br>
设<img width=143 height=45 id="_x0000_i1028" src="ans1\image006.gif"
align=middle>, 不妨设a<sub>j</sub>＞b<sub>j</sub>,令j=max{i|a<sub>i</sub>≠b<sub>i</sub>}<br>
a<sub>j</sub>·j!+a<sub>j-1</sub>·(j-1)!+…+a<sub>1</sub>·1! =b<sub>j</sub>·j!+b<sub>j-1</sub>·(j-1)!+…+b<sub>1</sub>·1!,
<br>
<img width=452 height=27 id="_x0000_i1029" src="ans1\image010.gif"
align=middle><br>
另一种证法：令j=max{i|a<sub>i</sub>≠b<sub>i</sub>}<br>
<img width=117 height=37 id="_x0000_i1030" src="ans1\image012.gif"
align=middle>, 两边被(j+1)!除,得余数a<sub>j</sub>·j!=b<sub>j</sub>·j!,矛盾. <o:p></o:p></span></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>2.证 nC(n-1,r)=(r+1)C(n,r+1).并给出组合意义。<br>
证：<img width=184 height=163 id="_x0000_i1031" src="ans1\image014.gif"
align=top><br>
组合意义：<br>
等式左边：n个不同的球，先任取出1个，再从余下的n-1个中取r个；<br>
等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。<br>
显然两种方案数相同。 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>3.证<img width=132 height=45
id="_x0000_i1032" src="1\image004.gif" align=middle>。<br>
证法一：设有n个不同的小球，A、B两个盒子,A盒中恰好放1个球,B盒中可放任意个球。有两种方法放球：<br>
①先从n个球中取k个球(k≥1),再从中挑一个放入A盒,方案数共为<sub><img width=76 height=44 id="_x0000_i1033"
src="ans1\image016.gif" u1:shapes="_x0000_i1101" align=middle></sub>,其余球放入B盒。<br>
②先从n个球中任取一球放入A盒，剩下n-1个球每个有两种可能，要么放入B盒，要么不放，故方案数为n2<sup>n-1</sup> . <br>
显然两种方法方案数应该一样。 <o:p></o:p></span></p>

<p><span style='font-size:10.0pt'>证法二：运用二项式定理<span lang=EN-US><sub><!--[if gte vml 1]><v:shapetype
 id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t"
 path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f">
 <v:stroke joinstyle="miter"/>
 <v:formulas>
  <v:f eqn="if lineDrawn pixelLineWidth 0"/>
  <v:f eqn="sum @0 1 0"/>
  <v:f eqn="sum 0 0 @1"/>
  <v:f eqn="prod @2 1 2"/>
  <v:f eqn="prod @3 21600 pixelWidth"/>
  <v:f eqn="prod @3 21600 pixelHeight"/>
  <v:f eqn="sum @0 0 1"/>
  <v:f eqn="prod @6 1 2"/>
  <v:f eqn="prod @7 21600 pixelWidth"/>
  <v:f eqn="sum @8 21600 0"/>
  <v:f eqn="prod @7 21600 pixelHeight"/>
  <v:f eqn="sum @10 21600 0"/>
 </v:formulas>
 <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
 <o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_i1054" type="#_x0000_t75" style='width:115.2pt;
 height:34.2pt' o:ole="">
 <v:imagedata src="./ti.files/image001.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=153 height=45
src="./ti.files/image002.gif" v:shapes="_x0000_i1054"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1054"
  DrawAspect="Content" ObjectID="_1069567289">
 </o:OLEObject>
</xml><![endif]-->.<o:p></o:p></span></span></p>

<p><span style='font-size:10.0pt'>我们在两边对<span lang=EN-US>x求导，得到<sub><!--[if gte vml 1]><v:shape
 id="_x0000_i1055" type="#_x0000_t75" style='width:141pt;height:34.2pt' o:ole="">
 <v:imagedata src="./ti.files/image003.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=188 height=45
src="./ti.files/image004.gif" v:shapes="_x0000_i1055"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1055"
  DrawAspect="Content" ObjectID="_1069567290">
 </o:OLEObject>
</xml><![endif]-->，令x=1,就可以得到答案。<o:p></o:p></span></span></p>

<p><span style='font-size:10.0pt'>注：证法一采用组合意义证明，关键在于巧妙的构造组合模型，技巧较高。证法二采用的方法具有一般性，<span
lang=EN-US><o:p></o:p></span></span></p>

<p><span style='font-size:10.0pt'>适用范围较广，可以和第二章的母函数法比较。<span lang=EN-US><o:p></o:p></span></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>4.有n个不同的整数，从中取出两组来，要求第一组数里的最小数大于第二组的最大数。问有多少种方案？<br>
解法一：设取的第一组数有a个,第二组有b个,而要求第一组数中最小数大于第二组中最大的，即只要取出一组m个数(设m=a+b),从大到小取a个作为第一组,剩余的为第二组。此时方案数为C(n,m)。从m个数中取第一组数共有m-1中取法。<br>
总的方案数为<sub><span style='mso-text-raise:-14.0pt'><!--[if gte vml 1]><v:shape
 id="_x0000_i1097" type="#_x0000_t75" style='width:169.2pt;height:34.2pt'
 o:ole="">
 <v:imagedata src="./ti.files/image005.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=225 height=46
src="./ti.files/image006.gif" v:shapes="_x0000_i1097"><![endif]></span></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1097"
  DrawAspect="Content" ObjectID="_1069567291">
 </o:OLEObject>
</xml><![endif]-->. <o:p></o:p></span></p>

<p><span style='font-size:10.0pt'>解法二：我们假设第一组的数中最大的在所有<span lang=EN-US>n个数中是第k个。那么这样的选法可以看作是前k-1个数中选出一个非空子集，在后n-k中也选取一个非空子集，这样的选法有<sub><!--[if gte vml 1]><v:shape
 id="_x0000_i1060" type="#_x0000_t75" style='width:130.2pt;height:18pt' o:ole="">
 <v:imagedata src="./ti.files/image007.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=174 height=24
src="./ti.files/image008.gif" v:shapes="_x0000_i1060"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1060"
  DrawAspect="Content" ObjectID="_1069567292">
 </o:OLEObject>
</xml><![endif]--> 个。<o:p></o:p></span></span></p>

<p><span style='font-size:10.0pt'>故所有的方案数为<span lang=EN-US><span
style="mso-spacerun: yes">&nbsp; </span><sub><!--[if gte vml 1]><v:shape id="_x0000_i1067"
 type="#_x0000_t75" style='width:158.4pt;height:34.2pt' o:ole="">
 <v:imagedata src="./ti.files/image009.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=211 height=46
src="./ti.files/image010.gif" v:shapes="_x0000_i1067"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1067"
  DrawAspect="Content" ObjectID="_1069567293">
 </o:OLEObject>
</xml><![endif]-->.<o:p></o:p></span></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>5.六个引擎分列两排，要求引擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。<br>
解：第1步从特定引擎对面的3个中取1个有C(3,1)种取法，第2步从特定引擎一边的2个中取1个有C(2,1)种取法，第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。所以共有C(3,1)·C(2,1)·C(2,1)=12种方案。
<o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>6.试求从1到1000000的整数中，0出现了多少次？<br>
解：首先所有数都用6位表示，从000000到999999中在每位上0出现了10<sup>5</sup>次,所以0共出现了6·10<sup>5</sup>次,0出现在最前面的次数应该从中去掉，<br>
000000到999999中最左1位的0出现了10<sup>5</sup>次，<br>
000000到099999中左数第2位的0出现了10<sup>4</sup>次，<br>
000000到009999左数第3位的0出现了10<sup>3</sup>次, <br>
000000到000999左数第4位的0出现了10<sup>2</sup>次, <br>
000000到000099左数第5位的0出现了10<sup>1</sup>次, <br>
000000到000009左数第6位的0出现了10<sup>0</sup>次。<br>
另外1000000的6个0应该被加上。 <br>
所以0共出现了 6·10<sup>5</sup>-10<sup>5</sup>-10<sup>4</sup>-10<sup>3</sup>-10<sup>2</sup>-10<sup>1</sup>-10<sup>0</sup>+6=488895次。
<o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>7.n个男n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？<br>
解：把n个男、n个女分别进行全排列，然后按乘法法则放到一起，而男女分别在前面,应该再乘2,即方案数为2·(n!)<sup>2</sup>个.<br>
围成一个圆桌坐下，根据圆排列法则，方案数为2·(n!)<sup>2</sup>/(2n)个. <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>8.n个完全一样的球，放到r个有标志的盒子,n≥r,要求无一空盒，试证其方案数为<img
width=48 height=48 id="_x0000_i1035" src="1\image006.gif" align=middle>.<br>
证：每个盒子不空，即每个盒子里至少放一个球，因为球完全一样，问题转化为将n-r个小球放入r个不同的盒子，每个盒子可以放任意个球，可以有空盒，根据可重组合定理可得共有C(n-r+r-1,n-r)=C(n-1,n-r)中方案。
根据C(n,r)=C(n,n-r),可得C(n-1,n-r)=C(n-1,n-1-(n-r))=C(n-1,r-1)个方案。证毕。 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>9.设<img width=127 height=25
id="_x0000_i1036" src="1\image008.gif" align=middle>,p<sub>1</sub>、p<sub>2</sub>、…、p<sub>l</sub>是l个不同的素数，试求能整除尽数n的正整数数目.<br>
解：每个能整除尽数n的正整数都可以选取每个素数p<sub>i</sub>从0到a<sub>i</sub>次，即每个素数有a<sub>i</sub>+1种选择，所以能整除n的正整数数目为(a<sub>1</sub>+1)·(a<sub>2</sub>+1)·…·(a<sub>l</sub>+1)个。
<o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>10.试求n个完全一样的骰子掷出多少种不同的方案？<br>
解：相当于把n个小球放入6个不同的盒子里，为可重组合，即共有C(n+6-1,n)中方案，即C(n+5,n)中方案。<o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>11.凸10边形的任意三个对角线不共点，试求这凸10边形的对角线交于多少个点？又把所有对角线分割成多少段？<br>
解：根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有C(10,4)中,即交于210个点。<br>
根据图论知识，每个对角线交点有4个度，每个顶点去掉与相邻两个顶点的连线还有7个度，可以得到<br>
<img width=136 height=41 id="_x0000_i1037" src="ans1\image020.gif"
align=middle>条边<o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>12.试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数。<br>
证：根据第9题的结论，<img width=127 height=24 id="_x0000_i1038" src="ans1\image022.gif"
align=middle>, 能被(a<sub>1</sub>+1)·(a<sub>2</sub>+1)·…·(a<sub>l</sub>+1)个数整除，<br>
而<img width=156 height=25 id="_x0000_i1039" src="ans1\image024.gif"
align=middle>,能被(2a<sub>1</sub>+1)·(2a<sub>2</sub>+1)·…·(2a<sub>l</sub>+1)个数整除，2a<sub>i</sub>+1为奇数(0≤i≤l)，所以乘积为奇数。<br>
证毕。 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>13.统计力学需要计算r个质点放到n个盒子里去,并服从下列假定之一，问有多少种不同的图象。假设盒子始终是不同的。<br>
(a)Maxwell-Boltzmann假定：r个质点是不同的，任何盒子可以放任意数个. <br>
(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)种图案。 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>14.从26个英文字母中取出6个字母组成一字，若其中有2或3个母音，问分别可构成多少个字(不允许重复)？<br>
解：其中有2个母音可构成C(21,4)C(5,2)6!个字。 其中有3个母音可构成C(21,3)C(5,3)6!个字。 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'>15.给出<img width=493 height=48
id="_x0000_i1040" src="1\image010.gif" align=middle>的组合意义.<br>
解：如图：<o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:10.0pt'><object
 classid="CLSID:D27CDB6E-AE6D-11CF-96B8-444553540000" name=DefaultOcxName
 id=DefaultOcxName width=300 height=200
 codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0">
 <param name=movie value="">
 <param name=quality value=High>
 <param name="_cx" value=7938>
 <param name="_cy" value=5292>
 <param name=Src value="">
 <param name=WMode value=Window>
 <param name=Play value=-1>
 <param name=Loop value=-1>
 <param name=SAlign value="">
 <param name=Menu value=-1>
 <param name=Base value="">
 <param name=Scale value=ShowAll>
 <param name=DeviceFont value=0>
 <param name=EmbedMovie value=0>