第5 章
组合计数
5.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.2(乘法原理) 如果一项工作需要t 步完成,第1步有n1 种不同的选择,第2步
有n2 种不同的选择,…,第t 步有nt 种不同的选择,那么完成这项工作所有可能的不同的
选择总数为n1×n2×…×nt。
排序 n 个不同元素x1,x2,…,xn 的一种排列为x1,x2,…,xn 的一个排序。
定理5.3 n 个元素的排列共有n!种。
排列 n 个(不同)元素x1,x2,…,xn 的r 排列是{x1,x2,…,xn}的r 元素子集上的排
列。n 个不同元素上的r 排列的个数记作P(n,r)。
定理5.4 n 个不同元素上的r 排列数目为P (n,r)=n(n-1)(n-2)…(n-r+1),
r≤n。
组合 给定集合X = x1,x2,…,{ xn} 包含n 个元素,从X 中无序、不重复选取的r 个
元素称为X 的一个r 组合,X 的所有r 组合的个数记作C(n,r)。
定理5.5 n 个不同元素上的r 组合数为
C(n,r)=P(n,r)
r! =n(n -1)…(n -r+1)
r! = n!
(n -r)!r! , r ≤n
定理5.6 令a1a2…ar 是{1,2,…,n}的一个r 组合。在字典排序中,第一个r 组合是
12…r。最后一个r 组合是(n-r+1)(n-r+2)…n。设a1a2…ar≠(n-r+1)(n-r+2)…n。
令k 是满足ak<n 且使得ak+1不同于a1,a2,…,ar 中的任何一个数的最大整数。那么在字典排
序中,a1a2…ar 的直接后继r-组合是a1…ak-1(ak +1)(ak +2)…(ak +r-k+1)。
定理5.7 设序列S 包含n 个对象,其中第1类对象有n1 个,第2类对象有n2 个,…,
第t 类对象有nt 个,则S 的不同排序个数为
n!
n1!n2!…nt !
定理5.8 X 为包含t 个元素的集合,在X 中允许重复、不计顺序地选取k 个元素,
共有
C(k +t-1,t-1)=C(k +t-1,k)
离散数学解题指导(第3 版)
11 8
种选法。
定理5.9(二项式定理) 设a 和b 为实数,n 为正整数,则
(a +b)n =Σn
k=0
C(n,k)an-kbk
其中C(n,r)为a+b 的幂的展开式中的系数,故称为二项式系数。
定理5.10 对任意1≤k≤n,C(n+1,k)=C(n,k-1)+C(n,k)。
定理5.11 鸽笼原理(第一种形式) n 只鸽子飞入k 个鸽笼,k<n,则必存在某个鸽笼
包含至少两只鸽子。
定理5.12 鸽笼原理(第二种形式) 设f 为有限集合X 到有限集合Y 的函数,且|X|>
|Y|,则必存在x1,x2∈X ,x1≠x2,满足f(x1)=f(x2),X 相当于第一种形式中的鸽子,Y
相当于第一种形式中的鸽笼。鸽子x 飞入鸽笼f(x1)。由鸽笼原理的第一种形式,至少有
两只鸽子x1,x2 ∈X 飞入同一个鸽笼,即对某两个x1,x2 ∈X ,x1 ≠x2,满足f (x1)=
f(x2)。
定理5.13 鸽笼原理(第三种形式) 设f 为有限集合X 到有限集合Y 上的函数,|X|=
n,|Y|=m 。令k=én/m ù,则至少存在k 个元素a1,a2,…,ak ∈X ,满足f(a1)=f(a2)=
…=f(ak)。
递推定义函数 为了定义以非负整数集合作为其定义域的函数,就要规定这个函数在
0处的值,并给出从较小的整数处的值来求出当前值的规则。这样的定义称为递推定义。
递推定义集合 递推定义可用来定义集合,先给出初始元素,然后给出从已知元素构造
其他元素的规则。以这种方式描述的集合是严格定义的。
常系数k 阶齐次线性递推关系 形为an =c1an-1+c2an-2+…+ckan-k ,ck ≠0的递推
关系称为常系数k 阶齐次线性递推关系。
特征方程与特征根 方程pk -c1pk-1-c2pk-2-…-ck-1p-ck =0称为k 阶线性齐
次递推关系an =c1an-1-c2an-2-…-ckan-k 的特征方程,其中p 是一个常数。方程的解
p 称为该递推关系的特征根。
定理5.14 令
an =c1an-1 +c2an-2 ①
为常系数二阶齐次线性关系。
(1)若S 和T 为式①的解,则U =bS+dT 也为式①的解。
(2)若r 为方程
t2 -c1t-c2 =0 ②
的一个根,则序列rn(n=0,1,…)为式①的一个解。
(3)若an 为式①定义的序列,
a0 =C0, a1 =C1 ③
且r1 和r2 为方程②的两个不相同的根,则存在常数b 和d,使得
an =brn1
+drn2
, n =0,1,…
成立。定理5.15(Master定理) 设a≥1,b>1为常数,f(n)为函数,T (n)为非负整数,且
T(n)=aT(n/b)+f(n),则有以下结果:
组合计数
第5章
1 19
(1)f(n)=O(nlogba-ε),ε>0,那么T(n)=Θ(nlogba)。
(2)f(n)=Θ(nlogba),那么T(n)=Θ(nlogbalogn)①。
(3)f(n)=Ω(nlogba+ε),ε>0,且对于某个常数c<1和所有的充分大的n 有af(n/b)≤
cf(n),那么T(n)=Θ(f(n))。
定理5.16 对输入规模为n 的二分法查找,在最坏情形下的时间复杂度为O(logn)。
生成函数 对于序列a0,a1,a2,…,多项式A(x)=a0+a1x+a2x2+… 称为序列a0,
a1,a2,…的生成函数。
下面用B(x)=b0+b1x+b2x2+…表示序列b0,b1,b2,…的生成函数;C (x)=c0+
c1x+c2x2+…表示序列c0,c1,c2,…的生成函数。
性质5.1 如果bn =αan ,α 为常数,则B(x)=αA(x)。
性质5.2 如果cn =an +bn ,则C(x)=A(x)+B(x)。
性质5.3 如果cn =Σn
i=0
aibn-i,则C(x)=A(x)·B(x)。
性质5.4 如果bn = 0, n<l
an-l, n≥l,则B(x)=xl·A(x)。
性质5.5 如果bn =an+l,则B(x)=
A(x)- Σl-1
n=0
anxn
xl 。
性质5.6 如果bn =Σn
i=0
ai,则B(x)=A(x)
1-x 。
性质5.7 如果bn =Σ∞
i=0
ai,且A(1)=Σ∞
n=0
an 收敛,则B(x)=A(1)-xA(x)
1-x 。
性质5.8 如果bn =αnan ,a 为常数,则B(x)=A(αx)。
性质5.9 如果bn =nan ,则B(x)=xA'(x)。
性质5.10 如果bn =
an
n +1,则B(x)=1 x∫x
0
A(x)dx。
指数型生成函数 对于序列a0,a1,a2,…,多项式
Ge(x)=a0 +a1
x
1! +a2
x2
2! +a3
x3
3! + …
称为序列a0,a1,a2,…的指数型生成函数。
性质5.11 设数列{an}和{bn}的指数型生成函数分别为Ae(x)和Be(x),则Ae(x)·
Be(x)=Σ∞
n=0
Cn
xn
n! ,其中Cn =Σn
k=0
n
k
.
è .
.
.÷akbn-k 。
5.2 例题精选
例5.1 设A 为n 元集,问:
(1)A 上的自反关系有多少个?
① 本书以2为底的对数直接表示为log,如log2b 表示为logb。
120
离散数学解题指导(第3版)
(2)
A
上的反自反关系有多少个
?
(3)
A
上的对称关系有多少个
?
(4)
A
上的反对称关系有多少个
?
解:(1)在
A
上的自反关系对应的关系矩阵中,主对角线元素都是1,其他位置的元
素
可以是1,也可以是0,每个位置有两种选择。这种位置有n2-
n
个,根据乘法原理,自反关
系的个数是2n2-
n
个。
(2)与(1)类似,反自反关系的个数也是2n2-
n
个。
(3)考虑
A
上对称关系的矩阵。考虑分步处理的方法,先考虑主对角线上的元素。对
于主对角线上的每个位置,元素可以选择0或1,有2种选法,总共有2n
种方法。再考虑不
在主对角线上的元素,它们的值的选择并不是完全独立的。因为矩阵是对称的,
i
行
j
列的
元素rij
必须与
j
行
i
列的元素rji相等。因此,当矩阵的上三角元素(或下三角元素)的值确
定以后,另一半对称位置的元素就完全确定了。这种能够独立选择0或1的位置有n2-
n
2
n2-nn2+
n
个。因此,根据乘法原理,构成矩阵的方法数是2n22=22。
(4)与(3)的分析类似,也采用分步处理的方法,区别在于对非主对角线位置元素取值
n2-n
的约束条件不一样。将这些位置分成2 组,每组包含处在对称位置的两个元素rij
和
rji。根据反对称的性质,i和rji
的取值有三种可能:①rj
=rj0;②rj
=0,rj
rj
i1,
i
=ii
=1;
n2-n
③rij
=rji=0。因此,所有这些位置元素的选择方法数为32。由乘法原理,考虑到主对角
n2-
n
线上的元素的选取,总方法数是2n32
。
例5.说明排列生成算法如何生成163542 的后继
。
2
解:首先考虑能否在163542 后找到一个形如1635__ 的排列。唯一与163542 不同的形
如1635__ 的排列是163524,但163524<163542,故163542 的后继不是形如1635__ 的排列。
再考虑能否在163542 后找到一个形如163___ 的排列。后三个数字必为{2,4,5}的一
个排列。由于542 是{2,4,5}上最大的排列,形如163___ 的排列都小于给定的排列。故
163542 的后继不是形如163___ 的排列。
给定排列的后继不能以1635 或163 开头,原因在于给定的排列中余下的数字逆序排列
(分别为42 和542 )。故从右向左扫描,找到第一个数字d,使它的右邻
r
满足d<r。本例
中,第三个数字3满足这个性质,所以给定的排列的后继以16 开头。16 后的第一个数字必
须大于3。为找到比给定排列大的最小的排列,该位应为4。于是,给定排列的后继以164
开头。为使排列最小,余下的三个数字235 应按升序排列。于是,给定排列的后继
为164235 。
例5.证明:把5个顶点放到边长为2的正方形中,至少存在两个顶点,它们之间的
3
距离小于或等于2。
证明:鸽笼原理可用于判断是否存在给定性质的对象。若鸽笼原理的条件成立,则存
在满足条件的对象,但鸽笼原理并不能指出这样的对象怎样去寻找,或是在哪里。运用鸽笼
原理时必须确定哪些对象相当于鸽子,哪些对象相当于鸽笼。本例中5个顶点相当于鸽子,
关键在于鸽笼的确定。若采用如图5-1(a)所示的方式,则不能说明对象具有对象之间的距
组合计数
离小于或等于2这样的性质。而采用如图5-1(b)所示的方式,则可以证明把5个顶点放到
边长为2的正方形中,至少存在两个顶点,它们之间的距离小于或等于2。
如图5-1(b)所示将边长为2的正方形分为4个边长为1的小正方形,根据鸽笼原理,5
个顶点中必有2个顶点会放到其中一个小正方形里,这两个顶点的距离显然小于或等
于2。
图5-例5.
13示意图
例5.4
在计算机中经常需要对数据进行排序,其中有一种排序算法称为插入排序。该
算法思想是:假设前i-1个数已经排好,从第i-1个数开始,从后向前,顺序将已经排好
的数与第
i
个数进行比较,直到找到第
i
个数应该放置的适当位置,然后插入第
i
个数。算
法开始时i=2,每当上述过程完成后
i
加1,直到i=
n
的过程完成为止。
试确定插入排序算法在最坏情况下的比较次数。为了简单起见,不妨设输入是
n
个不
同的数构成的数组,其中n=2k
为正整数。
k
,
解:设
W
(表示插入排序算法在最坏情况下的比较次数。如果n-1个数已经排好,
n)
为插入第
n
个数,最坏情况下需要将它与前n-1个数中的每一个都进行一次比较,因此得
到递推方程
W
(n)=
W
(-1)+n
n-1
W
(1)=0
设该方程的特解为
W
*(=将它代入递推方程得
n)P1n+P2,
P1n+P2-(P1(-1)+P2)=-1
化简得P1=n-1,左边是
n
的0次多项式,右(n) 边是
n 的1次多(n) 项式。没有常数P1 能够使
它成立。原因在于:如果特征根是1,当把特解代入方程后,在等式左边所设特解的最高次
项和常数项都被抵消了。为了保证等式两边的多项式的次数相等,必须将特解的次数提高。
不妨设特解为
W
*(=将它代入递推方程得
n)P1n2+P2n,
(2+P2(-1))
P1(n
P1n2+P2n)-(n-1)=n-1
化简得
2P1n-P1+P2=n-1
解得P1=1/2,P2=-1/2。通解为
W
(n)=nc+n(-1)/2=c+n(-1)/2
1nn
代入初值
W
(1)0, 0, n)n(1)/2。这说明
W
(=n2)。
=得c=最终得到
W
(=n-n)O(
第
章
121
122
离散数学解题指导(第3版)
5.应用案例
3
5.1
大使馆通信的码字数
3.
问题描述:某国大使馆与它的国家通信,所用的码字由长度为
n
的十进制数字串组成。
为了捕捉到传输中的错误,约定每个码字中字符3和字符7的总个数必须是奇数。可能的
码字有多少个?
解答:设sn
表示长度为
n
的容许码字的个数。下面推导s的递推关系。考虑长度为
n+1 的字
W
,它由sn+1 计数,它的末尾要么是3或7,要么都不是(n) 。如果它以3或7结尾,
那么从
W
中删除最后一个数字得到长度为
n
的字
W
*,它一定有偶数个3和7。因为共有
10n
个长度为
n
的十进制数字串,所以这种字
W
*共有10n
-sn
个。因为
W
的最后一个数
字可以是3或7,因此可能的这种形式的字
W
共有2×(10n
-sn
)个。
现在假设容许字
W
不以3或7结尾,那么删除它的最后一个数字后得到一个被sn
计
数的字。因为
W
的最后一个数字有8种可能性,所以这种形式的容许字的个数是8sn
。
综合上面两段的结果得到
n
sn+1=2×
(10-sn
)+8sn
=2×10n+6sn
其中,s0=0,因为空串不可能有表5-
1
用递推关系计算结果
n≥1 。显然,
奇数个3和7。可以利用这个递推关系计算
n
出如表5-1所示的结果。0
例如,1
s2 计算恰好有一个3或7的2位
的串的个数。因为可以用3也可以用7,又2
因为这可以是第一个数字也可以是第二个数3
字,并且因为剩下的那个数字有8种选择,因
此这样的串有2×2×8=32 个。
Sn
0
2×100+6×0=2
2×101+6×2=32
2×102+6×32=392
利用生成函数得到sn 的显式公式。设S是序列{sn}的生成函数,于是
S=s0+s1x+s2x2+s3x3+
…
有
S=s0+
(2×100+6s0)x+
(2×101+6s1)x2+
(2×102+6s2)x3+
…
12x2+
…)+6s0+s1x+s2x2+s3x3+
…)
=s0+2x(100+10x+10x(
=2+
…)+
6
0+2x(1+10x+
(10x)xS
-
=2x(1-10x)1+6xS
求解S,得到
S(1-6x)=2x(1-10x)
-1
或者
2x
S=
求常数a和b,使得
(1-6x)(1-10x)
2x
aba(1-10x)+b(1-6x)
(1-6x)(1-10x)
=
1-6x+1-10x=
(1-6x)(1-10x)
组合计数
由分子相等给出方程a+b=0和-10a-6b=2。很容易解得:a=-1/2,b=1/2。因
此有
1 -1 -1
S=-2(1-6x)1+
2(1-10x)
=
1[(1-10x)-1-(1-6x)-1]
2
1[(x2+
…)-(x2+
…)
]
=
21-10x+1001+6x+36
从中看到,S中xr 的系数是
:
rr
10-6
sr =
例如,10036)/232,3=(-
2
=392 。这些值与先前的计算相吻合。
s2=(-=s1000216)/2
5.2
条条道路通罗马
3.
问题描述:魔术表演者甲请他的临时助手乙想一个数字,然后甲用“心灵感应”来感应
乙的数字,如图5-2所示,甲可以感应出乙最终停的位置,请说明其中的数学原理。
图5-
2
条条道路通罗马
甲拿一副扑克牌,随便洗牌,发出来排好。先数牌,规则是从1~10 由乙随便选一个数
字,例如5(乙自己记住,不告诉甲), 按顺序依次数5张牌,若第5张牌的点数大于10(J、Q、
K), 则当成数字5继续数下去;若第5张牌的点数小于或等于10(A,2,3,…,10), 则按照第
5张牌的点数依次数下去;重复这一过程直到剩余牌的数目小于要数的数字时,数牌停止。
假设选的数字是5,图5-2给出了具体数牌的过程,上方标五星的是每次数的牌,从.7 开
始,最终停在.10 。【资料来源:刘炯朗.魔术中的数学[J].中国计算机学会通讯,2015
第
章
123
离散数学解题指导(第3版)
(12)】
解答:假设在魔术中乙(助手)想到的数字是6,而甲不知道乙的数字是什么。甲也选一
个数字,例如5(不一定与乙相同), 乙和甲都按照上述的规则数牌,数到最后,无法再走下去
了,可以发现乙的结果与甲的结果相同! 如图5-3所示,其中上方标记圆点为开始选数字5
的路径,上方标记菱形为开始选数字6的路径。这套魔术的秘密(数学原理)是甲可以把乙
停下的位置感应出来。
124
图5-
3
两条路径示例
还可以换别的数来尝试,例如开始选1,图5-3中上方标记五星的是数牌的路径,最后也
是停在.9 上。事实上,将一副牌排好,在数字1~10 中随便选一个,按照前面的规则数到
最后,停在同一个地方的概率大约为80% 。运气好的话,乙选的数字跟甲选的数字是会碰
头的。假如不碰头,甲可以说:“ 今天心灵感应有点问题,让我再感应一次”,最后总是能碰
头的。
这背后的数学原理是,只要助手乙和甲走的两条路中间有一点是两条路径碰头处,那么
之后的路径就是完全相同的,最后一定到达同一个地方停下来。已知52 张牌,一共是4×
(1+2+…+10)+12×5=280 点, 38 点,
平均每张牌是280÷52≈5.也就是说平均每5张就
会有一张在所选的路径上,那么在每5张牌中碰到的概率约为1/5,因此在这52 张牌中完
-10≈0.
全碰不上的概率约为(11/5)107,最终碰上的概率约为0.893 。上面这个模型是数学
8524,
家做出来的,但是通过模拟,可以发现结果也差不多,约为0.见图54。因此,乙想一
个数字,甲想一个数字,两条路径走到同一个终点的概率大概是85%~89% 。正如福尔摩
斯所说:当沿着两条不同的思路思考时,就会找到一个相交点,那应该就是相当接近真
相了。
组合计数
第5章
1 25
图5-4 “条条道路通罗马”的数学原理
5.4 习题解答
5.1 当执行完以下的代码后,k的值是多少?
k=0
for i1:=1 to n1
for i2:=1 to n2
.
for im:=1 to nm
k:=k+1
解:由于这个程序是从k=0开始,不断地给k 加1,而加1的个数就是执行循环的次
数,即n1n2…nm 次,所以当执行完代码后,k 的值是n1n2…nm 。
5.2 在一幅数字图像中,若将每个像素用8位进行编码,那么每个点有多少种不同的
取值?
解:用8位进行编码又分为8个步骤:选择第一个位,选择第二个位,…,选择第八个
位。每一位有两种选择,故根据乘法原理,8位编码共有2×2×2×2×2×2×2×2=28=
256种取值。
5.3 X 为n 个元素的集合,有多少满足A .B.X 的有序对(A ,B)?
解:给定一个满足A .B .X 的有序对(A ,B ),可知X 的每个元素必属于且仅属于
A 、B-A 、X -B 中的一个集合。反之,若指定X 的每一个元素到A(该元素在B 和X 中)、
B-A(该元素在X 中)、X -B 三个集合中的一个,也就唯一确定了满足A .B .X 的有序
对(A ,B)。可见,满A .B.X 的有序对(A ,B)的个数等于将集合X 中的元素指定到A 、
B-A 、X -B 三个集合的不同指派数。将这样的指派分为n 个步骤:指定X 中的第一个
元素到A 、B-A 、X -B 三个集合中的一个;指定X 中的第二个元素到A 、B -A 、X -B 三
个集合中的一个;……;指定X 中的第n 个元素到A 、B-A 、X -B 三个集合中的一个。每
一步有三种指定方法,故满足A .B.X 的有序对(A ,B)的个数为3....×..3..×....…..×....3 n个3
=3n 。
5.4 按字典序列出{1,2,3,4}上的所有排列以及{1,2,3,4,5,6}上的所有4组合。
解:{1,2,3,4}上的所有排列为
1234,1243,1324,1342,1423,1432,2134,2143,
2314,2341,2413,2431,3124,3142,3214,3241,
3412,3421,4123,4132,4213,4231,4312,4321
离散数学解题指导(第3 版)
12 6
{1,2,3,4,5,6}上的所有4组合为
1234,1235,1236,1245,1246,1256,1345,1346,
1356,1456,2345,2346,2356,2456,3456
与r 组合生成算法类似,排列生成算法可按字典序列出{1,2,…,n}上的所有排列。
5.5 若按字典序列出X ={1,2,3,4,5,6,7}上所有的4组合,则2367的下一个字串是
什么?
解:以23开头的最大的字串为2367,故字串2367的下一个字串以24开头。因为字串
2456是以24开头的最小的字串,故字串2367的下一个字串是2456。
5.6 说明排列生成算法如何生成163542的后继,应使左边尽可能多的数字保持不变。
解:见主教材例5.14。
5.7 求(a+b)9 展开式中a5b4 项的系数。
解:在二项式定理中令n=9,k=4,得展开式含a5b4 的一项为
C(n,k)an-kbk =C(9,4)a5b4 =126a5b4
故a5b4 项的系数为126。
5.8 求和:12+22+…+n2。
解:先求{n2}的生成函数A(x)= Σ∞
n=0
n2xn 。由1
(1-x)2 =Σ∞
n=1
nxn-1,得x
(1-x)2 =
Σ∞
n=1
nxn 。对上式两边求微分得1+x
(1-x)3 = Σ∞
n=1
n2xn-1,所以有(1+x)·x
(1-x)3 = Σ∞
n=1
n2xn =
Σ∞
n=0
n2xn =A(x)。令bn =Σn
i=1
ai,根据性质5.6可知,{bn}的生成函数是B(x)=A(x)
1-x =
x(1+x)
(1-x)4 = x
(1-x)4 + x2
(1-x)4。所以B(x)的展开式中xn 的系数是bn =
(n+2)(n+1)n
6 + (n +1)n(n -1)
6 =n(n +1)(2n +1)
6 。从而得到级数和12 +22 + …+
n2 =n(n +1)(2n +1)
6 。
5.9 证明:对于n 是正整数,有
1×
n1
.
è .
.
. ÷
+2×
n2
.
è .
.
. ÷+ … +n ×
n
n
.
è .
.
. ÷
=n ×2n-1
证明:由二项式定理(1+x)n = Σn
k=0
n
k
.
è .
.
.÷kxk-1,两边求导数得n(1+x)n-1 =
Σn
k=1
n
k
.
è .
.
.÷kxk-1。令x =1,即为要证明的等式。
5.10 列表中有80件物品的清单,每个物品的属性为“可用”或“不可用”,共有45个
“可用”物品,证明:至少有两件可用物品编号之差恰为9。例如,列表中可用物品13号和
22号,或69号和78号都满足条件。
证明:令ai 表示第i 个可用物品的编号,则只需证明存在i 和j,使ai-aj =9。考虑
两组数字:a1,a2,…,a45和a1+9,a2+9,…,a45+9。两组中90个数字的取值范围为1~
89,根据鸽笼原理的第二种形式,必有两个数字相等。由于前一组中的数字两两不同,后一