04 第四章 容斥原理.pptx

第1页：封面

第四章容斥原理Inclusion and Exclusion Principle(包含排斥原理)

第2页：容斥原理导读内容导览

主要内容§4.1容斥原理§4.2多重集的r-组合数§4.3错位排列§4.4有限制条件的排列问题§4.5有禁区的排列问题§4.6Möbius反演应用

第3页：容斥原理

§4.1容斥原理是求解组合计数问题常用的工具之一是加法法则的推广它给出了用满足某些性质的元素个数来表示不满足这些性质的元素个数的计数公式。

第4页：例在1-n的全排列

例在1-n的全排列中，1不在第一个位置的排列数是多少？

一、具有一种性质的情形解先求在1和500之间可以被5整除的个数有500÷5 =100个，则不能被5整除的数有500－100=400个。

例4.1.1求在1,2,…,500中不能被5整除的数的个数。

第5页：可以写成或者其中为A相

• 可以写成或者其中为A相对于S的补集.
• 这两个例子实际上用到如下原理：如果A是集合S的子集，则在A中的元素个数等于S的元素个数减去不在A中的元素个数。

第6页：解：先求5和6相邻的七位数

解：先求5和6相邻的七位数的个数N1.N1=2×6!×C(7,5)=30240不同数字的七位数有P(9,7)个，根据定理5.1,所求的七位数个数N= P(9,7)-N1=151200例从{1,2,…,9}中取7个不同的数字构成七位数，如果不允许5和6相邻，问有多少种方法？

第7页：二、具有两种性质的情形设S为有穷

二、具有两种性质的情形设S为有穷集,P1和P2分别表示两种性质。

A1表示S中具有性质P1的子集。

A2表示S中具有性质P2的子集。

第8页：则S中既不具有性质P1也不具有性

则S中既不具有性质P1也不具有性质P2的元素个数为：例在1-n的全排列中，1不在第一个位置，并且2不在第二个位置的排列数是多少？

第9页：三、具有三种性质的情形则S

三、具有三种性质的情形则S中既不具有性质P1也不具有性质P2也不具有性质P3的元素个数为：设S有穷集, P1P2P3分别表示三种性质。

A1A2A3分别表示S中具有性质P1P2P3的子集。

第10页：例4.1.2 在1-1000中不能被5,

例4.1.2求在1-1000中不能被5,6,8整除的数的个数。

解：令P1,P2和P3分别表示一个整数能被5，6和8整除的性质。

S={x|x是整数并且1<x<1000},Ai={x|x∈S⋀x具有性质Pi}, i=1,2,3.则有下面结果：|A1|=⌊1000/5⌋=200,|A2|=⌊1000/6⌋=166,|A3|=⌊1000/8⌋=125,

第11页：|A1A2|=⌊1000/[

|A1A2|=⌊1000/[ 5,6]⌋=⌊1000/30⌋=33|A1A3|=⌊1000/[ 5,8]⌋=⌊1000/40⌋=25|A2A3|=⌊1000/[ 6,8]⌋=⌊1000/24⌋=41| A1A2A3|=⌊1000/[ 5,6,8]⌋=⌊1000/120⌋=8根据定理4.1.1得

第12页：上面问题的小结

上面问题的小结

第13页：四、一般情形设S是有穷集

四、一般情形设S是有穷集，P1, P2,…,Pm是m个性质。

对于性质pi(i=1,2,…,m),S中的任何一个元素x或具有或不具有，两者必居其一。

Ai表示S中具有性质pi的元素构成的子集。

第14页：这时容斥原理可叙述

这时容斥原理可叙述为：定理4.1.1（容斥原理）S中不具有性质P1, P2,…,Pm的元素数是

第15页：证明：（贡献法

证明：（贡献法，思想）等式左边是S中不具有性质P1, P2,…，Pm的元素数。

我们将要证明，对S中的任何一个元素x,如果x不具有性质P1, P2,…，Pm，则对等式右边的贡献为1；

如果x至少具有其中的一条性质，则对等式右边的贡献为0。

设x不具有性质P1, P2,…，Pm，所以x Ai,i=1,2 …,m.令T={1,2, …,m}.对T的所有的2-组合{i,j}都有x AiAj,对T的所有的3-组合{i,j,k}都有x AiAjAk，…，直到x A1A1…Am,但x S,所以它对等式右边

第16页：的贡献是1-0+0-0+…+

的贡献是1-0+0-0+…+(-1)m0=1.设x具有n条性质，n>=1.则x对|S|的贡献为1，对的贡献为n= ,对的贡献为，对的贡献为所以x对等式右边的总贡献是：证明结束。

第17页：例４.1.3 对50辆汽车做氧化氮

例４.1.3对50辆汽车做氧化氮（NOx）、碳氢化合物（HC）和一氧化碳（CO）的污染物排放量的测试。

其中，1辆汽车的排放量超过所有三种污染物的环境标准，3辆汽车NOx和HC超标，2辆汽车NOx和CO超标，1辆汽车HC和CO超标，6辆汽车NOx超标，4辆汽车HC超标，3辆汽车CO超标，计算有多少辆汽车符合所有三种污染物的环境标准？

第18页：解令S是这50辆汽车的集合

解令S是这50辆汽车的集合，性质P1是NOx超标，性质P2是HC超标，性质P3是CO超标，Ai={x∣x∈S∧x具有性质Pi}，i = 1,2,3。

根据定理4.1.1得

第19页：1,推论在S中至少具有一条性质

1,推论在S中至少具有一条性质的元素数是证明：根据De Morgan定律

第20页：2,对称筛公式若性质P

2,对称筛公式若性质P1,P2,…,Pm是对称的，即具有k个性质的事物个数不依赖于这k个性质的选取，总是等于同一个数值，则这个值称为公共数，记为N(k)。

第21页：对称筛公式这样定理4.1.1就变

对称筛公式这样定理4.1.1就变成下面的形式：

第22页：例４.1.6 有多少种分法？解显然S是这

例４.1.6将20个学生分成不同的3个组，每组至少有1个学生，求有多少种分法？

解显然S是这20个学生不加以限制的分成3个不同组的方法的集合，则|S|=320。

因为3个组是不同的，我们分别加以编号1，2，3。

则性质P1,P2,P3分别表示1组，2组和3组为空。

显然这三条性质是对称的，符合对称筛公式。

有：N(1)=220, N(2)=1, N(3)=0,所以共有320-3×220+3=3483638676种分法。

本页含连续数字序列（方阵图、排列序号表等），源文本无法安全切分，需对照原课件图片人工还原为真表格。

第23页：3,引入如下的记号

3,引入如下的记号：则定理4.1.1的公式可写成：

第24页：定理4.1.2（Jordan公式） 集合

定理4.1.2（Jordan公式）集合S中恰具有r(0≤r≤m)种性质的事物的个数（广义包含排斥原理）

第25页：例４.1.5 对50辆汽车做氧化氮

例４.1.5对50辆汽车做氧化氮（NOx）、碳氢化合物（HC）和一氧化碳（CO）的污染物排放量的测试。

其中，1辆汽车的排放量超过所有三种污染物的环境标准，3辆汽车NOx和HC超标，2辆汽车NOx和CO超标，1辆汽车HC和CO超标，6辆汽车NOx超标，4辆汽车HC超标，3辆汽车CO超标，求有多少辆汽车正好超出1种污染物的环境标准？

第26页：解即我们要求的是N(1).容易计

解即我们要求的是N(1).容易计算：W(1)=6+4+3=13，W(2)=3+2+1=6，W(3)=1,则根据定理4.1.2有=13-2×6+3×1=4.因此，有4辆汽车正好超出1种污染物的环境标准。

第27页：例4.1.4 设n是正整数

例4.1.4设n是正整数,n>=2,欧拉函数表示小于n且与n互质的正整数的个数。

求的表达式。

解：任何大于等于2的正整数n都有如下的分解形式：其中p1,p2,…pk为质数。

令S={x|x是小于等于n的正整数}，Ai={x|x∈S⋀pi整除x}, i=1,2,…k.

第28页：则有下面的结果

则有下面的结果：|S|=n，|Ai|=⌊n/pi⌋=n/pii=1,2,…k|AiAj|=⌊n/[pi,pj]⌋=n/(pipj) 1≤i<j≤k………………|A1A2…Ak|=⌊n/[p1,p2,…pk]⌋=n/(p1p2…pk)

第29页：由定理4.1.

由定理4.1.1得：

第30页：例如：30=2×3×

例如：30=2×3×5，则即与30互质的正整数有8个，分别是1,7,11,13, 17,19,23,29.

第31页：例4.2.1 确定多重集S={3·a

例4.2.1确定多重集S={3·a,4·b,5·c}的10-组合数。

§4.2多重集的r-组合数求多重集S={n1·a1, n2·a2,…,nk·ak} r-组合数假定每个ni≤r，i=1,2,…,n.用容斥原理求S的r-组合数，第五章将介绍另外一种方法-生成函数的方法

第32页：解：令T={∞·a

解：令T={∞·a,∞·b，∞·c},T的所有10-组合构成集合W,根据定理3.3.3得：任取T的一个10-组合，如果其中的a多于3个，则称它具有性质P1;如果其中的b多于4个，则称它具有性质P2;如果其中的c多于5个，则称它具有性质P3，因此S的10-组合数就是W中同时不具有性质P1,P2和P3的元素个数，即W中同时满足a的个数小于等于3，b的个数小于等于4，并且c的个数小于等于5的10-组合个数。

第33页：令Ai={ x|x∊W并且x

令Ai={ x|x∊W并且x具有性质Pi}A1中的每个10-组合至少含有4个a,把4个a拿走就得到T的一个6-组合。

反之，对T的任意一个6-组合加上4个a就得到A1的一个10-组合，所以|A1|就是T的6-组合数，即同理可得：

第34页：用类似的方法可以计算所以S

用类似的方法可以计算所以S的10-组合数为

第35页：列出这6个10-组合如下

• 列出这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－组合数等于方程的非负整数解的个数。
• 用容斥原理来确定方程的非负整数解的个数

第36页：例4.2.2 确定方程x1+x2+x3=

例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。

第37页：错位排列

§4.3错位排列错位排列源自一个古老的“装错信封问题”，它是由数学家约翰·伯努利(Johann Bernoulli)的儿子丹尼尔·伯努利(Danid Bernoull)提出来的，并曾被著名数学家欧拉(Euler)称为“组合数论的一个妙题”。

其大意为：一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？

这个问题就是一个典型的错位排列问题。

第38页：设τ={

设τ={1,2,…,n},τ的一个错位排列就是排列i1i2…in,且ij≠j, j=1,2,…,n.用Dn表示τ的错位排列数。

一、定义二、计算公式当n=1时，不存在错位排列，D1=0;当n=2时，错位排列只有21，D2=1;

第39页：对于一般的n

对于一般的n,有以下的定理.定理4.3.1对于n≥1有当n=3时，错位排列有231, 312，D3=2;当n=4时，错位排列有2143,2341,2413,3142,3412,3421,4123,4312,4321，D4=9;… … … … … …

第40页：证明：设τ=

证明：设τ=12,…,n，X={1,2,…,n}.S---X的所有排列的集合。

性质Pj---在一个排列中，如果j在第j个位置上，则该排列具有性质Pj,对j=1,2,…,n,.Aj表示S中具有性质Pj的排列的集合，则τ的错位排列数就是中的排列。

第41页：（1）A1中的排列具有下面的形式

（1）A1中的排列具有下面的形式1i1i2…in,其中i1i2…in是{2,3,…,n}的一个排列，所以。

同理，对于j= 2,3,…,n,有(2)中的排列具有下面的形式：12i3…in，其中i3i4…in是{3,4,…,n}的一个排列，所以同理，对于{1,2,…,n}的任何一个2-组合{i,j}有：

第42页：(3)一般

(3)一般的，对于任意的整数k, 1≤k≤n,有其中i1,i2…,ik是{1,2,…,n}的一个k-组合。

根据容斥原理得：

第43页：三、Dn的递推关系

三、Dn的递推关系1

第44页：三、Dn的递推关系2Dn=(

三、Dn的递推关系2Dn=(n-1)(Dn-1+Dn-2), n≥3, n为整数D1=0, D2=1根据这个等式可以计算任意一个Dn的值。

第45页：所以当n比较大的时

所以当n比较大的时，而表示的错位排列数与X的排列数之比，即错位排列数出现的概率，这说明在n很大的时候，这个概率可看作1/e。

第46页：四、例题

四、例题（例4.3.1）在一次聚会上，6位先生各自寄存自己的帽子。

有多少种方法使得这些帽子返还时满足：（1）每位先生拿到的都不是自己原来的帽子；

（2）至少有一位先生拿到的是自己原来的帽子。

第47页：解（1）这是6个元素的错位排列问

解（1）这是6个元素的错位排列问题，显然有D6=265种方法。

（2）首先，所有返回帽子的方法数是6！

种，至少有一位先生拿到的是自己原来的帽子就是没有错位的排列，所以方法数应该是6!-265=455种。

第48页：补例：（1）重新排列

补例：（1）重新排列123456789，使得偶数在原来的位置上而奇数不在原来的位置上，问有多少种排法？

（2）如果要求只有4个数在原来的位置上，问有多少种排法？

解：（1）这是1，3，5，7，9五个数的错排问题，根据定理4.3.1得：

第49页：（2）先

（2）先从123456789中选取4个数的取法为C(9,4),再对其他5个数的错位排列，错位排列数为D5，根据乘法法则有：

第50页：例P104(4.9)证明下列等式

例P104(4.9)证明下列等式证明：将S={1,2,…,n}的所有排列分成下列情况，没有一个数在其自然位置上的排列数为；

恰有i个数在其自然位置上的排列数为(i=1,2,…,n),根据加法法则，而所有的排列个数为n!,等式成立。

第51页：错位排列的限制是对元素排列位置

错位排列的限制是对元素排列位置的限制。

本节介绍另外一类有限制条件的排列问题，是对元素之间的相邻关系的限制。

§4.4有限制条件的排列问题

第52页：例:有八个孩子外出散步

例:有八个孩子外出散步，他们排成成一列，记作a1a2…a8,其中a1排在最前面，a8排在最后面。

现在对这八个孩子重新排列成ai1ai2…ai8,使得没有ai和ai+1在队列中出现，1≤i≤7,问有多少种排列的方式？

这个问题就是一个有限制条件的排列问题.

第53页：一、定义一般来说

一、定义一般来说，令I={1,2,…,n}，在I的排列中不出现12,23,34,…(n-1)n的排列就叫做有限制条件的排列，把这种排列的个数记为Qn.二、当n=1时，Q1=1;当n=2时，所求排列为21，Q2=1;当n=3时，所求排列为213,321, 132,Q3=3;

第54页：对于一般的正整数n

对于一般的正整数n，有下面的定理：定理4.4.1对于n≥1有当n=4时，所求排列为4132,4321,4213,3214,3241,3142,2431,2413,2143,1324,1432，所以Q4=11;

第55页：证明：设I={

证明：设I={1,2,…,n}，I的排列有n!个，S----这些排列构成的集合.性质Pj----如果X的排列中有j(j+1)出现，则称这个排列具有性质Pj,对于j= 1,2,…,n-1,Aj----具有性质Pj的排列构成的子集，则(1)先计算|A1|,一个排列属于A1当且仅当12出现在这个排列里.所以A1中的排列就是{12,3,4,…,n}的一个排列,因此|A1|=(n-1)!,同理对j=2,…,n-1,也有|Aj|=(n-1)!,

第56页：(2)然后计算|Ai∩Aj|

(2)然后计算|Ai∩Aj|，其中{i,j}是{1,2,…,n-1}的一个2-组合，一个排列属于Ai∩Aj当且仅当i(i+1)和j(j+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)!(2.2) i+1≠j,这时排列中出现i(i+1)和j(j+1),这种排列就是{1,2,…,i-1,i(i+1),…,j(j+1),…,n-1}的一个排列,因此|Ai∩Aj|=(n-2)!(3)同理，对于任意的1≤k≤n-1,有根据包含排斥原理得证。

第57页：三、有限制条件的排列与错位排

三、有限制条件的排列与错位排列的联系将定理4.4.1的等式变形得到：Qn=Dn+Dn-1证明：

第58页：

本页源文件未提取到正文文字，仅有图片。该页位于「三、有限制条件的排列与错位排」与「下一页」之间，建议对照原课件图片补充本页要点说明。

第59页：

本页源文件未提取到正文文字，仅有图片。该页位于「」与「四、有限制条件的环排列问题有n」之间，建议对照原课件图片补充本页要点说明。

第60页：四、有限制条件的环排列问题有n

四、有限制条件的环排列问题有n个小孩坐在旋转木马上，如果让他们交换座位，使得每个小孩前面都不是他原来前面的孩子，问有多少种方法？

解：设I={1,2,…,n}，I的排列有(n-1)!个，S----这些排列构成的集合.性质Pj---如果X的环排列中有j(j+1)出现j=1,…,n-1,则称这个环排列具有性质Pj,对于

第61页：Aj----具有性质Pj的环排列

Aj----具有性质Pj的环排列构成的子集，则利用与定理5.3类似的方法不难得到

第62页：棋盘多项式有禁区的排列问题求

棋盘多项式有禁区的排列问题求解例题§4.5有禁区的排列问题

第63页：有禁区的排列问题指一类对元素排列

有禁区的排列问题指一类对元素排列位置有限制的问题。

例如：不允许1排在第2位；

且不允许2排在第3位；

1 2 3 41234

第64页：棋盘布棋问题1 2 3

• 棋盘布棋问题1 2 3 41234棋盘的行表示X中元素列表示相应元素在排列中的位置设I={1,2,…,n}则I的一个排列恰好对应n个相同棋子在n×n的棋盘上的一种布棋方案。
• 这种布棋方案对应排列3124

第65页：如果在排列中限制元素i不能排在第

如果在排列中限制元素i不能排在第j个位置，则相应的布棋方案中棋盘的第i行和第j列的方格不允许放棋子。

将所有不允许放棋子的方格称为禁区。

第66页：设C是一个棋盘

设C是一个棋盘，表示把k个相同的棋子布到C中的方案数。

在布棋时我们规定：当一个棋子放到C中的某个格以后，这个格所在的行和列就不能再放其他的棋子了。

规定对任意的棋盘C有：(C)=1一、布棋方案数

第67页：设C是一个棋盘矩阵图

= 2)(1r)(1r= 0)(2r)(2r)(2r

本页为数字或符号粘连序列（幻方、拉丁方等方阵图或公式提取结果），源文本无法安全切分，需对照原课件图片人工核对还原。

第68页：布棋方案数

布棋方案数（C）具有如下性质（1）对于任意的棋盘C和正整数k，如果k大于C中的方格数，则（C）=0。

（2）（C）等于C中的方格数。

（3）设C1和C2是两个棋盘，如果C1经过旋转或者翻转就变成了C2，则(C1)=(C2)。

（4）设Ci是从棋盘C中去掉指定的方格所在的行和列以后剩余的棋盘，Cl是从棋盘C中去掉指定的方格以后剩余的棋盘，则有

第69页：CCiCl

CCiCl

第70页：(5)设棋盘C由两个子棋盘C

(5)设棋盘C由两个子棋盘C1和C2组成，如果C1和C2的布棋方案是互相独立的，则有C2C1C2C1图(a)C1和C2的布棋方案相互独立图(b)C1和C2的布棋方案不相互独立

第71页：二、棋盘多项式定义4.5.1设C

• 二、棋盘多项式定义4.5.1设C是棋盘，则叫做棋盘多项式.
• R(C)一般只有有限项。

第72页：R(C)的性质(1)R(C)

R(C)的性质(1)R(C)=xR(Ci)+R(Cl), Ci和Cl含义如前所述。

证明：

第73页：(2) R(C)=R(C

• (2) R(C)=R(C1)
• R(C2), , C1和C2含义如前所述。将以上各式的两边分别相加得：证明：

第74页：解R()=xR( )+R(

解R()=xR( )+R( )=x(1+2x)+R( )R( )=x+2x2+(1+x)(xR( )+R( ) )=x+2x2+(1+x)(x(1+x)+(1+3x+x2))=x+2x2+(1+x)(1+4x+ 2x2))=x+2x2+ (1+5x+ 6x2+2x3)=1+6x+8x2+2x3例4.5.1计算棋盘多项式R()

第75页：例计算R( )解

例计算R( )解：R( )=xR( )+R( )=xR( )+R( )R( )=x(1+2x+x2)+(1+2x)(1+3x+x2)= 1 +6x+ 8x2+ 3x3

第76页：例计算R( )解矩阵图

R( )=x·R( )+R( )=x(1+x)+(1+2x)=1+3x+x2R( )=x·R( )+R( )=x·[x·R( )+R( )]+[x·R( )+R( )]=x[x(1+2x)+(1+3x+x2)]+[x(1+3x+x2)+1+4x+3x2]=1+6x+10x2+4x3

本页为数字或符号粘连序列（幻方、拉丁方等方阵图或公式提取结果），源文本无法安全切分，需对照原课件图片人工核对还原。

第77页：定理4.5.1 设C是n×n的具有给定禁

定理4.5.1设C是n×n的具有给定禁区的棋盘，这个禁区对应于集合{1,2,…,n}中的元素在排列中不允许出现的位置。

则这种有禁区的排列数是n!-r1(n-1)!+ r2(n-2)!-…+(-1)nrn其中ri表示i个棋子布置到禁区的方案数。

三、有禁区的排列问题利用棋盘多项式

第78页：证明：(1)S----带编号

证明：(1)S----带编号的棋子布到n×n棋盘上的方案构成的集合。

n个棋子布到n×n棋盘上方案有n!个。

如果对n个棋子分别编号1,2,…,n，并且认为编号不同的棋子放入同样的方格是不同的放置方案，那么这些方案数是n！

×n！

Pj-----第j个棋子落入禁区的性质，j=1,2,…,nAj-----S中具有性质Pj的方案构成的子集，那么所求的排列数就是

第79页：(2)1号棋子落入禁区的方案数

(2)1号棋子落入禁区的方案数为r1，当它落入禁区的某一格以后，2,3,…,n号棋子可以任意放置在(n-1)×(n-1)的棋盘上，由乘法法则得:|A1|=r1(n-1)!(n-1)!同理对i= 2,3,…,n有|Ai|=r1(n-1)!(n-1)!对i求和得：(3)1号和2号两个棋子落入禁区的方案数为2r2,它们落入以后，3,4,…,n号棋子可以任意放置在(n-2)×(n-2)的棋盘上，所以|A1∩A2|=2r2(n-2)!(n-2)!

第80页：同理对{i

同理对{i,j}∊{1,2,…,n}有|Ai∩Aj|=2r2(n-2)!(n-2)!，对所有的1≤i<j ≤n求和有

第81页：…………………|A1∩A2∩

…………………|A1∩A2∩…∩An|=rn·n!(4)根据包含排斥原理，带编号的n个棋子都不落入禁区的方案数是(5)而带编号的方案数与不带编号的方案数相差n!倍，因此结论成立，即：

第82页：这个定理适用于小禁区的布棋问题

这个定理适用于小禁区的布棋问题，如果是m×n的禁区或者是很大的禁区，那么只能直接求R(C)来求解。

第83页：例4.5.3 排列数

例4.5.3考虑如下有禁区的5×5的棋盘，阴影部分是禁区，求排列数。

第84页：解：首先求禁区的棋盘多项式R

解：首先求禁区的棋盘多项式R(x)=1+10x+35x2+50x3+25x4+2x5，所以所求排列数N=5!-r1×4!+r2×3!–r3×2!+r4×1!–r5×0!=5!-10×4!+35×3!–50×2!+25×1!–2×0!=13

第85页：例4.5.2 错位排列问题也可以看成是有

例4.5.2错位排列问题也可以看成是有禁区的排列问题，其禁区在主对角线上，下面根据定理4.5.1来求Dn.解：禁区的棋盘多项式是R( )=R( )·R( )·…·R( )n个=(1+x)n从而得r1=n,r2= ,…,rn=代入定理4.5.1得

第86页：

本页源文件未提取到正文文字，仅有图片。该页位于「例4.5.2 错位排列问题也可以看成是有」与「德国数学家」之间，建议对照原课件图片补充本页要点说明。

第87页：德国数学家

德国数学家、天文学家Möbius于1832年发现的经典数论结果是研究两个整型变量函数f(n)和g(n)互相表示的问题§4.6 Möbius反演

第88页：反演基本想法

• 反演基本想法：{an}易算，{bn}难算，{an}可用｛bn｝表示，利用反演，将{bn}用{an}表示．
• 二项式反演

第89页：Möbius函数定义设n∈Z+

Möbius函数定义设n∈Z+1，若n = 1;μ( n ) =0，若n = p1α1p2α2···pkαk存在αi>1(－1)k，若n = p1p2···pk如μ( 30) = μ( 2·3·5 ) = (－1)3μ( 12) = 0；

(121)=0.

第90页：Möbius反演公式定理4.

Möbius反演公式定理4.6.1 (Möbius反演公式)设f(n)和g(n)是定义在正整数集合上的两个函数.成立当且仅当下式成立其中(m)为Möbius函数,称f(n)与g(n)互为Möbius逆变换.(M1), (M2)称为Möbius反演公式.

第91页：要证明本定理需要先证明一个关

要证明本定理需要先证明一个关于Möbius函数(m)的一个性质作为引理.

第92页：引理序列(d)满足下面公式

引理序列(d)满足下面公式：证n=1,命题成立.如果n>1,设n=p11p22pkk, n1= p1p2pk用Č(k,j)表示{1,2,,k}中的j元子集所组成的集合,则有

第93页：设d1|n

设d1|n,引理中(1)等价于下列等式:

第94页：Möbius反演公式证明

Möbius反演公式证明：设(M1)成立, d|n,则有因d1|(n/d),所以存在m,使得dd1m=n从而d|(n/d1).将上式代入(M2)的右端,有

第95页：反之,设(M2)成立

反之,设(M2)成立,对d|n,有

第96页：以此代入(M1)的右端

以此代入(M1)的右端,得

第97页：Möbius反演公式的应用M

Möbius反演公式的应用Möbius反演公式在组合计数、数论、信息论、遗传密码等问题中有应用.考察可重复的圆排列问题.设有m个字母组成的字母表T,从中取出n个字母(允许重复)按顺时针方向可以组成一个圆排列: W=a1a2a3an.即为多重集

第98页：由于一个圆排列可以选取其中任意一

由于一个圆排列可以选取其中任意一个字母ai开始,故a1a2an,a2ana1,a3a1a2等都看作是同一圆排列.例1:当m=2, n=4,T={a,b}时,共有6个不同的圆排列:aaaa, bbbb, abab, aabb, aaab, bbba.这里圆排列aabb也可写成abba或bbaa.

第99页：问题:求圆排列总数Tm(n)

问题:求圆排列总数Tm(n)=?首先我们注意到由m种字母共可作出mn个可重复的线排列a1a2an,它与圆排列唯一区别在于首尾不相接.n个线状排列a1a2an, a2an,, ana1an-1一旦首尾相接均对应同一个圆排列a1a2an.由此似乎有Tm(n)=mn/n?但例子m=2,n=4指出T2(4)=64=24/4.

第100页：原因何在?原来一个圆排列所产

原因何在?原来一个圆排列所产生的n个线排列并不总是互异的.例如圆排列abab只能产生出两个不同线排列abab与baba.导致这种现象的原因在于有“周期”2：ai=ai+2.周期的严格定义如下:设有一个圆排列W= a1a2an,则称使得W=a1a2apa1a2apa1a2ap成立的最小正整数p为W的周期.

第101页：( a1a2···ap) ·

• ( a1a2···ap) ··· ( a1a2···ap)n p组只能形成p个不同的线排列。若一个圆排列可由一个长度为k的线排列重复若干次形成，则这样的k中最小者成为该圆排列的周期。一个圆排列中元素的个数（重复出现的按其重复次数计）称为它的长度
• p｜n时，由不重复的a1a2···ad重复n／p次构成的圆排列

第102页：设集合｛1

设集合｛1 , 2 , ··· , m｝中元素形成的长度与周期都是p的圆排列的个数为M(p)。

设n是一给定的正整数。

若p｜n，每个长度与周期都是p的圆排列可在p个位置上断开，重复n / p次形成p个长度为n的可重排列。

因此有∑ pM( p) = mn由Mǒbíus反演定理n M(n) = ∑μ( p ) m故M( n ) = (∑μ( p ) m ) /np｜np｜np｜nnpnp

第103页：

本页源文件未提取到正文文字，仅有图片。该页位于「设集合｛1」与「考虑，用三种颜色涂色装有5颗珠子」之间，建议对照原课件图片补充本页要点说明。

第104页：考虑，用三种颜色涂色装有5颗珠子

考虑，用三种颜色涂色装有5颗珠子的手镯，如果只考虑手镯的旋转，问有多少种涂色方案？

解：

第105页：例2 .证.仅须证n>

例2.证.仅须证n>1情形, n1为n不同素因子积.

第106页：利用这个例题的结果

利用这个例题的结果,可以把圆排列计数公式利用欧拉函数改进成单重求和形式: