浅论生成函数在组合数学中的应用
2017-08-17魏建刚
文理导航 2017年23期
魏建刚
【摘 要】发生函数是组合数学中许多问题的首要解决方法,他可以将很多数学问题转化为生成函数问题,从而简单明了提供解题思路与方法,使得复杂困难的问题迎刃而解。本文主要研究生成函数在组合计数、整数拆分、递推问题和恒等式证明等问题中的应用,从而体现生成函数在组合数学中的作用。
【关键词】组合函数;数学;应用
引言
所谓生成函数也就是母函数,又被称为发生函数,它是链接离散函数和连续函数的结合点,是组合数学中许多问题的首要解决方法。可以将很多数学问题转化为生成函数问题,从而简单明了的为数学中的许多问题提供解题思路与方法,使得复杂困难的问题迎刃而解。
1.生成函数在组合计数中的应用
生成函数作为在组合计数学习中极其重要的一个工具,在处理某些相关问题时运用生成函数,往往会使问题简单明了。
例1.现有1分2分5分邮票,邮票可重复使用,则能贴出那些面值的邮票?每种面值有多少种贴法?
解:a 把表示为用1分2分5分邮票贴出面值为n的有票的不同贴法,则我们可以得到一个数列{a }的生成函数f(x)=∑n≥0anxn=(1+x+x2+x3+…)(1+x2+x4+…)(1+x5
+x10+…)
=1+x+2x2+2x3+3x4+4x5+…
根据生成函数展开式可知
x表示贴出面值为1分的方案有1种:1分
2x 表示贴出面值为2分的方案有2种:1分+1分,2分
2x 表示贴出面值为3分的方案有2种:1分+1分+1分,2分+1分
3x 表示贴出面值为4分的方案有3种:1分+1分+1分+1分,2分+1分+1分,2分+2分
……
由生成函数就可以看出,可以贴出那些面值的邮票,贴出n面值的邮票有多少种贴法。
登录APP查看全文
