组合数学 第三章.doc

第三章 容斥原理和鸽笼原理一、 容斥原理设A，B为任意两个集合，U为全集，推广：设D为任意非空集，为集族，Demorgen原理，容斥原理：设是个有限集合，则 设n-1时结论成立，即则当时又，由归纳原理，易知命题成立。容斥原理另一描述 （N全集中元素个数）例1：求六个字母的全排列中不允许和df图象的排列数。解：全排列中出现的排列集，：全排列中出现的排列集则 ，从而 例2：求不超过120的素数的个数解：故不超过120的合数必然是2，3，5，7的倍数。令 ：不超过120的2的倍数集，：不超过120的3的倍数集 ：不超过120的5的倍数集，：不超过120的7的倍数集。全体素数274130例3：用26个英文字母作不允许重复的全排列，要求排除dog, god, gum, depth, thing字样出现，求满足这些条件的排列数解：出现dog 的排列全体， ：出现god的排列全体 ：出现gum的排列全体，：出现depth的排列全体 ：出现thing的排列全体则 ， ，例4 求完全由n个布尔变量确定的布尔函数的个数解：不出现的布尔函数类，则 例5 错排问题，排列123n的错排数 i不出现在第i位的排列全体，则 二、 棋盘多项式n个棋子放到 nn的棋盘上，当一个棋子置于棋盘的某一格子时，则这一格子所在行和列都不能再布任何棋子 ，布局方案数现令C表示任意棋盘（形状各一），将只棋子布到棋盘C上，当某一格布下棋子时，该格所在行和列均不布棋，设满足条件的方案数为。（ ）1， （ ）2， （ ）1，（ ）0 构成多项式 棋盘多项式R（ ）12R ( )=1+(1) 对某个棋盘C而言，令表示将C中某一格子所在行和列去掉后所余部分，表示将中某一格子去掉后所余部分，则于是 （n比较大）例如： C （2）如果棋盘C是由互相分离的两部分和组成，则三、 有禁区的排列给定一个棋盘，棋盘某些影线格为禁区，即级排列中不能出现元素放入禁区，求有禁区的排列数。令：第个棋子放入禁区的排列数，则有禁区的排列数，其中是由禁区部分构成的棋盘。 例1：有G，L，W，Y四位工作人员，A，B，C，D为四项任务，但G不能从事任务B，L不能从事B，C两项任务，W不能作C，D工作，Y不能从事任务D，若要求每人从事各自力所能及的三项工作，试问有多少种不同方案？4，这时棋盘多项式四、 圆排列问题 设是沿着圆周排列的序列，即它和看作相同的，这样的排列称为圆排列。如果不允许重复，则个线性排列是互不相同的。如果允许重复，比如当，则考虑如下圆排列n级圆排列它只能得到d个不同线排列。设由集合中元素形成的长度与周期都是d的圆排列个数，n是给定的正整数，则，由Mbius反演公式得，其中从而长度为的圆排列数五、 鸽笼原理n+1鸽子飞进n个鸽笼，则至少有一个笼子中至少有两只鸽子。例1：从1到2n的正整数中任取n+1个，则这n+1个数中至少有一对数，其中一个数是另一个数的倍数。解：设所取n+1个数是，并令为奇数，由于1到2n中只有个奇数，故中必有两个数相同，不妨设，则，如果，则 ，如果，则 例2：设是正整数序列，则至少存在整数和使得和是的倍数解：令 ， 如果存在，使得，则结论成立，否则被除余数只能为1，2，m-1中一个，故必有2个余数相同，不妨设和余数相同，则。鸽笼原理推广：设都是正整数，并且有只鸽子住进n个鸽笼，则第一个鸽笼至少有只鸽子，或第二个鸽笼至少有只鸽子，或第n个鸽笼至少有只鸽子，至少其中之一必然成立。推论1：m只鸽子，n个鸽笼，则至少有一个鸽笼里有不少于只鸽子。推论2：若取个球，放进n个盒子，则至少有1个盒子有m个球。推论3：若是n个正整数，而且则中至少有1个数不小于。例1：若序列的个实数两两不等，则从中至少可选出一组由n+1个实数组成的或为单调增或为单调减的子序列。Pf：设从为首的单调增的元素个数最多的子序列中含有个实数，则得到序列如果存在，使得则结论成立，否则相当于把个球放入n个盒子里，由于故存在个，使得，不妨设则对应的必满足，如若不然，设时，则可把元素加到从开始的长度为的单调增序列前面，构成从开始长度为的单调增序列，矛盾。例4：（Ramsey问题）六个人中至少存在三个人或是互相认识或是互相不认识。例5：9个人中若不是有3个人互不认识，则必有4人互相认识或者说，若不是有3个人互相认识，则必有4