?1.证：对n用归纳法。先证可表示性：当n=0,1时，命题成立。假设对小于n的非负整数，命题成立。对于n,设k!≤n＜(k+1)!,即0≤n-k!＜k·k!由假设对n-k!,命题成立，设n-k!=∑kai·i!∑ki=1，其中ak≤k-1,n=i=1ai·i!+k!，命题成立。?2.证：nC(n-1,r) = n ————(n-1)! (r+1)·n!r!·(n-r-1)! (r+1)·= ———————r!·(n-r-1)!= ——————(r+1)·n! (r+1)!·(n-r-1)!= (r+1)C(n,r+1).组合意义：等式左边：n个不同的球，先任取出1个，再从余下的n-1个中取r个；等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。显然两种方案数相同。?4.解：设取的第一组数有a个,第二组有b个,而要求第一组数中最小数大于第二组中最大的，即只要取出一组m个数(设m=a+b),从大到小取a个作为第一组,剩余的为第二组。此时方案数为C(n,m)。从m个数中取第一组数共有总的方案数为∑nm-1中取法。m=2(m-1)C(n,m)=n·2 +1n-1. ?5.解：第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种方案。?7.解：把n个男、n个女分别进行全排列，然后按乘法法则放到一起，而男女分别在前面,应该再乘2,即方案数为2·(n!) 2个. 围成一个圆桌坐下，根据圆排列法则，方案数为2 ·(n!) 2/(2n)个.?8.证：每个盒子不空，即每个盒子里至少放一个球，因为球完全一样，问题转化为将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)个方案。证毕。再证表示的唯一性：设n=∑kaki·i!=∑bi·i!,不妨设i=1a令i=1j＞bj,j=max{i|ai≠bi}aj·j!+aj-1·(j-1)!+…+a1·1! =bj·j!+bj-1·(j-1)!+…+b1·(aj-1j-1i=1j-1＞∑j-11!,j-bj)·j!=∑(bi-ai)·i!≥j!i=1i·i!≥∑|bi-ai|·i!≥∑(bi-ai)·i!另一种证法：令i=1j=min{i|ai=1i≠bi}∑ai·i!=∑b两边被i≥ji·i!,(j+1)!i≥j除,得余数aj·j!=bj·j!,矛盾.?3.证：设有n个不同的小球，A、B两个盒子,A盒中恰好放1个球,B盒中可放任意个球。有两种方法放球：①先从n个球中取k个球(k≥1),再从中挑n一个放入A盒,方案数共为∑球放入B盒。k=1kC(n,k),其余②先从n个球中任取一球放入A盒，剩下n-1个球每个有两种可能，要么放入B盒，要么不放，故方案数为n2 . n-1显然两种方法方案数应该一样。?6.解：首先所有数都用6位表示，从5000000到999999中在每位上0出现了10 次,所以0共出现了6·10 5次,0出现在最前面的次数应该从中去掉，000000到999999中最左1位的0出现了10 5次，000000到099999中左数第2位的0出现了10 4次，000000到009999左数第3位的0出现了10 3次, 000000到000999左数第4位的0出现了10 2次, 000000到000099左数第5位的0出现了10 1次, 000000到000009左数第6位的0出现了10 0次。另外1000000的6个0应该被加上。所以0共出现了6·10 5–10 5–10 4–10 3–10 2–10 1–10 +6 = 4888950次。?9.解：每个能整除尽数n的正整数都可以选取每个素数pi从0到ai次，即每个素数有ai+1种选择，所以能整除n的正整数数目为(a1+1)·(a2+1)·…·(al+1)个。?10.解：相当于把n个小球放入6个不同的盒子里，为可重组合，即共有C(n+6-1,n)中方案，即C(n+5,n)中方案。?11.解：根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有C(10,4)中,即交于210个点。

?11.(续前页)根据图论知识，每个对角线交点有4个度，每个顶点去掉与相邻两个顶点的连线还有7个度，可以得到———————210 ·4 + 10 ·72= 455条边?12.证：n= pa1pa根据第9题的结论，1 22…pall, 能被(a个数整除，而n = p21 a1+1)·(a2+1)·…·(al2+1)1 p22a…2pl2a,l能被(2a1+1)·(2a2+1)·…·(2al+1)个数整除，2ai+1为奇数(0≤i≤l) ，所以乘积为奇数。证毕。?15.解：题如图：A(-1,m)ymB(m-n,m)…………C(-r-1,0)-r-1 -1 0 m-n x可看作是格路问题：左边第i项为从点C到点(-1,i)直接经过(0,i)的路径,再到点B的所有路径数。左边所有项的和就是从点C到B的所有路径数即为右边的意义。?17.(续前页)数学证明：左边=∑nk=0C(m,k)C(m-k,n-k)=∑nk=0———m! (m-k)! nk!·(m-k)! (n-k)!··—————(m-n)!=∑m! n! k=0——k!·n! (n-k)!··—————(m-n)!=∑nn! k=0———=2 C(m,n)=nk!·(n-k)!·C(m,n)右边证毕。?22.证：(a)设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。对2n个球进行排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2 n次。得到2n个不同球放入n个不同的盒子里，每盒两个的方案数(2n)!/2 n若有3n个不同的球,放入n个不同盒子同理得(3n)!/(3!) n,故是整数。?13.解：(a) 每个质点放入盒子都有n种选择，r个质点共有r n种不同的图案。(b) 可重组合，共有C(n+r-1,r)种图案。(c) 一般组合问题，共有C(n,r)种图案。?14.解：其中有2个母音可构成C(21,4)C(5,2)6!个字。其中有2个母音可构成C(21,3)C(5,3)6!个字。?16.解：C(n+1,r+1)是指从n+1个元素a1, a2,…,an+1中任取r+1个进行组合的方案数。左边：若一定要选an+1,则方案数为C(n,r).若不选an+1,一定要选an,则方案数为C(n-1,r).若不选an+1,an,…ar+2,则方案数为C(r,r).所有这些可能性相加就得到了总方案数。?17.证：组合意义,右边：m个球,从中取n个,放入两个盒子,n个球中每个球都有两种放法,得到可能的方案数。左边：第i项的意义是一个盒子中放i个,另一个盒子放n-i个,所有的方案数相加应该等于右边。?18.解：圆排列:共有P(n,r)/r种不同的方案。?19.(略) 18题?20.(略)?21.证：取C(n,k)和C(n,k-1)进行比较。C(n,k)/C(n,k-1)=(n-k+1)/k。当k>n/2时,(n-k+1)/k<1,即C(n,k)1,即C(n,k)>C(n,k-1)得到当k为最接近n/2的数时，C(n,k)取到最大值。?22.(接上页)(b)有n 个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n )!/(n!) 2n是整数。另外由于n个盒子相同，放入不同的盒子是没有区别的，应该把n个盒子的排列数n!因此得到(n )!/(n!) 2n+1除去。是整数。

?23.解：(a) 相当于从n个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。共有方案：C(n,0)+C(n,1)+…+C(n,n)=2 n种。(b)相当于从2n+1个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。共有方案：C(2n+1,0)+C(2n+1,1)+…+C(2n+1,n)种。?25.解：当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)(m-2n)3∑q。所以总的方案数为C(m,2n)C(2n,n)(m-2n) 3n=0?26.解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1).?28.(续上页)(1)把两个1插入0得空当内，剩下的1插入1的前面。(2)把1个1插入0得空当内，再取两个1分别插入两端，剩下的1插入1的前面。故总方案数为C(4,2)·2 +C(4,1)·3=36. (b)m个0产生m-1个空当，若k为奇数,则必有且只有1个“1”插入头或尾,总方案数为2·C(m-1,——k-1)(——k+1(n－——k+12)若k为偶数,总方案数为22)C(m-1,—kk(n－—k(n－k+12)(—2) +C(m-1,2)——k-1k+1——2)2)(——2)?24.证：(a)归纳法：当n=1时,0出现偶数次的字符串有(3 +1)/2 =21个(即1,2),成立。假设当n=k时,0出现偶数次的字符串有(3 +1)/2 k种。总的字符串有3 种。0出现奇数次的字符串有(3 -1)/2 k种。当kn=k+1时，0出现偶数次的字符串包括两部分：n=k时,0出现偶数次再增加一位不是0的，共有2(3 +1)/2k0出现奇数次再增加一位0,共有(3 k种，–1)/2种。所以共有2(3 +1)/2+(3 kk–1)/2=(3 +1)/2k+1种，证毕。(b) 等式左边第m项是0出现m次的字符串数，总和就是0出现偶数次的字符串数，右边由(a)得是0出现偶数次的字符串数，两边显然相等。?27解：设从1~ n中选取互不相邻的k个数的方案数为g(n,k),若选n，则方案数为g(n-2,k-1),若不选n则方案数为g(n-1,k)。显然，g(n,k)=g(n-2,k-1)+g(n-1,k).且只有当n≥2k-1时，g(n,k)>0,否则g(n,k)=0.可给定初始值g(2k-1,k)=1,g(2k-2,k)=0。?28解：(a)先将5个0排成一列：00000，1若插在两个0中间，“010”，则出现2个“01”或“10”;若插在两端，则出现1个“01”或“10”;要使出现“01”,“10”总次数为4，有两种办法：