浅谈生成函数(1) | 生成函数引入

シャンと背筋を伸ばして 凛と目線を上げて

挺直腰板 抬起凛然的目光

今日も青空高く 果てしない

今天天空依旧湛蓝 广阔无际

这个系列的内容只是我在文化课之余的一些写作而已，写这些只是为了在无趣的文化课中保持自己的热情。

也有一些原因是至今没有见到一个非常好的生成函数教程，于是想自己写一个。我有很多想法，然而写作总比想难得多，所以这篇文章也未必是一个好的教程。

不会涉及到一些比较困难的内容，毕竟我自己也不会。而且这个只是科普性质的浅谈，如果有读者读过我的文章能够对计数组合学这门优雅的学科产生兴趣，那这篇文章就算成功了。

不过我本身文化课和文化课之外的压力就已经相当大，所以这个系列也只能每周勉强抽出一点时间更新。深入地再谈生成函数也许只能等到我高中毕业之后才能更新了。

在本系列文章中，我们会略过大部分工具的证明细节，但会尽量给出一些有证明的参考文章链接

准备工作

记号

1. 下降幂，即 $\displaystyle a^{\underline{b}}=\prod_{i=0}^{b-1}(a-i)$。其中 $a\in \mathbb R, b\in \mathbb Z$，注意 $b$ 可以取负数，其意义在下一条中陈述。

2. 上升幂，即 $\displaystyle a^{\overline{b}}=\prod_{i=0}^{b-1}(a+i)$。限制同上，有 $a^{\underline{-b}}=a^{\overline{b}}$。

3. 双阶乘，即 $\displaystyle a!!=\prod_{1\le i\le a,i\equiv a\pmod 2}i$，也就是所有 $\le a$ 的与 $a$ 奇偶性相同的数的乘积。

4. 对于一个一元多项式 $F(x)$，令 $[x^n]F$ 表示其 $x^n$ 项的系数

   对于多元多项式 $F(x_1,x_2,\cdots, x_n)$，令 $[x_1^{a_1}x_2^{a_2}\cdots x_n^{a_n}]F$ 表示其 $x_1^{a_1}x_2^{a_2}\cdots x_n^{a_n}$ 项的系数。

前置知识

1. 牛顿二项式定理，即

   $$(x+y)^{\alpha}=\sum_{r=0}^{\infty}\binom{\alpha}{r}x^{\alpha-r}y^{r}$$

   其中 $\displaystyle \binom{\alpha}{r}=\frac{\alpha^{\underline{r}}}{r!}$。