展开全部 +
首页 . 理学 . 数学 . 组合数学 . 计数组合学 . 生成函数

生成函数

/generating function/
条目作者谷珊珊

谷珊珊

最后更新 2022-01-20
浏览 266
最后更新 2022-01-20
浏览 266
0 意见反馈 条目引用

组合数学尤其是计数组合学方面的一个重要理论和工具,又称母函数。

英文名称
generating function
所属学科
数学
又称
母函数

通常用于研究未知(通项)数列规律,用这种方法在给出递推式的情况下求出数列的通项。使用生成函数解决问题的方法称为生成函数法。生成函数法是推导斐波那契数列的通项公式方法之一,另外组合数学中的卡塔兰数也可以通过这种方法得到。

瑞士数学家J.伯努利在考虑“当投掷粒骰子时,加起来点数总和等于的可能方式的数目”这个问题时首先使用了生成函数法,并得出可能的数目是的展开式中项的系数。L.欧拉在研究自然数的分解时也使用了该方法,并奠定了生成函数法的基础。1812年P.S.拉普拉斯在其出版的《概率的分析理论》中明确提出生成函数的概念,对生成函数思想做了延伸与发展,生成函数的理论由此基本建立。

通俗地讲,生成函数是用来表示计数函数的对象,一般表示为形式幂级数。形式幂级数是指形如(式中为复系数)的幂级数,只是不考虑级数收敛与发散的问题。

常见的生成函数包括一般生成函数

指数生成函数


此外还有狄里克雷生成函数、贝尔生成函数、兰伯特生成函数等,其中一般生成函数使用较多。

生成函数的基本思想是把离散数列同形式幂级数对应起来,把数列间的关系转化为形式幂级数之间的运算关系。它成为连接离散数学与连续数学的桥梁。若的生成函数有较好的形式,则从可得到的递推关系,甚至的显示表达式;还可以利用渐近分析得到对的估计。

  • STANLEY R P.Enumerative Combinatorics: Vol. I.Cambridge:Cambridge University Press,1997.
  • WILF H S.Generatingfunctionology. 3rd ed.Wellesley,MA:A K Peters, Ltd.,2006.

相关条目

阅读历史

    意见反馈

    提 交

    感谢您的反馈

    我们会尽快处理您的反馈!
    您可以进入个人中心的反馈栏目查看反馈详情。
    谢谢!