组合数学复习题.doc

1-23.(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-24.证明在由字母表{0,1,2}生成的长度为n的字符串中
(a)0出现偶数次的字符串有个；
(b),其中
[证].(a)方法一：采用（串值）数学归纳法
［基始］当n=1时，0出现偶数次，长度为1的字符串有=2个（即1和2两个长度为1的字符串）。所证结论成立；
［归纳假设］当n=m(1£m£k)时，假设所证结论成立。即，0出现偶数次，长度为m的字符串有个；
［归纳］当n=k+1时，0出现偶数次，长度为k+1的字符串包括两部分：
(1)给0出现偶数次，长度为k的字符串后面再增加一位不是0的数（只能是1或2），因此，按乘法原理，由归纳假设，此种字符串有×2=3k+1个；
(2)给0出现奇数次，长度为k的字符串后面再增加一位是0的数，因此，按乘法原理，由归纳假设，此种字符串有×1=个；
所以，按加法原理，0出现偶数次，长度为k+1的字符串共有
(3k+1)+= 个。所证结论成立；
归纳完毕。
方法二：采用指数型母函数方法
设：an—0出现偶数次，长度为n的字符串的个数，则{an}的指数型母函数

所以，（规定a0=1）。
(b)利用组合意义法来证
考虑0出现偶数次，长度为n的字符串的个数。根据上面(a)，已证其个数为；
另一方面，相当于先从n个位置中选取2m(0£2m£n)个（有种选择）放置上数0,再在剩下的n-2m个位置上放置数1或2（有2n-2m种放法），按乘法原理，是个，m=0,1,2,¼,q ()的方案数。
按加法原理，此方案数为。因此，我们有
。
(n+1,n+1)
(0,1)
(1,0)
(n,n+1)
(n,n)
(0,0)
第26题图1
1-26.在由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)格点)。故这样的字符串有
-=C(2n,n)-C(2n,n-1)个。

1-27.在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。
2-18.在一圆周上取n个点，每一对顶点可做一弦。不存在三弦共点的现象，求弦把圆分割成几部分？
v5
v6
v1
第14题图
v4
v3
v2
v7
[解].(参见 P98例6)
设an为过n个点的每两点作一条弦，且不存在三弦共点的现象，弦把圆分割成部分的个数。其中过n-1个点所作弦把圆分割成的部分为an-1，第n个点可以引出n-1条弦，第一条弦增加一个部分，第二条弦增加1×(n-3)+1个部分，第三条弦增加2×(n-4)+1个部分，……，第k条弦增加(k-1)×(n-k-1)+1个部分，……，第n-1条弦增加(n-1-1)×(n-(n-1)-1)+1=1个部分。

故
=
=
=
=
且 ，，，，
从而有 　　
于是 　　
同理可得
故有
同理可得
故有
同理可得
故有
同理可得
故有
对应的特征方程为
即 r=1是5重根
所以

n=2时，a2=A=2
n=3时，a3=A+B=4，B=2
n=4时，a4=A+2B+C=8，C=2
n=5时，a5=A+3B+3C+D=16，D=2
n=6时，a6=A+4B+6C+4D+E=31，E=1
故
或
或 。

2-19.求n位二进制数中相邻两位不出现11的数的个数。
[解].设：an—n位二进制数种相邻两位不出现11的数的个数；
n位二进制数种相邻两位不出现11的数的个数，可分为两个部分：
(1)第n位是0，这时第n-1位既可以是0又可以是1，故从第1位到第n-1位形成n-1位二进制数中相邻两位不出现11的数，相应的数的个数为an-1；
(2)第n位是1，这时第n-1位只能是0，第n-2位既可以是0又可以是1，故从第1位到第n-2位形成n-2位二进制数中相邻两位不出现11的数，相应的数的个数为an-2；
因此，按加法原理，n位二进制数中相邻两位不出现11的数的个数
an= an-1+an-2 。
初始条件a1=2，a2=3
因此，显然有an=Fn+2
所以，n位二进制数中相邻两位不出现11的数的个数是
。

2-20.从n个文字中取k个文字作允许重复的排列，但不允许一个文字连续出现三次，求这样的排列的数目。
[解].设：ak—从n个文字中取k个文字作允许重复的排列，没有一个文字连续出现三次，这样的排列的数目；
从n个文字中取k个文字作允许重复的排列，没有一个文字连续出现三次，这样的排列的数目，可分为两个部分：
(1)第k位与第k-1位不相同，因此，在前k-1位已形成满足条件的k-1位排列时，第k位只能有n-1种选择，相应的排列个数为(n-1)ak-1；
(2)第k位与第k-1位相同，因此，在前k-2位已形成满足条件的k-2位排列时，第k位与第k-1位一起只有n-1种选择，相应的排列个数为(n-1)ak-2；
因此，按加法原理，从n个文字中取k个文字作允许重复的排列，没有一个文字连续出现三次，这样的排列的数目
ak=(n-1)ak-1+(n-1)ak-2 。
初始条件：a1=n，a2=n2，a3=n3-n
特征方程为：r2-(n-1)r-(n-1)=0
特征根为：，
故递归方程的通解为：ak=A×ak+B×bk
利用初始条件可得方程组：
Aa+Bb=n
Aa2+Bb2=n2
利用特征根a，b满足特征方程，可得方程组：

解之，得

所以，从n个文字中取k个文字作允许重复的排列，没有一个文字连续出现三次，这样的排列的数目
。
2.42. 设{an}满足an - an-1- an-2 = 0，{bn}满足bn - 2bn-1- bn-2 = 0，cn = an + bn，n =0, 1, 2, 3, ¼，试证序列{cn}满足一个四阶线性常系数齐次递推关系。
[解]方法一：(特征系数法)
由于序列{an}满足递推关系：an - an-1- an-2 = 0 j
故显然也满足递推关系：
(an - an-1- an-2) + A1(an-1 - an-2- an-3) + A2(an-2 - an-3- an-4) = 0
这里A1，A2为任意常数
整理为：an + (A1 - 1)an-1+ (A2 - A1 - 1)an-2 - (A1 + A2)an-3 - A2an-4 = 0 k
由于序列{bn}满足递推关系：bn - 2bn-1- bn-2 = 0
故显然也满足递推关系：
(bn - 2bn-1- bn-2) + B1(bn-1 - 2bn-2- bn-3) + B2(bn-2 - 2bn-3- bn-4) = 0
这里B1，B1为任意常数
整理为：bn + (B1 - 2)bn-1+ (B2 - 2B1 - 1)bn-2 - (B1 + 2B2)bn-3 - B2bn-4 = 0 l
令：
解之得：，
将此解代入k和l，有：an - 3an-1 + 3an-3 + an-4 = 0 m
bn - 3bn-1 + 3bn-3 + bn-4 = 0 n
将m+n，并注意到cn = an + bn，我们有：
cn - 3cn-1 + 3cn-3 + cn-4 = 0 o
这就是序列{cn}所满足的四阶线性常系数齐次递推关系。
方法二：(特征根法)
序列{an}的递推关系：an - an-1- an-2 = 0
特征方程：g 2 - g - 1 = 0
特征根：g1 =，g2 =
故其通解为：bn = A×()n + B×()n
序列{bn}的递推关系：bn - 2bn-1- bn-2 = 0
特征方程：g 2 - 2g - 1 = 0
特征根：g1 =，g2 =
故其通解为：bn = C×()n + D×()n
于是有：cn = an + bn = A×()n + B×()n + C×()n + D×()n
因此序列{cn}所满足的线性常系数齐次递推关系的特征多项式为：
(g -)(g -)[g -()][g -()] = 0
整理为：(g 2 - g - 1)(g 2 - 2g - 1) = 0
再整理为：g 4 - 3g 3 + 3g + 1 = 0
因此，对应的四阶线性常系数齐次递推关系为：cn - 3cn-1 + 3cn-3 + cn-4 = 0 。

2.43.在习题2.42中，若cn = anbn，试讨论之。
[解](特征根法)
序列{an}的递推关系：an - an-1- an-2 = 0
特征方程：g 2 - g - 1 = 0
特征根：g1 =，g2 =
故其通解为：bn = A×()n + B×()n
序列{bn}的递推关系：bn - 2bn-1- bn-2 = 0
特征方程：g 2 - 2g - 1 = 0
特征根：g1 =，g2 =
故其通解为：bn = C×()n + D×()n
于是有：cn = anbn = [A×()n + B×()n ][C×()n + D×()n]
= AC×()n()n + AD×()n()n
+ BC×()n()n + BD×()n()n
因此序列{cn}所满足的线性常系数齐次递推关系的特征多项式为：
[g -()][g -()]
[g -()][g -()] = 0
整理为：[g 2 - ()g - ()2][g 2 - ()g - ()2] = 0
再整理为：g 4 - 2g 3 - 7g 2 - 2g + 1 = 0
因此，对应的四阶线性常系数齐次递推关系为：cn - 2cn-1- 7cn-2 - 2cn-3 + cn-4 = 0 。

2.44. 设{an}和{bn}均满足递推关系xn + b1xn-1+ b2xn-2 = 0，试证：
(a) {anbn}满足一个三阶齐次线性常系数递推关系；
(b) a0, a2, a4, ¼ 满足一个二阶线性常系数齐次递推关系。
[证](a)(特征根法)
二阶齐次线性常系数递推关系xn + b1xn-1+ b2xn-2 = 0的特征方程为：
x2 + b1x + b2 = 0
设其特征根为g1，g2
(1)如果 g1 ¹ g2 ，则有：an = A×+ B× ，bn = C×+ D×
于是：cn = anbn = (A×+ B×)(C×+ D×)
= AC×()n + (AD + BC)×(g1g2)n + BD×()n
这说明{cn}满足一个三阶齐次线性常系数递推关系。
其特征方程为：(x -)(x -g1g2)(x -) = 0
整理为：x3 - (+ g1g2 +)x2 + (+ +)x - (g1g2)3 = 0
由于g1 + g2 = - b1，g1g2 = b2，故+ g1g2 +=- b2
因此有：x3 - (- b2)x2 + b2(- b2)x -= 0
故此{cn}满足如下的三阶齐次线性常系数递推关系：
cn - (- b2)cn-1 + b2(- b2)cn-2 -cn-3 = 0 。
(2)如果 g1 = g2 = g ，是一个二重根，则有：an = (A + Bn)×g n ，bn = (C + Dn)×g n
于是：cn = anbn = (A + Bn)×g n(C + Dn)×g n = [AC + (AD + BC)n + BDn2]×(g 2)n
这说明{cn}满足一个三阶齐次线性常系数递推关系。
其特征方程为：(x3 -g 2)3 = 0
整理为：x3 - 3g 2x2 + 3g 4x -g 6 = 0
由于2g = - b1，g 2 = b2
因此有：x3 - 3b2x2 + 3x -= 0
故此{cn}满足如下的三阶齐次线性常系数递推关系：
cn - 3b2cn-1 + 3cn-2 -cn-3= 0 。
(b) (特征根法)
二阶齐次线性常系数递推关系xn+b1xn-1+b2xn-2 = 0的特征方程为
x2+ b1x+b2 = 0
设其特征根为g1，g2
(1)如果 g1 ¹ g2 ，则有：an = A×+B×
于是 a2n = A×+B×
因此，这说明{a2n}满足一个二阶齐次线性常系数递推关系
其特征方程为 (x-)(x-) = 0
整理为： x2-(+)x+×= 0
由于 g1+g2 = - b1，g1×g2 = b2 ，故有 +=- 2b2
于是 x2-(- 2b2)x+= 0
故此序列{a2n}满足一个二阶齐次线性常系数递推关系为：
cn -(- 2b2)cn-1 +cn-2= 0 。
(2)如果 g1 = g2 = g ，是一个二重根，则有：an = (A×+Bn)×gn
于是 a2n = (A×+Bn)×(g 2)n
因此，这说明{a2n}满足一个二阶齐次线性常系数递推关系
其特征方程为 (x-g 2)2 = 0
整理为： x2-2g 2x+g 4= 0
由于 2g = - b1，g 2= b2，
于是 x2-2b2x+= 0
故此序列{a2n}满足一个二阶齐次线性常系数递推关系为：
cn -2b2cn-1 +cn-2= 0 。

j
3.22.求满足条件：x1+x2+x3=20
3£ x1£9，0£ x2£8，7£ x3£17
的整数解的数目。
[解].方法一：利用容斥原理二
不定方程j与如下的不定方程k等价：
k
x1+x2+x3=10
0£ x1£6，0£ x2£8，0£ x3£10
(这可通过作变换来实现)。
对应于不定方程k的不受限的不定方程为：
l
x1+x2+x3=10
x1³0，x2³0，x3³0
设：X={x|x=(x1,x2 ,x3)是不定方程l的解};
A1={ x|x=(x1,x2 ,x3) 是不定方程l的解且x1³6+1=7};
A2={ x|x=(x1,x2 ,x3) 是不定方程l的解且x2³8+1=9};
A3={ x|x=(x1,x2 ,x3) 是不定方程l的解且x3³10+1=11};
因此,根据定理3.6.4.可知，不定方程l的解的数目：

p0=|X|=====66
A1对应的不定方程是：
m
x1+x2+x3=10
x1³7，x2³0，x3³0
令： (x1³0, x2³0, x3³0)。利用m我们得到：
x1+x2+ x3=( x1-7)+ x2+ x3=( x1+x2+x3)-7=10-7=3
所以不定方程m的解与下列不定方程：
m¢
x1+x2+ x3=3
x1³0, x2³0, x3³0
的解一一对应。故根据定理3.6.4.可知，不定方程m的解的数目为：
|A1|=====10
同理可得：
|A2|===3

A3对应的不定方程是：
n
x1+x2+x3=10
x1³0，x2³0，x3³11
由于解若满足条件x1³0，x2³0，x3³11，则有
x1+x2+x3³0+0+11=11>10
故不定方程n没有解，即
|A2|=0
因此p1=|A1|+|A2|+|A3|=10+3+0=13
A1ÇA2对应的不定方程是：
o
x1+x2+x3=10
x1³7，x2³9，x3³0
由于解若满足条件x1³7，x2³9，x3³0，则有
x1+x2+x3³7+9+0=16>10
故不定方程o没有解，即
|A1ÇA2|=0
同理可得：|A1ÇA3|=0，|A2ÇA3|=0
因此p2=|A1ÇA2|+|A1ÇA3|+|A2ÇA3|=0+0+0=0

A1ÇA2ÇA3对应的不定方程是：
p
x1+x2+x3=10
x1³7，x2³9，x3³11
由于解若满足条件x1³7，x2³9，x3³11，则有
x1+x2+x3³7+9+11=27>10
故不定方程p没有解，即
p3=| A1ÇA2ÇA3|=0
所以，不定方程k、也即不定方程j的解的数目为：
q0=||= p0-p1+ p2- p3=66-13+0-0=53 。
方法二：利用母函数方法
不定方程j对应的母函数是：
(1+x+x2+x3+x4+x5+x6)(1+x+x2+x3+x4+x5+x6+x7+x8)(1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10)
=(1+2x+3x2+4x3+5x4+6x5+7x6+7x7+7x8+6x9+5x10+4x11+3x12+2x13+x14) (1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10)
不定方程j的解的数目为上述母函数中x10的系数：
1´1+2´1+3´1+4´1+5´1+6´1+7´1+7´1+7´1+6´1+5´1
=1+2+3+4+5+6+7+7+7+6+5
=53 。

3.23.求满足下列条件：
j
x1+x2+x3=40
6£ x1£15，5£ x2£20，10£ x3£25
的整数解的数目。
[解].(仿3.22题)方法一.利用容斥原理二，不定方程j与如下的不定方程k等价：
k
x1+x2+x3=19
0£ x1 £9，0£ x2 £15，0£ x3 £15
(这可通过作变换来实现)。
对应于不定方程k的不受限的不定方程为：
l
x1+x2+x3=19
x1³0，x2³0，x3³0
设：X={x|x=(x1,x2 ,x3)是不定方程l的解};
A1={ x|x=(x1,x2 ,x3) 是不定方程l的解且x1³9+1=10};
A2={ x|x=(x1,x2 ,x3) 是不定方程l的解且x2³15+1=16};
A3={ x|x=(x1,x2 ,x3) 是不定方程l的解且x3³15+1=16};
因此,根据定理3.6.4.可知，不定方程l的解的数目：
p0=|X|=====210
A1对应的不定方程是：
m
x1+x2+x3=19
x1³10，x2³0，x3³0
令： (x1³0, x2³0, x3³0)。利用m我们得到：
x1+x2+ x3=( x1-10)+ x2+ x3=( x1+x2+x3)-10=19-10=9
所以不定方程m的解与下列不定方程：
m¢
x1+x2+ x3=9
x1³0, x2³0, x3³0
的解一一对应。故根据定理3.6.4.可知，不定方程m的解的数目为：
|A1|=====55
同理可得：
|A2|=====10
|A3|=====10
因此p1=|A1|+|A2|+|A3|=55+10+10=75
A1ÇA2对应的不定方程是：
n
x1+x2+x3=19
x1³10，x2³16，x3³0
由于解若满足条件x1³10，x2³16，x3³0，则有
x1+x2+x3³10+16+0=26>19
故不定方程n没有解，即
|A1ÇA2|=0
同理可得：|A1ÇA3|=0，|A2ÇA3|=0
因此p2=|A1ÇA2|+|A1ÇA3|+|A2ÇA3|=0+0+0=0
A1ÇA2ÇA3对应的不定方程是：
o
x1+x2+x3=19
x1³10，x2³16，x3³16
由于解若满足条件x1³10，x2³16，x3³16，则有
x1+x2+x3³10+16+16=42>19
故不定方程o没有解，即
p3=| A1ÇA2ÇA3|=0
所以，不定方程k、也即不定方程j的解的数目为：
q0=||= p0-p1+ p2- p3=210-75+0-0=135 。
方法二：利用母函数方法
不定方程k对应的母函数是：
(1+x+x2+x3+x4+x5+x6+x7+x8+x9) (1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15)2

=(1-x10-2x16+2x26+x32-x42)
(参见第三版习题2.16(P199)或第二版第二章习题7(P131))
不定方程j的解的数目为上述母函数中x19的系数：
1´-1´-2´
=--2´
=210-55-20
=135 。

3.24.求满足下列条件的整数解的数目：
j
x1+x2+x3+x4=20
1£ x1£5，0£ x2£7，4£ x3£8，2£ x4£6。
[解].(仿题3.22)方法一：利用容斥原理二，不定方程j与如下的不定方程k等价：
k
x1+x2+x3+x4=13
0£ x1£4，0£ x2£7，0£ x3£4，0£ x4£4
(这可通过作变换来实现)。
对应于不定方程k的不受限的不定方程为：
l
x1+x2+x3+x4=13
x1³0，x2³0，x3³0，x4³0
设：X={x|x=(x1,x2 ,x3,x4)是不定方程l的解};
A1={ x| x=(x1,x2 ,x3,x4)是不定方程l的解且x1³4+1=5};
A2={ x| x=(x1,x2 ,x3,x4)是不定方程l的解且x2³7+1=8};
A3={ x| x=(x1,x2 ,x3,x4)是不定方程l的解且x3³4+1=5};
A4={ x| x=(x1,x2 ,x3,x4)是不定方程l的解且x4³4+1=5};
因此,根据定理3.6.4.可知，不定方程l的解的数目：
p0=|X|=====560
A1对应的不定方程是：
m
x1+x2+x3+x4=13
x1³5，x2³0，x3³0，x4³0
令： (x1³0, x2³0, x3³0, x4³0)。利用m我们得到：
x1+x2+ x3+x4=( x1-5)+ x2+ x3+x4=( x1+x2+x3+x4)-5=13-5=8
所以不定方程m的解与下列不定方程：
m¢
x1+x2+x3+x4=8
x1³0, x2³0, x3³0, x4³0
的解一一对应。故根据定理3.6.4.可知，不定方程m的解的数目为：
|A1|=====165
同理可得：
|A2|=====56
|A3|=====165
|A4|=====165
因此 p1=|A1|+|A2|+|A3|+|A4|=165+56+165+165=551
A1∩A2对应的不定方程是：
n
x1+x2+x3+x4=13
x1³5，x2³8，x3³0，x4³0
令： (x1³0, x2³0, x3³0, x4³0)。利用n我们得到：
x1+x2+x3+x4=(x1-5)+(x2-8)+ x3+x4=( x1+x2+x3+x4)-(5+8)=13-13=0
所以不定方程n的解与下列不定方程：
n¢
x1+x2+x3+x4=0
x1³0, x2³0, x3³0, x4³0
的解一一对应。故根据定理3.6.4.可知，不定方程n的解的数目为：
|A1∩A2| ===1
同理可得：|A1∩A3| ====20
|A1∩A4| ====20
|A2∩A3| ===1
|A2∩A4| ===1
|A3∩A4| ====20
因此 p2=|A1∩A2|+|A1∩A3|+|A1∩A4|+|A2∩A3|+|A2∩A4|+|A3∩A4|
=1+20+20+1+1+20=63
A1∩A2∩A3对应的不定方程是：
o
x1+x2+x3+x4=13
x1³5，x2³8，x3³5，x4³0
由于解若满足条件x1³5，x2³8，x3³5，x4³0，则有
x1+x2+x3+x4³5+8+5+0=18>13
故不定方程o没有解，即 |A1∩A2∩A3| = 0
同理可得：|A1∩A2∩A4| = 0，|A1∩A3∩A4| = 0，|A2∩A3∩A4| = 0
p3=|A1∩A2∩A3|+|A1∩A2∩A4|+|A1∩A3∩A4|+|A2∩A3∩A4| = 0+0+0+0 = 0
A1∩A2∩A3∩A4对应的不定方程是：
p
x1+x2+x3+x4=13
x1³5，x2³8，x3³5，x4³5
由于解若满足条件x1³5，x2³8，x3³5，x4³0，则有
x1+x2+x3+x4³5+8+5+5=23>13
故不定方程p没有解，即
p4=| A1∩A2∩A3∩A4|=0
所以，不定方程k、也即不定方程j的解的数目为：
q0=|∩∩∩| = p0－p1+p2－p3+p4=560－551+63－0+0=72。
方法二.利用母函数方法,不定方程k对应的母函数是：
(1+x+x2+x3+x4+x5+x6+x7)(1+x+x2+x3+x4)3

=(1-3x5-x8+3x10+3x13-x15-3x18+x23)
(参见第三版习题2.16(P199)或第二版第二章习题7(P131))
不定方程j的解的数目为上述母函数中x13的系数：
1´-3´-1´+3´+3´
=-3´-+3´+3´1
=560-495-56+60+3
=72 。
3.58.n个人的集体，试证存在两个人，在余下的n-2个人中，至少有-1个人要么与二人互相认识，要么与这两人均不相识。
[证]. 证法一. 如果一个人在晚会上认识k个人，那么有k(n-k-1)对，他只认识其中一个人而不认识另一个人，所以有对，他都认识或都不认识。由AM-GM不等式

引入个盒子，一个盒子对应晚会上的一对人，对晚会上的三个人。如果c认识a和b或既不认识a也不认识b，则就将c放入盒子，所以我们至少有个物品放入个盒子。由鸽巢原理，一个盒子至少有

个物品。
证法二. 将问题转换为图论问题：n个人看作n个结点，相互认识的两人的一对结点间连一条边，这样就构成一n阶简单图G=(V,E) 。于是问题是要证存在着两个结点，在余下的n-2个结点中，至少有-1个结点要么与这二结点都相邻，要么与这两结点均不相邻。
考虑偶对(X, {Y, Z})的数目，这里X, Y, Z是互不相同的这样的三个结点，使得X正好只与Y, Z中的一个相邻。如果X只与k个结点相邻，那么只有k(n - 1 - k) ≤ k(n - k) ≤ (n - 1)2/4个(X, {Y, Z})这样的偶对。因此整个地至多有n(n - 1)2/4个这样的偶对。而可能的{Y, Z}有n(n - 1)/2 个。所以我们一定能够找到这样一个{A, B}，使得它至多属于个这样的偶对。因此至少有 (n - 2)-=-1个结点，它们或者与A和B都相邻，或者与A和B都不相邻。(如果符号引起困惑，那么请分别考虑n = 2m 与n = 2m+1！)
证法三. 将n个人看作n个结点，若两个人互相认识，则在表示他们的两个结点间连一条边，从而我们得到一个简单无向图G=(V,E)，并且|V|=n。并设|E|=m。
另外，我们设图G的补图为=(V, )。并设||=。于是m+=n(n-1)。问题变为要证：在图G中，至少存在着一对结点v0和w0，在余下的n-2个结点中至少有-1个结点，每个结点u与v0、w0二结点或者都有边相连，或者都无边相连。
(1)在图G中考虑由三个结点u,v,wÎV构成的如下形式的向量(u,(v,w))，其中(u,v)ÎE ,(u,w)ÎE，于是这种向量在G中的个数为。根据图论基本定理：各结点度数的总和是边数的二倍，有=2m。在边数m固定的条件下，将degG(u)看成连续变量，根据条件极值的Lagrange乘子法，求条件极值，易知当所有的degG(u)=时，达到极小值，故有³ m(-1)。
(2)同理，在补图中，也有向量(u,(v,w)) 的个数³ (-1)。
因此，由AM-GM不等式
+= m(-1) +(-1) =-( m+)
³-( m+)=( m+)[-1]。
所以，在图G中，与任一对结点v和w都有边相连或都无边相连的结点u的平均个数为
(+) /n(n-1) =-1=(n-1)-1³(-1)-1。
因而，根据鸽巢原理二的推论3.8.3可知，在图G中，至少存在着一对结点v0和w0，在余下的n-2个结点中至少有-1个结点，每个结点u与v0、w0二结点或者都有边相连，或者都无边相连。

注.来源于USA MO 1985/4，计算机56班 王绍鹏同学提供搜索，作者翻译并整理。
AM-GM不等式：几何平均值（GM）小于算术平均值（AM）。
证法一由一个不知名的中国人给出；证法二由一个不知名的外国人给出；证法三由作者给出。
3.60.下列m´n矩阵的元素是实数

每行的最大元素与最小元素之差不超过d>0。对每列元素进行重新排列成递减序列，即最大元素在第1行，最小元素在第m行。试证经过重排后的矩阵，每行最大元素与最小元素之差仍然不超过d。
[证]. 假设相反的，在重排的矩阵(其元素我们表示为bij , 1 £ i £ m, 1 £ j £ n)中，第i行的最大元素与最小元素之差超过d。设这些元素分别是bij 和 bik。那么考虑n+1个元素
b1j ³ b2j ³ ¼ ³ bij > bik ³ bi+1 k ³ ¼ ³ bm k
它们在重排的矩阵中处于位置

根据鸽巢原理，这n+1个元素必有两个元素在原矩阵中是在同一行中。它们之一应该是bpj，对某一p £ i，而另一个应该是bq k，对某一q ³ i。无论如何bpj - bq k ³ bij - bik > d 。因此，在原矩阵中那一行的最大元素与最小元素之差也超过d。这是一个矛盾。
3.61.n个单位各派两名代表出席一会议，2n位代表围一圆桌坐下。试问
(1)各单位代表并排坐着的方案有多少？
(2)各单位的两人互不相邻的方案数又等于多少？
[解].(1)先按单位做圆排列，n个单位有(n-1)!种排法；再将每个单位的两人做全排列，有2种排法，n个单位共有2n种排法；故按乘法原理，各单位代表并排坐着的
方案数= (n-1)!×2n 。
(2)设：Ai — 第i个单位的两个代表相邻的方案数；
C(n,k) —n个元素的k元子集的集合；
那么，的含义是先在n个单位中任选出k个单位，有种选法；其次让选出的这k个单位的两个代表一定相邻，故可看作是一个人，而其余n-k个单位的2n-2k个代表不一定相邻，因此这相当于2n-2k+k=2n-k个人做圆排列，有(2n-k-1)!种排法；另外，两个代表一定相邻的k个单位，每个单位的两人做全排列，有2种排法，k个单位共有2k种排法；故按乘法原理，

因此，各单位的两人互不相邻的方案数，按容斥原理二，为
。
4.18．若已给两个r色的球，两个b色的球，用它装在正六面体的顶点，试问有多少种不同的方案？
[解].正六面体顶点的置换群参见例4.7.2。

转动群
格式
置换
循环节
不动 0°
(1)8
1个
8个
面心-面 ±90°
(4)2
6个
2个
面心-面心 180°
(2)4
3个
1
4个
顶点-顶点 ±120°
(1)2(3)2
8个
1
4个
棱中-棱中 180°
(2)4
6个
4个
第8题 表

将2个r色,4个g色(装此色的球相当于不装球),2个b色的球装在正六面体的8个顶点上的问题，相当于用b，g， r三种颜色对正六面体进行染色。
于是根据母函数形式的Pólya定理，方案枚举：
P(b,g,r)=[(b+g+r)8+6(b4+g4+r4)2+9(b2+g2+r2)4+8(b+g+r)2(b3+g3+r3)2]
其中b2g4r2的系数即为所求嵌珠方案数：

=
=22(种)。
(或者 [C(8,2)C(6,2)+9C(4,2)C(2,1)]/24=22(种) )。
4.22.一幅正方形的肖像与一个立方体的面一样大，6副相同的肖像贴在立方体的6个面上有多少种贴法？

[解].绕面心—面心轴旋转任何度数，均不会产生不变的图象。由于一个人的肖像贴于一个立方体的一个正方形面上，其头部有上下、左右4种选择，故绕其它轴的旋转都相当于正六面体的面4着色。
参照例4.6 4，有共6个元素(6个面)的置换群：

转动群
格式
置换
循环节
所求方案数
不动 0°
(1)6
1个
6个
46
面心-面 ±90°
(1)2(4)1
6个
3个
0(无不动图象)
面心-面心 180°
(1)2(2)2
3个
4个
0(无不动图象)
顶点-顶点 ±120°
(3)2
8个
2个
1
6· 42
棱中-棱中 180°
(2)3
6个
3个
6· 43
第12题 表