的方法，应该得到(n)!/(n!)是整数。另外由于n个盒子相同，放入不同的盒子是没有区别的，应该把n个盒子的排列数n!除去。
因此得到(n)!/(n!)是整数。
23.(a)在2n个球中,有n个相同,求从这2n个球中选取n个的方案数。
(b)在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数.
解：(a) 相当于从n个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。
共有方案： C(n,0)+C(n,1)+?+C(n,n)=2n种。
(b)相当于从2n+1个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。 共有方案： C(2n+1,0)+C(2n+1,1)+?+C(2n+1,n)种。 24.证明在由字母表{0,1,2}生成的长度为n的字符串中.
2
n+1
2n
(a)0出现偶数次的字符串有个；
(b)，其中
1
.
证：(a)归纳法：当n=1时,0出现偶数次的字符串有(3+1)/2=2个(即1,2),成立。
假设当n=k时,0出现偶数次的字符串有(3k+1)/2种。总的字符串有3种。0出现奇数次的字符串有(3k-1)/2种。
当n=k+1时，0出现偶数次的字符串包括两部分：
n=k时,0出现偶数次再增加一位不是0的，共有2(3k+1)/2种，0出现奇数次再增加一位0,共有(3k-1)/2种。 所以共有2(3+1)/2+(3-1)/2=(3+1)/2种，证毕。 (b) 等式左边第m项是0出现m次的字符串数，总和就是0出现偶数次的字符串数，右边由(a)得是0出现偶数次的字符串数，两边显然相等。
25. 5台教学机器m个学生使用，使用第1台和第2台的人数相等，有多少种分配方案？
解：当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3(m-2n)。
qkkk+1
所以总的方案数为?C(m,2n)C(2n,n)3n?0(m?2n)
26.在由n个0及n个1构成的字符串中，任意前k个字符中，0的个数不少于1的个数的字符串有多少？ 解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1).
27.在1到n的自然数中选取不同且互不相邻的k个数，有多少种选取方案？
解：设从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。
较简单的新解法：
解：设这k个不相邻的数是 a1,a2,a3,…ak，
令
b1=a1 b2=a2-1 b3=a3-2 …
bk=ak-(k-1)
显然a1,a2,a3,…ak与 b1,b2,b3,…bk一一对应，且b1,b2,b3,…bk仅仅互不相同，无有不相邻的限制；且bk<=n-(k-1)。所以最终结果等于C(n-k+1,k)
28.(a)在5个0，4个1组成的字符串中，出现01或10的总次数为4的，有多少个?
(b)在m个0，n个1组成的字符串中,出现01或10的总次数为k的，有多少个？ 解：(a)先将5个0排成一列：00000，1若插在两个0中间，“010”，则出现2个“01”或“10”;若插在两端，则出现1个“01”或“10”;要使出现“01”,“10”总次数为4，有两种办法： (1)把两个1插入0得空当内，剩下的1插入1的前面。
(2)把1个1插入0得空当内，再取两个1分别插入两端，剩下的1插入1的前面。 故总方案数为C(4,2)·3+C(4,1)·3=30 (b)m个0产生m-1个空当，
若k为奇数,则必有且只有1个“1”插入头或尾,总方案数为2C(m?1,若k为偶数,总方案数为C(m?1,)C(n?1,n?2kk2)?C(m?1,k?22k?12)C(n?1,n?k?22) k?12)
)C(n?1,n?第一问，出现4个01或10，说明5个0被分成了3段，四个1被分成了两段，然后夹在一起形如001101100；或者5个0被分成了2段，四个1被分成了3段，然后夹在一起形如100100011。于是题目的考虑就变成了5个0如何拆分，4个1如何拆分。答案是： C(4,2)*C(3,1)+C(4,1)*C(3,2) []
第二章习题
?n??n??n?????1.证明等式????0??1??2???...???????222?n??2n??????n??n?? ????2解法一：利用第一章的第8节的公式7：令m = n, r = n即可。
解法二：利用恒等式(1?x)n(1?x)n?(1?x)2n，比较两边x的系数
?n??n??????k??n?k???k?0????nnx:n?n??2n??????k???n??。 k?0????nn2或是观察母函数(1?x)(1?2.求(1+x+x)
9545148100
x中x项的系数.
20
)的常数项，都可以得到结论。
n解 4x+8y=20并且x+2y=5解得x=5,y=0;x=1,y=2；x=3,y=1。
1?x??x?80:100!95!5!
100!1196?x??x?4381:96!3!1!100!97!1!2!
97?x??x?4182:
共91457520.
3.有红、黄、蓝、白球各两个，绿、紫、 黑的球各3个，问从中取出10个球，试问 有多少种不同的取法？
10
解：... (用指数型母函数，可得母函数 ,x系数即为所求。)
242331034437
解 同色球看做是相同的。求(1+x+x)(1+x+x+x)中x的系数。(1-x)(1-x)/(1-x) x : 0 0 0 1 1 2 2 3 x4 : 0 1 2 0 1 0 1 0 x : 10 6 2 7 3 4 0 1
?6?10??3??6?6??3??6?2??4??6?7??4??3??6?3??4??3??4??6?4??4??6?1??????????10????1????6????2????2????1????7????1????1????3????2????1?????2????4????3????1????????????????????????????????? 3
=678
4.求由A,B,C,D组成的允许重复的排列中 AB至少出现一次的排列数目。 解 设an为所求个数，bn为不出现AB的串的个数
an+bn=4, bn=4bn-1-bn-2,
an=4an-1+bn-2,
b1=4,b2=15,b0=1,b3=56. x2-4x+1=0 解得 x=2?bn=S(2+3)n+t(2-3)n
???2?S?t?13S?2?33n
3。
???3t?4?
S=
2?2,t=?12?233
bn?23?2???123?3?n?1?2?3?3?n?1?
??3an?4?n?2?????n?1?2???n?1?a?4n?n??123?2????3?n?1?2??3?n?1?
??5.求n位四进制数中2和3必须出现偶次的数目。
解：... 解
??x?Ge?x???1?x??...??2!???x14n22???e?exx?1???e2x???...???2!4!2???4x242x?x??? ?2e:2x?e142x?2?e?2?2?2x???e14n?1?2en?12x?1?n!?4nn??4?2
如果要求首位不是0,幂次减1，那么答案就是(4n?1?2n?1)?(4n?2?2n?2)?3?4n?2?2n?2.
6.试求由a,b,c三个文字组成的n位符号串 中不出现aa图像的符号串的数目。 解：...
解 设不出现aa的字符串的排列数为an
在所有符合要求的n位串中，最后一位是a,则n-1位是b或c，最后一位不是a，则是b或c.故有 an=2an-1+2an-2，a1=3，a2=8，a0=1. x2-2x-2=0,解得 x=1?3。
an=A(1+3)n+B(1-3)n
???1?A?B?13A?1?33???3B?333?
A=
?1?4?2,B=?143?1?4?2
n?2an???1????3??1??3?n?2?
??解法二：设a出现了k次，那么所有的a不能相邻。在1?n中去k个不相邻的数有C(n-k+1,k)
中取法（参见第一章-习题27）
?n?k?1?n?k?那么我们最后的答案就是??。 ??2kk?0???n????2?注： 比较解法一、二中的答案我们知道：
?n?k?1?n?k(3?23)(1?2?? = ??k?k?0???n????2?3)?(3?23)(1?6n3)n
怎么直接证明这个恒等式？可以思考一下。
7.证明序列 C(n,n),C(n+1,n),C(n+2,n),...的母函数为 证法一： 对n做归纳，n=0时,命题成立。 假设对于n-1，命题成立。即????n?k?k???n?x????n?1?k?k1?x?。 n?n?1?1?x???1?1?x?n?1。
Gn?x??????n?1?k?k???n?x?????n?1?k?k1????x?xGx?。 nn?n?1??1?x???Gn?x???n?k?k11??x??。 n?n?1?x?1?x???证毕。 证法二：
1(1?x).?(1?x?x?...)n?12n?1，xr的系数ar为在(n+1)个因式中取r个x。即将r个相同的球放
?n?1?r?1??n?r??入(n+1)个不同的盒子中。所以，ar???????n?? n????
相关推荐：
loading