第3讲数理统计.ppt

* +1，-1等也算表达式 * * +1，-1等也算表达式 * 齐次递推关系 * 例18——18种方法 例19—— * a1是1的个数，a2是2的个数，… * 根据贡献给序列p1(n),p2(n),…,pm(n)的幂次的特点，来确定x的幂次 * 第一类也称之为下阶乘函数，在组合数学中的地位如同幂函数xn在数学分析中的地位 * James stirling(1692.4.22~1770.12.5)苏格兰数学家，毕业于牛津大学贝列尔学院，以他名字命名的两个数学概念：stirling数和stirling近似公式 * * 1. * * * 例31 现有100台相同的微机，分配给10个实验室，每个实验室至少分6台，问有多少种分配方案？ 例32 4台机器分配到2个单位，列出其分配方案? 整数的有序拆分 * 整数的无序拆分 将n个相同的物件分配到m个相同的位置上，称为整数的无序拆分 分两种情况 无空位情况 有空位情况 * 整数的无序拆分—无空位 定义：将正整数n分成m个部分，n=n1+n2+…+nm(m≥1),ni≥1,且不考虑ni的次序，满足n1≥n2≥…≥nm ，n1为最大分项 拆分数记为Pm(n) * 整数的无序拆分—无空位 定理：正整数n拆分成m个部分的方案数等于整数n的拆分中最大分项为m (分项个数不限) 的方案数。记作：Pm(n)=Pm(n) 相当于方程 n=1x1+2x2+…+mxm , xi≥0 且xk≥1 非负整数解的组数，且最大分项小于或等于m 母函数为： * 整数的无序拆分—有空位 有空位情况 当n≥m时，方案数=P1(n)+P2(n)+…+Pm(n) 当n m时，方案数=P1(n)+P2(n)+…+Pn(n) * 整数的无序拆分—有空位 整数n拆分中，所有部分均为奇数，其母函数？ 整数n拆分中，所有部分不相等，其母函数？ * 整数的无序拆分—有空位 例33 若用1克、2克、3克和4克砝码各一枚，问能称出哪几种重量？每种重量有几种可能方案？ 例34 若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能称出哪几种重量？各有几种可能方案？ * 整数的无序拆分—有空位 定理 整数n拆分成不同整数和的拆分数等于拆分成奇数之和的拆分数 例35 求用1分、2分和3分面值的邮票贴出6分钱面值的方案数（邮票允许重复）？ 7 * 整数的无序拆分—有空位 例36 求方程x1+2x2+4x3=17非负整数解的个数？ * 集合的有序划分 n个不同物件，全部分配到m个不同的位置上（允许有空位），其分配方案数为mn n个不同物件，全部分配到m个不同的位置上（不允许有空位），其分配方案数为 * 集合的有序划分—有空位 例37 s = {a,b,c}，分配到2个不同位置上，求其方案数？ 23=8 例38 用红、绿、蓝三种颜色给1×n棋盘着色，共有多少种着色方案？ * 集合的无序划分 无空位划分 有空位划分 * 特殊计数序列 第一类stirling数定义 [x]n=x?(x-1) ?(x-2)… ?(x-n+1) =S1(n,0)+ S1(n,1)x+ S1(n,2)x2+...+ S1(n,n) xn 称S1(n,0), S1(n,1), S1(n,2),..., S1(n,n)为第一类stirling数 S1(n+1, k)=S1(n,k-1)-nS1(n,k) * 特殊计数序列 第一类斯特林数（stirling数） 组合意义：第一类Stirling数有正有負，其绝对值可以看做是将n个元素排成k个非空的圆排列的方案数 * 特殊计数序列 定理：第一类stirling数S1(n,k)有下列性质 S1(n,0) = 0 S1(n,1) = (n-1)! (-1)n-1 S1(n,n-1) = -C(n,2) S1(n,n) = 1 S1(n,k) = S1(n-1,k-1) – (n-1) S1(n-1,k) * 特殊计数序列 第二类stirling数定义 把S2(n,k) ，称为第二类stirling数 * 特殊计数序列 第二类斯特林数 组合意义：是将n个不同元素的集合划分为m个非空集合的方案数 * 特殊计数序列 例39 红、黄、蓝和白四种颜色的球,放到两个无区别的盒子里，不允许有空盒，其方案？ S2(4,2) 1 2 3 4 5 6 7 第1盒 r y b w ry rb rw 第2盒 ybw rbw ryw ryb bw yw yb * 特殊计数序列 定理：第二类stirling数S2(n,k