第5 章
组合计数
组合计数在许多学科中都会用到,特别是在计算机的算法设计与分析中
用于估计算法的复杂度函数。本章介绍了加法原理、排列与组合,并详细介
绍了计数的两个典型应用———鸽笼原理和递推关系。
递归关系是序列中第n 个元素与它前若干个元素之间的关系,可用于解
决一些特定的计数问题。由于递归关系和递归算法密切相关,因此递归关系
可以很自然地用于递归算法分析。
5.1 基本原理
5.1.1 加法原理 
加法原理是一个初等原理。它是全体等于它的各部分之和这一原理的
公式化。
定理5.1(加法原理) 假定S1,S2,…,St均为集合,第i 个集合Si 有ni 
个元素。若{S1,S2,…,St}为两两不交的集合(若i≠j,Si∩Sj =.),则可
以从S1,S2,…,St 选择出的元素总数为n1+n2+…+nt(即集合S1∪S2∪… 
∪St 含有n1+n2+…+nt 个元素)。
加法原理可总结为:当计数的元素可分解为若干个不相交的子集时,可
将每个子集元素的个数相加得到元素的总数。
例5.1 在1,2,…,10中,有5个偶数,4个素数,求1,2,…,10中是偶数
或是素数的个数。
解:由于2既是偶数,又是素数,所以,1,2,…,10中,是偶数或是素数的
个数不是简单地5+4=9,而是8。此例说明,不能不加分析地、简单地使用
加法原理。
例5.2 当执行完以下代码后,k 的值是多少? 
k:=0 
for i1:=1 to n1

1 64 离散数学(第3 版) 
k:=k+1 
for i2:=1 to n2 
k:=k+1 
. 
for im:=1 to nm 
k:=k+1 
解:k 的初始值是0,在执行完 
for i1:=1 to n1 
k:=k+1 
后,k=n1。实际上,这段程序是让k 从0起,不断地加1,共n1 次。同理,在执行完 
for i2:=1 to n2 
k:=k+1 
后,k=n1+n2。执行完最后的 
for im:=1 to nm 
k:=k+1 
后,k=n1+n2+…+nm 。所以,当执行完所有的代码后,k 的值是n1+n2+…+nm 。
5.1.2 乘法原理
乘法原理要稍微复杂一些,相当于加法原理的一个推论,主要反映乘法是重复加法的
这一事实。
定理5.2(乘法原理) 如果一项工作需要t 步完成,第一步有n1 种不同的选择,第二
步有n2 种不同的选择,……,第t 步有nt 种不同的选择,那么,完成这项工作所有可能的
不同的选择总数为n1×n2×…×nt。
乘法原理可总结为:当一项工作分为若干步时,将每一步的可选择数相乘便得到这
项工作的所有可选择个数。
例5.3 从5本不同的计算机书、3本不同的数学书和2本不同的艺术书中选出不同
类的两本,共有多少种选法? 
解:根据乘法原理不难得出,选择一本计算机书和一本数学书,共有5×3=15种选
法;同理,选择一本计算机书和一本艺术书共有5×2=10种选法;选择一本数学书和一本
艺术书共有3×2=6种选法。由于这3个集合两两不相交,根据加法原理可得:从5本
不同的计算机书、3本不同的数学书和2本不同的艺术书中选出不同类的两本,共有
15+10+6=31 
种选法。
用乘法原理可证明一个含有n 个元素的集合共有2n 个子集。
例5.4 用乘法原理证明含有n 个元素的集合{x1,x2,…,xn}有2n 个子集。
证明:构造一个子集分为n 个步骤:选取或不选取x1;选取或不选取x2;……;选取
或不选取xn 。每一步有两种选择,故所有可能的子集总数为

第5章组合计数

165
n 

............ 

2..×2n×..个2…×..2=2
运用乘法原理可对需要若干步完成的对象计数,当计算不相交子集中对象的总数时, 
可运用加法原理。

5.排列与组合
5.1 
排列
2.
定义5.1 n 
个不同元素x1,x2,…,xn 
x2,…,xn 

定理5.
的一种排列为x1,的一个排序。
3 n 
个元素的排列共有n!种。

证明:运用乘法原理。确定
n 
个元素的一个排列依次分为
n 
个步骤:选择第一个元
素;选择第二个元素;……; 选择第
n 
个元素。第一个元素有
n 
种选法;当第一个元素选
定后,第二个元素有n-1种选法;当第二个元素选定后,第三个元素有n-2种选法;以
此类推。根据乘法原理,共有n(1)(n!种排列。

n-n-2)…×2×1=

例5.

5 
10 个元素的排列共有
10!=10×9×8×7×6×5×4×3×2×1=3628800 种
定义5.2 n 
个(不同)元素x1,x2,…,xn 
的
r 
排列是{x1,x2,…,xn 
}的
r 
元素子集
上的排列。
n 
个不同元素上的
r 
排列的个数记作P(
r 
定理5.4 n 
个不同元素上的
r 
排列数目为P(
n,)。
n(1)(2)…(r+1), 
r≤n。
n,r)=n-n-n

证明:对从
n 
个不同元素中选取
r 
个元素的排列方法进行计数。第一个元素有
n 
种
选法;当第一个元素选定以后,第二个元素有n-1种选法;依次不断选取,直到当第r-1 
个元素选定后,选取第
r 
个元素。最后一个元素有n-
n 
个

n,r)=n(n-n-
r+1 
n-
种选法。根据乘法原理,
不同元素上的
r 
排列数目为P(1)(2)…(r+1 )。
例5.依定理5.X={b,上的2排列数为

6 
4,a,c} 

这6种排列依次为
P(3,2)=3×2=6 
ab,c,a,c,a,b

abbcc

5.2 
组合
2.
定义5.给定集合X={x2,…,xn 
其包含
n 
个元素, 
n,)。
不重复选

3 
x1,}, 从
X 
中无序、
取的
r 
个元素称为
X 
的一个
r 
组合,
X 
的所有
r 
组合的个数记作C(
r 
接下来用两种方法导出
n 
个元素上的
r 
组合数C(n,的公式:第一种方法是利用
C(n,r)公式
公式导出
。
; n,
r)

P(n,r) 第二种方法是直接从C(r)的性质入手。两种方法将得到相同的

将构造一个
n 
个元素集
X 
上的
r 
排列分为两个步骤:选出一个
X 
上的
r 
组合;将这
个
r 
组合排序。例如,构造{b,d} 先选择一个2组合,

a,c,上的一个2排列, 再将2组合


166
离散数学(第3版) 

进行排序。图5.a,c,上的2排列。由乘法原

理可知,1说明了如何通过这种方法构造一个{b
即
,d} 
r 
排列数等于
r 
组合数与
r 
个元素排列数的乘积, 
P(r)=n,r!n,C(r)


图5.1 
{b,d}的2排列

a,c,

于是

C(r)P(r)

n,=n,

下面的定理将给出C(r) 
r! 

定理5.
n,的另外一种表示法
。
5 n 
个不同元素上的
r 
组合数
为


P(r) n-1)…(r+1) n!C(n,r)
= 
rn!
,=n(
r! 
n-=n-r)!r!,
r 
≤
n 
例5.(
(
共有多少种不同的选法?

7 
1)从10 个人中选出一个3个人的委员会,

(2)从5个女人和6个男人中选出由2个女人和3个男人组成的委员会,共有多少
种选法? 
解:(1)由于委员会中的成员不计次序,故共有

C(10,3)
= 
10×9×8 =120 种

(2)选出2名女性委员, 5,=
3! 
选出3名男性委员, 6,=
共有C(2)10 种选法, 共有C(3)
20 种选法。选出委员会可分为两步:选出女性委员;选出男性委员。根据乘法原理,共有
10×20=200 种选法。

5.排列组合生成算法
3 

5.1 
排列生成算法
3.
如果将整数
n 
从{1,n} 则结果是{2,…,1}

2,…,的一个排列中删除, 1,n-的一个排

←→ 

列。给定一个整数k,通过在其上画一个向左或向右的箭头表示方向:k或k。考虑{1, 
2,…,的一个排列,其中的每一个整数都给定一个方向。如果一个整数
k 
的箭头指向

n} 
一个与其相邻但比它小的整数,那么这个整数
k 
就是活动的。例如, 

→→→←→→

263154
只有3,5和6是活动的。由此可知,1绝不可能是活动的,因为{1,2,…,中不存在比1 
还小的整数。除下面两种情况外,整数
n 
总是活动的。
n} 

(1)而它的箭头指向左边:←…。
n 
是第一个整数, n


第5章组合计数

167
2)
n 
是最后一个整数,而它的箭头指向右边:…n

→

(

。

这是因为只要
n 
的箭头指向一个整数, 
最大的整数。下面给出生成{

生成{

从
n 
当存在一个活动的整数时, 
1)求出最大的活动整数m; 
2)交换
m 
和其箭头指向的与其相邻的整数; 

…

←2
←1
((

它就是活动的,因为
n 
是集合{2,…,中
的所有排列的算法。
1,n}

1,2,…,

n}

2,…,

开始
n
。
}的排列的算法

1,

← 

3)交换所有满足p>
m 
的整数
p 
的方向。
这里就n=4叙述该算法。结果用两列显示,第一列给出前12 个排列。

(

←1 
←1 
←1 
→4←4←
1 
←1 
←1 
→3 
→3 
→3 
→4 
←2←2→4←1←1←4→3→3←1←1→4→3
→3→4←2←2→3→3←4←2←2→4←1←1
→4→3→3→3←2←2←2←4→4←2←2←2
←4←3←3←3←2←2←2→4←4←2←2←2
←3←4←2←2←3←3→4←2←2←4←1←1
←2←2←4←1←1→4←3←3←1←1←4←3
←1←1←1←4→4←1←1←1←3←3←3←4
→4
→3
←1
←2
所以算法终止。

由于在

中没有活动的整数, 
通过对
n 
的归纳法可以得知,这个算法生成{1,2,…,n}的所有的排列,并且具有
与前面的方法相同的顺序。我们叙述从n=4的归纳法中的一步。从

←4
←3
←2
←1
3到n=

开

始,其中4是最大的活动整数。4始终是活动的,直到达到最左边位置为止。此时4已

←3
←2
←1
经以各种可能的方式插入{1,2,3}的排列123 中。现在4又不再是活动的。最大的活
中的最大的活动整数相同。然后3和2交换位置且4改变方向。

动整数是3,它和

这个交换与

←3
←2
←1
中出现的交换是相同的。现在的结果变成

;

←2
←3
←1
→4
此时4又变成活动

的,并将活动状态保持到4到达最右边位置为止。然后再进行交换,该交换与发生在

←2
←3
←1
中的交换相同。算法如此继续进行,4以各种可能的方式交错地插入{1,2,3}的每
一个排列中。


168
离散数学(第3版) 

3.组合生成算法
5.2 

令
S 
是
n 
个元素的集合。为了分析清楚起见,取
S 
为集
合
S={-1,…,x0}


xnx1,
现在我们寻找一种生成
S 
所有2n 
个组合(子集)的算法。也就是说,要找一个将
S 
的所
有组合列出的系统过程。算法的结果应该包含
S 
的所有的组合(并且只是
S 
的组合), 而
且没有重复。

给定
S 
的一个组合A,每一个元素xi 
或者属于
A 
或者不属于A。如果用1表示属
于,用0表示不属于,就能够用2n 
个0和1的
n 
元组
(-1,…,a0)a

ana1,=n1…a1a0
区分
S 
的2n 
个组合。对于每个i0,n-1,令
n 
元组的第
i 
项ai 。


=1,…,对应元素xi 
例如,当n=3时,23=8个组合以及它们对应的3元组如下: 
a2 a1 a0 

.000 
{x0}0 0 1 
{x1}0 1 0 

{x1,x0}0 1 1 

{x2}1 0 0 
{x2,x0}1 0 1 
{x2,x1}1 1 0 

{x2,x1,x0}1 1 1 
例5.令S={x5,x3,x1,x0}, x5,x2,x0}的7元组

8 
x6,x4,x2,对应组合{x4,0110101 。对应7元组1010001 的组合是{x6,x0}。

1. 
生成{x0}组合的算法
x4,
…

1,
从an-1…a1a0=0…00 开始
。
当an-1…a1a0≠1…11 时
,


(1)求出使得aj 
=0的最小的整数j(在n-1和0之间); 
(2)用1代替aj 
并用0代替aj-1,…,a0 中的每一个值(由对
j 
的选择可知,在用
0代替以前,它们都等于1)。
a1,
当an-1…a1a0=1…11 时算法结束,它是在结果列表中最后的二进制
n 
元组。
定理5.令a1a2…a是{2,…,的一个r组合。在字典排序中,第一个r-组合

6 
1,n} 
r 
-n-n-
r 
≠(n

是12…。最后一个r组合(r) 是(r+1)(r+2)…n。设a1a2…an-r+1)(
r+2)ar

…n。令
k 
是满足ak 
<
n 
且使得ak 
+1 不同于a1,a2,…,中的任何一个数的最
大整数。那么,在字典排序中,的直接后继r-组合是

a1a2…ar 

xn

,

x1,


56.
定理证明

ak 
+r-k+1)ak 
+2)…(
组合。

a1…ak

ak 
+1)(
下列算法生成{2,…,的字典序的所有r

1(

1,n}

从定理5.

6断言, 

-

…

2. 
生成{1,2,
,的字典序r组合的算法

n} 
-组合a1a2…ar 
=12…
r 
开始。

从r


169
第5章组合计数

当a1a2…
r 
≠(r+1)(r+2)…
n 
时,

n-n

(1)确定的整数k, a2,…,
r 。最大(a) 使ak 
+1≤
n 
且ak 
+1 不是a1,a

(2)用r-组合
a1…ak-1(ak 
+2)…(k+1) 
替换a1a2…a。
ak 
+1)(ak 
+r

例5.应(r) 用生成S={1,2,3,4,5,6}的4-组合算法,得到下列结果。

123412562345 

123513452346 

123613462356 

124513562456 

124614563456 

9 

如果将生成一个集合的排列的算法与生成一个n-元素集合的r-组合的算法结合起
来,就得到生成n-元素集合的r-排列的算法。
10 
-124,134,

例5.生成{1,2,3,4}的3排列。首先生成字典序的3-组合:123,234 。

对于每一个3-组合,再生成其所有的排列: 

123124134234 

132142143243 

312412413423 

321421431432 

231241341342 

通过确定在{1,n} -
213214314324 
-组合的位置结束本节。

2,…,的r组合的字典序中的每一个r

例5.若按字典序列出{1,2,3,4,5,6,7}上所有的组合,第一个为12345,接下来
的两个为12346 和12347,然后是12356 和12357,最后一个为34567 。
例5.12 
若按字典序列出
X 
={1,2,3,4,5,6,7}上所有的组合,13467 的下一个是
什么? 

以134 开头的最大的字符串为13467,故13467 的下一个以135 开头。因为13567 是
以135 开头的最小的字符串,故13467 的下一个是13567 。不难发现上例中的模式。给
定一个与{sr} s1…sr 
,求
α 
的下一个字符串β=t1… 

11 

s1,…,上的
r 
组合对应的字符串α=
t。从右向左找到第一个非最大值的元素sm 
sr 
的最大值为n,r-1的最大值为n-1, 此(r) 类推), 则
(s以

ti=si,i=1,…,m-1 

tm 
=sm 
+1 

(m+2)(… 

由此可得组合生成算法。
tm+1…tr=ssm+3)
例5.说明组合生成算法如何生成{2,4,6,-组

合。设
13 
1,3,5,7}上23467 的下一个5

s1=2,s2=3,s3=4,s4=6,s5=7 
s3 是从右向左第一个非最大值的元素。将s3 赋值为5,

s4 和s5 分别被赋值为6和7, 


170
离散数学(第3版) 


例5.4解答


例5.5解答

1

此时, 

s1=2,s2=3,s3=5,s4=6,s5=7 
于是就生成了23467 的下一个5-组合23567 。
例5.找到{2,4,6} 应使左边尽可能多的数字

14 
1,3,5,上排列163542 的后继
,
保持不变
。


5.广义的排列和组合
4 

前述的排列组合主要考虑不允许重复的情况下,如何对选择和排序计数。本节介绍
允许重复的情况下,如何对选择和排序计数,即广义的排列和组合。
定理5.设序列
S 
包含
n 
个对象, 第2类对象有n2 个,……, 

7 
其中第1类对象有n1 个, 
第t类对象有nt 
个,则
S 
的不同排序个数为
n! 
n1!n2!…n! 
证明:指定
n 
个对象的位置可得
S 
的一个排(t) 序。共有C(n,n1)种不同的方法为n1 
个第1类的对象指定位置;指定第1类对象的位置后, n-n1,种不同的方法为

共有C(n2) 
n2 个第2类的对象指定位置;以此类推。根据乘法原理,不同的排序个数为
C(n,n1)nn2)n-n1n2,…C(--…n-n)

C(-n1,C(-n3)nn1-t1,t

(n1)! (-…1)! 

n! n-n-n1-nt

= 
· ·…·

n1!(-n1)! n2!(-n2)! !0!

nn-n1nt

n! 

= 

n1!n2!…nt! 

例5.将8本不同的书分给3个学生,学生甲分4本,乙分2本,丙分2本,共有多
少种不同的分法? 
利用等价关系同样可以证明定理5.7。设序列
S 
包含
n 
个对象,其中第
i 
类有ni 
个
1,t。将
S 
中的同类对象用下标加以区分, 

15 

相同的对象,i=2,…,得到集合X。例如,序
列
S 
为
MISSISSIPPI 
则集合
X 
为
{
M 
,S2,S3,I3,P2,

I1,S1,I2,S4,P1,I4}
在
X 
的所有排列上定义关系R:p1Rp2,当且仅当p1 可以通过交换同类对象(但不改变
它们的位置)的位置而得到p2。例如,容易验证如下关系
R 
是
X 
的所有排列集合上的等
价关系。
(I3P1P2R(I1S4S1I4M 
)

I1S1S2I2S3S4I4M 
)I2S3S2I3P1P2
若将同类对象看作相同的,则排列
P 
的等价类中
X 
的所有元素可视为相同,故每个
等价类包含n1!n2! !(2,…,个元素。由于等价类与
S 
上的排序一一对

…nti=1,t)
应,故等价类的数目等于
S 
个, 7,

上排序的数目。
X 
上的排列共有n! 故由定理5.
S 
上排
序的个数为

n! 
n1!n2!…nt! 


第5 章 组合计数1 71 
下面讨论允许重复的情况下,如何对不计顺序的选择计数。
定理5.8 X 为包含t 个元素的集合,在X 中允许重复、不计顺序地选取k 个元素, 
共有
C(k +t-1,t-1)=C(k +t-1,k) 
种选法。
证明:令X ={a1,a2,…,at}。考虑将k 个“×”和t-1“|”填入下面的k+t-1个
空格中, 
— — — … — — 
每种排列方法决定X 上的一个选择:第一个“×”左边“|”的个数n1 表示选择n1a1 的个
数;第一个“|”和第二个“|”之间“×”的个数n2 表示选择n2a2 的个数;以此类推。由于为
t-1个“|”选定位置共有C(k+t-1,t-1)种选法,故共有C(k+t-1,t-1)个X 上的
选择。若考虑为k 个“×”选定位置,则共有C(k+t-1,k)种选法,所以共有
C(k +t-1,t-1)=C(k +t-1,k) 
种选法,在X 上允许重复、不计顺序地选取k 个元素。
例5.16 把12本相同的数学书分给甲、乙、丙、丁4个学生,共有多少种分法? 
若将问题看作在12本书上分别写上4个学生的名字,则可利用定理5.8计算分法
数。这相当于在集合{甲,乙,丙,丁}上允许重复、不计顺序地选择12个元素。根据定理
5.8,共有
C(12+4-1,4-1)=C(15,3)=455 
种分法。
例5.17 (a)方程x1+x2+x3+x4=29有多少个非负整数解? (b)上述方程有多少
满足x1>0,x2>1,x3>2,x4≥0的整数解? 
5.5 二项式系数和组合恒等式
本节主要讨论组合数的性质、组合数序列的求和以及组合恒等式的证明等内容。本
节引入一个新的符号
n
r
.
è .
.
. ÷ 
,当n 和r 都是自然数时,它就等于组合数C(n,r)。
5.5.1 二项式定理
表达式(a+b)n 看似与组合数无关,但通过n 个对象的r 组合数可以得出表达式
(a+b)n 的展开式。代数表达式在很多情况下都与计数问题相关,利用代数方法常常可
以得到一些高级的计数技巧。二项式定理给出了(a+b)n 展开的各项系数。由于
(..a..+..b..)..(a....+..b..)..…..(a..+..b....) n个因子 
从每个因子中选择a 或b,将n 个因子中的选择相乘,再将所有选择的乘积相加,即
得展开式。例如,为展开(a+b)3,需从第一个因子中选择a 或b,从第二个因子中选择a 
或b,从第三个因子中选择a 或b,将选出的3项相乘得展开式中的一项,将所有选择的乘
例5.17解答

172
离散数学(第3版) 

积相加得展开式。若从3个因子中都选择a,则得项aaa;若从第一个因子中选择a,从第
二个因子中选择b,从第三个因子中选择a, ba。表5.

则得项a1列出了所有可能的项。
将所有选择的乘积相加,有

3

(=(a+b)(

a+b)a+b)(a+b) 
=aaa+aab+aba+ab 
+baa+bab+
ba+
b 
=a3+a2b+a2b+ab2+a2b+ab2+ab2+b3 
=a3+3a2b+3ab2+b3 

式中,在
n 
个因子中选择
k 
个
b 
和n-
k 
个a,可得项an-kbk 
。因为从
n 
个对象中选择
k 
个共有C(n,k) 所以项an-kbk 
n,个,

种选法, 共有C(k) 则

nnn-1n-2

(C(0)n,b1+C(2)

a+b)=n,ab0+C(1)n,ab2+ 
…
+ 

n-n

bn,
这就是所谓的二项式定理
C(
( 
n
见表
,n-
51.1)a)。
11+C((a) n)a0b

表5.计算(3

1 
a+b)

从第一个因子
(a+b)中选择
从第二个因子
(a+b)中选择
从第三个因子
(a+b)中选择
选择结果的乘积
a a a 
aaa=a3 
a a b 
aab=a2b a b a 
aba=a2b a b b 
ab 
=ab2 
b a a 
baa=a2b b a b 
bab=ab2 
b b a ba=ab2 
b b b b 
=b3 

定理5.9(二项式定理) 
n 
为正整数,

设
a 
和
b 
为实数,则

n 
n-k

(C(k)bk

a+b)=Σ(n) n,a

k=

利用数学归纳法归纳于n,同样可证二项式定(0) 理。
C(r)为a+
b 
的幂的展开式中的系数,故称为二项式系数。

n,
例5.18 
在定理5.3,


9中令n=可得
a+b)3=C(3,0)b0+C(3,1)b1+C(3,2)b2+C(3,3)

(a3a2a1a0b3 

=a3+3a2b+3b2+b3
19 
3x-
2


例5.利用二项式定理展开((a) y)4。

解:在定理5.令a=y,4,可得

(4=(
9中, x,

3b=-2n=

4

3x-2y)a+b)
a4a3a2a1a0b4

=C(4,0)b0+C(4,1)b1+C(4,2)b2+C(4,3)b3+C(4,4)
C(4,0)(x)0+C(4,1)(x)1+C(4,2)(x)2+

=34(-2y)33(-2y)32(-2y)

4

3)(1(3+C(4)(0(

C(4,3x)-2y)4,3x)-2y)