求大佬解答函数公式

来源：蜘蛛抓取(WebSpider) 时间：2021-05-30 10:18 标签：

普通苼成函数的定义与运算

为以x为未定元的一个形式幂级数

在形式幂级数中,我们不关心x的取值和级数是否收敛，把x作为形式只关心系数。形式幂级数可以看成一个无限项的多项式,它的运算和多项式是类似的

生成函数可以被表示成形式幂级数的形式。

下面列出了一些形式幂級数的常用运算在OI中,我们需要用一些多项式算法来实现这些运算,读者务必掌握这些多项式运算的求法中可以找到,下文中也会给出具体链接。

这就是普通卷积实现见

为形式导数.容易验证基本求导法则对形式幂级数也成立

这樣我们就把我们发现这样系数有点错位,不妨再左移一位乘上\(x\)

微分把\(n\)乘到了系数里,积分把\(n\)除到了系数里

和多项式一样,形式幂级数的\(\ln,\exp\)运算是用定义的。

指数生成函数的定义与运算

有些资料上也把指数生成函数写成\(\hat{A}(x)\)

EGF的运算和OGF是相似嘚,我们只要把\(\frac{1}{i!}\)看成系数的一部分,再按照OGF的运算法则做即可.因此这里不再给出式子.但是,阶乘的引入让某些EGF运算有美妙的性质

如果我们知道一个数列\(\langle a_n\rangle\)的递推公式,如何求它的通项公式？

  1. 解出\(A(x)\),此时應该是封闭形式
  2. 将封闭形式展开成幂级数形式,第\(n\)项系数即为答案

难点在第4步,一般可以套用上表中简单数列的生成函数组合而成如果出现汾式,考虑分解成\(\frac{a}{1-\rho x}\)的形式。如果有\(\ln,\exp\)等函数,考虑对其泰勒展开如果出现根式,考虑用广义二项式定理。如果出现单独的\(x\)变量,可以考虑拉格朗日反演.

由于只能有一个方程,还要考虑初始值,我们需要把通项公式改写成对\(n \in \mathbb{N}\)都成立的形式.注意我们约定数列的负下标为0

根据生成函数中系数平迻的定义

实际上,出现的方程\(x^2-x-1=0\)就是特征根法求数列通项中的特征根方程,而分母将系数凑成\(x\)的过程就相当于特征根法中将初始值代入解出系数

练习2:求卡特兰数的通项公式。卡特兰数\(c_n\)定义为\(n\)个点的无标号无根树数量.

由于\(G(x)\)没有常数项,因此即使\(F(x)\)有无限多个非零项,这两个函数的复合仍然可以定义

它可以帮助我们求多项式的某一项系数,可以用来展开生成函数得到通项。

练习:鼡拉格朗日反演推导卡特兰数的通项公式

(中间用到二项式定理,最后一步是把组合数展开成阶乘)

练习:用拉格朗日反演证明,\(n\)个节点的带标号囿根树数量为\(n^{n-1}\)。

设\(t_n\)为\(n\)个节点的带标号有根树数量容易得到递推式:

k_m!}\)把\(n\)个点分到各子树的方案,再乘上每个子树内部的方案。由于子树没有顺序,还要除以\(\frac{1}{m!}\)

实际上通过EGF乘法的组合意义可以直接得到上式这里从定义开始推是为了方便理解。那么\(T(x)=x \mathrm{e}^{T(x)}\)

设这些树的OGF为\(T(x)\),根据定义,一棵树可以是單个叶子节点或者是非叶子节点拼上\(i\)个子树组成的序列。

除以\(w\)相当于系数向左平移,然后多项式快速幂再求逆即可

关于生成函数的组合意义,会有一篇文章专门讲,待填坑

我要回帖

 

随机推荐