组合数学 母函数与递推关系

组合数学课件资料

组合数学

第二章

母函数与递推关系

组合数学课件资料

§2.1

母函数

递推关系是计数的一个强有力的工具， 特别是在做算法分析时是必需的。递推关 系的求解主要是利用母函数。当然母函数 尚有其他用处，但这主要是介绍解递推关 系上的应用。例如(1 a1 x)(1 a 2 x) (1 anx) 1 (a1 a 2 an) x (a1a 2 a1a 3 an 1an) x 2 a1a 2 anx n (2 - 1 - 1)

组合数学课件资料

§2.1 母函数

x 项的系数 a1a2 a1a3 an 1an 中所有的项包括n个元素a1,a2, …an中2

取两个组合的全体；同理项系数包含了从 n个元素a1,a2,… an中取3个元素组合的 全体。以此类推。

组合数学课件资料

§2.1 母函数 若令a1=a2= …=an=1,在(2-1-1)式 2 中 x 项系数：a1a 2 a1a3 an 1an 中 每一个组合有1个贡献，其他各项以此类推。 故有：(1 x) n 1 C (n,1) x C (n,2) x 2 C (n, n) x n (2 - 1 - 2)

组合数学课件资料

§2.1 母函数

另一方面：

(1 x) m (1 x) n (1 x) m n [C (n,0) C (n,1) x C (n, n) x n ] [C (m,0) C (m,1) x 1 C (m, m) x m ] x [C (m n,0) C (m n,1) x C (m n, m n) xm n m

组合数学课件资料

§2.1 母函数 比较等号两端项对应系数，可得一等式

C (m n, r ) C (m,0)C (n, r ) C (m,1)C (n, r 1) C (m, r )C (n,0)

组合数学课件资料

§2.1 母函数 同样对于 1 x) n (1 1 / x) m , ( n m (设 ),用类似的方法可得等式：C (m n, m) C (n,0)C (m,0) C (n,0)C (m,0) C (n,0)C (m,0) 正法如下： (2 - 1 - 3)m n

(1 x) (1 1 / x) x (1 x)n m

m

组合数学课件资料

§2.1 母函数 [C (n,0) C (n,1) x C (n, n) x ]n

[C (m,0) C (m,1) x C (m, m) x ] x [C (m n,0) C (m n,1) x C (m n,2) x C (m n, m n) xm n m 2

1

m

比较等式两端的常数项，即得公式(2-1-3)

组合数学课件资料

§2.1 母函数 又如等式： (1 x) C (n,0) C (n,1) x C (n,2) x 2

C (n, n) x n令x=1 可得

C (n,0) C (n,1) C (n,2) C (n, n) 2 (2 - 1 - 4)n

组合数学课件资料

§2.1 母函数 (2-1-2)式等号的两端对x求导可得：C (n,1) 2C (n,2) 3C (n,3) nC (n, n) n2n 1 (2 - 1 - 5)

等式(2-1-5)两端令x=1,得：C (n,1) 2C (n,2) 3C (n,3) nC (n, n) n2n 1 (2 - 1 - 5)

组合数学课件资料

§2.1 母函数 用类似的方法还可以得到：

C (n,1) x 2C (n,2) x 2 3C (n,3) x 3 nC (n, n) x nx(1 x)n2 2

n 1

C (n,1) 2 C (n,2) 3 C (n,3) n C (n, n)2

n(n 1)2n 2

(2 - 1 - 7)

组合数学课件资料

§2.1 母函数 还可以类似地推出一些等式，但通过上 n 面一些例子已可见函数 (1 x) 在研究序列 C (n,0), C  , n) 

(n,1), , C (n   的关系时所起的作用。对其他序列也有同样 的结果。现引进母函数概念如下：

定义：对于序列 a0 , a1 , a2 , , 构造一 函数： 2

G( x) a0 a1 x a2 x , 称函数G(x)是序列a0 , a1 , a2 , 的母函数

组合数学课件资料

§2.1 母函数 例如 是序列 n ( , C (n, n) C ( ,0), C n,1),     的母函数。 如若已知序列 a0 , a1 , a2 , , 则对应的母函 数G(x)便可根据定义给出。反之，如若以求得 序列的母函数G(x),则该序列也随之确定。 序列 a0 , a1 , a2 , , 可记为 {an }。

(1 x) n

组合数学课件资料

§2.2

递推关系

利用递推关系进行计数这个方法在算法 分析中经常用到，举例说明如下： 例一.Hanoi问题：这是个组合数学中的 著名问题。N个圆盘依其半径大小，从下而 上套在A柱上，如下图示。每次只允许取一 个移到柱B或C上，而且不允许大盘放在小 盘上方。若要求把柱A上的n个盘移到C柱上 请设计一种方法来，并估计要移动几个盘 次。现在只有A、B、C三根柱子可用。

组合数学课件资料

§2.2 递推关系

Hanoi问题是个典型的问题，第一步要设 计算法，进而估计它的复杂性，集估计工作量。 算法： N=2时 第二步把下面的一个圆盘移到C上                   第一步先把最上面的一个圆盘套在B上  最后把B上的圆盘移到C上 到此转移完毕

A

B

C

组合数学课件资料

§2.2 递推关系 假定n-1个盘子的转移算法已经确定。 对于一般n个圆盘的问题， 先把上面的n-1个圆盘经过C转移到B。 第二步把A下面一个圆盘移到C上 最后再把B上的n-1个圆盘经过A转移到C上

A

B

C