1、第 3章 容斥原理与鸽巢原理3.1 De Morgan定理 13.2 容斥原理 13.3 容斥原理举例 13.4 棋盘多项式与有限制的排列 23.5 有禁区的排列 23.6 广义的容斥原理 33.7 广义容斥原理的应用 32.8 第二类 Stirling数的展开式 12.9 欧拉函数 (n) 12.10 n对夫妻问题 3*2.11 Mobius反演定理 2.12 鸽巢原理 42.13 鸽巢原理举例 42.14 鸽巢原理的推广 4*2.15 Ramsey数 13.4 棋盘多项式和有限制条件的排列一、有限制的排列对有重复的排列或无重复的排列，可以对一个或多个元素的 出现次数 进行限制，也可以对某些
2、元素 出现的位置进行限制 ，这两种情况统称为有限制条件的排列。1、解决这些问题的工具有：(1)、指数型母函数：(3)、递推关系：(2)、容斥原理：23.4 棋盘多项式和有限制条件的排列(1)指数型母函数主要解决限制元素出现次数的排列问题例 1 求 1,3,5,7,9这 5个数字组成的 n位数个数，要求其中 3出现的次数为偶数，其它数字出现的次数无限制。 33.4 棋盘多项式和有限制条件的排列(2)、容斥原理：既可解决限制元素出现次数的问题，也能解决元素出现位置的问题典型特征是：问题能够化为集合问题：例 2 求 a,b,c,d,e,f这 6个字母的全排列中不允许出现 ab和 de图像的排列数。4
3、3.4 棋盘多项式和有限制条件的排列(3)递推关系既可解决限制元素出现次数的问题，也能解决元素出现位置的问题典型特征是：写出递推关系53.4 棋盘多项式和有限制条件的排列(4)棋盘多项式解决无重复排列元素出现位置的问题例 3:甲乙丙丁 4个人 ,有 4项工作 1,2,3,4,甲干不了 1,2,3号工作 ,乙干不了 2,3,4号工作 ,丙干不了 1、 4号工作 ,丁干不了 1,2,4号工作 ,求满足各人工作要求的方案数。6n个不同元素的某一排列可以看做是 n个相同的棋子在 nn 的棋盘上的一种布局。3.2 棋盘多项式和有限条件的排列41352 512341、棋盘多项式的由来7xxxxx棋盘的每一个布局每行每列有且有一个棋子；3.4 棋盘多项式和有限条件的排列类似于象棋中的车无对攻原则。8n个不同元素取 r个的排列可以看做是 n个相同的棋子在 rn 的棋盘上的一种布局，例如 :1,2,3,4,5中取 3个的排列3.2 棋盘多项式和有限条件的排列435 5129xxxxx令 rk(c)表示 k只棋子布到棋盘 C的不同的方案数，规则是当一只棋子布到棋盘的某一格时，则这个格子所在的行和列上的其他格子不再允许布上别的棋子。3.4 棋盘多项式和有限条件的排列10
