组合数学Csequences.pptxVIP

1 1 第二章 母函数与递推关系 组合数学 马昱春 MA Yuchun myc@mail.tsinghua.edu.cn Project I 全排列生成算法的研究和实现 10分，必作 C/C++ or Java 11月27日前网络学堂提交 目标 Research and Novelty（每组1-3人） 在实现和研究4种全排列生成算法基础上进行创新 算法效率和复杂度分析或理论证明 新的算法, 有关排列生成的任何相关内容的创新点 Paper (80%)： 3-6页 代码以及可执行文件 (20%) 3 母函数 定义2-1 对于序列a0, a1, a2…, 构造一函数 G(x)= a0+a1x+a2x2+…, 称G(x)为序列a0, a1, a2…的母函数。 a0 a1 a2 a3 a4 a5 x0 x1 x2 x3 x4 x5 母函数就是一列用来展示一串数字序列的挂衣架。 — 赫伯特·维尔夫 4 §2.8 母函数和递推关系应用举例 例：求图2-8-6所示的n级网络的等效电阻 。 所谓等效电路，相当于图2-8-6中虚线所包围的块用一电阻 取代，使在两端点 和 之间的效果一样。 4 5 §2.8 母函数和递推关系应用举例 Rn可以作为由Rn-1等效电阻如图2-8-7所示的方式串并联构成的. 递推关系 5 6 令 因此 令 6 7 将 代入 得到 特征方程是 7 8 §2.8 母函数和递推关系应用举例 解方程组 8 9 §2.8 母函数和递推关系应用举例 例：设有地址从1到n的单元，用以纪录一组信息。这个信息的每个元素都占用两个单元，而且存放的地址是完全随机的，因而可能出现两个存放信息单元之间留下一个空单元无法存放其他信息，求这n个单元留下空单元的平均数。 设这个平均数为 。 存储单元如上图，设某一信息占用了第i+1，i+2两个单元，把这组单元分割成两个部分，一是从1到i，另一从i+3到n。 9 10 （2-8-13）式是变系数递推关系，可改为 10 由于用相邻两个单元的几率相等， 11 设 11 12 12 13 §2.8 母函数和递推关系应用举例 例6：设有n条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这样的n条曲线把平面分割成几个部分？ 设满足条件的n条封闭 曲线所分割成的域的数目为 ，其中 条封闭曲线 所分割成的域的数目为 14 §2.8 母函数和递推关系应用举例 第n条封闭曲线和这些曲线相交于 个点，这 个点把第n条封闭曲线截成 条弧，每条弧把 个域中的每个域一分为二。故新增加的域数为 15 利用递推关系 得 对应的特征方程为 三重根 计算机界的精灵 一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列? 1，2，3, 4 1 2 3 4 17 计算机界的精灵 一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列? 第一次为空时进行分步？ 1 2 3 4 第一次为空时有k个元素出栈，即1出栈的序号; 将1~n的序列分成两个序列，其中一个是1~k-1共k-1个元素 另外一个是k+1~n，共n-k个元素 设f(n)是n个元素的出栈序列数 f(n)= f(k-1)* f(n-k) k =1~n f(n) = f(0)*f(n-1) + f(1)*f(n-2) + .......+ f(n-2)*f(1) + f(n-1)*f(0) 分两块的策略？ 二叉树 n个节点构成的二叉树，共有多少种情形？ 根肯定会占用一个结点，设T(i, j)表示根的左子树含i个结点，右子树含j个结点 除了根之外剩余的n-1个结点可以有如下的分配方式，T(0, n-1),T(1, n-2),...T(n-1, 0)，。 设问题的解为f(n)， 假设f(0) = 1，那么f(1) = 1, f(2) = 2, f(3) = 5。 f(n) = f(0)*f(n-1) + f(1)*f(n-2) + .......+ f(n-2)*f(1) + f(n-1)*f(0) Catalan数 1751年欧拉在与哥德巴赫的通信中提出一个问题： 正n边形化分为不重叠的三角形有多少种方法？ C(n) = C(0)*C(n-1) + C(1)*C(n-2) + .......