《组合数学 第三章》由会员分享，可在线阅读，更多相关《组合数学 第三章（7页珍藏版）》请在金锄头文库上搜索。
1、1第三章 容斥原理和鸽笼原理一、容斥原理设 A，B 为任意两个集合，U 为全集， ，|Bx或|BxA且， ，|且 ,|UxA推广：设 D 为任意非空集， 为集族，D，,|xA ,|AxDDemorgen 原理，DA容斥原理：设 是 个有限集合，则nA,21 kjijkijnijijiin A11121 n 21)( :pf 21211 AAn设 n-1 时结论成立，即 jijniniA 1121 12121 )(nnjijkijni A则当 时 nnAA )(121121 nnA又 )()(|)()( 121121 nnn A 2kjijkijnijijniini AAA 111，由归纳原理，
2、易知命题成立。nn 2)(容斥原理另一描述（N全集中元素个数）nn AANA 32121 kjijkijnijijiniN111nn2)(例 1：求 六个字母的全排列中不允许 和 df 图象的排列数。fedcba, ace解： ：全排列中出现 的排列集， ：全排列中出现 的排列集Aa2Adf则 ，!3,!5,!42121 从而 58266121例 2：求不超过 120 的素数的个数解： 故不超过 120 的合数必然是 2，3，5，7 的倍数。,1令 ：不超过 120 的 2 的倍数集， ：不超过 120 的 3 的倍数集AA：不超过 120 的 5 的倍数集， ：不超过 120 的 7 的倍数
3、集3 4 312143214210 A32143 AAA 42143142。06 70867全体素数 274130例 3：用 26 个英文字母作不允许重复的全排列，要求排除 dog, god, gum, depth, thing字样出现，求满足这些条件的排列数解： ：出现 dog 的排列全体， 1A：出现 god 的排列全体A3：出现 gum 的排列全体， ：出现 depth 的排列全体3A4A：出现 thing 的排列全体5则 ，312154321 ,0!, A， 5243214 !,.0.0! AA0 !9!54533 0, 5212121 A ,0045343 AA !17, 5322,
4、5431531431 A22 AA，0543 05431 !2436!1792!621 AA!79例 4 求完全由 n 个布尔变量确定的布尔函数的个数解： ：不出现 的布尔函数类，iixni,3,21则 knnn CA)1()()(2221 .,)1(),(CknCkn例 5 错排问题，排列 123n 的错排数i 不出现在第 i 位的排列全体，A则 n21 nA21!1),()!(,)(,! CC4二、棋盘多项式n 个棋子放到 nn 的棋盘上，当一个棋子置于棋盘的某一格子时，则这一格子所在行和列都不能再布任何棋子 ，布局方案数 !12)(nn现令 C 表示任意棋盘（形状各一） ，将 只棋子布到
5、棋盘 C 上，当某一格布下棋子时，k该格所在行和列均不布棋，设满足条件的方案数为 。)(rk（ ）1， （ ）2， （ ）1， （ ）0 0r1r2r 3k构成多项式 棋盘多项式knkxCR)()(0R（ ）12 2R ( )=1+ x(1)对某个棋盘 C 而言，令 表示将 C 中某一格子所在行和列去掉后所余部分， 表)(i )(eC示将 中某一格子去掉后所余部分，则 于是 c ),()()(1ekikkrrekikk xrxrxr)()()(1（n 比较大）kekniknCkn crc)(0)(10)(0 )()(eiRxR例如： C 3210 )()(xcrxcr325 )(i )(xCR
6、i)(e 2)(41e()()(ixCR（2）如果棋盘 C 是由互相分离的两部分 和 组成，则1C25)()(210CRrrikikik三、有禁区的排列给定一个 棋盘，棋盘某些影线格为禁区，即 级排列中不能出现元素放入禁区，nn求有禁区的排列数。令 ：第 个棋子放入禁区的排列数，则iA有禁区的排列数 )!1(! 12121 nCrAnn，其中 是由禁区部分构成的棋盘。)()!2(2 CrnCrn例 1：有 G，L，W，Y 四位工作人员， A，B，C ，D 为四项任务，但 G 不能从事任务 B， L 不能从事 B，C 两项任务，W 不能作 C，D 工作，Y 不能从事任务 D，若要求每人从事各自力
7、所能及的三项工作，试问有多少种不同方案？4，!12!3431rrN!120!64这时棋盘多项式 32xx四、圆排列问题设 是沿着圆周排列的序列，即它和 看作相na21 121132,nnnaa同的，这样的排列称为圆排列。如果 不允许重复，则 个线性排列n,21 n nnn,13221是互不相同的。21na如果 允许重复，比如当 ，则考虑如下圆排列n,21 d|n 级圆排列它只能得到 d 个不同线排列。)()( 211dd aa设由集合 中元素形成的长度与周期都是 d 的圆排列个数 ，n 是,m )(M给定的正整数，则 ，由 Mbius 反演公式得，nnd)(| dndm1)(|6其中 个 不
8、同 素 因 子有 有 重 素 因 子kddk)1(01从而长度为 的圆排列数n)()(|dMnT五、鸽笼原理n+1 鸽子飞进 n 个鸽笼，则至少有一个笼子中至少有两只鸽子。例 1：从 1 到 2n 的正整数中任取 n+1 个，则这 n+1 个数中至少有一对数，其中一个数是另一个数的倍数。解：设所取 n+1 个数是 ，并令 为奇数，121,na iniri,20in由于 1 到 2n 中只有 个奇数，故 中必有两个数相同，不妨设 ，则nrr jir，如果 ，则 ，如果 ，则 jjini rar2,jiji| jinija|例 2：设 是正整数序列，则至少存在整数 和 使得和m,1 k,1,mll
9、是 的倍数lk解：令 ， ， 1as212ammaas21如果存在 ，使得 ，则结论成立，否则 被 除余数只能为iis| s,1，2，m-1 中一个，故必有 2 个余数相同，不妨设 和 余数相同，则 。ij jis|鸽笼原理推广：设 都是正整数，并且有 只鸽子住进 n 个鸽nm,21 121nm笼，则第一个鸽笼至少有 只鸽子，或第二个鸽笼至少有 只鸽子，或第 n 个鸽1 2笼至少有 只鸽子，至少其中之一必然成立。n推论 1：m 只鸽子，n 个鸽笼，则至少有一个鸽笼里有不少于 只鸽子。1nm推论 2：若取 个球，放进 n 个盒子，则至少有 1 个盒子有 m 个球。1)(7推论 3：若 是 n 个
10、正整数，而且m,21 ,121rnmn则 中至少有 1 个数不小于 。n,21 r例 1：若序列 的 个实数两两不等，则从中至少可选出一组3212,na由 n+1 个实数组成的或为单调增或为单调减的子序列。Pf：设从 为首的单调增的元素个数最多的子序列中含有 个实数，则得到序列ia il如果存在 ，使得 则结论成立，否则1212,nll k,1nlk相当于把 个球放入 n 个盒子里，由于,2ii 2故存在 个 ，使得 ，不.12n121,nkkll llnkk121妨设 则对应的 必满足 ，如若不,121nkk 121,nkka 121 nkka然，设 时 ，则可把元素 加到从 开始的长度为 的单调增序列前面，ji jikai j l构成从 开始长度为 的单调增序列，矛盾。ikal例 4：（Ramsey 问题）六个人中至少存在三个人或是互相认识或是互相不认识。例 5：9 个人中若不是有 3 个人互不认识，则必有 4 人互相认识或者说，若不是有 3个人互相认识，则必有 4 人互不相识。五、Ramsey 数对于 r 个顶点的完全图，如果用红、蓝两种颜色对边着色，如果存在 个顶点的完a全 边形红色，或者存在 个顶点完全 边形蓝色，称满足此性质的最小 叫做 Ramseyab r数，记为 ),( ,ar )2,( )1,(),1(brrb
