组合数学（张永刚）吉林大学 第四章、容斥原理.pptVIP

考虑教材156页例8.3，用三种颜色涂色装有5颗珠子的手镯，如果只考虑手镯的旋转，问有多少种涂色方案？ 解： 例2. 证. 仅须证n1情形, n1为n不同素因子积. 利用这个例题的结果, 可以把圆排列计 数公式利用欧拉函数改进成单重求和形式: * R(C)=R(C1)?R(C2), , C1和C2含义如前所述。 将以上各式的两边分别相加得： 证明： 例 4.5.1 计算棋盘多项式R( ) 解 R ( ) =x R( )+ R( ) =x(1+2x)+ R( ) R( ) =x+2x2 +(1+x)(x R( )+ 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 根据布置的规则，可以得出L= {1，2，…，n}的一个排列恰好对应了n个棋子在n×n棋盘上的一种布棋方案。 每个方格用坐标(i, j)表示，其中i表示其所在的行，j表示其所在的列。 如果以横坐标表示 L中的元素，纵坐标表示在该元素在排列中的位置，则这种放棋方案就对应了排列3124。 1 2 3 4 1 2 3 4 对应的排列：3 1 2 4 相同棋子的步棋总数N！ 不同棋子的步棋总数N！ N！ 4个棋子：（1，2）、（2，3）、 （3，1） 、 （4，4）。 反过来也一样。 如果在排列中限制元素 i 不能排在第 j 个位置，则相应的布棋方案中棋盘的第i 行第j 列的方格不许放棋子。如果把所有这些不许放棋的方格称做禁区，则相应地，有禁区的排列问题就对应了有禁区的布棋问题 例　设对于排列P=P1 P2 P3 P4，规定P1≠2，P２≠3、４， P３≠1， P4≠2、3。 P1 P 2 P3 P4 1 2 3 4 定理4.5.1 设C是n×n的具有给定禁区的棋盘，这个禁区对应于集合{1,2,…,n}中的元素在排列中不允许出现的位置。则这种有禁区的排列数是 N=n!-r1(n-1)!+ r2(n-2)!-…+(-1)nrn 其中ri表示i个棋子布置到禁区的方案数。 证明：容斥原理。 如果没有禁区，那么n个棋子布到n×n的棋盘上的方案有n!个。 如果对n个棋子分别编号1,2,…,n，并且认为编号不同的棋子放入同样的方格是不同的放置方案，那么带编号的棋子布到n×n棋盘上的方案数是n！× n！，把这些方案构成的集合记为S. 对j= 1,2,…,n，令Pj表示第j个棋子落入禁区的性质，并令Aj是S中具有性质Pj的方案构成的子集，那么所求的排列数就是 （1）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求和得： （2）1号和2号两个棋子落入禁区的方案数为2r2, 它们落入以后， 3,4,…,n号棋子可以任意放置在 (n-2)×(n-2)的棋盘上， |A1 ∩ A2|=2r2(n-2)!(n-2)! 对所有的1 ≤ij ≤n求和有 同理对{i,j}?{1,2,…,n}有 |Ai ∩ Aj|=2r2(n-2)!(n-2)!， ………………… |A1 ∩ A2 ∩… ∩ An |=rn·n! 根据包含排斥原理，带编号的n个棋子都不 落入禁区的方案数是 而带编号的方案数与不带编号的方案数相 差n!倍，因此结论成立，即： 需要说明一点，这个定理适用于小禁区的布 棋问题，如果是很大的禁区或者是m×n的棋盘， 那么只能直接求R(C)来求解。 例　１，２，３，４四位工人，A，B， C，D四项任务( * )。条件如下： １不干B