第一章习题
1.证任一正整数 n可唯一地表成如下形式：
n=∑aii!,0≤ai≤i,i＝ 1,2,… 。 解
2.证 nC(n-1,r) = (r+1)C(n,r+1).并给出组合意义。 解
3.证 ∑kC(n,k)=n2 。 解
4.有 n个不同的整数，从中取出两组来，
要求第一组数里的最小数大于第二组的最大数。问有多少种方案？ 解
i≥1
i≥1
k n-1
5.六个引擎分列两排，要求引擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。 解
6.试求从 1到 1000000的整数中,0出现了多少次？ 解
7.n个男 n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？ 解
8.n个完全一样的球，放到 r个有标志的盒子,n≥r,要求无一空盒，试证其方案数为
( ).解n-1r-1
9.设 n=p1 p2 …p l,p1,p2,…,pl是 l个不同的素数，试求能整除尽数 n的正整数数目,
解
10.试求 n个完全一样的骰子掷出多少种不同的方案？ 解
11.凸 10边形的任意三个对角线不共点，
试求这凸 10边形的对角线交于多少个点？
又把所有对角线分割成多少段？ 解
12.试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数。 解
a1 a2 al
13.统计力学需要计算 r个质点放到 n个盒子里去,并服从下列假定之一，问有多少种不同的图象。假设盒子始终是不同的。
(a)Maxwell-Boltzmann假定,r个质点是不同的，任何盒子可以放任意数个,
(b)Bose-Einstein假定,r个质点完全相同，
每一个盒子可以放任意数个,
(c)Fermi-Dirac假定,r个质点都完全相同，
每盒不超过一个,解
14.从 26个英文字母中取出 6个字母组成一字，若其中有 2或 3个母音，问分别可构成多少个字 (不允许重复 )？ 解
15.给出 ( )( )+( )( )+( )( )+…+
( )( )= ( )的组合意义。 解
16.给出 ( )+( )+( )+…+ ( )=( )的组合意义。 解
n
m
r
0
n-1
m-1
n-2
m-2
n-m
0
n+r+1
m
r+1
1
r+2
2
r+m
m
r
r
r+1
r
r+2
r
n
r
n+1
r+1
17.证明,解
( )( )+( )( )+( )( )+…+ ( )( )=2 ( )
18.从 n个人中选 r个围成一圆圈，问有多少种不同的方案？ 解
19.分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法。 (解略 )
20.(a)按照第 19题的要求，写出邻位对换法
(排列的生成算法之二 )的相应算法。
(b)写出按照邻位对换法由给定排列生成其下一个排列的算法。 (解略 )
m
0
m
n
m
1
m
2
m
n
m
n
m-1
n-1
m-2
n-2
m-n
0
n
21.对于给定的正整数 n,证明当
22.(a)用组合方法证明 和 都是整数,
(b)证明 是整数,解
23.(a)在 2n个球中,有 n个相同,求从这 2n个球中选取 n个的方案数。
(b)在 3n+1个球中，有 n个相同，求从这 3n+1个球中选取 n个的方案数。 解
k=
n-1
2
n
2
,n+12
时,C(n,k)是最大值。 解若 n是奇数若 n是偶数
(2n)! (3n)!
2 2 · 3n n n
(n )!
(n!)n+1
2
24.证明在由字母表 {0,1,2}生成的长度为 n
的字符串中,
(a)0出现偶数次的字符串有 ——个；
(b) ( )2 +( )2 +…+ ( )2 = ——，
其中 q=2 —,解
25,5台教学机器 m个学生使用，使用第 1
台和第 2台的人数相等，有多少种分配方案？ 解
n
0
n
2
n
q
3 +1
2
3 +1
2
n n-1 n-q
n
n
n
2
26.在由 n个 0及 n个 1构成的字符串中，任意前 k个字符中,0的个数不少于 1的个数的字符串有多少？ 解
27.在 1到 n的自然数中选取不同且互不相邻的 k个数，有多少种选取方案？ 解
28.(a)在 5个 0,4个 1组成的字符串中，出现 01或 10的总次数为 4的，有多少个？
(b)在 m个 0,n个 1组成的字符串中,出现 01或 10的总次数为 k的，有多少个？ 解习题解答
1.证,对 n用归纳法。 题先证可表示性：
当 n=0,1时，命题成立。
假设对小于 n的非负整数，命题成立。
对于 n,设 k!≤n＜ (k+1)!,即 0≤n-k!＜ k·k!
由假设对 n-k!,命题成立，
设 n-k!=∑ai·i!,其中 ak≤k-1,
n=∑ai·i!+k!,命题成立。
i=1
k
i=1
k
再证表示的唯一性：
设 n=∑ai·i!=∑bi·i!,
不妨设 aj＞ bj,令 j=max{i|ai≠bi}
aj·j!+aj-1·(j-1)!+…+a 1·1!
=bj·j!+bj-1·(j-1)!+…+b 1·1!,
(aj-bj)·j!=∑(bi-ai)·i!≥j!＞ ∑i·i!
≥∑|bi-ai|·i!≥∑(bi-ai)·i!
另一种证法：令 j=min{i|ai≠bi}
∑ai·i!=∑bi·i!,
两边被 (j+1)!除,得余数 aj·j!=bj·j!,矛盾,
i=1
k
i=1
k
i=1
j-1
i=1
j-1
i=1
j-1
i=1
j-1
i≥j i≥j
2.证,题组合意义：
等式左边,n个不同的球，先任取出 1个，
再从余下的 n-1个中取 r个；
等式右边,n个不同球中任意取出 r+1个，
并指定其中任意一个为第一个。
显然两种方案数相同。
nC(n-1,r) = n ———— = ———————(n-1)! (r+1)·n!r!·(n-r-1)! (r+1)·r!·(n-r-1)!
= —————— = (r+1)C(n,r+1).(r+1)·n! (r+1)!·(n-r-1)!
3.证,题设有 n个不同的小球,A,B两个盒子,A
盒中恰好放 1个球,B盒中可放任意个球。
有两种方法放球：
①先从 n个球中取 k个球 (k≥1),再从中挑一个放入 A盒,方案数共为 ∑kC(n,k),其余球放入 B盒。
②先从 n个球中任取一球放入 A盒，剩下
n-1个球每个有两种可能，要么放入 B盒，
要么不放，故方案数为 n2,
显然两种方法方案数应该一样。
k=1
n
n-1
4.解,设取的第一组数有 a个,第二组有 b个,而要求第一组数中最小数大于第二组中最大的，
即只要取出一组 m个数 (设 m=a+b),从大到小取 a
个作为第一组,剩余的为第二组。此时方案数为
C(n,m)。 从 m个数中取第一组数共有 m-1中取法。
总的方案数为 ∑(m-1)C(n,m)=n·2 +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种方案。
m=2
n n-1
6.解,首先所有数都用 6位表示，从 000000到
999999中在每位上 0出现了 10 次,所以 0共出现了 6·10 次,0出现在最前面的次数应该从中去掉，
000000到 999999中最左 1位的 0出现了 10 次，
000000到 099999中左数第 2位的 0出现了 10 次，
000000到 009999左数第 3位的 0出现了 10 次,
000000到 000999左数第 4位的 0出现了 10 次,
000000到 000099左数第 5位的 0出现了 10 次,
000000到 000009左数第 6位的 0出现了 10 次。
另外 1000000的 6个 0应该被加上。
所以 0共出现了
6·10 –10 –10 –10 –10 –10 –10 +6 = 488895次。
5
5
5
4
3
2
1
0
5 5 4 3 2 1 0
题
7.解,把 n个男,n个女分别进行全排列，然后按乘法法则放到一起，而男女分别在前面,应该再乘 2,即方案数为 2·(n!) 个,围成一个圆桌坐下，
根据圆排列法则，方案数为 2 ·(n!) /(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)个方案。
证毕。 题
2
2
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 · 7
2
12.证,根据第 9题的结论，
n= p1 p2 …p l,能被 (a1+1)·(a2+1)·…· (al+1)
个数整除，而 n = p1 p2 … p l,能被
(2a1+1)·(2a2+1)·…· (2al+1)个数整除,2ai+1
为奇数 (0≤i≤l),所以乘积为奇数。
证毕。 题
———————= 455条边 题
a1 a2 al
2 2a1 2a2 2al
13.解,题
(a) 每个质点放入盒子都有 n种选择,r个质点共有 r 种不同的图案。
(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!个字。
n
15.解,题如图：
-r-1 -1 0 m-n x
y
mA(-1,m) B(m-n,m)
…… ……
可看作是格路问题：左边第 i项为从点 C
到点 (-1,i)直接经过 (0,i)的路径,再到点 B
的所有路径数。左边所有项的和就是从点 C到 B的所有路径数即为右边的意义。
C(-r-1,0)
16.解,C(n+1,r+1)是指从 n+1个元素 a1,
a2,…,a n+1中任取 r+1个进行组合的方案数。
左边：若一定要选 an+1,则方案数为 C(n,r).
若不选 an+1,一定要选 an,则方案数为 C(n-1,r).
若不选 an+1,an,…a r+2,则方案数为 C(r,r).题所有这些可能性相加就得到了总方案数。
17.证,组合意义,右边,m个球,从中取 n
个,放入两个盒子,n个球中每个球都有两种放法,得到可能的方案数。左边：第 i项的意义是一个盒子中放 i个,另一个盒子放
n-i个,所有的方案数相加应该等于右边。
17.(续前页 )数学证明：
左边 =∑C(m,k)C(m-k,n-k)
=∑———·—————
=∑——·—————
=∑———·C(m,n)
=2 C(m,n)=右边证毕。 题
k=0
n
m! (m-k)!
k!·(m-k)! (n-k)!·(m-n)!k=0
n
k=0
n m! n!
k!·n! (n-k)!·(m-n)!n!
k!·(n-k)!k=0
n
n
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)<C(n,k-1)
当 k<n/2时,(n-k+1)/k>1,即 C(n,k)>C(n,k-1)
得到当 k为最接近 n/2的数时,C(n,k)取到最大值。 题
22.证,(a)设有 2n个不同球放入 n个不同的盒子里，每盒两个，这个方案数应该是整数。对 2n个球进行排列得到方案数为 (2n)!。 而把 2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数,n个盒子内部的排列共重复计算了 2 次。得到 2n个不同球放入 n个不同的盒子里，每盒两个的方案数 (2n)!/2
若有 3n个不同的球,放入 n个不同盒子,故同理得 (3n)!/(3!) 是整数。
n
n
n
22.(接上页 )
(b)有 n 个不同的球，放入 n个相同的盒子里，每盒 n个，求方案数，方案数应该是一个整数。按前面 (a)的方法，应该得到
(n )!/(n!) 是整数。另外由于 n个盒子相同，
放入不同的盒子是没有区别的，应该把 n
个盒子的排列数 n!除去。
因此得到 (n )!/(n!) 是整数。 题
2 n
2 n+1
23.解,题
(a) 相当于从 n个不同的小球中分别取出 m个小球 (0≤m≤n),再从 n个相同的小球中取出 n-m个小球。共有方案：
C(n,0)+C(n,1)+…+C(n,n)=2 种。
(b)相当于从 2n+1个不同的小球中分别取出 m个小球 (0≤m≤n),再从 n个相同的小球中取出 n-m个小球。共有方案：
C(2n+1,0)+C(2n+1,1)+…+C(2n+1,n) 种。
n
24.证,(a)归纳法,题当 n=1时,0出现偶数次的字符串有 (3 +1)/2 =2个
(即 1,2),成立。假设当 n=k时,0出现偶数次的字符串有 (3 +1)/2 种。总的字符串有 3 种。 0出现奇数次的字符串有 (3 -1)/2 种。当 n=k+1时,0
出现偶数次的字符串包括两部分,n=k时,0出现偶数次再增加一位不是 0的，共有 2(3 +1)/2种，
0出现奇数次再增加一位 0,共有 (3 –1)/2种。所以共有 2(3 +1)/2+(3 –1)/2=(3 +1)/2种，证毕。
(b) 等式左边第 m项是 0出现 m次的字符串数，
总和就是 0出现偶数次的字符串数，右边由 (a)
得是 0出现偶数次的字符串数，两边显然相等。
1
k
k
k
k
k
k k k+1
25.解,当使用第 1台机器的学生为 n个时，
使用第 2台机器的学生也为 n,从 m个学生中选出 2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为
C(m,2n)C(2n,n)(m-2n)。 所以总的方案数为 ∑C(m,2n)C(2n,n)(m-2n) 题
26.解,转化为格路问题 (弱领先条件 ),即从 (0,0)到 (n,n),只能从对角线上方走,可以碰到对角线,故方案数为 C(2n,n)-C(2n,n-1).
题
3
n=0
q 3
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，有两种办法：
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为偶数,总方案数为
C(m-1,—)(—) +C(m-1,——)(——)
k-1
2
k+1
2
k+1
2(n－ ——)
k-1
2
k+1
2
k+1
2(n－ ——)k
2
k
2
k
2(n－ —)
1.证任一正整数 n可唯一地表成如下形式：
n=∑aii!,0≤ai≤i,i＝ 1,2,… 。 解
2.证 nC(n-1,r) = (r+1)C(n,r+1).并给出组合意义。 解
3.证 ∑kC(n,k)=n2 。 解
4.有 n个不同的整数，从中取出两组来，
要求第一组数里的最小数大于第二组的最大数。问有多少种方案？ 解
i≥1
i≥1
k n-1
5.六个引擎分列两排，要求引擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。 解
6.试求从 1到 1000000的整数中,0出现了多少次？ 解
7.n个男 n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？ 解
8.n个完全一样的球，放到 r个有标志的盒子,n≥r,要求无一空盒，试证其方案数为
( ).解n-1r-1
9.设 n=p1 p2 …p l,p1,p2,…,pl是 l个不同的素数，试求能整除尽数 n的正整数数目,
解
10.试求 n个完全一样的骰子掷出多少种不同的方案？ 解
11.凸 10边形的任意三个对角线不共点，
试求这凸 10边形的对角线交于多少个点？
又把所有对角线分割成多少段？ 解
12.试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数。 解
a1 a2 al
13.统计力学需要计算 r个质点放到 n个盒子里去,并服从下列假定之一，问有多少种不同的图象。假设盒子始终是不同的。
(a)Maxwell-Boltzmann假定,r个质点是不同的，任何盒子可以放任意数个,
(b)Bose-Einstein假定,r个质点完全相同，
每一个盒子可以放任意数个,
(c)Fermi-Dirac假定,r个质点都完全相同，
每盒不超过一个,解
14.从 26个英文字母中取出 6个字母组成一字，若其中有 2或 3个母音，问分别可构成多少个字 (不允许重复 )？ 解
15.给出 ( )( )+( )( )+( )( )+…+
( )( )= ( )的组合意义。 解
16.给出 ( )+( )+( )+…+ ( )=( )的组合意义。 解
n
m
r
0
n-1
m-1
n-2
m-2
n-m
0
n+r+1
m
r+1
1
r+2
2
r+m
m
r
r
r+1
r
r+2
r
n
r
n+1
r+1
17.证明,解
( )( )+( )( )+( )( )+…+ ( )( )=2 ( )
18.从 n个人中选 r个围成一圆圈，问有多少种不同的方案？ 解
19.分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法。 (解略 )
20.(a)按照第 19题的要求，写出邻位对换法
(排列的生成算法之二 )的相应算法。
(b)写出按照邻位对换法由给定排列生成其下一个排列的算法。 (解略 )
m
0
m
n
m
1
m
2
m
n
m
n
m-1
n-1
m-2
n-2
m-n
0
n
21.对于给定的正整数 n,证明当
22.(a)用组合方法证明 和 都是整数,
(b)证明 是整数,解
23.(a)在 2n个球中,有 n个相同,求从这 2n个球中选取 n个的方案数。
(b)在 3n+1个球中，有 n个相同，求从这 3n+1个球中选取 n个的方案数。 解
k=
n-1
2
n
2
,n+12
时,C(n,k)是最大值。 解若 n是奇数若 n是偶数
(2n)! (3n)!
2 2 · 3n n n
(n )!
(n!)n+1
2
24.证明在由字母表 {0,1,2}生成的长度为 n
的字符串中,
(a)0出现偶数次的字符串有 ——个；
(b) ( )2 +( )2 +…+ ( )2 = ——，
其中 q=2 —,解
25,5台教学机器 m个学生使用，使用第 1
台和第 2台的人数相等，有多少种分配方案？ 解
n
0
n
2
n
q
3 +1
2
3 +1
2
n n-1 n-q
n
n
n
2
26.在由 n个 0及 n个 1构成的字符串中，任意前 k个字符中,0的个数不少于 1的个数的字符串有多少？ 解
27.在 1到 n的自然数中选取不同且互不相邻的 k个数，有多少种选取方案？ 解
28.(a)在 5个 0,4个 1组成的字符串中，出现 01或 10的总次数为 4的，有多少个？
(b)在 m个 0,n个 1组成的字符串中,出现 01或 10的总次数为 k的，有多少个？ 解习题解答
1.证,对 n用归纳法。 题先证可表示性：
当 n=0,1时，命题成立。
假设对小于 n的非负整数，命题成立。
对于 n,设 k!≤n＜ (k+1)!,即 0≤n-k!＜ k·k!
由假设对 n-k!,命题成立，
设 n-k!=∑ai·i!,其中 ak≤k-1,
n=∑ai·i!+k!,命题成立。
i=1
k
i=1
k
再证表示的唯一性：
设 n=∑ai·i!=∑bi·i!,
不妨设 aj＞ bj,令 j=max{i|ai≠bi}
aj·j!+aj-1·(j-1)!+…+a 1·1!
=bj·j!+bj-1·(j-1)!+…+b 1·1!,
(aj-bj)·j!=∑(bi-ai)·i!≥j!＞ ∑i·i!
≥∑|bi-ai|·i!≥∑(bi-ai)·i!
另一种证法：令 j=min{i|ai≠bi}
∑ai·i!=∑bi·i!,
两边被 (j+1)!除,得余数 aj·j!=bj·j!,矛盾,
i=1
k
i=1
k
i=1
j-1
i=1
j-1
i=1
j-1
i=1
j-1
i≥j i≥j
2.证,题组合意义：
等式左边,n个不同的球，先任取出 1个，
再从余下的 n-1个中取 r个；
等式右边,n个不同球中任意取出 r+1个，
并指定其中任意一个为第一个。
显然两种方案数相同。
nC(n-1,r) = n ———— = ———————(n-1)! (r+1)·n!r!·(n-r-1)! (r+1)·r!·(n-r-1)!
= —————— = (r+1)C(n,r+1).(r+1)·n! (r+1)!·(n-r-1)!
3.证,题设有 n个不同的小球,A,B两个盒子,A
盒中恰好放 1个球,B盒中可放任意个球。
有两种方法放球：
①先从 n个球中取 k个球 (k≥1),再从中挑一个放入 A盒,方案数共为 ∑kC(n,k),其余球放入 B盒。
②先从 n个球中任取一球放入 A盒，剩下
n-1个球每个有两种可能，要么放入 B盒，
要么不放，故方案数为 n2,
显然两种方法方案数应该一样。
k=1
n
n-1
4.解,设取的第一组数有 a个,第二组有 b个,而要求第一组数中最小数大于第二组中最大的，
即只要取出一组 m个数 (设 m=a+b),从大到小取 a
个作为第一组,剩余的为第二组。此时方案数为
C(n,m)。 从 m个数中取第一组数共有 m-1中取法。
总的方案数为 ∑(m-1)C(n,m)=n·2 +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种方案。
m=2
n n-1
6.解,首先所有数都用 6位表示，从 000000到
999999中在每位上 0出现了 10 次,所以 0共出现了 6·10 次,0出现在最前面的次数应该从中去掉，
000000到 999999中最左 1位的 0出现了 10 次，
000000到 099999中左数第 2位的 0出现了 10 次，
000000到 009999左数第 3位的 0出现了 10 次,
000000到 000999左数第 4位的 0出现了 10 次,
000000到 000099左数第 5位的 0出现了 10 次,
000000到 000009左数第 6位的 0出现了 10 次。
另外 1000000的 6个 0应该被加上。
所以 0共出现了
6·10 –10 –10 –10 –10 –10 –10 +6 = 488895次。
5
5
5
4
3
2
1
0
5 5 4 3 2 1 0
题
7.解,把 n个男,n个女分别进行全排列，然后按乘法法则放到一起，而男女分别在前面,应该再乘 2,即方案数为 2·(n!) 个,围成一个圆桌坐下，
根据圆排列法则，方案数为 2 ·(n!) /(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)个方案。
证毕。 题
2
2
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 · 7
2
12.证,根据第 9题的结论，
n= p1 p2 …p l,能被 (a1+1)·(a2+1)·…· (al+1)
个数整除，而 n = p1 p2 … p l,能被
(2a1+1)·(2a2+1)·…· (2al+1)个数整除,2ai+1
为奇数 (0≤i≤l),所以乘积为奇数。
证毕。 题
———————= 455条边 题
a1 a2 al
2 2a1 2a2 2al
13.解,题
(a) 每个质点放入盒子都有 n种选择,r个质点共有 r 种不同的图案。
(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!个字。
n
15.解,题如图：
-r-1 -1 0 m-n x
y
mA(-1,m) B(m-n,m)
…… ……
可看作是格路问题：左边第 i项为从点 C
到点 (-1,i)直接经过 (0,i)的路径,再到点 B
的所有路径数。左边所有项的和就是从点 C到 B的所有路径数即为右边的意义。
C(-r-1,0)
16.解,C(n+1,r+1)是指从 n+1个元素 a1,
a2,…,a n+1中任取 r+1个进行组合的方案数。
左边：若一定要选 an+1,则方案数为 C(n,r).
若不选 an+1,一定要选 an,则方案数为 C(n-1,r).
若不选 an+1,an,…a r+2,则方案数为 C(r,r).题所有这些可能性相加就得到了总方案数。
17.证,组合意义,右边,m个球,从中取 n
个,放入两个盒子,n个球中每个球都有两种放法,得到可能的方案数。左边：第 i项的意义是一个盒子中放 i个,另一个盒子放
n-i个,所有的方案数相加应该等于右边。
17.(续前页 )数学证明：
左边 =∑C(m,k)C(m-k,n-k)
=∑———·—————
=∑——·—————
=∑———·C(m,n)
=2 C(m,n)=右边证毕。 题
k=0
n
m! (m-k)!
k!·(m-k)! (n-k)!·(m-n)!k=0
n
k=0
n m! n!
k!·n! (n-k)!·(m-n)!n!
k!·(n-k)!k=0
n
n
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)<C(n,k-1)
当 k<n/2时,(n-k+1)/k>1,即 C(n,k)>C(n,k-1)
得到当 k为最接近 n/2的数时,C(n,k)取到最大值。 题
22.证,(a)设有 2n个不同球放入 n个不同的盒子里，每盒两个，这个方案数应该是整数。对 2n个球进行排列得到方案数为 (2n)!。 而把 2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数,n个盒子内部的排列共重复计算了 2 次。得到 2n个不同球放入 n个不同的盒子里，每盒两个的方案数 (2n)!/2
若有 3n个不同的球,放入 n个不同盒子,故同理得 (3n)!/(3!) 是整数。
n
n
n
22.(接上页 )
(b)有 n 个不同的球，放入 n个相同的盒子里，每盒 n个，求方案数，方案数应该是一个整数。按前面 (a)的方法，应该得到
(n )!/(n!) 是整数。另外由于 n个盒子相同，
放入不同的盒子是没有区别的，应该把 n
个盒子的排列数 n!除去。
因此得到 (n )!/(n!) 是整数。 题
2 n
2 n+1
23.解,题
(a) 相当于从 n个不同的小球中分别取出 m个小球 (0≤m≤n),再从 n个相同的小球中取出 n-m个小球。共有方案：
C(n,0)+C(n,1)+…+C(n,n)=2 种。
(b)相当于从 2n+1个不同的小球中分别取出 m个小球 (0≤m≤n),再从 n个相同的小球中取出 n-m个小球。共有方案：
C(2n+1,0)+C(2n+1,1)+…+C(2n+1,n) 种。
n
24.证,(a)归纳法,题当 n=1时,0出现偶数次的字符串有 (3 +1)/2 =2个
(即 1,2),成立。假设当 n=k时,0出现偶数次的字符串有 (3 +1)/2 种。总的字符串有 3 种。 0出现奇数次的字符串有 (3 -1)/2 种。当 n=k+1时,0
出现偶数次的字符串包括两部分,n=k时,0出现偶数次再增加一位不是 0的，共有 2(3 +1)/2种，
0出现奇数次再增加一位 0,共有 (3 –1)/2种。所以共有 2(3 +1)/2+(3 –1)/2=(3 +1)/2种，证毕。
(b) 等式左边第 m项是 0出现 m次的字符串数，
总和就是 0出现偶数次的字符串数，右边由 (a)
得是 0出现偶数次的字符串数，两边显然相等。
1
k
k
k
k
k
k k k+1
25.解,当使用第 1台机器的学生为 n个时，
使用第 2台机器的学生也为 n,从 m个学生中选出 2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为
C(m,2n)C(2n,n)(m-2n)。 所以总的方案数为 ∑C(m,2n)C(2n,n)(m-2n) 题
26.解,转化为格路问题 (弱领先条件 ),即从 (0,0)到 (n,n),只能从对角线上方走,可以碰到对角线,故方案数为 C(2n,n)-C(2n,n-1).
题
3
n=0
q 3
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，有两种办法：
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为偶数,总方案数为
C(m-1,—)(—) +C(m-1,——)(——)
k-1
2
k+1
2
k+1
2(n－ ——)
k-1
2
k+1
2
k+1
2(n－ ——)k
2
k
2
k
2(n－ —)
