当前位置：首页 > news >正文

生成函数的第一部分

news 2026/3/27 0:34:56

计数问题你首先考虑的问题是：你要对什么东西计数。

组合类

组合对象指满足某一性质的树、图、串等可数的对象。组合对象组成的集合成为组合类。

我们用 \(\mathcal{ABCDEFGHIJKLMNOPQRSTUVWXYZ}\) 来表示组合类。

我们将大小为 \(n\) 的组合类集合记作 \(\mathcal{A_n}\)

我们的任务很多是求出 \(|\mathcal{A_n}|\)

笛卡尔积

每个集合中各取一个元素形成有序多元组的集合。

记作 \(A \times B\)

我们显然有 \(|A \times B| = |A| \times |B|\)

OGF

我们设一个数列 \(A\) , \(F(x)=\sum\limits_{i=0} A_i x^i\)

\(x\) 仅仅就是一个符号这一点需要注意。

\[(1,1,1 \dotsb 1) \to \frac{1}{1-x} \\ \]

\[(a^0,a^1 \dotsb a^n) \to \frac{1}{1-ax} \\ \]

\[\sum\limits_{i=0} x^{ik}= \frac{1}{1-x^k} \\ \]

OGF

\[\sum\limits_{i=0} a^ix^{ik}= \frac{1}{1-ax^k} \\ \]

\[(0,1,\frac{1}{2},\frac{1}{3} \dotsb \frac{1}{n}) \to \ln(\frac{1}{1-x})=-\ln(1-x) \\ \]

\[(0,1,\frac{1}{2!},\frac{1}{3!} \dotsb \frac{1}{n!}) \to e^x \\ \]

\[(0,1,\frac{a^2}{2!},\frac{a^3}{3!} \dotsb \frac{a^n}{n!}) \to e^{ax} \\ \]

OGF

什么卡特兰数 \((C(x))\)，斐波那契数 \((F(x))\) 已经烂大街了。

\[F(x)-xF(x)-x^2F(x)=x \]

\[[x^{n+1}]C(x+1)=\sum_{i=0}^n C_i C_{n-i}=[x^{n}]C(x)^2 \]

\[C(x)^2=C(x+1)=\frac{C(x)-1}{x} \]

OGF

广义二项式定理：

\[(a+b)^k=\sum\limits_{i=0} {k \choose i} a^i b^{k-i} \\ \]

其中

\[\mathbf{} {k \choose i}=\dfrac{k \times (k-1) \dotsb (k-i+1)}{i!} \]

就是下降幂。
组合意义：加法：无 \(∩\) 集合，乘法：笛卡尔积。

OGF

设某种号码由小写英文字母和阿拉伯数字组成，且满足所有数字都出现在字母之后。允许没有英文或数字。

求长度为 \(n\) 的号码个数。

OGF

太简单了。

\[G(x) =\sum_{i=0} 10^i x^i = \frac{1}{1-10x} \\ \]

\[F(x) =\sum_{i=0} 26^i x^i = \frac{1}{1-26x} \\ \]

\[Ans(x)=F(x) \times G(x) =\frac{1}{1-26x}\frac{1}{1-10x} \]

后面是 dirty work。

\[\frac{1}{1-26x}\frac{1}{1-10x}= \frac{A}{1-26x} + \frac{B}{1-10x} \]

一个有用的东西：不同有理根展开定理。这里不写，应为写不下（。

UVA12298 Super Poker II

太简单了。考虑列出四种颜色的 \(OGF\)，有的点为 \(1\)，其他是 \(0\)。

FFT/大模数 NTT 即可。

注意没有取模。

P4931 [MtOI2018]情侣？给我烧了！ (加强版)

\[\begin{aligned} &= \dfrac{(n!)^2 2^x}{x!}\sum_{i=0}^m \dfrac{(-2)^i}{i!} {2m-2i\choose m-i}\\ \end{aligned} \]

前面是常数，考虑后面。

\[F(x) =\sum_{i=0} \dfrac{(-2)^i}{i!} x^i \to e^{-2x} \\ G(x) = \sum_{i=0} {2i \choose i} x^i \to \frac{1}{\sqrt{1-4x}}\\ \]

第二个是什么啊等一下。

\[\begin{aligned} & F(x) =\frac{e^{-2x}}{\sqrt{1-4x}} \\ &\texttt{两边平方} \\ & F^2(x) (1-4x) = e^{-4x} \\ &\texttt{两边求导} \\ & (1-4x) \times 2F \times F'-4F^2 =-4e^{-4x} \\ & (1-4x) \times 2F \times F'-4F^2 =(-4) F^2(x) (1-4x) \\ & (1-4x) \times 2F' =16xF\\ & (n+1)F[n] =8F[n-1]+4nF[n]\\ \end{aligned} \]

EGF

这里也给出一些常用的 EGF :

\(\{1,1,1,1,1 \dotsb \} \to e^x\)
\(\{1,-1,1,-1,1 \dotsb \} \to e^{-x}\)
\(\{1,c,c^2,c^3,c^4 \dotsb \}\to e^{cx}\)
\(\{1,c,c^2,c^3,c^4 \dotsb \}\to e^{cx}\)
\(\{1,a^{\underline{1}},a^{\underline{2}},a^{\underline{3}}\dotsb \} \to (1+x)^a\)