生成函数简介(上)

xiaoee posted @ 2009年3月28日 12:29 in Mathematics with tags 生成函数 函数 数列 递推 特征函数 证明 排列 组合 级数 特征值 , 8056 阅读

在提出「生成函数」的数学定义之前,我们先考虑几个简单的排列组合问题。(不知道怎么回事,发表这篇文章首页显示会有问题,搞了好久没找到问题,于是清空重新输入了一遍,并把所有公式都去掉了,用文本代替,首页显示终于没问题了,可能公式就得你费力看了)。

考虑恒等式:(1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ac)x^2+abcx^3

如将a,b,c 看作代表三个对象,它的右边是一多项式,其系数恰代表了将 a,b,c 作组合的各种可能。常数项1表示在三对象中一个都不取;x 的系数a+b+c 表示在a,b,c 中取一个的各种组合,即或取a,或取b,或取 cx^2 的系数ab+bc+ac 表取二个的各种组合;x^3之系数表示了三个皆取的唯一方法。在这里可能产生各种情形是用+号连接,同时发生之事件则用乘法(即符号并列)表示。 

又设有5个球 a,a,a,b,c,其中三个球a 完全一样,则恒等式: 

 (1+ax+a^2x^2+a^3x^3)(1+bx)(1+cx)= 1+(a+b+c) x+(a^2+a b+a c+b c) x^2+(a^3+a^2 b+a^2c+

a b c) x^3+(a^3 b+a^3 c+a^2 b c) x^4+a^3 b c x^5

其中 x^r的系数表示了选取r个的各种可能组合(1<=r<=5 ) 

在排列组合问题中,加法原则与乘法原则是大家熟知的两个法则。加法原则是讲如一事件可能发生情况有 m 种,另一种事件可能发生情况有 n 种,则这两种事件其一发生情况有m+n 种。乘法原则是讲如一事件可能发生情况有m种,另一事件可能发生情况有n种,则这两事件同时发生情况有mn种。我们在上面两例用到的是一种符号运算,它遵从这两法则。在第二个例子中,因子(1+ax+a^2x^2+a^3x^3)表示了或不取a,或取一个a,或取2a,或取三个a 的各种情况;而在第一个例子中,(1+ax)(1+bx)表示了如果 a , b 被允许同时选取时可能产生之各种情况。

在很多场合中,我们只对事件发生可能之个数有兴趣,而不在乎事件发生的具体形式。这时我们可以取代表不同对象的符号a,b,c 等均为1,例如在第一个例子中,令 a=b=c=1,则  (1+x)(1+x)(1+x)=1+3x+3x^2+x^3

其中x^r的系数为在三个对象中取r个的组合数。

我们看到上面由组合原理得出的恒等式有这样的形式g(x)=a0+a1x+a2x^2+a3x^3+…,

我们就把g(x)叫做系数数列{a0,a1,a2,a3,…}的生成函数(准确的说是组合生成函数)。

我们熟悉的二项式定理:(1+x)^n=C(n,0)+C(n,1)x+C(n,2)x^2+…+C(n,r)x^r+…+C(n,n)x^n

其中x^r的系数正好是在n个中取r个的组合数。也就是说(1+x)^n是:{C(n,0),C(n,1),C(n,2),C(n,3),….}的生成函数。我们看到要从n个对象中取r个的组合数问题与其生成函数(1+x)^n的系数有一种对应关系存在。

我们上面定义的生成函数,在数学上又称作形式幂级数(formal power series),也就是它只是形式上的考虑,而不考虑实际上的数值,而其中幂级数则是无穷项的多项式。形式幂级数是一种只讨论形式上而不考虑收敛性的幂级数,只需要它所构成的运算是可以定义的即可

我们先看几个简单数列的生成函数。{1,1,1…}的生成函数是1+x+x^2+x^3+x^4+…..=1/(1-x),由于只是从形式上考虑,我们总当生成函数是收敛的。可以看到虽然这个数列是无穷多项,但它的生成函数却可以是很简单的。也就是因为这样,有时候研究生成函数比直接研究数列本身方便,通过生成函数也可以揭示数列的某些性质。

从组合生成函数的提出过程可以看出,我们有时并不需要提前知道完整的系数数列就可能得出它的生成函数,反倒是可以利用生成函数求出系数数列。

例如:设有n个物件,并设 n(r) 是由n个不同对象中可任意重复地取r个对象的组合数。这个组合问题的生成函数即是x^r的系数等n(r)的生成函数。对一个对象来说,我们可以不选取,选取一次,选取二次等等,其方法可用式子表示为:1+x+x^2+x^3+x^4+…=1/(1-x)。对第二个,第三个,一直到第n个都是这样的,根据组合原理可得其生成函数为(1+x+x^2+x^3+x^4+…)^n=1/(1-x)^n,经过进一步的推理可得:

1/(1-x)^n =1+C(n,1)x^1+C(n+1,2)x^2+C(n+2,3)x^3+...+C(n+r-1,r)x^r+...。上面的式子也可以通过对1/(1-x)的展开式两边不断求导得到。也就是说n(r)= C(n+r-1,r)

   我们再来看一个更具体点的例子(听说这是《组合数学》上很经典的一个例题,很多书上都会有这类题。)

   我们要从苹果、香蕉、橘子和梨中拿一些水果出来,要求苹果只能拿偶数个,香蕉的个数要是5的倍数,橘子最多拿4个,梨要么不拿,要么只能拿一个。问按这样的要求拿n个水果的方案数。(其实这个例子很像开始的第二个例子)。

   根据组合原理,我们可以很容易知道这个问题的生成函数就是:

g(x)=(1+x^2+x^4+...)(1+x^5+x^10+..)(1+x+x^2+x^3+x^4)(1+x)

        =[1/(1-x^2)]*[1/(1-x^5)]*[(1-x^5)/(1-x)]*(1+x) (前两个分别是公比为x^2x^5的几何级数,后两个相乘就是1-x^5

        =1/(1-x)^2   (约分,把一大半都约掉了)

        =(1-x)^(-2)=C(1,0)+C(2,1)x+C(3,2)x^2+C(4,3)x^3...   (参见对1/(1-x)^n的展开)

        =1+2x+3x^2+4x^3+5x^4+....

于是哪n个水果的方案数就是n+1。其实这只是换了个运用组合原理的形式。

最后我们讨论生成函数与递推数列的关系。也许你用过特征方程的方法来求解过递推数列,这个方程式为何会有这么神奇的性质呢?它又是怎么得来的呢?

我们下面只分析从一般的二阶(常系数线性齐次)递归数列:

An+pAn-1+qAn-2=0,q!=0  特征多项式:K(x)=x^2+px+q

则如我们所说的,令数列的生成函数

g(x)=a0+a1x+a2x^2+a3x^3+… 

则我们会有下面这个好用的算式:

g(x)=A0+A1x+A2x^2+A3x^3+A4x^4… 

  px*g(x)=pA0x+pA1x^2+pA2x^3+pA3x^4…

 qx^2*g(x)=qA0x^2+qA1x^3+qA2x^4+…

相加得到(1+px+qx^2)g(x)=A0+(A1+pA0)x+(A2+pA1+qA2)x^2+(A3+pA2+qA1)x^3….

由递推关系可得(1+px+px^2)g(x)=A0+(A1+pA0)x

所以g(x)=( A0+(A1+pA0)x)/( 1+px+px^2)

      令分母为D(x)=1+px+qx^2

      如果r1r2K(x)的两根的话,那么D(x)=(1-r1x)(1-r2x)

      当r1!=r2时,g(x)=A/(1-r1x)+B/(1-r2x),其中A,B是两个常数。

      回忆公式1/(1-x)=1+x+x^2+x^3+…于是

     g(x)=A(1+r1x+(r1x)^2+(r1x)^3+…)+ A(1+r2x+(r2x)^2+(r2x)^3+…)=AΣ(r1*x)^n+BΣ(r2*x)^n

     所以有g(x)=ΣAn*x^n=Σ(A*r1^n+B*r2^n)x^n,

     对比系数可得:An=A*r1^n+B*r2^n; 其中r1,r2为特征多项式的两根。

     如果r1=r2=r,则g(x)=A/(1-rx)+B/(1-rx)^2,

     通过展开可得:g(x)=ΣAn*x^n=AΣ(r*x)^n+BΣ(n+1)(r*x)^n;

     同样比较系数可得:An=(A+B(k-1))r^n

                                   =(C+Bk)r^n;

 

     以上我们利用组合生成函数成功的解决了一类组合问题,推导了二阶递推数列问题特征多项式。

Avatar_small
views63 说:
2012年5月14日 13:17

呃,这边的文章排版看起来有些累。公式可以考虑用 Mathjax,效果不错。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter