组合数学课件--第三章第二节棋盘多项式和有限制条件的排列.ppt

* 例3.5 一婚姻介绍所，登记有5名男性A，B，C，D，E和4名女性1，2，3，4，经了解：1不能与B,C,D,E，2不能与A,D,E,3不能与A,B,C，4不能与A,B,C,D求可能婚配的方案数。 解： A B C D E 1 2 3 4 3.4 棋盘多项式和有限条件的排列 * 解： A B C D E 1 2 3 4 3.4 棋盘多项式和有限条件的排列 R(C) =(1+x)(1+2x)(1+3x+x2) =1+6x+12x2+9x3+2x4 *** * 例6:设对于1,2,3,4的排列P=P1P2P3P4，规定P1≠3，P２≠1，P３≠2，P4≠4。 3.5 有禁区的排列 P1 P2 P3 P4 * 定理3.3 有禁区的排列数为 n!-r1(n-1)!+r2(n-2)!-…+(-1)nrn 其中ri是有i个棋子布置到禁区部分的方案数。 证明： 设Ai为第i个棋子布入禁区，其他棋子任意布的方案集的集合，i =1 , 2 , 3, …,n。 3.5 有禁区的排列 * 布n个棋子无一落入禁区的方案数应为： 两个棋子落入禁区的方案数设为r2,而其余n-2个棋子为无限制条件的排列，方案数是(n-2)!。 3.5 有禁区的排列 * 例3.7 有G,L,W,Y4位工作人员，A,B,C,D为4项任务，但G不能从事任务B;L不能从事B，C两项任务；W不能做C,D工作；Y不能从事任务D。若要求每人从事各自力所能及的一项工作，问有多少种不同方案？ A B C D G L W Y 解： 3.5 有禁区的排列 * 按照定理3.3，相当于r1=6,r2=10,r3=4,代入公式： =x(1+x)(1+2x)+(1+2x)(1+3x+x2) = xR( ) + R( ) = 1+6x +10 x2 +4x3 R( ) 3.5 有禁区的排列 * 例3.8 错排问题 · · · 对角线棋盘的棋盘多 项式为： 将错排问题看做是有禁区的排列，可看作禁区是在对角线上的方格。 x x x x x 3.5 有禁区的排列 * 3.2 棋盘多项式和有限条件的排列 因此错排的方案数为： *** * 第3章 容斥原理与鸽巢原理 3.1 De Morgan定理 1 3.2 容斥原理 1 3.3 容斥原理举例 1 3.4 棋盘多项式与有限制的排列 2 3.5 有禁区的排列 2 3.6 广义的容斥原理 3 3.7 广义容斥原理的应用 3 2.8 第二类Stirling数的展开式 1 2.9 欧拉函数?(n) 1 2.10 n对夫妻问题 3 *2.11 Mobius反演定理 × 2.12 鸽巢原理 4 2.13 鸽巢原理举例 4 2.14 鸽巢原理的推广 4 *2.15 Ramsey数 × 谢谢！ * 第3章 容斥原理与鸽巢原理 3.1 De Morgan定理 1 3.2 容斥原理 1 3.3 容斥原理举例 1 3.4 棋盘多项式与有限制的排列 2 3.5 有禁区的排列 2 3.6 广义的容斥原理 3 3.7 广义容斥原理的应用 3 2.8 第二类Stirling数的展开式 1 2.9 欧拉函数?(n) 1 2.10 n对夫妻问题 3 *2.11 Mobius反演定理