组合数学第四版卢开澄标准答案-第一章

第1章 排列与组合

1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：[解] (a) a -b =5

将上式分解，得到⎧a -b =+5

(a ) a -b =5; (b ) a -b ≤5.

⎨

⎩a -b =-5

a = b–5，a=1，2，„，45时，b ＝6，7，„，50。满足a=b-5的点共50-5=45个点. a = b+5，a=5，6，„，50时，b ＝0，1，2，„，45。满足a=b+5的点共45个点. 所以，共计2×45=90个点. (b) a -b ≤5

(6+10) ⨯5+11⨯(45-4) =16⨯5+11⨯41=531个点。

1.2 5个女生，7个男生进行排列，

(a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？

(c) 两男生A 和B 之间正好有3个女生的排列是多少？

[解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。

（7＋1）! ×5!=8!×5! ＝40320×120=4838400

(b) 先将男生排列有7! 种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有C 8种选择。将女生插入，有5! 种方案。故按乘法原理，有：

7! ×C 8×5!=33868800(种) 方案。

(c) 先从5个女生中选3个女生放入A ，B 之间，有C 5种方案，在让3个女生排列，有3! 种排列，将这5个人看作一个人，再与其余7个人一块排列，有

(7+1)! = 8!

由于A ，B 可交换，如图

**A***B** 或 **B***A**

故按乘法原理，有：

2×C 5×3! ×8!=4838400（种）

1.3 m个男生，n 个女生，排成一行，其中m ，n 都是正整数，若

(a) 男生不相邻(m≢n+1)； (b) n个女生形成一个整体； (c) 男生A 和女生B 排在一起； 分别讨论有多少种方案.

[解] (a) 先将n 个女生排列，有n! 种方法，共有n+1个空隙，选出m 个空隙，共有C n +1种

m

3

3

5

5

方法，再插入男生，有m! 种方法，按乘法原理，有：

n! ×C n +1×m! ＝n! ×

m

(n +1)! n ! (n +1)!

m!=×种方案。

m ! (n +1-m )! (n +1-m )!

(b) n个女生形成一个整体，看作一个人，与m 个男生做重排列，然后，n 个女生内部

再作排列，按乘法原理，有(m+1)!×n! 种方案。

(c) 男生A 和女生B 排在一起，看作一人，和其余n-1+m-1=n+m-2个人一起，作排列，共有(n+m-2+1)=(n+m-1)!种方法，A ，B 两人内部交换，故有2×(n+m-1)!种方案。 1.4 26个英文字母进行排列，要求x 和y 之间有5个字母的排列数.

5

[解] 选入26－2＝24个字母中选取5个字母，有C 24种方法，5个字母内部排列，有

5! 种方案，再将X*****Y这7个字母看作一个，与其余19个合起来作排列，共有(19+1)!=20!种方案，又因为X 与Y 可交换，故按乘法原理，有：

24! ⎛24⎫ 5

2×C 24×5! ×20!=2××5! ×20!=40×24! ≈ 40×2π⨯24× ⎪

5! ⨯19! e ⎝⎭

又因为：ln40+0.5(lgπ+lg48)+24(lg24–lge)

≈1.602059991+0.5(0.497149872+1.681241237)+24(1.380211242-0.434294481) =25.39325777

所以，结果为e ⨯1025＝2.473191664×1025

1.5 求3000到8000之间的奇整数的数目，而且没有相同的数字. [解] 3000~8000中各位不同的奇数，分类讨论：

首位3，1×8×7×4（末位不能取3） 首位4，1×8×7×5（末位全取） 首位5，1×8×7×4 首位6，1×8×7×5 首位7，1×8×7×4 从而，由加法原理，得：

8×7×（4＋5＋4＋5＋4）=56×22＝1232个。 1.6 计算

1⨯1! +2⨯2! +3⨯3! + +n ⨯n !

24

! +2⨯2! +3⨯3! + +n ⨯n ! =(n +1)! -1 (参见p14) (n ! -1=[解] 1⨯1

1.7 试证

被2n 除尽.

∑k ⨯k ! )

k =1

n -1

(n +1)(n +2) (2n )

(2n )! (2n )! ! (2n -1)! ! 2n ⋅n ! ⋅(2n -1)! !

==2n (2n -1)! ! [证] (n +1)(n +2) (2n ) ==

n ! n ! n !

故能被2整除。

n

1.8 求1040和2030的公因数. [解]因为1040=240·540，2030=(22·5) 30=260·530, 所以它们的公因数为形如2m ·5n 的数，其中0≢m ≢40，0≢n ≢30，故它们的公因数的数目为(40+1)(30+1)=1271。 1.9 试证n 2的正除数的数目是奇数.

[证]当n=1时，因数为10；当n=2时，因数为20，21，22；当n=3时，因数为30，31，32；

设n =p 11p 22 p n n ，(p 1, p 2, , p n , 均为质数) ，则n =p 11p 22 p n n 的正除数可表示为

k n k 2

p 1k 1p 2 p n ，其中k 1, k 2, , k n , 均为整数，且

l

l

l

2

2l

2l

2l

0≤k 1≤2l 1,0≤k 2≤2l 2, ,0≤k n ≤2l n , ，所以n 2的正除数的个数为(2l 1+1)(2l 2+1) (2l n +1) ，结果是奇数的乘积为奇数。

1.10 证明任一正整数n 可惟一地表示成如下形式：

n =∑a i i ! ,(0≤a i ≤i , i ≥1)

i ≥1

[证]. (1)可表示性：

令M={(a m-1, a m-2, ⋯, a 2, a 1):0≤a i ≤i ，i=1,2,⋯,m-1}，显然|M |=m!；

N={0,1,2,⋯,m!-1}，显然|N |=m!，其中m 是大于n 的任意整数。 定义函数f : M→N

f (a m-1, a m-2, ⋯, a 2, a 1)=a m-1(m-1)!+a m-2(m-1)!+⋯+a 22!+a 11! (*)

显然，0= 0(m-1)!+0(m-1)!+⋯+0⋅2!+0⋅1! ≤ a m-1(m-1)!+a m-2(m-1)!+⋯+a 22!+a 11!

≤ (m-1)(m-1)!+(m-2)(m-1)!+⋯+2⋅2!+1⋅1!= m!-1 （见P 14） 即0≤ f(a m-1, a m-2, ⋯, a 2, a 1) ≤m!-1

由于f 是用普通乘法和普通加法所定义的，故从而f 无歧义。从而有一确定的数K （0≤K ≤m!-1），使K =f (a m-1, a m-2, ⋯, a 2, a 1)

为证N 中的任一数均可表示成上边(*)的形式，只要证明f 是满射函数即可。但由于在两相等且有限的集合上定义的函数，满射性与单射性、双射性是等价的，故只须证明f 是单射函数即可。

否则，设存在某数K 0∈N , 有(a m-1, a m-2, ⋯, a 2, a 1) ≠(b m-1, b m-2, ⋯, b 2, b 1) 均属于M ，使

K 0=f (a m-1, a m-2, ⋯, a 2, a 1) 且K 0=f (b m-1, b m-2, ⋯, b 2, b 1)

由于不相等, 故必有某个j(≤m-1) ，使a j ≠b j 。不妨设这个j 是第一个不使相等的，即ai=bi(i =m -1, j +1) ，aj ≠bj 且aj

a m-1(m-1)!+a m-2(m-1)!+⋯+a 22!+a 11!= bm-1(m-1)!+b m-2(m-1)!+⋯+b 22!+b 11! 就可有(b j -a j )j!+(b j-1-a j-1)(j-1)!+⋯+(b 2-a 2)2!+(b 2-a 1)1!=0 但是

(b j -a j )j!+(b j-1-a j-1)(j-1)!+⋯+(b 2-a 2)2!+(b 2-a 1)1! ≥(b j -a j )j!-[|b j-1-a j-1|⋅(j-1)!+⋯+|b 2-a 2|⋅2!+|b 2-a 1|⋅1!] ≥j!-[(j-1)⋅(j-1)!+⋯+2⋅2!+1⋅1!]=j!-(j!-1)=1 矛盾，这说明f 是单射函数。

由于|M |=|N |=m!有限，故f 是双射函数，当然是满射函数，从而0到m!-1中的任何一个数都可以表示成上边(*)的形式。故，由n ∈N ，都有(a m-1, a m-2, ⋯, a 2, a 1) ∈M ，使得

n=a m-1(m-1)!+a m-2(m-1)!+⋯+a 22!+a 11! 这就证明了任何n 可表示成以上形式。 (2)唯一性：用证明单射的方法，就可以证明表示法的唯一性(表示方法见P 14), 留给读者。 1.11 证明nC (n -1, r ) =(r +1) C (n , r +1) ，并给予组合解释. [证]. (参见 P 28 (1-8-4))

nC (n -1, r ) =n

(n -1)! n !

=(r +1) =(r +1) C (n , r +1)

r ! (n -r -1)! (r +1)! (n -r -1)!

组合意义：（等式右边）由n 个元素中取出r+1个元素组合（有C (n,r+1)种），再从每个组合中取出1个（有r+1种），全部结果为C (n,r+1)(r+1)。（等式左边）由此所得的全部结果相当于从n 个元素中直接取1个元素（有n 种），但有重复，其重复数等于剩下的n-1个元素中取r 个元素的组合C (n-1,r)，故n C (n-1,r)= (r+1)C (n,r+1)。 1.12 试证等式：

∑kC (n , k ) =n 2

k =1

n

n -1

[证]. 证法一：根据二项式定理，(参见 P 29 (1-8-5))

(1+x ) n =1+C (n,1)x +C (n,2)x 2+⋯+ xn

两边对x 求导，有n(1+x ) n-1=C (n,1)+2C (n,2)x +⋯+ nx n-1

令x =1，即得∑kC (n , k ) =n 2n -1。

k =1n

证法二：组合意义：设有n 个不同的小球，并有A 、B 两个合子，A 合中恰好放入一个球，B 合中可放入任意多个球。有两种放球方法：

(1)（等式左边）先从n 个球中选取k 个，再从这k 个球中任选一个放入A 合，剩下的k-1个球全部放入B 合中，方案数共为∑kC (n , k ) ；

k =1n

(2)（等式右边）先从n 个球中任选一个放入A 合，剩下的n-1个球每个都有两种可能，要么放入B 合，要么不放，方案数共为n2n-1；

显然，两种放球方法等效，两种放球方案数相等，即∑kC (n , k ) =n 2n -1。

k =1n

1.13 有n 个不同的整数，从中取出两组来，要求第1组的最小数大于另一个组的最大数. [解] 设这n 个不同的数为m 1

若假定第一组取k 1个数，第二组取k 2个数，并且令m=k1+k2(m≥2) ，则要求第一组数里的最小数大于第二组的最大数，我们只要先从上边那n 个数中任选m 个数(有C(n,m)种选法) ，再从这m 个数中从大到小取k 1个数作为第一组数(有k 1=1,2,⋯,m-1共m-1种取法) ，将其余k 2个数作为第二组数，即可。故总方案数为

m =2

。 ∑(m -1) C (n , m ) =(n -2) 2n -1+1（参见第3题等式）

n

1.14 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少

种方案？

[解] 第一次点火仅有一种选择，即点某个特定引擎的火；第二次点另一组某个引擎的火，有三种选择；第三次有2种, „„。

即方案数为1⋅3⋅2⋅2⋅1⋅1=12。

1.15 试求从1到1 000 000的整数中，0出现的次数. [解] (参见P 8) 从1到1 000 000的整数中，0出现的次数相当于10-99，100-999，1000-9999, 10000-99999, 100000-999999, 以及1 000 000中的0的个数。 10-99中的零的个数为： 9

100-999中的零的个数为： 2⨯9+9⨯9+9⨯9=18+81+81=180

十位、个

位为零，故对百位的每一种取法，有两个零

十位为零

个位为零

21

1000-9999中的零的个数为：3⨯9+2⨯C 3⨯9⨯9+C 3⨯9⨯9⨯9 有三位为零

有两位为零

有一位为零

=27+486+2 187 =2 700

10000-99999中的零的个数为：

321

4⨯9+3⨯C 4⨯9⨯9+2⨯C 4⨯9⨯9⨯9+C 4⨯9⨯9⨯9⨯9

有四位零

有三位零

有二位零

有一位零

=36+972+8 748+26 244 =36 000

100000-99999中的零的个数为：

4321

5⨯9+4⨯C 5⨯9⨯9+3⨯C 5⨯9⨯9⨯9+2⨯C 5⨯9⨯9⨯9⨯9+C 5⨯9⨯9⨯9⨯9⨯9 有五位零

有四位零

有三位零

有二位零

有一位零

=45+1 620+21 870+131 220+295 245=450 000 1，000，000中的0的个数为： 6 故1到1，000，000的整数中0的个数为：9+180+2 700+36 000+450 000+6=488 895。 1.16 n个完全一样的球放到r 个有标志的盒（n ≣r ）中，无一空盒，试问有多少种方案？ [解]

1.17 n和r 都是正整数，而且r ≢n ，试证下列等式：

-1

(a ) P r n =nP r n -1

(b ) P r n =(n -r +1) P r n -1n

P r n -1, r

(d ) P r n +1=P r n +rP r n -1(c ) P r n =

n -1r (e ) P r n +1=r ! +r (P r n -1+P r -1+ +P r -1)

[解] (a) 方法一

n !

P ==n (n -1) (n -r +1) =n (n -1) [n -1-(r -1) +1]

(n -r )!

(n -1)! -1

=n =nP r n -1

[(n -1) -(r -1) +1]!

n r

方法二（组合意义）

等式左边：从n 个元素种取r 个元素做排列有P r n 种，就是等式左边；

等式右边：先从n 个元素中拿出一个元素排在首位，有n 种方法，然后再从剩下的n-1

-1n -1

个元素中取r-1个元素做后面r-1位的排列, 有P r n -1种方法, 按乘法原理, 共有n P r -1种方法。

(b) 方法一

P r n =

n !

=n (n -1) (n -r +2)(n -r +1)

(n -r )!

=(n -r +1) ⋅n (n -1) [n -(r -1) +1] =(n -r +1)

n !

=(n -r +1) P r n -1

[n -(r -1)]!

方法二（组合意义法）

等式左边：从n 个元素中取r 个元素做r 位排列，有P r n 种方案。

等式右边：先从n 个元素中取r-1个元素做r-1位排列，有P r n 再从剩下的n-r+1-1种方法；个元素中取1个元素，共有n-r+1种选法，按乘法原理，共有(n -r +1) P r n -1

(c) 方法一

P r n =

n !

=n (n -1) (n -r +2)(n -r +1)

(n -r )! n =(n -1) (n -r +2)(n -r +2)(n -r +1)(n -r ) n -r n n (n -1)! n =(n -1) (n -r +1)[(n -1) -r +1]==P r n -1n -r n -r [(n -1) -r ]!n -r

方法二：（组合意义法）

等式左边：从n 个元素中取r 个元素做r 位排列，其方案数为P r n ；

等式右边：从n 个元素中先取出一个元素放在第一位，有n 种方法，再从剩下的n-1个元素种取出r 个元素放在第2位，„，第r 位，第r+1位，有P r n -1种方法，这样就多了一位，故应除去第r+1位的选取方法，共有n-r 种选法，故总方案为

(d) 方法一

n

P r n -1。 n -r

P r n +1=

(n +1)!

=(n +1) n (n -r +2) =[(n -r +1) +r ]n (n -r +2)

(n +1-r )!

=n (n -r +2)(n -r +1) +r ⋅n [n -(r -1) +1] =

n ! r ⋅n !

+=P r n +rP r n -1

(n -r )! (n -r +1)!

方法二：（组合意义）

等式左边：从n+1个不同的元素中取r 个元素进行r 位排列。其方案为P r n +1； 等式右边：(a) 不取某特定元素b ，则r 个元素需从剩下的n 个元素中取，然后做r 位

排列，共有P r n 种方案。

(b) 取定某特定元素b ，则其余r-1个元素需从剩下的n 个元素中取，先做r-1位排列，共有P r n -1种方法，再将特定元素b 插入这r-1个元素形成的r 个空隙中，有r 种方法，故按乘法原理，共有r P r n 种方案。

(e) 方法一 （根据(d)可得）

P r n +1=P r n +rP r n -1

-1n

=P r n -1+rP r n -1+rP r -1

-2n -1n =P r n -2+rP r n -1+rP r -1+rP r -1-2n -1n =P r n -2+rP r n -1+rP r -1+rP r -1

1n -1n =P r r +rP r r -1+rP r r -+1+ +rP r -1+rP r -11n -1n =r ! +r (P r r -1+P r r -+1+ +P r -1+P r -1) n -1r +1r =r ! +r (P r n -1+P r -1+ +P r -1+P r -1

方法二：组合意义（同样根据d ）

等式左边：从n+1个不同元素取r 个元素做r 位排列，其方案数为：P r n +1 等式右边：设b 1, b 2, b 3, , b n +1-r 是n-r+1个特定元素。

(a) 不取特定元素b 1, b 2, b 3, , b n +1-r ，剩下的r 个元素做全排列，有P r r =r!种方案。 (b)(1)：取特定元素b 1，但不取特定元素b 2, b 3, , b n +1-r ，于是先在剩下的r 个元素中取r-1个元素做排列，有P r r -1种方法，然后将b 1插入这r-1个元素的r 个空隙，共有r 种方法，故按乘法原理，有r P r r -1种方案。

(2)：取特定元素b 1，但不取特定元素b 3, , b n +1-r ，于是先在剩下的r+1个元素中取r-1

1

个元素做排列，有P r r -+1种方法，然后，将b 1插入这r-1个元素的r 个空隙，共有r 种方法，1故按乘法原理，有r P r r -+1种方案。

„„

(n-r)：取特定元素b 1，但不取特定元素b n +1-r ，于是先在剩下的n-1个元素中取r-1个

-1元素做排列，有P r n -1种方法，然后，将b 1插入这r-1个元素的r 个空隙，共有r 种方法，故-1按乘法原理，有r P r n -1种方案。

(n-r+1）：取特定元素b 1，先在剩下的n 个元素中取r-1个元素做排列，有P r n -1种方法， 然后，将b 1插入这r-1个元素的r 个空隙，共有r 种方法，故按乘法原理，有r P r n -1种方案。

最后，按加法原理，共有：

n -1n r ! +r (P r n -1+P r -1+ +P r -1)

1.18 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？

[解] 先将5个球进行全排列，有5! 种方法，再将三个空格插入5个球的6个空隙中，有

C 36

种方法，然后将这些元素的排列一对一的放入8个盒子中，即完成了每盒最多一球，空盒不相邻的放球要求，总方案有：C 3⨯5! =2400（种）

1.19 n+m位由m 个0，n 个1组成符号串，其中n ≢m+1，试问不存在两个1相邻的符号串的数目。

[解]：先将m 个0排成一排，再将n 个1插入m 个0的m+1个空隙（因为n ≢m+1,这可实现）, 就得到了无相邻的n+m位0-1符号串，其方案数为

6

⎛m +1⎫

⎪⎪。 n ⎝⎭

1.20 甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产

生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志5位. 试问有多少种方案？ [解] 甲单位选4人，则乙单位只能选3人；另外男同志要5人，而乙单位的3人全是男同志，还差2名男同志，故甲单位的男同志人数应至少是2，至多为4。

⎛10⎫⎛4⎫⎛15⎫⎛10⎫⎛10⎫⎛4⎫⎛15⎫⎛10⎫⎛10⎫⎛4⎫⎛15⎫⎛10⎫ 2⎪⎪ 2⎪⎪ 3⎪⎪ 0⎪⎪+ 3⎪⎪ 1⎪⎪ 2⎪⎪ 1⎪⎪+ 4⎪⎪ 0⎪⎪ 1⎪⎪ 2⎪⎪=768600 ⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭

1.21 一个盒子里有7个无区别的白球，5个无区别的黑球. 每次从中随机取走一个球，已知前面取走6个，其中3个是白的. 试问取第6个球是白球的概率. [解] 已知前面取走6个球，有3个白球，则有3个黑球。

故总的取球方案是 ⎪⎪⋅7⋅6⋅5⋅5⋅4⋅3；

⎛6⎫

⎝3⎭

⎛5⎫

第六个球是白球的方案是 2⎪⎪⋅7⋅6⋅5⋅5⋅4⋅3

⎝⎭

⎛5⎫ 2⎪⎪⋅7⋅6⋅5⋅5⋅4⋅31⎝⎭==0. 5 因此取出第6个球是白球的概率P =

2⎛6⎫

⎪⋅7⋅6⋅5⋅5⋅4⋅3 3⎪⎝⎭

1.22 求下图中从0到P 的路径数：

(a) 路径必须过A 点； (b) 路径必须过道路AB ；

(c) 路径必须过A 和C ；

(d) 道路AB 封锁（但A ，B 两点开放）.

[解] O(0,0), A(3,2), B(4,2), P(8,5), C(6,3)

(a) 路分为两段：先从O 到A ，再从A 到P ，则有：

⎛3+2⎫⎛8-3+5-2⎫⎛5⎫⎛8⎫ ⎪ 2⎪⎪ 5-2⎪= 2⎪⎪ 3⎪⎪=560⎝⎭⎝⎭⎝⎭⎝⎭

(b)路分为三段：先从O 到A ，再从A 到B ；再从A 到B ；然后从B 到P ；

⎛3+2⎫⎛8-4+5-2⎫⎛5⎫⎛7⎫ ⎪ 2⎪⎪⋅1⋅ 5-2⎪= 2⎪⎪ 3⎪⎪=350⎝⎭⎝⎭⎝⎭⎝⎭

(c) 路分为三段：先从O 到A ；再从A 到C ；然后从C 到P ；

⎛3+2⎫⎛6-3+3-2⎫⎛8-6+5-3⎫⎛5⎫⎛4⎫⎛4⎫

⎪⎪ 2⎪⎪⋅ 3-2⎪⋅ 5-3⎪= 2⎪⎪ 1⎪⎪ 2⎪⎪=240⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭

(d) (采用排除法)

从O 到P 的满足不过AB 的路 ＝ 从O 到P 的路－从O 到P 经过AB 的路，因此：

⎛8+5⎫⎛3+2⎫⎛8-4+5-2⎫⎛13⎫ ⎪- ⎪⋅1⋅ ⎪= ⎪-350=1287-350=937 525-2⎝⎭⎝⎭⎝⎭⎝5⎭

1.23 另s={1,2,3…,n+1},n≣2

T ={(x , y , z ) |x , y , z ∈s , x

[证]

⎛n +1⎫⎛n +1⎫

T =∑k 2=+2 +2⎪ ⎪

23k =1⎝⎭⎝⎭

n

2

T =∑∑∑1=∑(z -1)=∑k 2

z =1y =1x =1

z =1

k =1

n +1z -1z -1n +1n

而(k +1)=k 3+3k 2+3k +1，故k =

3

2

1

(k +1)3-k 3-3k -1 3

[]

n n

1⎡n 3⎤1⎡3⎤33

k =(k +1) -k -3k -n =n +1-1-n n +1-n ()()∑∑∑∑⎥3⎢⎥3⎢2⎣⎦k =1k =1k =1⎣k =1⎦

2

n

11(n +1) 1113

=n (n +1) +(n +1) 3-n (n +1) -(n +1) (n +1)-n (n +1)-

323233

n +1⎛n +1⎫⎛⎫11⎛1⎫22

= ⎪+(n +1) (n +1) -n -⎪= ⎪+(n +1)(n +2n +1-3n -1)

3⎭⎝2⎭3⎝3⎝2⎭=

⎛n +1⎫1⎛n +1⎫(n +1) n (n -1) ⎛n +1⎫⎛n +1⎫2

= +(n +1)(n -n ) =+2⋅= ⎪ ⎪⎪+2 ⎪222333⋅2⋅1⎝⎭⎝⎭⎝⎭⎝⎭

1.24 A={(a , b)|a , b∈Z, 0≢a ≢9,0≢b ≢5}

(a) 求x-y 平面上以A 作顶点的长方形的数目. (b) 求x-y 平面上以A 作顶点的正方形数目. [解] (a) 先选定横作标，再选定纵坐标，其方案数为：

⎛10⎫⎛6⎫10⨯96⨯5 2⎪⎪ 2⎪⎪=2⨯2=675⎝⎭⎝⎭

(b) 求x －y 平面上以A 作顶点的正方形数目。

按边长分类：

边长为1的正方形：9×5＝45

边长为2的正方形：(9-1)×(5-1)=32 边长为3的正方形：(9-2)×(5-2)=21 边长为4的正方形：(9-3)×(5-3)=12 边长为5的正方形：(9-4)×(5-1)=5

故总的以x －y 平面上A 点作顶点的正方形的数目，按加法原理可得数目为115.

1.25 平面上有15个点P 1, P2, … , P15，其中P 1, P2, P3, P4, P5共线，此外不存在3点共线的.

(a) 求至少过15个点中两点的直线的数目. (b) 求由15个点中3点组成的三角形的数目. [解] (a) (采用排除法)

至少过15个点中两点的直线数目＝在15个点中任选2个点将有一条直线－从P 1～P 5

中选2点构成直线＋P 1～P 5所在的直线l

⎛15⎫⎛5⎫= 2⎪⎪- 2⎪⎪+1⎝⎭⎝⎭=96

(b) (采用排除法)

由15个点中3点组成的三角形的数目＝任在15个点中取3点构成三角形的数目－在5个点P 1～P 5中取3点构成的“三角形”的数目

⎛15⎫⎛5⎫= 3⎪⎪- 3⎪⎪⎝⎭⎝⎭=445

1.26 S={1, 2, … , 1000}，a ，b ∈S ，使ab ≡0 mod 5，求数偶{a, b}的数目.

[解] 因为 ab ≡0m od 5

所以 ab ＝5k （k 是整数）

1≢a ≢1000, 1≢b ≢1000

1≢ab ≢1000000

1≢5k ≢1000000

1≢k ≢200000

所以满足 ab ≡0m od 5且1≢a,b ≢1000的{a,b}的数目为200000

1.27 6位男宾，5位女宾围一圆桌而坐

(a) 女宾不相邻有多少种方案？

(b) 所有女宾在一起有多少种方案？

(c) 一女宾A 和两位男宾相邻又有多少种方案？

[解] (a) 先将6位男宾作圆排列有Q 6=5! =120

再将5位女宾插入6个空格，每格一人，共有6×5×4×3×2×1＝720

按乘法原理：有120×720＝86400

(b) 5位女宾在一起，可看作一人，与6位男宾一起，先做圆排列，有Q 7=6!=720 然后5位女宾内部作线排列，有5! ＝120。

所以，总方案为：720×120＝86400

(c)先将6个男宾做圆排列，共有Q 6=120种方法。

再将女宾A 随便插入6个空格中的一个，有6种方法。

然后将剩下的4个女宾插入5个空格中，但每个空格不限人数，故相当于将4个有区别676

⎛4+5-1⎫的球放入5个不同的盒子中的放球方案(可重组合) ，共有 4⎪⎪=5×6×7×8＝1680。⎝⎭

所以，按乘法原理，有120×6×1680＝1209600种方案。

1.28 k和n 都是正整数，kn 位来宾围着k 张圆桌而坐，试求其方案数.

[解] 先将k ×n 个来宾分成k 堆，每堆n 个人，有

⎛kn ⎫⎛(kn )! ⎫(kn )! n , n , , n (k 堆) ⎪⎪= n ! ⋅n ! ⋅ ⋅n ! ⎪=(n ! ) k ⎭⎝⎭⎝

再将每堆n 个人做圆排列，有

故按乘法原理，有 n Q n k [(n -1)! ]＝(n-1)!,共有种方法。

(kn )! (kn )! k [](n -1)! =(n ! ) k n k

1.29 从n 个对象中取r 个作圆排列，求其方案数目. 已知1≢r ≢n.

[解] 每一个r 个人围成的圈（圆排列）a 1, a 2, , a r -1, a r

⎧a 1, a 2, , a r -1, a r ⎪⎪a 2, a 3, a r , a 1⇔(线排列) ⎨ ⎪⎪⎩a r , a 1, a r -2, a r -1

即每一个r 圈相当于r 个r 排列。故不同的方案数为N =11n ! P (n , r ) =r r (n -r )!

若不计顺逆方向，则为N =

1.30 试证下列等式 11n ! 。 P (n , r ) =⋅2r 2r (n -r )!

⎛n ⎫n ⎛n -1⎫(a ) ⎪= ⎪,1≤r ≤n r r -1⎝⎭r ⎝⎭

⎛n ⎫n -r +1⎛n ⎫(b ) ⎪= ⎪,1≤r ≤n r ⎝r ⎭⎝r -1⎭

⎛n ⎫n ⎛n -1⎫(c ) ⎪= ⎪,0≤r ≤n ⎝r ⎭n -r ⎝r ⎭

[证] (a) 方法一

⎛n ⎫n ! n (n -1)! n ⎛n -1⎫==⋅= ⎪ ⎪ ⎝r ⎭r !(n -r )! r (r -1)! ⨯[(n -1) -(r -1)]!r ⎝r -1⎭

方法二：组合意义法：

一方面，从n 个元素中取出r 个元素，然后再做排列，故按乘法原理，其数目为

⎛n ⎫ r ⎪⎪⋅r ! ⎝⎭

另一方面：先从n 个元素中取出1个元素，排在第一位，再从剩下的n-1个元素中取出r-1个元素，并将这r-1个元素排在第2～r 位，故按乘法原理，其方案数为

⎛n -1⎫n r -1⎪⎪⋅(r -1)! ⎝⎭

⎛n ⎫⎛n -1⎫ ⎪ ⎪⋅r ! =n ⋅⋅(r -1)! 这两方面的组合意义相同，故有 ⎪ ⎪⎝r ⎭⎝r -1⎭

因此，有： ⎪⎪=

(b) 方法一 ⎛n ⎫⎝r ⎭n ⎛n -1⎫ ⎪⎪ r -1r ⎝⎭

⎛n ⎫n (n -1) (n -r +2)(n -r +1) ⎪=r ! ⎝r ⎭ (n -r +1)⋅n (n -1) (n -r +2) =n -r +1⋅⎛n ⎫= ⎪r (r -1)! r ⎝r -1⎭

方法二：组合意义

一方面：从n 个元素中取出r 个元素来，然后，在做排列，故按乘法原理，其方案数为

⎛n ⎫ r ⎪⎪⋅r ! ⎝⎭

另一方面：先从n 个元素中先取出r-1个元素，将其排排列再第1～r-1位，再从剩下的n-r+1个元素中取出1个元素排在第r 位。故按乘法原理，其方案数为：

⎛n ⎫ r -1⎪⎪⋅(r -1)! ⋅(n -r +1) ⎝⎭；

这两方面的组合意义相同，故有

⎛n ⎫⎛n ⎫ ⎪ ⋅r ! r -1⎪⎪⋅(r -1)! ⋅(n -r +1) r ⎪⎭⎝⎭＝⎝

所以，有：

⎛n ⎫n -r +1⎛n ⎫ ⎪ r ⎪⎪= ⎪r ⎝⎭⎝r -1⎭

(c) 方法一

⎛n ⎫n (n -1) (n -r +1)(n -r )(n -r -1) 1 ⎪=r !(n -r )(n -r -1) 1⎝r ⎭

n (n -1) (n -r +1)(n -r )(n -r -1) 1 =⋅n -r r !(n -r -1) 1

=n (n -1)! n ⎛n -1⎫⋅= ⎪n -r r !(n -1-r )! n -r ⎝r ⎭

方法二：组合意义

一方面，从n 个元素中取出n-r 个元素，然后再做排列，按乘法原理，其方案数为：

⎛n ⎫⎛n ⎫ ⎪ (n -r )! = n -r ⎪ r ⎪⎪(n -r )! ⎝⎭⎝⎭

另一方面，选从n 个元素中取出1个元素排再第一位，再从剩下的n-1个元素中选取n-r+1个元素，排在第2～n-r 位。故按乘法原理，其方案数为

⎛n -1⎫⎛n -1⎫n ⋅ n -r -1⎪⎪⋅(n -r -1)! =n ⋅ r ⎪⎪⋅(n -r -1)! ⎝⎭⎝⎭

这两方面的组合意义相同，可得：

⎛n ⎫⎛n -1⎫ ⎪ (n -r )! =n ⋅ r ⎪ r ⎪⎪⋅(n -r -1)! ⎝⎭⎝⎭

⎛n ⎫n ⎛n -1⎫ ⎪= r ⎪n -r r ⎪⎪⎝⎭⎝⎭

1.31 试证任意r 个相邻数的连乘：

被r ！除尽.

[证] (n +1)(n +2) (n +r ) =(n +1)(n +2) (n +r ) ⎛n +r ⎫(n +r )! ⎪r ! = ⋅r ! ⎪r ! n ! ⎝r ⎭

⎛n +r ⎫⎪由于 r ⎪是从n+r个元素中选取r 个元素的组合数，故当然是整数，因此，⎝⎭

⎛n +r ⎫⎪(n+1)(n+2)„(n+r)可以整除r! ，其商为组合数 r ⎪。 ⎝⎭

1.32 在a, b, c, d, e, f, x, x, x, y, y的排列中，要求y 必须夹在两个x 之间，问这样的排列数等于多少？

[解] 由于y 必须乘在两个x 之间，故两个y 只能夹在仅有的三个x 之间，形成图象xyxyx ，形成6个空档。其余的6个元素a,b,c,d,e,y, 只能放在这6个空格处，这相当于将6个不同的小球放入6个不同的盒子中，允许空盒，且盒内还要排列的方案数。故：

⎛6+6-1⎫11! ⎪6! =6! ⋅=332640 6-1⎪5! 6! ⎝⎭

1.33 已知r, n, k 都是正整数，r ≣nk ，将r 个无区别的球放在n 个有标志的盒子里，每盒至少k 个球，试问有多少种方案？

[解] 先将nk 个球放入n 个有标志的盒中，每盒k 个球，其方案为1。

再将剩下的r-nk 个球放入这n 个盒中，每盒球数不限，其方案数为

⎛n +(r -nk ) -1⎫⎛r -n (k -1) -1⎫ ⎪⎪ r -nk ⎪= n -1⎪⎝⎭⎝⎭

故总的方案为

⎛r -n (k -1) -1⎫⎛r -n (k -1) -1⎫⎪⎪1⋅ n ⎪= n -1⎪⎝⎭⎝⎭

1.34 在r, s, t, u, v, w, x, y, z的排列中求y 居x 和z 中间的排列数.

[解] 由于y 必须居于x 和z 之间，故形成图象xyz ，形成4个空格。其余r,s,t,u,v,w 这6个元素，只能放在这4个空格处，这相当于将6个不同的小球放入4个不同的盒子中，允许空盒，且盒内还要进行排列的方案数。故有：

⎛6+4-1⎫9! ⎪6! ⋅ =6! =60480 4-1⎪3! 6! ⎝⎭

将9个字母进行全排列，有9! 中排列，而x,y,z 这3个字母形成的3! 个排列只看作一种排列xyz ，故有：

9! =60480 3!

1.35 凸十边形的任意三条对角线不共点. 试求这凸十边形的对角线交于多少个点？

[解] 从一个顶点可引出7条线和第一条（从右到左）交

的有1⋅7，和第二条交的有2⋅6条, 故和一个顶点引出的7条

线相交的点为： 1⋅7+2⋅6+3⋅5+4⋅4+5⋅3+6⋅2+7⋅1=84

故和从10点引出的对角线交的点有个84⨯10=840，但每

个点重复了四次（因为每个点在两条线上，而每条线有两个

端点）。故凸10 边形（这样的）对角线交于

4=故也可为C 10840=210个点, 410⨯9⨯8⨯7=210 4⨯3⨯2⨯1

1.36 试证一整数是另一整数的平方的必要条件是除尽它的数的数目是整数.

[证] “必要性”。若整数n 是另一个整数的平方，则n 一定可写成如下形式：

2αe 2α12α2n =P P P 12e （参见P7例4）

其中P1,P2, ⋯,Pe 是e 个不同的素数。由于第9题可得，除尽n 的正整数数目为 (2α1+1)(2α2+1)⋯(2αe+1)为奇数。

“充分性”。若除尽正整数n 的正整数的数目为奇数。则n 一定是某个正整数的平方，否则，n 不是平方数，则n 一定是可分解成如下形式：

β1βe n =P P 2β2 P 1e

其中P1,P2, ⋯,Pe 是e 个不同的素数，且β1, β2, ⋯, βe 中至少有一个奇数（否则n 为平方数）。于是(2β1+1)(2β2+1)⋯(2βe+1)必为偶数，与充分性假设矛盾。

1.37 给出

⎛n ⎫⎛r ⎫⎛n -1⎫⎛r +1⎫⎛n -2⎫⎛r +2⎫⎛n -m ⎫⎛r +m ⎫⎛n +r +1⎫+++ +⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪= ⎪ ⎝m ⎭⎝0⎭⎝m -1⎭⎝1⎭⎝m -2⎭⎝2⎭⎝0⎭⎝m ⎭⎝m ⎭

的组合意义.

[证] 组合意义一：

从(n+r+1)个元素{1,2,⋯,n+r+1}中取出(n +r +1-m ) 个元素i 1

⎛n +r +1⎫⎛n +r +1⎫

⎝⎭⎝⎭

r+1,r+2,⋯,r+1+m。

当i r+1取(r+1+k)时(k=0,1,2,⋯,m) ，前边r 个数i 1,i 2, ⋯,i r 可在{1,2,⋯,r+1+(k-1)}这(r+k)

⎛r +k ⎫⎛r +k ⎫个数里取，故有 r ⎪⎪= k ⎪⎪种取法；后边[(n+r+1-m)-(r+1)]=n-m个数i r+2, ⋯,i n+r+1-m可

⎝⎭⎝⎭

⎛n -k ⎫⎛n -k ⎫在{r+1+k+1, ⋯,n+r+1}这[(n+r+1)-(r+1+k)]=n-k个数中取，故有 n -m ⎪⎪= m -k ⎪⎪。根据乘

⎝⎭⎝⎭

⎛n -k ⎫⎛r +k ⎫⎛n -k ⎫⎛r +k ⎫法原理，当i r+1=r+1+k时，这样的组合数为 m -k ⎪⎪⋅1⋅ k ⎪⎪= m -k ⎪⎪ k ⎪⎪。根据加法⎝⎭⎝⎭⎝⎭⎝⎭

原理，对k=0,1,2,⋯,m 作和，就有

⎛n ⎫⎛r ⎫⎛n -1⎫⎛r +1⎫⎛n -2⎫⎛r +2⎫⎛n -m ⎫⎛r +m ⎫⎛n +r +1⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ +++ + m ⎪ 0⎪ m -1⎪ 1⎪ m -2⎪ 2⎪ 0⎪⎪ m ⎪⎪= m ⎪⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭。

注：参见《 Combinatorial Problems and Exercise》 by L.Lovasz 0143.7 L896c

P 18-42 (i) P 96 P 172

(i)The number of those(n+r+1-m)-tuples of{1,2,⋯,n+r+1}Whose st (r +1) element is r+k+1is ⎛r +k ⎫⎛n -k ⎫ k ⎪⎪ m -k ⎪⎪. Summing for k=0,1,2,⋯,m,we ⎝⎭⎝⎭

get the result. 组合意义二：（格路方法）

等式左端：从点A(-r-1,0)到点

C(-1,k)(k=0,1,2,⋯,m) 直接经过点D(0,k)再到

点B(n-m,m)的路径数(参见本题图1) ；

等式右端：从点A(-r-1,0)到点B(n-m,m)

的路径数。 ⎛r ⎫⎛r +1⎫⎛r +2⎫⎛n ⎫⎛n +1⎫1.38 给出 ⎪+ ⎪+ ⎪+ + ⎪= ⎪的组合意义. r r r r r +1⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭

[证]. 组合意义一：

等式右端是从n+r+1个元素a 1, a 2, , a n +1中取出r+1个作不允许重复的组合，结果不外乎有以下几种情况(参见P 25等式3的组合意义) ：

(1) r+1个元素的组合中含有a 1

的，相当于从n 个元素a 2, a 3, , a n +1

⎛n ⎫中取r 个组合，其组合数为 （即A ）。 r ⎪⎪⎝⎭

(2)r+1个元素的组合中不含有

a 1，但又含有元素a 2的。即一个(r-1)-第16题图1

组合。依a 1来分，不外乎含a 1和不含a 1；不含a 1的又依a 2分，不外乎含a 2和不含a 2。不含a 1而含a 2的组合，相当于从n-1个元素a 2, a 3, , a n +1中取r 个元素的组合，然后加上a

2

⎛n -1⎫而成，其组合数为 r ⎪⎪即A 1 A 2。 ⎝⎭()

(3)r+1个元素的组合中不含a 1和a 2，但含有元素a 3的。即不含a 1, a 2的依a 3来分，不外乎含a 3和不含a 3。不含a 1, a 2而含a 3的组合，相当于从n-2个元素a 4, , a n +1中取出r 个元素的组合，然后再加上a 3而成，其组合数为 ⎛n -2⎫⎪⎪即A 1 A 2 A 3。 r ⎝⎭()

取出的r+1个组合元素中不含a 1, a 2, a 3, , a n -r -1，但含有元素a n -r 的。即不含a 1, a 2, a 3, , a n -r -1的，又依a n -r 来分，不外乎含有a n -r 和不含有a n -r 。不含a 1, a 2, , a n -r -1而含a n -r 的组合，相当于从n-(n-r-1)=r+1个元素a n -r , a n -r -1, , a n +1中取出r 个元素的组合

⎛r +1⎫而加上a n -r 而成，其组合数为 r ⎪⎪(即A 1 A 2 A n -r -1 A n -r ) 。 ⎝⎭

⎛r +1⎫⎛r ⎫(4)由a n -r +1, a n -r +2, , a n +1组成的(r+1)-组合的组合数为 r +1⎪⎪= r ⎪⎪ ⎝⎭⎝⎭

(即A 1 A 2 A n -r ) 。而且

A 1 (A 1 A 2) (A 1 A 2 A 3) (A 1 A 2 A n -r -1 A n -r )

(A 1 A 2 A n -r -1 A n -r ) =X(即全集)

组合意义二：

等式右端：从n+1个不同元素a 1,a 2, ⋯,a n ,a n+1, 中任选r+1个元素的组合方案数； 等式左端：从n+1个不同元素a 1,a 2, ⋯,a n ,a n+1, 中选取r+1个元素，一定选元素a r+k+1(k=0,1,2,⋯,n-r) ，但是不选元素a r+k+2, ⋯,a n ,a n+1的组合方案数。

1.39 证明

⎛m ⎫⎛m ⎫⎛m ⎫⎛m -1⎫⎛m ⎫⎛m -n ⎫n ⎛m ⎫ ⎪⎪+ ⎪⎪+ + ⎪⎪=2 ⎪ 0n 1n -1n 0⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝n ⎭

⎛m ⎫⎛m -r ⎫⎛m ⎫⎛n ⎫[证]. 借助P 28等式4，可知： r ⎪⎪ n -r ⎪⎪= n ⎪⎪ r ⎪⎪ (n≥r) (r=0,1,2,⋯,n)

⎝⎭⎝⎭⎝⎭⎝⎭

⎛m ⎫⎛m ⎫⎛m ⎫⎛m -1⎫⎛m ⎫⎛m -n ⎫⎛m ⎫⎛n ⎫⎛m ⎫⎛n ⎫⎛m ⎫⎛n ⎫⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ++ +=++ +从而有 0⎪ n ⎪ 1⎪ n -1⎪ n ⎪ 0⎪ n ⎪ 0⎪ n ⎪ 1⎪ n ⎪⎪ n ⎪⎪ ⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭

⎛m ⎫⎡⎛n ⎫⎛n ⎫⎛n ⎫⎤n ⎛m ⎫⎪ ⎪ ⎪ ⎪ = ++ +=2 n ⎪⎢ 0⎪ 1⎪ n ⎪⎥ n ⎪⎪(用了P 29等式5)

⎝⎭⎣⎝⎭⎝⎭⎝⎭⎦⎝⎭

组合意义一：

等式右端可看作从m 个元素中取出n 个元素进行组合。然后对这取出的n 个元素进行

⎛m ⎫n 染色（红，白）的所有方案，它为 n ⎪⎪2；

⎝⎭

⎛m ⎫等式左端可看作先从m 个元素中取出k 个元素（个数为 ，全部染以红色。再从剩 k ⎪⎪）

⎝⎭

⎛m -k ⎫下的(m-k)个元素中取出(n-k)个元素（个数为 ，全部染以白色。根据乘法原理，从 n -k ⎪⎪）

⎝⎭

⎛m ⎫⎛m -k ⎫m 个元素中取出n 个元素，k 个染上红色，(n-k)个染上白色的方案数为 k ⎪⎪ n -k ⎪⎪，

⎝⎭⎝⎭

k=0,1,2,⋯,n ；

而从m 个元素中取出n 个元素染以红白两色的方案可分解成有0个，1个，„，n 个染以红色的总和。故根据加法原理，17题成立。

组合意义二：

等式右端：将从m 个不同的小球中任意选出的n 个小球放入两个不同的合子里，注意到每个小球都有两种放法，就得到了可能的放球方案数；

等式左端：先从m 个球中任选k 个球放入第一个合子里(k=0,1,2,⋯,n) ，再从剩下的m-k 个球中任选n-k 个球放入第二个合子里，然后对k 从0到n 求和，就得到了所有可能的放球方案数。

1.40 从n 个人中选r 个围成一个圆圈，问有多少种不同的方案？

⎧a 1, a 2, , a r -1, a r ⎪⎪a 2, a 3, a r , a 1[解]. 每一个r 个人围成的圈（圆排列）a 1, a 2, , a r -1, a r ⇔(线排列) ⎨ ⎪⎪⎩a r , a 1, a r -2, a r -1

即每一个r 圈相当于r 个r 排列。故不同的方案数为N =11n ! P (n , r ) =r r (n -r )!

若不计顺逆方向，则为N =11n ! 。 P (n , r ) =⋅2r 2r (n -r )!

1.41 分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法.

[解]. （略）

1.42 (a) 按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法.

(b) 写出按照邻位对换法由给定排列生成其下一个排列的算法.

[解]. （略）

1.43 对于给定的正整数n ，证明，当

⎧n -1n +1或，若n 是奇数⎪⎪22k =⎨时，C(n,k)的最大值.

⎪n ，若n 是偶数⎪⎩2

[证] 取C (n,k)与C (n,k-1)进行比较。C (n,k)/C (n,k-1)=(n-k+1)/k。

当k 1，即C (n,k)>C (n,k-1)；

当k >n/2时，(n-k+1)/k

因此，得到当k=n/2或最接近n/2时，C (n,k)取得最大值。

1.44 (a) 用组合方法证明(2n )! (3n )! 和都是整数. n n n 22⨯3

(n 2)! (b) 证明是整数. (n !) n +1

[证] (a)考虑2n 个不同的球放入n 个不同的合子里，每合两个的方案数。这个方案数应该是整数。

对2n 个球进行排列的方案数为(2n)!。而把2个球放入同一个合子里不计顺序，重复因子是2。n 个合子内部的排列共重复计算了2n 次，故总的重复因子是2n 。因此，把2n 个不

(2n )! (2n )! 同的球放入n 个不同的合子里，每合两个的方案数是n 。所以，n 是整数。 22

同理，考虑3n 个不同的球放入n 个不同的合子里，每合3个的方案数。这个方案数应该是整数。

对3n 个球进行排列的方案数为(3n)!。而把3个球放入同一个合子里不计顺序，重复因子是3!=2⋅3。n 个合子内部的排列共重复计算了2n ⋅3n 次，故总的重复因子是2n ⋅3n 。因此，

(3n )! (3n )! 把3n 个不同的球放入n 个不同的合子里，每合3个的方案数是n n 。所以，n n 是整2⋅32⋅3

数。

(b)考虑n 2个不同的球放入n 个相同的合子里，每合n 个的方案数。这个方案数应该是整数。

对n 2个球进行排列的方案数为(n2)! 。而把n 个球放入同一个合子里不计顺序，重复因子是n! 。n 个合子内部的排列共重复计算了(n!)n 次，故重复因子是(n!)n 。另外，由于n 个合子相同，放入不同的合子是没有区别的，其重复因子是n! 。故此，总的重复因子是(n!)n+1。

(n 2)! (n 2)! 因此，把n 个不同的球放入n 个相同的合子里，每合n 个的方案数是。n +1(n ! ) n +1(n ! ) 2

是整数。

1.45 (a) 在2n 个球中，有n 个相同. 求从这2n 个球中选取n 个的方案数.

(b) 在3n+1个球中，有n 个相同. 求从这3n+1个球中选取n 个的方案数.

[解] (a)相当于从n 个不同的小球中取出m 个小球(0≤m ≤n), 再从n 个相同的小球中取出n-m 个小球，m=0,1,2,⋯,n 的方案数。

根据加法原理，这个方案数应该是：C (n,0)+ C(n,1)+⋯+ C(n,n)=2n 。

同理，考虑3n 个不同的球放入n 个不同的合子里，每合3个的方案数。这个方案数应该是整数。

(b)相当于从2n+1个不同的小球中取出m 个小球(0≤m ≤n), 再从n 个相同的小球中取出

n-m 个小球，m=0,1,2,⋯,n 的方案数。

根据加法原理，这个方案数应该是：C (2n+1,0)+ C(2n+1,1)+⋯+ C(2n+1,n)。

1.46 证明在由字母表{0, 1, 2}生成的长度为n 的字符串中

(a) 0出现偶数次的字符串有3n +1个； 2

⎛n ⎫n ⎛n ⎫n -2⎛n ⎫n -q 3n +1⎡n ⎤=, 其中q =2⎢⎥ (b) ⎪2+ ⎪2+ + ⎪22⎣2⎦⎝0⎭⎝2⎭⎝q ⎭

[证] (a)方法一：采用（串值）数学归纳法

31+1［基始］当n=1时，0出现偶数次，长度为1的字符串有=2个（即1和2两个2

长度为1的字符串）。所证结论成立；

［归纳假设］当n=m(1≤m ≤k) 时，假设所证结论成立。即，0出现偶数次，长度为m 的3m +1字符串有个； 2

［归纳］当n=k+1时，0出现偶数次，长度为k+1的字符串包括两部分：

(1)给0出现偶数次，长度为k 的字符串后面再增加一位不是0的数（只能是1或2），3k +1因此，按乘法原理，由归纳假设，此种字符串有⋅2=3k +1个； 2

(2)给0出现奇数次，长度为k 的字符串后面再增加一位是0的数，因此，按乘法原理，⎛k 3k +1⎫3k -1由归纳假设，此种字符串有 3-2⎪⎪⋅1=2个；

⎝⎭

所以，按加法原理，0出现偶数次，长度为k+1的字符串共有

3k -13k +1+1(3+1)+= 个。所证结论成立；归纳完毕。 22k 方法二：采用指数型母函数方法

设：a n —0出现偶数次，长度为n 的字符串的个数，则{an }的指数型母函数

x n

A (x ) =∑a n ⋅n ! n =0∞

x 2x 4x 6x x 2x 3

=(1++++ )(1++++ ) 2! 4! 6! 1! 2! 3!

e x +e -x

2x =⋅e 2 3x x e +e =2

13x (3x ) 2(3x ) 3x x 2x 3

=[(1++++ ) +(1++++ )]21! 2! 3! 1! 2! 3!

1(3+1) x (32+1) x 2(33+1) x 3

=[(1+1) ++++ ]21! 2! 3!

3n +1所以，a n =（规定a 0=1）。 2

(b)利用组合意义法来证

3n +1考虑0出现偶数次，长度为n 的字符串的个数。根据上面(a)，已证其个数为； 2

⎛n ⎫另一方面，相当于先从n 个位置中选取2m (0≤2m ≤n ) 个（有 2m ⎪⎪种选择）放置上数

⎝⎭

⎛n ⎫n -2m 0, 再在剩下的n-2m 个位置上放置数1或2（有2n-2m 种放法），按乘法原理，是 2m ⎪⎪2⎝⎭

⎢n ⎥个，m=0,1,2,⋯,q (q =2⎢⎥) 的方案数。 ⎣2⎦

⎛n ⎫n ⎛n ⎫n -2⎛n ⎫n -q ⎪ ⎪ 按加法原理，此方案数为 2+2+ + 0⎪ 2⎪ q ⎪⎪2。因此，我们有 ⎝⎭⎝⎭⎝⎭

⎛n ⎫n ⎛n ⎫n -2⎛n ⎫n -q 3n +1 0⎪⎪2+ 2⎪⎪2+ + q ⎪⎪2=2。 ⎝⎭⎝⎭⎝⎭

1.47 5台教学机器m 个学生使用. 使用第1台和第2台的人数相等，有多少种分配方案？

[解] 先从m 个学生中选取k 个使用第1台机器，再从剩下的m-k 个学生中选取k 个使用第2台机器，其余m-2k 个学生可以任意使用剩下的3台机器，按乘法原理，其组合数为C (m,k)

⎢m ⎥C (m -k , k ) ⋅3(m -2k ) 。这里k=0,1,2,⋯,q (q =⎢⎥) ，于是，按加法原理，共有 ⎣2⎦

∑C (m , k ) C (m -k , k ) ⋅3

k =0q (m -2k ) 种使用方案。 1.48 在由n 个0及n 个1构成的字符串中，在任意前

k 个字符中，0的个数不少于1的个数的字符串有多

少？

[解] 转化为格路问题（弱领先条件—参见P36例4该例是强领先条件）。即从(0,0)到(n,n)，只能从对角线上方走，但可以碰到对角线。它可看作是从(0,1)到(n,n+1)

的强领先条件（只能从对角线上方走，但不可以碰到

对角线）的格路问题。更进一步的，它可看作是从(0,0)到(n,n+1)的强领先条件的格路问题(因为此种格路第一步必到(0,1)格点) 。故这样的字符串有

⎛n -0+(n +1) -1⎫⎛n -1+(n +1) -0⎫ ⎪- ⎪=C (2n , n ) -C (2n , n -1) n n -1⎝⎭⎝⎭

1.49 在1到n 的自然数中选取不同且互不相邻的k 个数，有多少种选取方案？

[解] 设：g (n,k)为从1~n中选取不同且互不相邻的k 个数的方案数。

于是，按这k 个数中有无数n 而分为两种情况：(1)若选n ，则必不能选n-1，故此种方

案数为g (n-2,k-1)；(2)若不选n ，则可以选n-1，故此种方案数为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。

1.50 (a) 在由5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个？

(b) 在m 个0，n 个1组成的字符串中，出现01或10的总次数为k 的字符串，有多少个？

[解] (a)先将5个0排成一列：00000，一个1若插在两个0中间，就形成一个“010”，则同时出现“01”和“10”，计数为2；若插在两端，则仅出现一个01”或“10”，计数为1。

现在要出现01”或“10”的总次数为4，可有两种办法：

(1)先把两个1插入五个0所形成的四个空档内，再将剩下的两个1放在已插入的1的前面，比如：011100100。按乘法原理，有C (4,2)⋅C (2+2-1,2)= C(4,2)⋅C (3,2)种方案；

(2)先把一个1插入五个0所形成的四个空档内，然后取两个1分别插入两端，剩下的一个1放在已插入的1的前面，比如：100011001。按乘法原理，有C (4,1)⋅3种方案；

最后，按加法原理，总的方案数为C (4,2)⋅C (3,2)+C (4,1)⋅3=30。

k -1个1插入m 个0所形成的m-1个空档内，2

k +1k +1然后取一个1插入头或尾，最后将剩下的n -个1放在已插入的个1的前面，形22

成出现k 个01或10的格局。按乘法原理，总的方案数为 (b)若k 为奇数，则只有一种办法：先把

2⋅C (m -1, k -1k +1k +1k +1k -1k +1) C (n -+-1, n -) =2⋅C (m -1, ) C (n -1, n -) ； 222222

k k 个1插入m 个0所形成的m-1个空档内，再将剩下n -的个1放在已插入22若k 为偶数，则现在可有两种办法： (1)先把

的k 个1的前面，形成出现k 个01或10的格局。按乘法原理，有 2

k k k k k k C (m -1, ) C (n -+-1, n -) =C (m -1, ) C (n -1, n -) 种方案； 222222

k -2个1插入m 个0所形成的m-1个空档内，然后取两个1分别插入两端，2

k +2k +2再将剩下的n -个1放在已插入的个1的前面，形成出现k 个01或10的格局。22

按乘法原理，有 (2)先把

C (m -1, k -2k +2k +2k +2k -2k +2) C (n -+-1, n -) =C (m -1, ) C (n -1, n -) 222222种方案；

最后，按加法原理，总的方案数为

k k k -2k +2C (m -1, ) C (n -1, n -) +C (m -1, ) C (n -1, n -) 。 2222

1.51 从N={1, 2, … , 20}中选出3个数，使得没有两个数相邻，有多少种方案？

[解] 方法一（采用排除法）

在20个数中选取3个数都不相邻的方案数；

从1～20这20个数中选取3个数，总数为 ⎛20⎫⎪ ⎪⎝3⎭

然后在其中去掉有3个数相邻的方案数，也要去掉有两个数相邻的方案数。这样，就是在20个数中选取3个数都不相邻的方案数。

设选取的3个数a 1，a 2，a 3。

如果这三个数相邻，若a 1≢a 2≢a 3，则1≢a 1≢18。故此种方案有18个。

如果有两个数相邻，不妨设是a 1a 2，且a 1≢a 2，则1≢a 1≢19，但是，当a 1＝1或19时，a 2＝2或20，a 3只有3和18不能选，故a 3有3个数不能选，17种选择方案；当a 1≠1或19时，a 3有4个数不能选。故a 3有16种选择，因此，此种方案数为：

2×17＋17×16

故此，从1～20这20个数种选取3个互不相邻的数的方案数为：

⎛20⎫ 3⎪⎪-18-(2⨯17+17⨯16) =816 ⎝⎭

方法二（采用一一对应技术）

设：A:从1～20这20个数中选取三个数a 1，a 2，a 3，使得无两数相邻的方案集。 B ：从1～18这18个数中选取三个数b 1，b 2，b 3，使得三数可相邻的方案集。

这里，a 1

设：b 1

建立双射函数h ：A →B ，使得：

h(a 1, a 2, a 3)=(b 1, b 2, b 3)

⎧b 1=a 1⎪⎨b 2=a 2-1

⎪b =a -23⎩3

其有逆函数h :B→A, -1

h -1（b 1，b 2，b 3）＝（a 1，a 2，a 3）

⎧a 1=b 1⎪⎨a 2=b 2+1

⎪a =b +23⎩3

故此，根据一一对应技术，有A =B = 3⎪⎪=816 ⎝⎭

1.52 从N={1, 2, … , n}中选出k 个数，使之没有两数相邻，求不同方案数.

[解] （采用一一对应技术）

设：A ：从1～n 这n 个数中选取k 个数a 1，a 2，„，⎛18⎫a k ，使之无二数相邻的方案集。 B ：从1～n-k+1这n-k+1个数中选取k 个数b 1，b 2，„，

这里：①

②b k ，二数可相邻的方案集。 a 1

建立双射函数：h ：A →B

h(a 1, a 2, „, a k )=(b 1, b 2, „, b k )

⎧b 1=a 1⎪b =a -1⎪22⎨⎪

⎪⎩b k =a k -(k -1)

其逆函数为：h :B→A

⎧b 1=a 1⎪b =a -1⎪22⎨⎪

⎪⎩a k =b k +(k -1) -1

故此，根据一一对应技术，有：

⎛n -k +1⎫⎪A =B = k ⎪⎝⎭

1.53 把n 个无区别的球放进有标志1, 2, … , n的n 个盒子中，每个盒子可放多于一个球，求有多少种方案？

[解] （采用一一对应技术）

设：A ：将n 个无区别的球放进n 个有区别的盒子中，每盒球数不限的方案集。

B ：n 个“*”，n-1个隔档“1”构成的线性图案集。

于是一种放球方案与一种图案一一对应，根据一一对应技术，有

A =B =(2n -1)! ⎛2n -1⎫⎪= ⎪n -1n ! (n -1)! ⎝⎭

1.54 m个1，n 个0进行排列，求1不相邻的排列数. 设n>m.

[解] n个0有n+1个空隙（内外都计），选取m 个空隙（可以选取，因为m

⎛n +1⎫ m ⎪⎪⎝⎭ m 个1 ，每空插入一个1，使得后两个1相邻。故其方案数为：

1.55 偶数位的对称数，即从左向右读法与从右向左的读法相同，如3223. 试证这样的数可被11整除.

[证] 此种偶数位得对称数《形式语言》称为迴文。

设任一个这样得数m 有2n 位，故有：

m =a 1⋅102n -1+a 2⋅102n -2+ +a n ⋅10n +a n ⋅10n -1+ +a 2⋅10+a 1

=a 1(102n -1+1) +a 2(102n -2+10) + +a n (10n +10n -1)

=a 1(102n -1+1) +a 2⋅10⋅(102n -3+1) + +a n ⋅10n -1⋅(10+1)

由于10+1=(10+1)(10k k -1 -10k -2+ +(-1)k -1) （当k 是奇数时），故10k +1可被11整除。

1.56 n个男人与n 个女人沿一圆桌坐下，问两个女人之间坐一个男人的方案数. 又m 个女人n 个男人，且m

[解] ○1先将n 个女人进行圆排列，共有Q n =(n-1)! 种方法，再将n 个男人插入n 个女人形成得n 个空位中，则有n! 种方法。故按乘法原理，此种方案数为(n-1)!×n! 个。

n 2先将n 个男人进行圆排列，共有Q n =(n-1)! 种方法，再将m 个女人插入n 个男人形○n

成得n 个空位中。则有P (n , m )=n ! n ! (n -1)! ⋅ 。按乘法原理，此种排法有(n -m )! (n -m )!

1.57 n个人分别沿着两圆桌坐下，一张r 个人，另一张n-r 个人，试问有多少种不同的方案？

⎛n ⎫ r ⎪⎪r Q ⎝⎭r [解] 先从n 个人中选取r 个人，有种选法，然后将r 个人排成一圆桌，有=(r-1)!种

方法，再将其余(n-r)个人排成一圆桌n -r Q n -r =(n-r-1)!种方法，故共有

n ! n ! ⎛n ⎫(r -1)! (n -r -1)! = ⎪(r-1)!(n-r-1)!= ×× r ⎪r ! (n -r )! r (n -r ) ⎝⎭

1.58 一圆周上n 个点标以1, 2, …, n. 每一点与其他n-1个点连以直线，试问这些直线交于圆内有多少点？

[解] 每4个点形成矩形，其对角线有一个交点，故圆内交点有：

C (n , 4) =

n (n -1)(n -2)(n -3) 1=n (n -1)(n -2)(n -3) 4⨯3⨯2⨯124