的排列(1) 指数型母函数主要解决限制元素出现次数的排列问题例1 求1,3,5,7,9 这5个数字组成的 n位数个数,要求其中 3出现的次数为偶数,其它数字出现的次数无限制。 4 3.4 棋盘多项式和有限制条件的排列(2) 、容斥原理: 既可解决限制元素出现次数的问题,也能解决元素出现位置的问题典型特征是:问题能够化为集合问题: nA ...AA??? 21 nAAA???... 21例2 求a,b,c,d,e,f 这6个字母的全排列中不允许出现 ab和de图像的排列数。 5 3.4 棋盘多项式和有限制条件的排列(3) 递推关系既可解决限制元素出现次数的问题,也能解决元素出现位置的问题典型特征是:写出递推关系 6 3.4 棋盘多项式和有限制条件的排列(4) 棋盘多项式解决无重复排列元素出现位置的问题例3:甲乙丙丁 4个人,有4项工作 1,2,3,4, 甲干不了 1,2,3 号工作,乙干不了 2,3,4 号工作,丙干不了 1、4号工作,丁干不了 1,2,4 号工作,求满足各人工作要求的方案数。 7 n个不同元素的某一排列可以看做是 n个相同的棋子在 n×n的棋盘上的一种布局。 3.2 棋盘多项式和有限条件的排列 41352 51234 1、棋盘多项式的由来 8xx xxx 棋盘的每一个布局每行每列有且有一个棋子; 3.4 棋盘多项式和有限条件的排列类似于象棋中的车无对攻原则。 9 n个不同元素取 r个的排列可以看做是n个相同的棋子在 r×n的棋盘上的一种布局, 例如:1,2,3,4,5 中取 3个的排列 3.2 棋盘多项式和有限条件的排列 435 512 10 xx xxx 令r k(c)表示 k只棋子布到棋盘 C的不同的方案数,规则是当一只棋子布到棋盘的某一格时,则这个格子所在的行和列上的其他格子不再允许布上别的棋子。 3.4 棋盘多项式和有限条件的排列
全文预览