母函数的简单应用

论文总字数：5520字

摘 要

关键词：母函数，组合计数，递推关系，整数拆分

Abstract： Generating function and generating function, it is based on power series and polynomial theory basis. In this paper, the generating function of the basic definitions and properties and the in combinatorial enumeration, recursive relationship, the application of integer resolution, etc. do the related presentations.

Keywords：generating function, combinatorial counting,recurrence relation, integer resolution

目 录

1 前言 4

2 母函数的定义 4

3母函数的性质 5

4母函数的简单应用 6

4.1利用母函数证明组合恒等式 6

4.1.1一些常见序列的母函数 6

4.1.2利用母函数法证明组合恒等式的举例 6

4.2 母函数在递推关系上的应用 7

4.3 利用母函数进行整数的拆分 8

4.4 母函数在概率论上的应用 10

结 论 12

参考文献 13

1 前言

母函数又称生成函数、发生函数，其思想的萌芽可以追溯到18世纪Jacob B.的《猜度术》一书. 随着Euler L.关于自然数的分拆的研究逐步地确立了母函数的理论体系. 1812年，法国数学家Laplace P.S.在其著作《概率的分析理论》的开始部分就着力于研究母函数计算的数学方法及其相关的数学理论，这使得母函数理论得到进一步发展和完善.

母函数分为普通型和指数型两种类型, 在当代数学理论中有着诸多应用. 它是解决组合学中计数问题的重要工具， 是解决递推数列通项问题的方法之一，同时也在程序编程、概率计算方面有着重要应用. 我们可以根据母函数的简单性质来研究未知数列的通项，进而推导数列的通项. 例如组合数学中的Fibonacci、Catalan数就可以通过母函数的方法得到. 由此我们可以看出母函数在我们的数学实践中有种广泛应用以及实际意义,合理地运用母函数及其思想，可以将数学上的很多难题有效的解决. 那么下面我们将从母函数的定义、性质与其具体应用三个方面进行论述.

2 母函数的定义

定义1^[1] 对于任意的数列，构造成一幂级形式函数，则称是数列的母函数，又称生成函数.

定义2 对于数列，称函数 为数列

的普通型母函数（简称普母函数）．

定义3 对于数列，称函数

为数列的指数型母函数（简称指母函数）．

定义4 设与是上的两个母函数. 若对任意，有. 则称与相等.记作.

定义5 设为任意实数. ,则称作与的数乘积.

定义6 设与是上的两个母函数.

（1）将与相加定义为，并称为与的和，把运算“ ”称作加法.

（2）将与相乘定义为，并称为与的积，把运算“”称作乘法.

我们在对母函数的定义有了一定了解后，下面将对母函数其具有的一些性质做简单介绍.

3母函数的性质

由于母函数与数列之间存在一一对应的关系，所以通常的，我们在研究母函数的相关性质的时候将其转化为研究两个数列之间的关系. 这样，母函数的相关性质更容易表述.

我们假定，序列{}，{}的母函数分别为

那么它们满足以下性质：

(1) 若 ，则

(2) 若 ，则

(3) 若，则

(4) 若 ，则

(5) 若 ，则 ）

(6) 若 ，则 =

(7) 若 ，则 =，其中是收敛的

(8) 若 ，则

(9) 若 ，则

(10) 若 ，则 =

根据我们上述介绍的母函数的相关性质，我们容易发现母函数与其序列直接的一些联系. 对其性质的了解的基础之上，我们紧接着给出母函数在数学计算中的一些应用，这些应用对于我们解决生活中的很多问题都有帮助.

4母函数的简单应用

4.1利用母函数证明组合恒等式

在组合数学中，运用组合的定义以及对某些多重集的排列的观察，可以直接证明出一些简单的恒等式. 但是对于一些复杂的组合恒等式，我们就很难通过观察得出结论. 这时采用母函数的方法是我们发现与证明组合恒等式的一种有效途径. 母函数法的实质是从已知序列的母函数出发，通过母函数的运算得出新的结果，从而达到发现和证明复杂的组合恒等式.

4.1.1一些常见序列的母函数

（1）

（2）

（3）

（4）

（5）

（6）

（7）

4.1.2用母函数法解决组合恒等式证明问题的举例

例1 若p,q,n是任意的非负整数,证明

证明 由于

（1）

另一方面

（2）

比较（1）与（2）右端的系数得

.

4.2 母函数在递推关系上的应用

递推关系是数学计算的一个重要工具，但其求解一般比较困难. 这时采用母函数法能很好解决这个问题.

定义7^[4] 序列{}相邻的项间有如下关系：

，，

我们称为序列{}的常系数线性齐次递推关系.

剩余内容已隐藏，请支付后下载全文，论文总字数：5520字