📄 ti.htm
字号:
<html><head><title>组合数学</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><body><p>1.证任一正整数n可唯一地表成如下形式:<img width=69 height=36src="./1/image002.gif" align="middle">,0≤a<sub>i</sub>≤i,i＝1,2,…。<br> 证：对n用归纳法。</p><p>先证可表示性：当n=0,1时，命题成立。<br> 假设对小于n的非负整数，命题成立。 <br> 对于n,设k!≤n＜(k+1)!,即0≤n-k!＜k·k! <br> 由假设对n-k!,命题成立，设<img width=103 height=45src="./ans1/image002.gif" align="middle">，其中a<sub>k</sub>≤k-1,<img width=105 height=45src="./ans1/image004.gif" align="middle">，命题成立。<br> 再证表示的唯一性： <br> 设<img width=143 height=45src="./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=27src="./ans1/image010.gif" align="middle"><br> 另一种证法：令j=max{i|a<sub>i</sub>≠b<sub>i</sub>}<br><img width=117 height=37src="./ans1/image012.gif" align="middle">, 两边被(j+1)!除,得余数a<sub>j</sub>·j!=b<sub>j</sub>·j!,矛盾. </p><p> 2.证 nC(n-1,r)=(r+1)C(n,r+1).并给出组合意义。<br> 证：<img width=184 height=163src="./ans1/image014.gif" align="top"><br> 组合意义：<br> 等式左边：n个不同的球，先任取出1个，再从余下的n-1个中取r个；<br> 等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。<br> 显然两种方案数相同。 <br></p><p> 3.证<img width=132 height=45src="./1/image004.gif" align="middle">。<br> 证：设有n个不同的小球，A、B两个盒子,A盒中恰好放1个球,B盒中可放任意个球。有两种方法放球：<br> ①先从n个球中取k个球(k≥1),再从中挑一个放入A盒,方案数共为<span lang=EN-US><sub><img width=76 height=45src="./ans1/image016.gif" v:shapes="_x0000_i1101" align="middle"></sub></span>,其余球放入B盒。<br> ②先从n个球中任取一球放入A盒，剩下n-1个球每个有两种可能，要么放入B盒，要么不放，故方案数为n2<sup>n-1</sup> . <br> 显然两种方法方案数应该一样。 <br></p><p>4.有n个不同的整数，从中取出两组来，要求第一组数里的最小数大于第二组的最大数。问有多少种方案？<br> 解：设取的第一组数有a个,第二组有b个,而要求第一组数中最小数大于第二组中最大的，即只要取出一组m个数(设m=a+b),从大到小取a个作为第一组,剩余的为第二组。此时方案数为C(n,m)。从m个数中取第一组数共有m-1中取法。<br> 总的方案数为<span lang=EN-US><sub><img width=275 height=45src="./ans1/image018.gif" v:shapes="_x0000_i1104" align="middle"></sub></span>. </p><p>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种方案。 </p><p>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次。 </p><p>7.n个男n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？<br> 解：把n个男、n个女分别进行全排列，然后按乘法法则放到一起，而男女分别在前面,应该再乘2,即方案数为2·(n!)<sup>2</sup>个.<br> 围成一个圆桌坐下，根据圆排列法则，方案数为2·(n!)<sup>2</sup>/(2n)个. </p><p>8.n个完全一样的球，放到r个有标志的盒子,n≥r,要求无一空盒，试证其方案数为<img width=48 height=48src="./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)个方案。证毕。 </p><p>9.设<img width=127 height=25src="./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)个。 </p><p>10.试求n个完全一样的骰子掷出多少种不同的方案？<br> 解：相当于把n个小球放入6个不同的盒子里，为可重组合，即共有C(n+6-1,n)中方案，即C(n+5,n)中方案。</p><p>11.凸10边形的任意三个对角线不共点，试求这凸10边形的对角线交于多少个点？又把所有对角线分割成多少段？<br> 解：根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有C(10,4)中,即交于210个点。<br> 根据图论知识，每个对角线交点有4个度，每个顶点去掉与相邻两个顶点的连线还有7个度，可以得到<br> <img width=136 height=41src="./ans1/image020.gif" align="middle">条边</p><p>12.试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数。<br> 证：根据第9题的结论，<img width=127 height=25src="./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=25src="./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> 证毕。 </p><p>13.统计力学需要计算r个质点放到n个盒子里去,并服从下列假定之一，问有多少种不同的图象。假设盒子始终是不同的。<br> (a)Maxwell-Boltzmann假定：r个质点是不同的，任何盒子可以放任意数个. <br>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -