例4.2.2 确定方程 x1+x2+x3=12
(-1≤ x1 ≤2, 1≤ x2 ≤5, 2≤ x3 ≤7) 的整数解的个数.
解：令y1= x1+1, y2= x2-1, y3= x3-2, 则有0≤ y1 ≤3， 0≤ y2 ≤4， 0≤ y3 ≤5，
用y1-1代替 x1 ，y2+1代替x2，y3+2代替x3得： y1+y2+y3=10 (0≤ y1 ≤3， 0≤ y2 ≤4， 0≤ y3 ≤5) 这个 方程的整数解的个数就是原来方程的整数解的个 数，即为多重集{3·a,4·b,5·c}的10-组合数。参 照例4.2.1的方法，结果为6。
2143,2341,2413,3142,3412,3421,4123,4312,4321， D4=9; … … … … … … 对于一般的n, 有以下的定理.
定理4.3.1 对于n≥1有
D n!(1 1 1 1 (1)n 1 )
n
1! 2! 3!
n!
证明：
设 τ = 12,…,n，
5
1! 2! 3! 4! 5!
60 20 5 1 44
（2）先从123456789中选取4个数的取法 为C(9,4), 再对其他5个数的错位排列，错 位排列数为D5，根据乘法法则有：
9 D 126 44 5544 5 5
例P71(4.8) 证明下列等式
则 Qn | A1 A2 An1 | (1) 先计算|A1|,一个排列属于A1当且仅当12
出现在这个排列里. 所以A1中的排列就是 {12,3,4,…,n}的一个排列, 因此|A1|=(n1)!,同理对j=2,…,n-1,也有|Aj|=(n-1)!,
(2)然后计算|Ai∩Aj|，其中{i,j}是{1,2,…,n-1}的 一 i(i+个12)和-组j(合j+1，)都一出个现排在列这属个于排Ai列∩A里j 当. 分且两仅种当情 况：
§ 4.3 错位排列
错位排列源自一个古老的“装错信封问题”， 它是由数学家约翰·伯努利(Johann Bernoulli)的 儿子丹尼尔·伯努利(Danid Bernoull)提出来的， 并曾被著名数学家欧拉(Euler)称为“组合数论 的一个妙题”。其大意为：一个人写了n封不同 的信及相应的n个不同的信封，他把这n封信都 装错了信封，问都装错信封的装法有多少种？
| A |
28
1

6
6 2
同理可得：
3 5 1 7 7
| A |
21
2 5 5 2
3 4 1 6 6
| A |
15
3

4
4 2
用类似的方法可以计算
| A A | 3 11 3, 1 2 1
| A A | 3 0 1 3,
1
3

0

| A A | 0,| A A A | 0.
2
3
1
2
3
所以S的10-组合数为
| A A A | 66 （28 21 15）（3 1 0） 0 6.
b的个数小于等于4， 并且c的个数小于等于5的10组合个数。
令Ai={ x|x∊W并且x具有性质Pi} A1中的每个10-组合至少含有4个a, 把4个a 拿走就得到T的一个6-组合。反之，对T的
任意一个6-组合加上4个a就得到A1的一个 10-组合，所以|A1|就是T的6-组合数，即
3 6 1 8 8
n
D n! (n 1)! (n 2)!
n
1
2
(1)n n 0! n
n! n! n! n! (1)n n!
1! 2! 3!
n!
n!(1 1 1 1 (1)n 1 )
1! 2! 3!
1
2
同理，对于{1,2,…,n}的任何一个2-组合{i,j}
有：
| A A | (n 2)!
i
j
(3) 一般的，对于任意的整数k, 1≤k≤n, 有
其中i1,i2…,ik是{1,2,…,n}的一个k-组合。
| A A A | (n k)!
i1
i2
ik
根据容斥原理得：
n
其中i1i2…in是{2,3,…,n}的一个排列，
所以 | A | (n 1)! 。 1
同理，对于j= 2,3,…,n,有 | A | (n 1)! j
Hale Waihona Puke (2) A A 中的排列具有下面的形式：
1
2
12i3…in ，其中i3i4…in是{3,4,…,n}的一个
排列，所以 | A A | (n 2)!
| A1 A2 Am | W (0) W (1) W (2) W (3) (1)m W (m)
定理4.1.2（Jordan公式） 集合 S中恰具有 r(0≤r ≤m)种性质的事物的个数
N(r) W (r) r 1W (r 1) r 2W (r 2) (1)mrmW (m)
S中不具有性质P1, P2,…,Pm的元素数是
A1 A2 Am
m
S Ai Ai Aj Ai Aj Ak
i1
1i jm
1i jkm
A A (1)m
1
2
Am
这样定理4.1.1就变成下面的形式：
N(0) N mN(1) mN(2) (1)mmN(m)
成一列，记作a1 a2 …a8,其中a1排在最前面， a8排在最后面。现在对这八个孩子重新排列成 ai1 ai2 …ai8,使得没有ai和ai+1在队列中出现， 1≤i≤7, 问有多少种排列的方式？
这个问题就是一个有限制条件的排列问题.
一、定义 一般来说，令I={1,2,…,n}，在I的排列 中不出现12,23,34,…(n-1)n的排列就叫做 有限制条件的排列，把这种排列的个数 记为Qn.
n! nD nD n D nD
0 n 1 n1
n 1 1 n 0
证明：将S={1,2,…,n}的所有排列分成下列 情况，没有一个数在其自然位置上的排列
数为
n 0 Dn
；恰有i个数在其自然位
1
2
3
列出这6个10-组合如下： {1·a,4·b,5·c}， {2·a,3·b,5·c}， {2·a,4·b,4·c} {3·a,2·b,5·c}， {3·a,3·b,4·c}， {3·a,4·b,3·c}
• 多重集的r－组合数等于方程的非负整数解 的个数。 • 用容斥原理来确定方程的非负整数解的个数
X={1,2,…,n}.
S---X的所有排列的集合。
性质Pj---在一个排列中，如果j在第j个位置 上，则该排列具有性质Pj,对j=1,2,…,n,.
Aj表示S中具有性质Pj的排列的集合，
则 τ 的错位排列数就是 A A2 A
1
n
中的排列。
（1）A1中的排列具有下面的形式1i1i2…in,
Qn

n! n11
(n
1)! n21
(n

2)!
(1)
n1
n n
11 1!
证明：设I={1,2,…,n}，I的排列有n!个，
S----这些排列构成的集合.
性质Pj ----如果X的排列中有j(j+1)出现，则 称这个排列具有性质Pj,对于j= 1,2,…,n-1, Aj ----具有性质Pj的排列构成的子集，
四、例题（例4.3.1） （1）重新排列123456789，使得偶数在
原来的位置上而奇数不在原来的位置上，问 有多少种排法？
（2）如果要求只有4个数在原来的位置 上，问有多少种排法？
解：（1）这是1，3，5，7，9五个数的错 排问题，根据定理4.3.1得：
D 5!(1 1 1 1 1 1 )
这个问题就是一个典型的错位排列问题。
一、定义
设τ={1,2,…,n}, τ的一个错位排列就是排列
i1i2…in, 且ij≠j, j=1,2, …,n.
用Dn表示τ的错位排列数。
二、计算公式
当n=1时，不存在错位排列， D1=0; 当n=2时，错位排列只有21， D2=1;
当n=3时，错位排列有231, 312， D3=2; 当n=4时，错位排列有
例4.2.1 确定多重集S={3·a,4·b,5·c} 的10-组合数。
解：令T= {∞·a,∞ ·b，∞ ·c} ,T的所有10-组合构成 集合W,根据定理3.3.3得：
| W | 3 10 1 12 12 66 10 10 2
任取T的一个10-组合， 如果其中的a多于3个，则称它具有性质P1; 如果其中的b多于4个，则称它具有性质P2; 如果其中的c多于5个，则称它具有性质P3， 因的此元S的素1个0-数组，合即数W就中是同W时中满同足时a不的具个有数性小质于P等1,P于2和3，P3
第四章 容斥原理
Inclusion and Exclusion Principle
(包含排斥原理)
主要内容
§4.1 容斥原理
§4.2 多重集的r-组合数
§4.3 错位排列
应用
§4.4 有限制条件的排列问题
§4.5 有禁区的排列问题
§4.6 Möbius反演
这时容斥原理可叙述为：
定理4.1.1 （容斥原理）
(2.1) i+1=j, 这时排列中出现i(i+1)(i+2),这种排 列就是 {1,2,…,i-1,i(i+1)(i+2),i+3,…,n-1}的一 个排列, 因此|Ai∩Aj|=(n-2)!