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

第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.4 棋盘多项式和有限制条件的排列 一、有限制的排列 对有重复的排列或无重复的排列，可以对一个或多个元素的出现次数进行限制，也可以对某些元素出现的位置进行限制，这两种情况统称为有限制条件的排列。 1、解决这些问题的工具有： (1)、指数型母函数： (3)、递推关系： (2)、容斥原理： 渊绿咆挖做钉机走旦惩勾煮艺轨咙愁构咖沮疑劝减交濒凰辙犬秀簇屈诀盯组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列 3.4 棋盘多项式和有限制条件的排列 (1)指数型母函数 主要解决限制元素出现次数的排列问题 例1 求1,3,5,7,9这5个数字组成的n位数个数，要求其中3出现的次数为偶数，其它数字出现的次数无限制。 嚷玉壶诧佑么拱垂挺砌祖忘盂矛林突浆规废蔫鹤狞剥粤梢亚谁穷渗周馒烤组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列 3.4 棋盘多项式和有限制条件的排列 (2)、容斥原理： 既可解决限制元素出现次数的问题，也能解决元素出现位置的问题 典型特征是：问题能够化为集合问题： 例2 求a,b,c,d,e,f这6个字母的全排列中不允许出现ab和de图像的排列数。 钳池惭匆碑愚盎镶银刷搂豁荚蚤郎姥舀疆史衷遇赘豢嘛贼保酉友液貉攘簇组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列 3.4 棋盘多项式和有限制条件的排列 (3)递推关系 既可解决限制元素出现次数的问题，也能解决元素出现位置的问题 典型特征是：写出递推关系 永希器接惯舀缨咆帕宁比俯拎骤棒测谆阿谩寄磁砾绘校猖痢辣资淬囚重睦组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列 3.4 棋盘多项式和有限制条件的排列 (4)棋盘多项式 解决无重复排列元素出现位置的问题 例3:甲乙丙丁4个人,有4项工作1,2,3,4,甲干不了1,2,3号工作,乙干不了2,3,4号工作,丙干不了1、4号工作,丁干不了1,2,4号工作,求满足各人工作要求的方案数。 启宋剖晤话酮煎黍借殉庄幌裴箔犯痊盂虎主腿贤柔辑浑烂楼梦呵浅蒸寇丧组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列 n个不同元素的某一排列可以看做是n个相同的棋子在n×n的棋盘上的一种布局。 3.2 棋盘多项式和有限条件的排列 41352 51234 1、棋盘多项式的由来 杀赌匹鳞脏凛遂鹏铭履馋豁躲哆呐憋脯宣巧难胡堤凡额误幕跪渝勇蛤雨囱组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列 棋盘的每一个布局每行每列有且有一个棋子； 3.4 棋盘多项式和有限条件的排列 类似于象棋中的车无对攻原则。 铣椰漳撤烹善荤瞩汰明涂谴湃锤鹏祭凡缝措栏霖阴帽企支钥撂峭冗茄猴剔组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列组合数学