- 1、本文档共21页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
组合数学第二章第九节
* * 2.9 费勒斯(Ferrers)图像 假设正整数n拆分成n=n1+n2+…+nk。 其中n1≥n2 ≥n3 ≥… ≥nk。将他们排成阶梯形,左边对齐,第一行n1格,第二行n2格,第k行nk格。 3 2 2 1 1 2 3 4 例如:8=3+2+2+1 1、什么是费勒斯图像 2、费勒斯(Ferres)图像的性质: (1)每一层至少有一个格子; (3)行与列互换,即第1行与第1列互换,第2行与第2列互换,……,也就是沿对角线旋转180°,仍然是费勒斯图像; 后一个费勒斯图像称为前一个费勒斯图像的共轭图像,而且互为共轭。 (2)下一层的格数不多于上一层的格子数; (1) 整数n拆分成k个数的和的拆分数,与数n拆分成最大数为k的拆分数相等。 因为整数n拆分成k个数的和的拆分可以用一个k行的图像表示。所得的Ferrers图像的共轭图像最上面一行有k个格子。例如: 3. 利用Ferrers图像可以得到一些关于整数拆分的结果: 24=6+6+5+4+3 5个数,最大数为6 24=5+5+5+4+3+2 6个数,最大数为5 理由和(1)相类似。 因此,拆分成最多不超过m个数的和的拆分数的母函数是: (2) 整数n拆分成最多不超过m个数的和的拆分数,与n拆分成最大不超过m的拆分数相等。 正好拆分成m个数的和的拆分数的母函数为 (3) 整数n拆分成互不相同的若干奇数的和的的拆分数,与n拆分成自共轭的Ferrers图像的拆分数相等。 设整数n拆分为n=(2n1+1)+(2n2+1)+…+(2nk+1),其中n1n2…nk。 构造一个Ferrers图像,第一行第一列都是n1+1格,对应于2n1+1,第二行第二列都是n2+1格,对应于 2n2+1,依此类推。 这样得到的Ferrers图像一定是自共轭的。 反过来,自共轭的Ferrers图像也可以对应到一些不同奇数的和。 例如17=9+5+3对应的Ferrers图像为: (4) 正整数n剖分成不超过k个数的和的剖分数,等于将n+k剖分成恰好k个数的剖分数。 不超过k层的Ferrers图像的每一层加上一个格子,一一对应到一个刚好k层的Ferrers图像。 2.11 指数型母函数 考虑n个元素组成的多重集,其中a1重复了n1次,a2 重复了n2次,…,ak重复了nk次,n=n1+n2+…+nk。从中取r个排列,求不同的排列数。 若r=n,即考虑n个元素的全排列,则不同的排列数为: 但是对于一般的r,情况就比较复杂了。 8 7 6 5 4 3 2 3 2 5 4 3 2 3 2 2 3 2 3 6 9 10 9 6 3 1 ) 1 ( ) 2 3 3 2 1 ( ) 1 )( 1 )( 1 ( ) ( x x x x x x x x x x x x x x x x x x x x x x x x x G + + + + + + + + = + + + + + + + + = + + + + + + + + = 先看一个具体的问题:假设有8个元素,其中a1重复3次,a2重复2次,a3重复3次。从中取r个组合,其组合数为cr,则其对应的母函数为: 从x4的系数可知,从这8个元素中取4个组合,不同的组合数为10。 这10个组合可从下面的展开式中得到: 其中4次方项表示了所有从8个元素中取4个的组合方案。 例如 表示一个a1三个a3的组合, 表示两个a1两个a3的组合,依此类推。 接下来讨论从这8个元素中取4个的不同排列总数。 以两个a1两个a3组合为例,不同排列数为4!/(2!2!)。 同样一个a1三个a3的不同排列数为4!/(1!3!)。 依此类推可以得到不同的排列总数为: 为了便于计算,利用上述特点,形式地引进函数 从右边很容易可以看出,取2个的排列数为9,取3个的排列数为28,取4个的排列数为70…依此类推。 定义:对于序列a0,a1,a2,…,函数 称为序列a0,a1,a2,…对应的指数型母函数。 这样,对于一个多重集,其中a1重复n1次,a2 重复n2次,…,ak重复nk次,从中取r个排列的不同排列数所对应的指数型母函数为: 例1 求下列数列的指数型母函数: 例2 由1,2,3,4四个数字组成的五位数中,要求数1出现次数不超过2次,但不能不出现; 2出现次数不超过1次; 3出现次数最多3次,可以不出现;4出现次数为偶数。求满足上述条件的数的个数。 设满足上述条件的r位数个数为cr,则其对应的指数型母函数为: 由此可见满足条件的5位数共215个。 例3 求由1,3,5,7,9五个数字组成的n位数的个数,要求其中3,7出现的次数为偶数,其他1,5,9出现次数不加限制。 设满足上述条件的n位数个数
您可能关注的文档
最近下载
- 水文测验与资料整编:第6章 流量数据处理(整编).ppt
- 24春江苏开放大学计算机应用基础第二次形成作业(Word 操作)6.docx
- 金寨县植被覆盖度时空变化特征及其驱动力因素-水土保持与荒漠化防治专业论文.docx VIP
- 初中数学教学:生活情境项目化学习案例.doc
- 《青纱帐——甘蔗林》课件【中职专用】高教版 基础模块下册.pptx
- 9.《复活(节选)》课件(共34张PPT) 统编版高中语文选择性必修上册.pptx VIP
- DB12∕T 942-2020 乡村公路工程质量检验评定标准.docx
- (完整版)交管12123学法减分考试题库及答案.docx
- 2024河北邯郸市公安局特警支队训练基地招聘机动处突队员55人笔试备考试题及答案解析.docx VIP
- 九年级化学上册第三单元课题2 原子的结构.pptx VIP
文档评论(0)