哈工大-组合数学讲义(2010版-新).ppt

组合数学 Combinatorics 哈尔滨工业大学 威海 计算机科学与技术学院孟凡超Email mfc Tele参考书目 组合数学 第四版 美 布鲁斯 Brualdi R A 著 北京机械工业出版社 2005 2卢开澄 组合数学 清华大学出版社 主要内容 概述鸽巢原理排列与组合生成排列和组合二项式系数容斥原理及应用递推关系和生成函数特殊计数序列二分图中的匹配Polya计数法 概述 数学研究问题研究连续对象 微积分 研究离散对象 组合数学 组合数学研究的问题将一个集合的物体排列成满足一些指定规则的格式 如下两类问题反复出现 排列存在性 如果想要排列一个集合的成员使得某些条件得以满足 并且这种排列不总是可能的 那么这种排列在什么样的条件下满足 排列的计数和分类 如果一个指定的排列是可能的 那么会有多少种方法去实现它 此时 人们就可以计数并将它们分类 概述 棋盘的完美覆盖 考虑一张8 8 8行8列 的64个正方形的国际象棋棋盘 设有形状一样的多米诺牌 每张牌恰好覆盖棋盘上相邻的两个方格 那么 是否能够把32张多米诺牌摆放到棋盘上 使得任何两张多米诺牌均不重叠 每张多米诺牌覆盖两个方格 并且棋盘上的所有方格都被覆盖住 我们把这样一种排列称为棋盘的多米诺牌的完美覆盖 8 8棋盘 完美覆盖1 完美覆盖2 完美覆盖数 12988816 24 901 2 概述 与上述问题同时出现的另外两种组合数学问题 研究一个已知的排列 当人们建立起满足某些指定条件的一个排列以后 可能要考察这个排列的性质和结构 这样的结构可能会涉及到分类问题 构造一个最优的排列 如果可能存在多于一个的排列 人们也许想要确定满足某些优化准则的一个排列 即找出某种规定意义下的 最好的 或 最优的 排列 概述 例 设S 1 2 3 4 为一个集合1 从S中取两个不相同的元素进行排列 这样的排列有多少种2 列出所有可能的排列 3 求出两个元素之和最大的排列 组合数学是研究离散结构的存在 计数 分析和优化等问题的一门科学 概述 问题1 如果将棋盘变为m n m行n列 则完美覆盖是否存在 问题2 对于什么样的m和n存在完美覆盖 当且仅当m和n中至少有一个是偶数时 m n棋盘存在完美覆盖 不一定存在 例如 3行3列的棋盘就不存在完美覆盖 概述 问题3 8 8的棋盘用一把剪刀剪掉棋盘一副对角上的两个方格 总共剩下62个方格 那么是否能够排列31张多米诺牌来得出对这幅被剪过棋盘的完美覆盖 不存在完美覆盖 在一副8 8棋盘上交替地将方格涂成黑色和白色 则其中的32个方格是黑色 32个方格是白色 如果我们剪掉棋盘一副对角线上的两个方格 那么我们就剪掉同样种颜色的两个方格 比如两个白色方格 这就变成了32个黑方格和30个白方格 但是 每张多米诺牌需要一个白方格和一个黑方格 于是 31张不重叠的多米诺牌则覆盖住31个黑方格和31个白方格 因此 这幅被剪过的棋盘不存在完美覆盖 概述 问题4 将m n的棋盘上的方格交替涂成黑色和白色 切除一些方格 得到一块被剪过的棋盘 这块棋盘什么时候有一个完美覆盖 必要条件 这块被剪过的棋盘必须具有相等的黑方格数和白方格数 该条件不是充分条件 4 5棋盘 概述 B 牌 设b是一个正整数 我们用b个1 1的方格并排连接成的1 b的方格条来代替多米诺牌 这些方方格条称为b 牌 一张5 牌 一张2 牌 多米诺牌 m n棋盘被B 牌的完美覆盖 b 牌在m n棋盘上没有两张重叠 每一条b 牌盖住棋盘上的b个方格 并且盘上的所有方格都被覆盖住 概述 问题5 m n棋盘何时具有b 牌的完美覆盖 当且仅当b是m的一个因子或者b是n的一个因子 充分性 如果b是m的一个因子或者b是n的一个因子 则m n棋盘存在b 牌完美覆盖 如果b是m的一个因子 我们就可以对n列的每一列用m b个b 牌覆盖并进而完成对m n棋盘的完美覆盖 如果b是n的一个引子 我们就可以对m行的每一行用n b个b 牌覆盖并进而完成对m n棋盘的完美覆盖 概述 必要性 如果m n棋盘存在b 牌完美覆盖 则b或者是m一个因子或者是n的一个因子 我们需要证明m和n除以b的余数至少有一个是零 设b除以m和n得到商p和q以及余数r和s m pb r 0 r b 1 n qb s 0 s b 1 我们不妨设r s 因此 我们需要证明r 0 采用反证法 设r 0 主要内容 概述鸽巢原理排列与组合生成排列和组合二项式系数容斥原理及应用递推关系和生成函数特殊计数序列二分图匹配Polya计数法 鸽巢原理 鸽巢原理 简单形式定理1 如果n 1个物体被放进n个盒子中 那么至少有一个盒子包含两只或更多的物体 其它表述形式 如果n 1只鸽子被放进n个鸽巢中 那么至少有一个鸽巢包含两只或更多的鸽子 如果n 1个物体用种颜色涂色 那么必然有两个物体被涂成相同的颜色 鸽巢原理 4个物体 3个盒子 存放 1 2 3 4 5 鸽巢原理 例题 例1 在13个人中存在两个人 他们的生日在同一个月份里 考虑12个盒子 每个盒子对应一个月份 将13个人放到12个盒子中 则至少有一个盒子包含两个或两个以上的人 即 这在13个人中存在两个人 他们的生日在同一个月份里 例2 设有n对已婚夫妇 为保证能够有一对夫妇被选出 至少要从这2n个人中选出多少人 应至少选择n 1个人 考虑n个盒子 每个盒子对应一对夫妇 如果我们选择n 1个人并把他们中的每一个人放到他们对偶所在的那个盒子中去 那么就有同一个盒子含有两个人 也就是说 我们选择了一对已婚夫妇 如果选择n个人 可以只选择所有丈夫或只选择所有的妻子 鸽巢原理 与鸽巢原理相关的原理定理2 如果将n个物体放入n个盒子并且没有一个盒子是空的 那么每个盒子恰好包含一个物体 定理3 如果将n个物体放入n个盒子且没有一个盒子被放入多于一个物体 那么每个盒子里有一个物体 鸽巢原理 函数基本知识函数 集合之间的函数 function 或说映射mapping 设X和Y是任意两个集合 而f是X到Y的一个关系 如果对于每一个x X 有唯一的y Y 使得 f 称关系f为函数 记作f X Y或X Y 原象和象 如果 f 则x称为自变元 原象 y称为在f作用下x的象 image f亦可记作y f x 且记f X f x x X 鸽巢原理 函数基本知识定义域 函数f X Y的定义域 domain domf定义为 domf x 存在某个y Y使得 f X 值域 函数f X Y的值域 range ranf定义为 ranf y x x X f Y 全函数 f是全函数 totalfunction 若domf X f是全函数 否则称f是偏函数 partialfunction 鸽巢原理 函数基本知识满射 f是满射 surjection 或说fmapsXontoY 如果ranf Y 即对任意的y Y都有原像 设f X Y是满射 即对任意的y Y 必存在x X 使得f x y成立 入射 f是入射 injection 或说fisonetoone是一对一 设f X Y是入射 即对任意的x1 x2 X 如果f x1 f x2 则x1 x2 或者如果x1 x2 则得f x1 f x2 鸽巢原理 从函数角度来分析鸽巢原理的含义设X和Y是两个有限集 并令f X Y是一个从X到Y的函数 如果X的元素多于Y的元素 那么f就不是一对一的 如果X和Y含有相同个数的元素 并且f是映上 onto 的 那么f就是一对一的 如果X和Y含有相同个数的元素 并且f是一对一的 那么f就是映上的 鸽巢原理 例3 给定m个整数a1 a2 am 存在整数k和l 0 k l m 使得ak 1 ak 2 al能够被m整除 也就是说 在序列a1 a2 am中存在连续个元素 它们的和能被m整除 考虑m个和 a1 a1 a2 a1 a2 a3 a1 a2 a3 am如果这些和中存在一个可以被m整除 那么结论就成立 否则 这些和中的任意一个都不能被m整除 即 这些和中的每一个除以m都有一个非零余数 余数等于1 2 m 1 由于m个和而只有m 1个余数 如果我们将和看成是物体 余数看成是盒子 根据鸽巢原理 那么必有两个和除以m有相同的余数 因此 存在整数k和l k l 使得a1 a2 ak和a1 a2 al除以m有相同的余数r a1 a2 ak bm r a1 a2 al cm r两式相减 有ak 1 ak 2 al c b m 从而ak 1 ak 2 al能够被m整除 鸽巢原理 例4 一位国际象棋大师有11周的时间备战一场锦标赛 他决定每天至少下一盘棋 但是为了使自己不过分疲劳他还决定在每周不能下棋超过12盘 证明存在连续若干天 期间这位大师恰好下了21盘棋 一共备战11 7 77天 令x1 x2 x77分别为第1 2 77天下的棋数 则xi 1 i 1 2 77 我们构造如下严格递增序列 a1 x1 a2 x1 x2 a3 x1 x2 x3 a77 x1 x2 x3 x77 其中 ai表示前i i 1 2 77 天下棋的总数 并且1 a1 a2 a3 a77 11 12 132 则序列a1 21 a2 21 a3 21 a77 21也是一个严格递增序列 并且22 a1 21 a2 21 a3 21 a77 21 153 鸽巢原理 于是 这154个数 a1 a2 a77 a1 21 a2 21 a77 21中的每一个都是1到153中的一个整数 如果我们将这个序列中的每个元素作为物体 1到153中的每个数作为盒子 根据鸽巢原理 在这154中必有两个元素相等 既然a1 a2 a77中没有相等的元素 a1 21 a2 21 a77 21中也没有相等的元素 则必然存在一个i和j 1 i j 77 使得aj ai 21 从而这位国际象棋大师在第i 1 i 2 j天总共下了21盘棋 鸽巢原理 例5 从整数1 2 3 200中我们选择101个整数 证明 在所选择的这些整数之间存在两个这样的整数 其中一个可以被另一个整除 整数分解知识 任何一个整数都可以写成2k a的形式 其中 k 0 a为奇数 对于1 2 3 200之间的一个整数 a是100个数1 3 199中的一个 因此 如果我们将所选择的101个数作为物体 1 3 199这100个奇数作为盒子 根据鸽巢原则 在这101中存在两个整数 当写成上述形式时这两个数具有相同的a值 令这两个数是2r a和2s a 如果rs 那么第二个数就能被第一个数整除 鸽巢原理 例6 中国乘余定理 令m和n是两个互素的整数 并令a和b为两个整数 且0 a m 1以及0 b n 1 于是存在一个整数x 使得x除以m的余数为a 并且x除以n的余数为b 即 x既可以写成x pm a的同时又可以写成x qn b的形式 在这里 p和q为两个整数 素数定义 如果两个整数m和n的最大公约数为1 我们称m和n为互素 为了证明这个结论 我们需要构造出x 那么如何构造 我们首先按照x pm a的形式构造x p取0 1 n 1 考虑如下n个整数 a m a 2m a n 1 m a 这些整数中的每个除以m的余数都为a 即x可以写成pm a的形式 如果我们能够证明a m a 2m a n 1 m a这n个数中存在一个数能够写成qn b的形式 则即可证明本题结论 鸽巢原理 如果a m a 2m a n 1 m a中的每个数除以n的余数都不相等 则我们将这n个数作为物体 n的余数0 1 2 n 1作为盒子 根据鸽巢原理 定理3 0 1 2 n 1中的每个数作为余数都会出现 特别是数b作为余数也会出现 令p为整数 满足0 p n 1 且使数x pm a除以n的余数为b 则对某个适当的q 有x qn b 因此 x pm a且x qn b 从而x具有所要求的性质 否则 如果这n个数存在两个数除以n有相同的余数r 我们令这两个数分别为im a和jm a 其中 0 i j n 1 因此 存在两个整数qi和qj 使得 鸽巢原理 im a qin r jm a qjn r 用第二个方程减去第一个方程 得到 j i m qj qi n 这说明n是 j i m的一个因子 由于n与m没有除了1之外的公因子 因此n是j i的一个因子 然而 0 j i n 1 也就是说 n不可能是j i的一个因子 这个矛盾产生于我们假设a m a 2m a n 1 m a中有两个除以n会有相同的余数 因此 我们断言 这n个数中的每一个除以n都会有不同的余数 这样根据前述结论即可证明本题正确性 鸽巢原理 鸽巢原理 加强形式定理4 令q1 q2 qn为n个正整数 如果将q1 q2 qn n 1个物体放入n个盒子内 那么 或者第一个盒子至少含有q1个物体 或者第二个盒子至少含有q2个物体 或者第n个盒子至少含有qn个物体 证明 采用反证法 设将q1 q2 qn n 1个物体放入到n个盒子中 如果对于每个i 1 2 n 第i个盒子含有少于qi个物体 那么所有盒子中的物体总数不超过 q1 1 q2 1 qn 1 q1 q2 qn n这与物体的总数为q1 q2 qn n 1相矛盾 所以或者第一个盒子至少含有q1个物体 或者第二个盒子至少含有q2个物体 或者第n个盒子至少含有qn个物体 鸽巢原理 鸽巢原理的简单形式是其加强形式通过q1 q2 qn 2来实现的 这时 q1 q2 qn n 1 2n n 1 n 1 q1 2 q2 3 q3 4 q1 q2 q3 3 1 7 b1 2 或 或 b1 b2 b3 b1 3 b1 4 鸽巢原理 推论1 m个物体 n个盒子 则至少有一个盒子里有不少于 m 1 n 1个物体 证明 采用反证法 设所有盒子了最多有 m 1 n 个物体 则n个盒子中的物体数最多为n m 1 n m 1 与假设矛盾 推论2 若取n m 1 1个物体放入n个盒子中 则至少有1个盒子有m个物体 这个推论相当于q1 q2 qn m时的特殊情况 采用着色的术语来表述 如果q1 q2 qn n 1个物体中的每一个物体被指定用n种颜色中的一种着色 那么 存在这样一个i 使得第i种颜色的物体至少有qi个 鸽巢原理 推论3 若m1 m2 mn是n个正整数 而且 则m1 m2 mn中至少有1个数不小于r 证明 将该问题与推论2建立联系 取n r 1 1个物体放入n个盒子中 设mi i 1 2 n 是第i个盒子中的物体个数 于是 这n个数m1 m2 mn的平均数为 由于这个平均数大于r 1 故而有一个整数mi至少是r 鸽巢原理 练习1 如果n个非负整数m1 m2 mn的平均数小于r 1 即 则m1 m2 mn中至少有1个数不超过r 练习2 如果n个非负整数m1 m2 mn的平均数小于r 1 即 则m1 m2 mn中至少有1个数不超过r 鸽巢原理 例7 一篮子水果装有苹果 香蕉和橘子 为了保证篮子内或者至少8个苹果或者至少6个香蕉或者至少9个橘子 则放入篮子中的水果的最小件数是多少 例8 两个碟子 其中一个比另一个小 它们均被分成200个恒等的扇形 在大碟子中任选100个扇形并涂成红色 而其余的100个扇形则涂成蓝色 在小碟子中 每一个扇形或者涂成红色 或者涂成蓝色 所涂红色和蓝色扇形的数目没有限制 然后将小蝶子放到大碟子上面是两个碟子的中心重合 证明 能够将两个碟子的扇形对齐使得小碟子和大碟子上相同颜色重合的扇形数目至少是100个 鸽巢原理 例8 证明每个由n2 1个实数构成的序列a1 a2 an2 1或者含有长度为n 1的递增子序列 或者含有长度为n 1的递减子序列 证明 我们首先了解一下什么是子序列的概念 子序列 如果b1 b2 bm是一个序列 那么 则是一个子序列 其中 1 i1 i2 ik m 例如 b2 b4 b5是序列b1 b2 b3 b4 b5 b6的一个子序列 而b2 b6 b5则不是 递增 减子序列 子序列若满足条件则称为递增子序列 而满足则称为递减子序列 鸽巢原理 我们假设不存在长度为n 1的递增子序列 则需要证明必然存在长度为n 1的递减子序列 对于每一个k 1 2 n2 1 令mk为从ak开始的最长递增子序列长度 由于假设不存在长度为n 1的递增子序列 则对每个k 1 2 n2 1 有1 mk n 如果将m1 m2 mn2 1这n2 1个数作为物体 最长子序列的长度1 2 n作为n个盒子 其中 第i个盒子代表长度为i的序列 根据鸽巢原理的加强形式 在m1 m2 mn2 1中有n 1个是相等的 令 其中 1 k1 k2 kn 1 设对于某个i 1 2 n 有 于是 由于ki ki 1 我们可以做成一个从 开始的最长 的递增子序列并将 放到前面而得到一个从 开始 鸽巢原理 的递增子序列 但这意味着 因此 我们断言 由于这对每一个i 1 2 n均成立 因此我们有 从而我们断言 是一个长度为n 1的 递减子序列 鸽巢原理 Ramsey定理Ramsey定理最容易理解的例子 在6个 或更多的 人中 或者有3个人 他们中的每两个人都相互认识 或者有3个人 他们中的每两个人都相互不认识 在给出这个证明以前 先给出一个抽象的公式 K6 K3 K3 读做K6箭指K3 K3 我们用K6代表6个物体 例如 6个人 和由它们配成的15对的集合 我们可以通过在平面上选出6个点来画出K6 其中没有3个点是共线的 然后 划出连接每一对点的连线或边 这些边代表这些点对 鸽巢原理 K6 K5 K4 K3 K2 我们把边涂成红色表示认识 涂成蓝色表示不认识 鸽巢原理 K6 K3 K3 K6箭指K3 K3 含义 无论K6的边用红色和蓝色如何去涂 总有一个红K3 原始的6个点中有3个点 它们之间的3条线段均被着成红色 或蓝K3 原始的6个点中有3个点 它们之间的3条线段均被着成蓝色 简而言之 总有一个单色的三角形 K6 着色方案1 着色方案2 鸽巢原理 证明K6 K3 K3 证明 考虑K6的任意一点p 它接触到5条边 由于这5条边的每一条都被涂成红色或蓝色 根据鸽巢原理的加强形式可知 这5条边中或者至少有3条边被涂成红色 或者至少有3条边被涂成蓝色 我们设接触到p点的5条边有3条是红色 令这三条边分别与a b c三点相连 考虑a b c两两相连的边 1 如果这些边都是蓝色 那么a b c就确定了一个蓝色的K3 2 如果它们中的一条边 比如连接a和c的边是红色的 那么p a c就确定一个红K3 因此 我们得到 确实存在一个红K3 或者是一个蓝K3 b 鸽巢原理 K5 K3 K3是否成立 鸽巢原理 思考题 证明对10个顶点的完全图用红 蓝两色任意着色 证明 必然存在3个点使得连接该3点的3条线段都是红色 或者必然存在4个点使得连接该4个点的6条线段都是蓝色 即K9 K3 K4 将上面的10换成9是否成立 即K9 K3 K4 思考题 证明对18个顶点的完全图用红 蓝两色任意着色 证明至少存在一个同色的完全四边形 即K18 K4 K4 鸽巢原理 定理5 Ramsey定理 给定m和n 存在一个正整数p 使得如果Kp的边被涂成红色或蓝色 那么或者有一个红色的Km 或者有一个蓝色的Kn 无论Kp的边如何着色 红色Km或者蓝色Kn的存在性是保证的 如果Kp Km Kn m 2 n 2 那么对任何的q p 都有Kq Km Kn Ramsey数 Ramsey数r m n 是使得Kp Km Kn成立的最小整数p 例如 r 3 3 6 r 3 4 9 r 4 4 18 鸽巢原理 推论4 证明r 2 n n r m n r n m 证明 只需证明r 2 n n以及r 2 n n 1 1 如果我们把Kn的边或者涂成红色或者涂成蓝色 那么 或者Kn的某条边是红色的 因此我们得到了一个红K2 或者Kn的所有边都是蓝色的 因此我们得到了一个蓝Kn 即 Kn K2 Kn 由于r 2 n 是使得Kn K2 Kn成立的最小整数 所以 r 2 n n 2 如果我们将Kn 1的边都涂成蓝色 那么我们既得不到红K2 也得不到蓝Kn 所以 r 2 n n 1 鸽巢原理 m n 常见的Ramsey数r m n 非平凡Ramsey数 平凡Ramsey数 Ramsey定理说明了对于任意m n r m n 都是存在的 虽然Ramsey定理说明了Ramsey数的存在性 但是对于Ramsey数的求法 目前还没有非平凡的结论 比如说r 3 10 r 5 5 现在还没人知道它们的准确取值 鸽巢原理 推论5 当m n 3时 r m n r m 1 n r m n 1 证明 令N r m 1 n r m n 1 对KN的边采用红 蓝两色进行任意着色 设p是KN的一个顶点 在KN中与p相连的边有r m 1 n r m n 1 1条 这些边要么为红色 要么为蓝色 根据鸽巢原理的加强形式 要么至少有r m 1 n 条红边 要么至少有r m n 1 条蓝边 1 对于至少有r m 1 n 条红边的情形 以这些与p相连的红边除p以外的r m 1 n 个顶点构成的完全图Kr m 1 n 中 或者有一个红色Km 1 或者有一个蓝色的Kn 如果有一个红色的Km 1 则该红色Km 1加上顶点p以及p与Km 1之间的红边 就构成一个红色Km 否则 就有一个蓝色的Kn 鸽巢原理 2 对于至少有r m n 1 条蓝边的情形 以这些与p相连的蓝边除p以外的r m n 1 个顶点构成的完全图Kr m n 1 中 或者有一个红色Km 或者有一个蓝色的Kn 1 如果有一个蓝色的Kn 1 则该蓝色Kn 1加上顶点p以及p与Kn 1之间的蓝边 就构成一个蓝色Kn 否则 就有一个红色的Km 这说明KN Km Kn 由于r m n 是使得KN Km Kn成立的最小整数N 所以 r m n KN r m 1 n r m n 1 鸽巢原理 Ramsey定理的推广情况 如果n1 n2和n3是大于或等于2的3个整数 则存在一个整数p使得Kp Kn1 Kn2 Kn3 也就是说 如果Kp的每条边被涂上红色或蓝色或绿色 那么或者存在一个红Kn1 或者存在一个蓝Kn2 或者存在一个绿Kn3 Ramsey数的推广情况 Ramsey数r n1 n2 n3 是使得Kp Kn1 Kn2 Kn3成立的最小整数p Ramsey定理的任意推广情况 Kp Kn1 Kn2 Kn3 Kns Ramsey数的任意推广情况 r n1 n2 ns 鸽巢原理 证明r 3 3 3 17 证明 考虑用3种颜色进行着色的完全图K17 设p是K17的一个顶点 由鸽巢原理可知 以p为端点连接其余16个顶点的16条线中必有6条颜色相同 比如都是红色 考察这6条线的除p外的6个顶点所形成的完全图K6 如果K6中有一条是红色 则这条边的两个顶端加上p就形成了一个红色三角形 结论成立 否则 K6中没有一条红色边 则K6为用两种颜色着色的完全图 此时K6必含有一个同色的三角形 因此 K17中必含有一个同色的三角形 从而r 3 3 3 17 鸽巢原理 Ramsey定理的一般形式 在这种形式中点对 两个元素的子集 由t个元素的子集代替 其中t 1为某个整数 令Knt表示n个元素的集合中所有的t个元素的子集的集合 定理6 Ramsey定理一般形式 给定整数t 2及整数q1 q2 qk t 存在一个整数p使得Kpt Kq1t Kq2t Kqkt 也就是说 存在一个整数p使得如果将p元素集合中的每一个t元素子集指定k种颜色c1 c2 ck中的一种 那么或者存在q1个元素 这些元素的所有t元素子集都被指定颜色c1 或者存在q2个元素 这些元素的所有t元素子集都被指定颜色c2 或者存在qk个元素 这些元素的所有t元素子集都被指定颜色ck Ramsey数的一般形式 满足上述条件的最小整数p被称为Ramsey数rt qk q1 q2 qk 鸽巢原理 r1 q1 q2 qk q1 q2 qk q 1 设t 1 于是 r1 q1 q2 qk 就是最小的数p 它满足如果p个元素集合的元素用颜色c1 c2 ck中的一种颜色涂色 那么或者存在q1个涂成颜色c1的元素 或者存在q2个涂成颜色c2的元素 或者存在qk个涂成颜色ck的元素 因此 由鸽巢原理的加强形式 有r1 q1 q2 qk q1 q2 qk q 1 这说明Ramsey定理是鸽巢原理的加强形式的推广 鸽巢原理 若令R m r 3 3 3 目前已知R 1 3 R 2 6 R 3 3 3 17 m 思考题 证明R m m R m 1 1 2 主要内容 概述鸽巢原理排列与组合生成排列和组合二项式系数容斥原理及应用递推关系和生成函数特殊计数序列二分图匹配Polya计数法 排列与组合 四个计数原理加法原理集合划分 令S为给定的非空集合 A S1 S2 Sn 若1 Si S Si i 1 2 n 2 Si Sj i j i j 1 2 n 3 S S1 S2 Sn 则称A为集合S的划分 其中Si i 1 2 n 称为该划分的部分 例 对08级的研究生按照性别 年龄 专业进行划分 排列与组合 加法原理 设 S1 S2 Sn 为集合S的划分 则S的元素的个数可以通过找出它的每一个部分的元素的个数来确定 我们把这些数相加 得到 S S1 S2 Sn 加法原理的另一表述方式 如果有p种方法能够从一堆物品中选择一个物品 而有q种方法也能够从另一堆物品中选择一个物品 那么从这两堆物品中选择一个物品的方法共有p q种 例 从ICES中心 9人 和信息安全中心 6人 选择一名研究生的方法数是多少 排列与组合 乘法原理 乘法原理 令S是元素的序偶 a b 的集合 其中第一个元素a来自大小为p的一个集合 而对于a的每个选择 元素b存在着q种选择 于是 S的大小为p q 即 S p q 乘法原理的另一种表述方式 一项任务有p个结果 而不论第一项任务的结果如何 第二项任务都有q个结果 那么 这两项任务连续执行就有p q个结果 1 2 a b S1 S2 1 a 1 b 2 a 2 b c 1 c 2 c 排列与组合 乘法原理是加法原理的一个推论 令a1 a2 ap是对元素a的p个不同的选择 我们将S划分成部分S1 S2 Sp 其中Si是S内第一个元素为ai i 1 2 p 的序偶的集合 每个Si的大小为q 因此由加法原理有 S S1 S2 Sp q q q p q 1 a 1 b 2 a 2 b 1 c 2 c 集合1 第一个元素为1 集合大小为3 集合2 第一个元素为2 集合大小为3 S 3 3 2 3 6 排列与组合 例 从ICES中心 9人 和信息安全中心 6人 各选择一名研究生的方法数是多少 1 2 a b ICES中心 c 3 4 5 6 7 8 9 e f g i j 信息安全中心 S S1 S2 S9 8 9 72 排列与组合 思考题 从08级研究生选择两名属于不同中心的学生方法数是多少 08级研究生情况 1 ICES 9人 2 信息安全 6人 3 生物信息 4人 4 嵌入式 2人 5 医学图像 2人 6 在职 1人 排列与组合 减法原理 令A是一个集合 而U是包含A的更大的集合 设 是A在U中的补 那么A中的元素个数 A 由下列法则给出 排列与组合 除法原理 令S是一个有限集 它以下述方式方式被划分成k部分 每一部分包含相同数目的元素 此时 划分中的部分数目由下述公式给出 排列与组合 例1 确定数34 52 117 138的正整数因子的个数 例2 两位数字有多少两个位互异且非零的两位数 例3 计算口令字计划由0 1 2 9和小写字母a b c z中取出的6个字符构成的一个串组成 具有重复字符的计算机口令共有多少 例4 在1000和9999之间有多少具有不同数字的奇数 例5 在0和10000之间有多少个整数恰好有一位数字是5 排列与组合 集合的排列S的r排列 令r为正整数 我们把n个元素的集合S的一个r排列定义为n个元素中的r个元素的有序摆放 例如 S a b c 则S的1排列为 a b c S的2排列为 a b a c b a b c c a c b S的3排列为 a b c a c b b a c b c a c a b c b a 排列与组合 r 排列数目 我们用P n r 表示n个元素集合的r 排列的数目 如果r n P n r 0 如果r 1 P n 1 n 定理1 对于正整数n和r r n 有P n r n n 1 n r 1 证明 在构建n 元素集的一个r排列时 我们可以用n种方法选择第一项 不论第一项如何选出 都可以用n 1种方法选择第二项 以及不论前r 1项如何选出 都可以用n r 1 种方法选择第r项 根据乘法原理 这r项可以用n n 1 n r 1 种方法选出 排列与组合 1 2 3 n 第一项有n种方法 第二项有n 1种方法 1 2 r 第r项有n r 1种方法 S 排列与组合 例 将08级的24个研究生排列使得ICES中心 9个学生 的任意两个学生都不能相继出现 这种排列的方法总数是多少 例 有多少种方法从08级的24个研究生中取7个人进行排列 并且使得王伟和谢冬辉不能以任何顺序相继出现 排列与组合 循环排列 例 6个孩子沿圆圈行进 他们能够以多少种不同的方式形成一个圆 1 2 3 4 5 6 6 1 2 3 4 5 5 6 1 2 3 4 4 5 6 1 2 3 3 4 5 6 1 2 2 3 4 5 6 1 123456 612345 561234 456123 345612 234561 排列与组合 如果两个循环排列通过一个旋转 即一个循环移位 从其中的一个变到另一个 那么可以将它们看成是相同的 这样 在6个孩子的线性排列和6个孩子的循环排列之间就存在着6到1的对应 因此 要想求得循环排列的数目 我们只要用6去除线性排列的数目即可 所以 6个孩子的循环排列数目等于6 6 5 排列与组合 定理2 n个元素的集合的循环r 排列的个数为 特别地 n个元素的循环排列的个数是 n 1 证明 可以把线性r 排列的集合划分成一些部分 使得两个线性r 排列对应同一个循环r 排列当且仅当它们在同一个部分中 于是 循环r 排列的个数等于部分的个数 既然每一个部分都含有r个线性r 排列 根据除法原理 部分的数目等于 排列与组合 例 ICES中心08级的9个研究生要围坐一个圆桌 其中有两个人不愿意彼此挨着就座 共有多少循环座位排放方法 例 6男6女围坐一个圆桌 如果男女交替围坐 可以有多少围坐方式 排列与组合 集合的组合S的r组合 令r为非负整数 我们把n个元素的集合S的r 组合可以定义为从S的n个元素中对r个元素的无序选择 例如 S a b c d 的3的组合为 a b c a b d a c d b c d r 组合数目 我们用表示n 元素集的r 组合的个数 如果r n 0 如果r 0 0 n 0 1 n 1 n n n 1 0 0 1 排列与组合 定理3 对于0 r n 因此 证明 令S是一个n 元素集 S的每个r 排列都是由下面的两个任务执行结果产生 1 从S中选出r个元素 2 将所选出的r个元素以某种顺序排列 执行第一个任务的方法数根据定义可知为组合数 排列与组合 执行第二个任务的方法数则是P r r r 根据乘法原理我们有 所以 排列与组合 定理4 证明 通过对n 元素集S的组合计数来证明 1 S的每一个组合是S对于r r 0 1 2 n 的一个r 组合 由于 等于S的r 组合数 由加法原理 等于S的所有组合的总个数 排列与组合 2 把一个组合的选取分成n个任务来完成 令S的元素为x1 x2 xn 在选择S的一个组合时 对n个元素的每一个都有两种选择 xi i 1 2 n 要么在这个组合里 xi i 1 2 n 要么不在这个组合里 因此 由乘法原理 存在2n种方法使得我们可以形成S的一个组合 使两种方法相等就完成了定理的证明 排列与组合 多重集排列多重集多重集同一般集合一样 是一组对象的整体 只不过不像一般集合那样必须要求集合中的每个元素互不相同 例如 S a a a b c c d d d d d 是一个10元素的多重集 其中 有3个a 1个b 2个c和4个d 我们可以将S表示为S 3 a 1 b 2 c 4 d 一般地 多重集可以表示为S k1 a1 k2 a2 kn an 其中 a1 a2 an为S中所有的互不相同的元素 S中有ki个ai 1 i n 称ki为ai的重数 ki是正整数 也可以是 表示S中有无限多个ai 排列与组合 多重集排列设S 3 a 1 b 2 c 4 d 那么acbc cbcc为S的4排列 而abaacddcdd是S的一个排列 10排列 定理 令S a1 a2 ak 是一个多重集 则S的r 排列的个数为kr 证明 第一项有k种方法 第二项有k种方法 1 2 r 第r项有k种方法 S 所以 S的r 排列个数为kr 排列与组合 该问题是求S a b z 的包含4个元音字母的8 排列数 在长度为8的字符串中 4个元音字母出现的位置的选择方式有种 而每个元音位置可以取5个元音字母中的任何一个 4个辅音位置可以取21个辅音字母中的任何一个 因此 满足要求的字符串有 54 214个 例 用26个英文字母可以构造出多少个包含4个元音字母 长度为8的字符串 排列与组合 例 把r个不同的球放入k个不同的盒子中 每个盒子可以放多个 也可以不放 其方案数为多少 方法1 第一个球有k个盒子可放 第二个球有k个盒子可放 第r个球也有k个盒子可放 由乘法原理知 不同的方案数为kr 方法2 把这r个球分别记作x1 x2 xr 这k个不同的盒子分别记为a1 a2 ak 令S a1 a2 ak 是一个多重集 将球xi放入盒子aj对应于多重集S的r排列 因此 方案数为kr 排列与组合 定理 令S n1 a1 n2 a2 nk ak 是一个多重集 n n1 n2 nk 则S的排列数等于 证明 1 2 n S 排列与组合 首先决定哪些位置被a1占据 由于S中有n1个a1 必须从n个位置的集合选出n1个位置的子集 有种方法 然后决定哪些位置被a2占据 由于S中有n2个a2 必须从剩下的n n1个位置的集合选出n2个位置的子集 有种方法 最后决定哪些位置被ak占据 由于S中有nk个ak 必须从剩下的n n1 nk 1个位置的集合选出nk个位置的子集 有种方法 排列与组合 由乘法原理可知 S的排列的总数等于 根据组合数计算公式 这个数等于 化简后得到 排列与组合 例 将6个篮球 5个红球 4个白球和3个黄球排成一排 要求黄球不挨着 问有多少种排列方式 在构造排列时 先将蓝 红 白三种球进行全排列 再将3个黄球插入其中 令S 6 b 5 r 4 w 则S的排列数为15 6 5 4 然后在15个空选出3个位置插入黄球 共有种取法 所以 共有 15 6 5 4 种取法 排列与组合 其中 盒子1含有n1个元素 盒子2含有n2个元素 盒子k含有nk个元素 如果这些盒子不被做成标签 那么划分的个数为 定理 令n是一个正整数 并令n1 n2 nk是正整数且n n1 n2 nk 将n个元素的集合划分成k个被做标签的盒子B1 B2 Bk的方式数为 a2 a2 a2 an B1 B2 Bk 该问题等价于多重集S n1 B1 n2 B2 nk Bk 的全排列 n1 n2 nk 排列与组合 证明 首先选择n1个元素放入第一个盒子 然后从剩下的n n1个元素中取n2个元素放入第2个盒子中 然后从剩下的n n1 n2个元素中取n3个元素放入第3个盒子中 最后从剩下的n n1 n2 n3 nk 1个盒子中取nk个元素放入第k个盒子中 根据乘法原理 进行这些选择的方法数为 排列与组合 a1 a2 a3 例 4元素的集合S a1 a2 a3 a4 2个盒子B1和B2 B1含有2个元素 盒子B2含有2个元素 a1 a2 a3 a1 a2 a3 a1 a2 a3 6种划分 a4 a4 a4 a4 a1 a2 a3 a1 a2 a3 a1 a2 a3 a4 a4 a4 排列与组合 如果盒子不做标签 a1 a2 a3 a1 a2 a3 a1 a2 a3 a4 a4 a4 3种划分 排列与组合 a1 a2 a3 例 3元素的集合S a1 a2 a3 2个盒子B1和B2 B1含有2个元素 盒子B2含有1个元素 a1 a2 a3 a1 a2 a3 a1 a2 a3 划分1 划分2 划分3 排列与组合 如果盒子不做标签 a1 a2 a3 a1 a2 a3 a1 a2 a3 排列与组合 现在设对这些盒子不做标签 此时的结果必须被k 整除 因为对于把元素放入k个无标签的盒子中的每一种方法 现在存在k 种方法将标签1 2 k贴在盒子上 因此 使用除法原理 具有无标签盒子的划分的个数为 该定理等价于把r个不同的球放入k个不同的盒子中 第1个盒子放r1个球 第2个盒子放r2个球 第k个盒子放rk个球 且r1 r2 rk r 排列与组合 例 在8 8棋盘上对于8个非攻击型车有多少可能的方法 我们给棋盘上的每个方块一对坐标 i j 整数i指出方块的行数 整数j指出方块的列数 因此 i和j是1和8之间的整数 由于棋盘是8 8 棋盘上就能有8个车它们不能彼此攻击 每行上必然有一个车 因此 这些车必然占据8个方块而且具有坐标 1 j1 2 j2 8 j8 由于每一列上恰好有一个车 这使得数j1 j2 j8中没有两个是相等的 因此 该问题可以等价于 1 2 8 的全排列 其总数为8 排列与组合 例 在8 8棋盘上对于8个不同颜色的非攻击型车有多少可能的方法 例 假设有1个红 R 车 3个蓝车 4个黄车 并且同颜色的车之间没有区别 那么在8 8棋盘上对于这些颜色的非攻击型车有多少可能的方法 排列与组合 定理 有n个车共k种颜色 第一种颜色的车有n1个 第二种颜色的车有n2个 第k种颜色的车有nk个 将这些车摆放在n n棋盘上 使得没有车能够互相攻击的摆放方法数为 如果这些车的颜色都不相同 k n且所有的ni 1 则该公式变为 n 2 如果这些车的颜色都相同 k 1且n1 n 则该公式变为 n 排列与组合 多重集组合设S为一个多重集 那么S的r组合是S中的r个元素的一个无序选择 S的r组合本身也是一个多重集 该多重集是S的一个子多重集 例如 如果S 2 a 1 b 3 c 那么S的3组合有 2 a 1 b 2 a 1c 1 a 1 b 1 c 1 a 2 c 1 b 2 c 3 c a a b c c c a a b a a c a b c a c c b c c c c c S 排列与组合 定理 令S为具有k种类型元素的一个多重集 每种元素均具有无限的重复数 则S的r 组合的个数等于 证明 令S的k种类型的元素为a1 a2 ak 满足S a1 a2 ak S的任意一个r组合均呈 x1 a1 x2 a2 xk ak 的形式 其中 x1 x2 xk皆为非负整数 且x1 x2 xk r 反过来 满足x1 x2 xk r的非负整数的每个序列x1 x2 xk对应S的一个r组合 因此 S的r组合的个数等于方程 x1 x2 xk r的解的个数 其中 x1 x2 xk为非负整数 排列与组合 下面 我们证明 这些解的个数等于两种不同类型元素的多重集T r 1 k 1 的排列数 给定T的一个排列 k 1个 把r个1划分成k组 设第一个 的左边有x1个1 在第一个 号和第2个 号之间有x2个1 最后一个 号的右边有xk个1 于是 x1 x2 xk是满足x1 x2 xk r的非负整数 反之 给定非负整数x1 x2 xk 满足x1 x2 xk r 则可以根据上述步骤将该方程构造成T的排列 于是多重集S的r组合的个数等于多重集T的排列的个数 等于 x1 x2 xk x1个1 x2个1 xk个1 排列与组合 例 一家面包房生产8种面包 如果一个盒子内装有一打面包 那么你能够买到多少种不同的盒装面包 该问题等价于8种类型元素的多重集的12组合问题 这个数等于 例 其项取自1 2 k的长度为r的非减序列的个数是多少 要被计数的非减序列可以首先通过从多重集S 1 2 k 中选择一个r组合 然后 再以递增的顺序排列这些元素 这样的序列等于S的r 组合的个数 因此 该数等于 排列与组合 例 令S是具有四种元素a b c d的多重集 10 a 10 b 10 c 10 d S的使得四种元素的每一种都至少出现一次的10 组合的数目是多少 该问题等价于求方程x1 x2 x3 x4 10的正整数解的个数 x1代表10组合中a的个数 x2代表10组合中b的个数 x3代表10组合中c的个数 x4代表10组合中d的个数 由于重复数都等于10 而10又是被计数的组合长度 因此可以忽略这个重复数 令y1 x1 1 y2 x2 1 y3 x3 1 y4 x4 1 则方程变为y1 y2 y3 y4 6 由于这些xi是正整数 则yi就是非负整数 根据多重集的r组合数定理 该方程的非负整数解的个数等于 主要内容 概述鸽巢原理排列与组合生成排列和组合二项式系数容斥原理及应用递推关系和生成函数特殊计数序列二分图中的匹配Polya计数法 生成排列和组合 生成排列 如果将整数n从 1 2 n 的一个排列中删除 那么结果则是 1 2 n 1 的一个排列 例如 n 5 从排列3 4 1 5 2中删除5 则得到3 4 1 2 5 3 4 1 2 3 4 1 2 删除5得到序列 3 5 4 1 2 3 4 5 1 2 3 4 1 5 2 3 4 1 2 5 生成排列和组合 1 2 n 1 的每一个排列都可以由 1 2 n 的恰好n个排列中删除n而得到 给定 1 2 n 1 的一个排列 恰好存在n种方法将n插入到该排列中而得到 1 2 n 的一个排列 n 2 为了生成 1 2 的所有排列 把 1 的唯一排列写两遍并交错插入2 1 2 2 1 生成排列和组合 n 3 为了生成 1 2 3 的所有排列 把 1 2 的每一个排列以前面的生成方式写三次并交错插入3 1 2 2 1 1 2 1 2 2 1 2 1 1 2 3 3 2 1 1 3 2 3 1 2 2 3 1 2 1 3 生成排列和组合 n 4 为了生成 1 2 3 4 的所有排列 把 1 2 3 的每一个排列以前面的顺序写四遍并交错插入4 1 2 3 1 2 3 1 2 3 1 2 3 1 3 2 1 2 3 4 1 2 4 3 1 4 2 3 4 1 2 3 1 3 2 1 3 2 1 3 2 4 1 3 2 1 4 3 2 1 3 4 2 1 3 2 4 生成排列和组合 3 1 2 3 1 2 3 1 2 3 1 2 3 2 1 3 2 1 3 2 1 3 2 1 3 1 2 4 3 1 4 2 3 4 1 2 4 3 1 2 4 3 2 1 3 4 2 1 3 2 4 1 3 2 1 4 生成排列和组合 2 3 1 2 3 1 2 3 1 2 3 1 2 1 3 2 1 3 2 1 3 2 1 3 2 3 1 4 2 3 4 1 2 4 3 1 4 2 3 1 4 2 1 3 2 4 1 3 2 1 4 3 2 1 3 4 生成排列和组合 整数的方向 给定一个整数k 通过在其上面画一个指向左或向右的箭头来表示一个方向 或 活动的整数 将 1 2 n 的一个排列的每一个整数都给定一个方向 如果一个整数k的箭头指向一个与其相邻但比它要小的整数 那么这个整数k称为活动的 哪些整数是活动的 6 3 5 生成排