卢开澄组合数学--组合数学第二章.pptx

文档介绍：§ 母函数
递推关系是计数的一个强有力的工具,特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处,但这主要是介绍解递推关系上的应用。例如
库文档分享
§ 母函数
项的系数中所有的项包括n个元素a1,a2, …an中取两个组合的全体;同理项系数包含了从n个元素a1,a2,… an中取3个元素组合的全体。以此类推。
库文档分享
§ 母函数
若令a1=a2= …=an=1,在(2-1-1)式中项系数: 中每一个组合有1个贡献,其他各项以此类推。故有:
库文档分享
§ 母函数
另一方面:
库文档分享
§ 母函数
比较等号两端项对应系数,可得一等式
库文档分享
§ 母函数
同样对于,(设),用类似的方法可得等式:
正法如下:
库文档分享
§ 母函数
比较等式两端的常数项,即得公式(2-1-3)
库文档分享
§ 母函数
又如等式:
令x=1 可得
库文档分享
§ 母函数
(2-1-2)式等号的两端对x求导可得:
等式(2-1-5)两端令x=1,得:
库文档分享
§ 母函数
用类似的方法还可以得到:
库文档分享