[理学]组合数学ch05-2.ppt

问题2 3. 给顶节点组成二叉树的问题。 　　给定N个节点，能构成多少种形状不同的二叉树？ 利用牛顿二项式定理，有 因为 ，开方应该取负号，故舍去 显然一个凸n+1边形中有 种不同的剖分方法。 * * 三、 Catalan数列的应用 1.括号化问题。 矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种) 2.出栈次序问题。 　　一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列? §5.4.2 Stirling数列的生成函数 在3.5节中介绍过第一类和第二类Stirling数。本节中我们首先从另外一个角度介绍第一类Stirling数和它的性质，最后给出第二类Stirling数的生成函数。 设有多项式 ，它的展开式具有下面的形式： □ - □ + □ - …， 不考虑各项系数的符号，则 的系数就是第一类Stirling数 ，上面的式子变成： 我们称 这些数为第一类Stirling数。 根据3.5节有，第一类Stirling数具有下面的性质，我们给出不同的证明方法。 * 证明 为 项的系数，即多项式中的常数项，显然为0。 是x项的系数， 各因式在相乘时分别贡献负数 -1，-2 ，…，-(n-1) ，从而得到 x项。不考虑这些数的符号，它们之积是 (n-1)! 所以 是 项的系数，显然为1。 是 项的系数，为了得到 ，n个因式中只能有一个因式贡献常数，由加法原理得出提供常数的总和为 所以 。 * 2. 第一类Stirling数满足下面的递推关系。 证明 考虑多项式 上式两边同乘以 得 即 比较上式两边 的系数得 * 定理5.4.1 序列 的生成函数为 并有 证明： 对递归关系 两端同乘以 ，并对n求和，得 即： 令 则有 * 故： 从而 等式右端展开后，各 项的一般形式为 * 其中， ，且 。合并同类项后的 的系数为 其中， 是满足 非负整数解，因此 * 作为验证，我们计算 ，其中n=4，k=2，n-k=2， n1+n2=2的所有非负整数解为（0，2），（1，1），（2，0），因此 根据第3章的知识，结果显然是正确的。 * 计算机科学与技术学院 * 第五章 生成函数 5.1 生成函数的定义和性质 5.2 组合数的生成函数 5.3 指数型生成函数与多重集的排列数 5.4 Catalan数列与Stirling数列的生成函数 5.5 分拆数的生成函数 吉林大学 §5.2 组合数的生成函数 * 问题3 确定多重集S={3·a,4·b,5·c}的10-组合数。 问题1 求 的k组合数 定理 5.2.1 设多重集 ，则M的k-组合数 ck 对应序列{ck}的生成函数为 其中， ck 为 展开式中 的系数。 * 证明: 令 中各 的项分别对应各个元素的 可能取法。例如 ，对 时x2表示元素a2 选取了 2次，其中依次类推。 展开式中的项 xk 具有一般形式 其中