3.1母函数及基本组合计数问题2014.pdf

组 合 论 第三章 母 函 数 (Generating Function) 1 概 述 母函数起源 母函数也叫生成函数, 诞生于18世纪。 1730年, de Moivre 用母函数方法讨论了 Fibonacci 数； 十年后, Euler 用母函数方法研究了正整 数的分拆； 但直到1812年, 在Laplace 的经典名著 《概率的解析理论》中母函数才得到充 分的应用, 系统的发展。 2 1 概 述 母函数方法的基本思想是将要研究的离 散数列转化成一个幂级数, 然后用幂级数 的代数运算或分析运算得出数列的有关性 质，从而达到研究数列的目的. 给定一数列{a :k≥0}= a , a , a , …, k 0 1 2 2 … k 称幂级数g (x)= a +a x+a x + =∑ a x 0 1 2 k≥0 k 为数列{a :k≥0} 的母函数(普通型母函数)或 k 生成函数. 3 概 述 母函数是组合论中求解计数问题的重要工具 求有限制条件的组合个数 求有限制条件的排列个数 研究分拆数 研究某些特殊数的性质 解递推关系 证明某些组合恒等式 广泛应用于数论、概率论、密码学等领域 4 2 概 述 知识点： 形式幂级数 两类母函数 内容及掌握程度 理解母函数概念 熟练掌握母函数性质 熟练掌握两类母函数的应用 5 组 合 论 第三章 母 函 数 §3.1母函数与基本组合计数问题 6 3 本讲内容 一、母函数与不定方程的解 二、母函数与基本组合计数 7 一、母函数与不定方程的解 例1：给定正整数n，二项式系数的数列  n  n n        :k 0 ,, ,0,0,       k 0 n    