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

二、分拆数的母函数 例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