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

1、第一、三章回弹原理和鸽巢原理， 3.1 De Morgan定理1 3.2反相原理1 3.3反相原理示例1 3.4棋盘多项式和限制数组2 3.5限制区域阵列2 3.6广义反相原理3 3 3.7广义反相原理应用3 2.8第二类斯特林数扩展1 2.9欧拉函数(n) 1 2.10 n对夫妇问题3 * 2.11 mobis反相联定理2.12鸽子巢原理4 2.13 2，3.4板多项式和有限数组，1，有限数组，有重复和不重复数组，1，解决这些问题的工具包括，(1)，指数函数：(3)，递归关系：(2)，宽容原则：3，3.3 示例2 a、b、c、d、e、f、5，3.4棋盘多项式和有限数组；(3)迭代关系；限制元

2、素发生次数的问题；解决元素发生问题的一般特征是创建迭代关系；6，3.4棋盘多项式和有限数组；(4)棋盘多项式解决不重复的元素发生问题，甲不能工作1，2，3次，乙不能工作2，3，4次，病日不能工作1，2，4次，更正不能工作1，2，4次，找不到满足每个人工作要求的方案数。7，N个徐璐其他元素阵列可以看作是N个相同的棋盘在nn的棋盘上的布局。(约翰f肯尼迪，Northern Exposure美国电视电视剧，3.2板多项式和有限条件的安排，41352，51234，)，3.4棋盘多项式和有限条件的安排类似于国际象棋的汽车无污染原则。9，N个徐璐其他元素R个数组在rn的棋盘上可以看作是N个相同棋盘的布局，

3、例如，1，2，3，4，5到3个数组，3.2板多项式和有限条件的数组，435，512，乙不能买2，3，4房间，1 2 3 4，甲乙丙丁，1 2，3.4棋盘多项式和有限条件的安排，例43360甲丙丁4人宿舍，5个1，2，3，4，5，甲1，2，3.4棋盘多项式和有限条件的阵列，R2()，R1()，=2，=0，r()，=1 2x，2，棋盘多项式的定义，* * *，3.4棋盘多项式和有限条件的数组，3，棋盘多项式的简化，17，公式1，RK(C)=RK1(C)(I)RK(C)，3.4棋盘多项式和有限条件的数组公式1，RK，证明：3.4棋盘多项式和有限条件的数组，19，规则r0(C)=1，r0()=1。3.

4、4棋盘多项式和有限条件的阵列，公式1，rk (c)=rk1 (c (I) rk (c (e)，r0 () R1()，=，R1(1 55)，=x(1x)=1 2x；=x(1 x) 1 x，=1 2x x2。3.4棋盘多项式和有限条件的阵列，简单棋盘多项式，23，r()，=x r()，=x 1 2xx2，=1 3xx2。3.4棋盘多项式和有限条件的阵列，r()，24，r()，=x r()，=x (1 x) (1 2x)，=1 4x2x2。3.4棋盘多项式和有限条件的数组，由R()，25，C徐璐分隔的C1，C2组成，相互分隔是同行者同一列中不同时属于C1和C2的晶格。例如，证明：C1，C2是分开的，

5、因此C1的布和C2的布不会徐璐影响。C上有一千个K片到C1上有一千个I，C2上有一千个k-i，方案数是3.4板块多项式和有限条件的数组，26，C上有一千个K片到C1上有一千个I，C2上有一千个k-i，方案数是3.4板块多项式=1 5x 6x2 x3，3.4棋盘多项式和甲1，2，3房间，乙2，3，4房间，C有满足要求的方案数。甲乙丙丁，1 2 3 4，4，棋盘多项式的应用，30，3.4棋盘多项式和有限条件的数组，r (c)，=(1 x) (1 x) (1 3xx2)=1 5x8x2 5x3x4，1 5x 4，分析：A B C D E，1 2 3 4，3.4检查器多项式和有限条件的数组，32，分析

6、：A B C D E，1 2 3 4，3.4检查器多项式和有限条件的数组，r (c)，=(1 x)，3.5限制区数组-r1(n-1)！R2(n-2)！-(-1)nrn其中ri是在禁区内放置I个棋子的方案数。证明：将Ai作为I的第一个棋子放在限制区中，设置其他棋子任意布的方案集，I=1，2，3，n。3.5限制区安排，35，千棋子都不落入限制区的方案数应如下。两个棋子落在限制区的方案数设定为R2，剩下的n-2是无限阵列，方案数为(n-2)！3.5限制区数组，36，示例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限制区域阵列，37，根据清理3.3，R1=6，R2=；=16x10x2 4x3，R()， 3.1 De Morgan定理1 3.2反冲原理1 3.3反冲原理示例1 3.4棋盘多项式和限制数组2 3.5限