[数学]组合数学斯特林数.ppt

  1. 1、本文档共38页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[数学]组合数学斯特林数

二、分拆数的母函数 例1 把 n 分拆成 1,2,3 之和(可重复), 求其分拆数的生成函数。 解: n拆成1,2,…,m之和(可重复),生成函数是: 例2 把 n 分拆成 1,2,3 之和,3至少出现1次, 求其分拆数的生成函数。 解: n拆分出的最大数= m,其生成函数是: 定理1 (分拆数的生成函数) Ferrer图: 三、 Ferrer 图 最大=6的5个数 最大=5的6个数 Ferrer图的共轭性: 三、分拆数的组合应用 (1) 把n分拆成“最大为m”的分拆数,也是 把n分拆成“m个数之和”的分拆数, 等价于: 把n个相同的球放入m个相同的非空盒子 的方法数。 (2) 把n分拆成“最大数不超过m”的分拆数,也是 把n分拆成“至多m个数之和”的分拆数, 等价于: 把n个相同的球放入m个相同的盒子(盒可以 空)的方法数。 四、分球问题 序号 球标号? 房标号? 房可 空? 方法数 000 × × × n拆成“恰好m个数”的分拆数 001 × × √ n拆成“至多m个数”的分拆数 010 × √ × (插入m-1道墙壁) 011 × √ √ 100 √ × × S(n,m) —— 第2类斯特林数 101 √ × √ S(n,1)+S(n,2)+…+S(n,m) 110 √ √ × m!S(n,m) 111 √ √ √ 把n个球放入m间房中,可分为8种情况 习题8(第4版)221 6,7,9 12,13,16,19 26, §2 差分序列与斯特林(Stirling)数 一、差分序列 1. 差分的定义 2. 差分表 0 1 2 3 4 例1. 0 1 2 3 4 5 6 7 0 1 4 9 16 25 36 49 1 3 5 7 9 11 13 … 2 2 2 2 2 2 … 0 0 0 0 0 0 … 例2. 0 1 2 3 4 5 6 1 6 15 28 45 66 91 … 5 9 13 17 21 25 … 4 4 4 4 4 4 … 0 0 0 0 0 0 … … … … … 3. 差分序列的性质 证明: 性质1 降阶效应,类似导数 (定理1) 证明: 由于 所以 是p-1次多项式, 而其他项的次数至多是 p-1 性质2 0 1 2 3 4 5 6 … … … … 类似于泰勒展开,f (x) 由x=0 点的各阶导数值确定。 差分表为 0 1 2 3 4 5 6 7 8 9 0 0 0 0 1 5 15 35 70 0 0 0 1 4 10 20 35 56 0 0 1 3 6 10 15 21 28 0 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 例3 解: 由于 不妨设 因此 性质3 线性(类似导数) 性质4 (定理2) 0 1 2 3 4 1 3 17 49 … 2 14 32 … 12 18 24 6 6 6 0 0 0 例4: 解: 例5 解: 解: 性质5 (定理3) 例6 0 1 16 81 256 625 1 15 65 175 369 … 14 50 110 194 … 36 60 84 … 24 24 … 0 0 … 性质6 二、第二类斯特林数 1、定义 比较系数,知: 2、递推式(定理4) k p 0 1 2 3 4 5 6 7 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 x2 x3 x4 x5 x6 证明: n=(n-k)+k 3、第二类斯特林数的应用 例如: 把 a,b,c,d 4个人分配到2间无差别的房间,不必考虑房间顺序,且没有空房,可行的分配方案为: 应用1: S(p,k)是把p个人分进 k 间无差别的房间 (无空房)的方法数。(定理5) a | bcd b | acd c | abd d | abc ab | cd ac | bd ad | bc 由递推表可知: S(4,2)= 7 证明: 设 a(p,k)是p人分进k间相同房间(无空房)的方法数。 显然, a(p,0)=0(不可能做到), a(p,p)=1(每人一间)。 若1号人单占一间:其余p-1人占k

文档评论(0)

hhuiws1482 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

版权声明书
用户编号:5024214302000003

1亿VIP精品文档

相关文档