CloudySky

纵使世界万般残酷

总有温暖值得守护

生成函数 学习笔记

简单的瞅了几眼生成函数，口胡了这个学习笔记。

生成函数的概念

生成函数，又称形式幂级数。大概分成三种：

  • 普通形式幂级数 F(x)=∑iaixiF(x) = \sum_ia_ix^i
  • 指数级形式幂级数 F^(x)=∑iaixii!\hat{F}(x) = \sum_ia_i\dfrac{x^i}{i!}
  • 迪利克雷生成函数。仅仅是听说过，听机房的大佬说不用学。

对于它的概念，理解成用来表示某个序列的函数就行。

关于 xx 的实际含义：没有实际含义，不然为什么叫形式幂级数呢？

生成函数的封闭形式

可能会很好奇，指数生成函数哪里和指数有关了？

生成函数的封闭形式大概就是换了一种更加直观的书写方式。

如常数列 ⟨1,1,1,⋯ ⟩\langle 1, 1, 1, \cdots \rangle 。它的普通生成函数为 F(x)=1+x+x2+⋯F(x) = 1 + x + x^2 + \cdots 然后把他乘上 xx 得 xF(x)=x+x2+⋯xF(x) = x + x^2 + \cdots 然后相减得 F(x)−xF(x)=1F(x) - xF(x) = 1 。这里可能就有问题，他都取到到无穷了还能这么减？我也不知道为什么，反正他就是能这么减。

指数生成函数的原因就是还是对于刚才那个常数数列，它的指数生成函数的封闭形式为 exe^x 。

生成函数封闭形式小练习

（题目来自 OI-wiki）

求下面函数的生成函数封闭形式：
  1. ⟨0,1,1,1,⋯ ⟩\langle 0, 1, 1, 1, \cdots \rangle

推导过程

挺套路的，生成函数为F(x)=0+x+x2+…上来直接xF(x)=0+x2+x3+⋯发现需要补个x才能取等xF(x)+x=F(x)(1−x)F(x)=xF(x)=x1−x挺套路的，生成函数为 \\ F(x) = 0 + x + x^2 + \dots \\ 上来直接 xF(x) = 0 + x^2 + x^3 + \cdots \\ 发现需要补个 x 才能取等 \\ xF(x) + x = F(x) \\ (1 - x)F(x) = x \\ F(x) = \dfrac{x}{1 - x}

  1. ⟨0,1,0,1,⋯ ⟩\langle 0, 1, 0, 1, \cdots \rangle

推导过程

F(x)=1+x2+x4+⋯x2F(x)=x2+x4+x6+⋯x2F(x)+1=F(x)F(x)=11−x2F(x) = 1 + x^2 + x^4 + \cdots \\ x^2F(x) = x^2 + x^4 + x^6 + \cdots \\ x^2F(x) + 1 = F(x) \\ F(x) = \dfrac{1}{1 - x^2}

  1. ⟨1,2,3,4,⋯ ⟩\langle 1, 2, 3, 4, \cdots \rangle

推导过程

可能是靠数感吧F(x)=1+2x+3x2+⋯xF(x)=x+2x2+3x3+⋯发现系数缺点东西。随便试试1xF(x)=1x+2+3x+4x2+5x3+⋯(x+1x)F(x)=1x+2+2⋅2x+2⋅3x2+⋯再稍微整理一下F(x)=1(x−1)2可能是靠数感吧 F(x) = 1 + 2x + 3x^2 + \cdots \\ xF(x) = x + 2x^2 + 3x^3 + \cdots \\ 发现系数缺点东西。随便试试 \\ \dfrac{1}{x}F(x) = \dfrac{1}{x} + 2 + 3x + 4x^2 + 5x^3 + \cdots \\ (x + \dfrac{1}{x})F(x) = \dfrac{1}{x} + 2 + 2\cdot2x + 2\cdot3x^2 + \cdots \\ 再稍微整理一下 F(x) = \dfrac{1}{(x - 1)^2}

就推出来了这几个剩下的太菜了推不出来 qwq 小学数学没过关。

广义二项式定理

广义组合数：

(rk)=rk‾k!(r∈C,k∈N){r\choose k} = \frac{r^{\underline{k}}}{k!} (r\in \mathbf{C},k\in \mathbf{N})

广义二项式定理：

(1+x)α=∑n(αn)xn(1 + x)^{\alpha} = \sum_n{\alpha\choose n}x^n

本文作者：CloudySky
写作时间： 2022-01-26
最后更新时间： 2022-01-26
遵循协议： BY-NC-SA

Top