普通生成函数

[sshwy]

https://oi-wiki.org/math/gen-func/ogf/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[Ame-sora]

斐波那契数列封闭形式那里应该是
$$\frac{1}{1-x-x^2}$$吧

[STPGUY]

封闭形式是对的吧，倒是展开方式一的分子应该是x？

[sshwy]

@BruceW-07
请问「斐波那契数列的生成函数 ---- 展开方式二」 中 「根据等比数列的展开式」 具体是指什么？

https://oi-wiki.org/math/gen-func/ogf/#_2

[BruceW-07]

@sshwy

@BruceW-07
请问「斐波那契数列的生成函数 ---- 展开方式二」 中 「根据等比数列的展开式」 具体是指什么？

https://oi-wiki.org/math/gen-func/ogf/#_2

Thx

[BruceW-07]

再问一下。「斐波那契数列的生成函数 ---- 展开方式二」中 「我们往往先求出 $Q(x)$ 的根，把分母表示为 $\prod (1 - p_i x)^{d_i}$ 的形式，然后再求分子。」 是什么意思？不是很理解。

[Ame-sora]

@BruceW-07
再问一下。「斐波那契数列的生成函数 ---- 展开方式二」中 「我们往往先求出 $Q(x)$ 的根，把分母表示为 $\prod (1 - p_i x)^{d_i}$ 的形式，然后再求分子。」 是什么意思？不是很理解。

就是和上面那个例子一样解个方程代入啊（

[Ame-sora]

@BruceW-07
再问一下。「斐波那契数列的生成函数 ---- 展开方式二」中 「我们往往先求出 $Q(x)$ 的根，把分母表示为 $\prod (1 - p_i x)^{d_i}$ 的形式，然后再求分子。」 是什么意思？不是很理解。

因为通分之后等式两边分子分母对应所以先求下面的然后代入分子然后再求

[BruceW-07]

@Ame-sora

@BruceW-07
再问一下。「斐波那契数列的生成函数 ---- 展开方式二」中 「我们往往先求出 $Q(x)$ 的根，把分母表示为 $\prod (1 - p_i x)^{d_i}$ 的形式，然后再求分子。」 是什么意思？不是很理解。

因为通分之后等式两边分子分母对应所以先求下面的然后代入分子然后再求

哦哦哦，懂了，谢啦

[YOYO-UIAT]

从斐波那契数列到卡特兰数的 gap 有亿点点大吧……对我这种初中生非常不友好

[TURLEing]

@alanjimmy
封闭形式是对的吧，倒是展开方式一的分子应该是x？

如果是这样的话那展开方式一不就有误了吗？

[letitdown]

斐波那契展开方式一那里少乘了一个x导致每一位都往前平移了一位吧。。。

[Taystered]

斐波那契展开方式一那里，$n$ 是大于 $0$ 的吧

[Zzzcr0]

小练习第三个也可以构造一个G(x) = 1 + x + x^2 + ...

[Zzzcr0]

手滑发出来了，F(x) - G(x) = xF(x)，然后把G(x)封闭算一下就行了