生成函數

生成函數亂抄

生成函數

普通生成函數(OGF)

定義

對于一類對象構成的集合 \(A\) ，若滿足

• 對于每個元素 \(a\in A\) ，定義非負整數 \(|a|\) 為元素 \(a\) 的“大小”或“權值”
• 對于給定的 \(n\) ，大小為 \(n\) 的元素的個數是有限的（但 \(A\) 可以是無限集），其對應的元素個數記為 \(A_n\)

我們定義 \(A(x)=\sum\limits_{n\ge 0}A_nx^n\) 為 集合 \(A\) 的普通生成函數。

注意這裡的 \(A(x)\) 認為是一個形式幂級數，在 \(\bmod x^n\) 以及系數 \(\bmod P\) 的意義下運算

基本運算

設有兩個集合 \(A,B\) 。

定義它們的不交并為 \(C\) ，則 \(C(x)=A(x)+B(x)\)

通俗點其實就是把它們的元素原來是什麼樣還是什麼樣塞到 \(C\) 裡面

定義兩個集合的笛卡爾積為 \(D\) ，則 \(D=A*B\)，這裡指卷積。

意思是對于 \(a\in A,b\in B\)，我們有 \(d=a+b,|d|=|a|+|b|\) （這裡前面可以簡單的了解成定義了元素的并 \(b\) ）

序列OGF

對于一類對象構成的集合 \(A\)，定義 \(\mathbf {SEQ}(A)\) 是由 \(A\) 的元素排列而成的序列組成的集合，對于其中某一個長度為 \(n\) 的序列，可以看作是 \(n\) 個 \(A\) 進行笛卡爾積的結果。

例如 \(A=\{0,1\}\) 即字元 \(0,1\) 構成的二進制集，則 \(\mathbf {SEQ(A)}\) 表示所有的 \(01\) 字元串。

例如 \(A=\mathbb Z^+\) 即正整數集，則 \(\mathbf {SEQ} (A)\) 表示正整數序列。

對于 \(\mathbf {SEQ}(A)\) 中的一個元素 \((a_1,a_2,\dots)\) ，定義其大小為\(|a_1|+|a_2|+\dots\) ，那麼顯然有序列 \(\mathbf{SEQ} (A)\) 的 \(OGF\) 為 \(\mathbf {SEQ} (A)=1+A+A^2+\dots=\frac{1}{1-A}\)

下面給出用 序列OGF 進行數數的例子

若 \(A=\{0,1\}\) 即字元 \(0,1\) 構成的二進制集

• 我們定義所有元素的大小為 \(1\) ，則 \(A\) 的生成函數為 \(A(x)=2x\)

則 \(\mathbf {SEQ} (A)\) 的生成函數為 \(1+2x+4x^2+8x^3+\dots\) ，其系數表示長度為 \(i\) 的序列的個數

我們也可以定義元素 \(i\) 的大小為 \(|i|\) ，則序列 \(A\) 的生成函數為 \(A(x)=1+x\)

則 \(\mathbf {SEQ} (A)\) 的生成函數為 \(1+(1+x)+(1+x)^2+(1+x)^3+\dots\) ，其系數表示有 \(i\) 個元素 \(1\)的序列 的個數

若 \(A=\mathbb Z^+\) 即正整數集

• 定義元素 \(i\) 的大小為 \(|i|\) ，則 \(A\) 的生成函數為 \(A(x)=\sum\limits_{i\ge 1}x^i=\frac{x}{1-x}\)

則 \(\mathbf {SEQ}(A)\) 的生成函數為 \(\frac{1}{1-A}=1+x+2x^2+4x^3+8x^4+\dots\)，其系數實際上表示的是正整數的有序拆分數。

常見數列的 OGF

\[\begin{aligned}

&<1,0,0,\dots>\Rightarrow A(x)=1\\

&<1,1,1,\dots>\Rightarrow A(x)=1+x+x^2+\dots=\frac{1}{1-x}\\

&<1,-1,1,\dots>\Rightarrow A(x)=1-x+x^2-\dots=\frac{1}{(1+x)}\\

&<1,2,3,\dots>\Rightarrow A(x)=1+2x+3x^2+\dots=(1+x+x^2+\dots)^2=\frac{1}{(1-x)^2}\\

\end{aligned}

\]

指數生成函數(EGF)

對于一類帶标号對象構成的集合 \(A\) ，若滿足 \(OGF\) 的兩個要求

我們定義 \(A(x)=\sum\limits_{n\ge 0}\frac{A_n}{n!}x^n\) 為集合 \(A\) 的指數生成函數。

帶标号對象是為了合并兩個帶标号集合。當兩個大小分别為 \(n,m\) 的帶标号集合進行合并時，需要重新進行标号，并保留在原集合的相對标号，其方案數為 \(\binom{n+m}{m}\)

同 \(OGF\) ，但笛卡爾積合并的是兩個帶标号集合。

序列EGF

對于一類帶标号對象構成的集合 \(A\)，定義 \(\mathbf {SEQ}(A)\) 是由 \(A\) 的元素排成的序列組成的集合且進行保序重标号，其餘與 \(OGF\) 類似。

集合EGF

對于一類帶标号對象構成的集合 \(A\)，定義 \(\mathbf{SET}(A)\) 是由 \(A\) 的子集組成的集合且進行保序重标号。但由于 \(A\) 的子集互相間是無序的，所有有 \(\mathbf{SET}(A)=1+A+\frac{A^2}{2!}+\frac{A^3}{3!}+\dots=e^A\)

下面給出用 集合EGF 進行數數的例子

若 \(G\) 為所有帶标号簡單無向圖構成的集合

• 定義每個圖的大小為它的點數，則 \(G\) 的生成函數為 \(\sum\limits_{n\ge 0} \frac{2^{\binom{n}{2}}}{n!}x^i\)

若 \(G^+\) 為所有簡單無向連通圖構成的集合

• 定義每個圖的大小為它的點數，則有 \(G=\mathbf{SET} (G^+)=e^{G^+}\)

是以有 \(G^+=\ln G\)

若 \(T\) 為所有帶标号樹構成的集合

• 定義每個圖的大小為它的點數，則 \(T\) 的生成函數為 \(\sum\limits_{n\ge 0}\frac{n^{n-2}}{n!}x^i\)

設 \(F\) 為是以帶标号森林構成的集合

• 定義每個圖的大小為它的點數，則有 \(F=e^T\)

常見數列的 EGF

<1,1,1,\dots>&\Rightarrow A(x)=1+x+\frac{x^2}{2}+\frac{x^3}{6}+\dots=e^x\\

<0,1,2,\dots>&\Rightarrow A(x)=x+x^2+\frac{x^3}{2}+\frac{x^4}{6}+\dots=xe^x\\

<1,c,c^2\dots>&\Rightarrow A(x)=x+cx+\frac{c^2x^2}{2}+\frac{c^3x^3}{6}+\dots=e^{cx}\\

常見數列與生成函數

Fibonacci 數列

設 Fib 數列 \(<1,1,2,3,5,\dots>\) 的 OGF 為 \(F(x)\)

F(x)=&1+x+2x^2+3x^3+5x^4+\dots\\

=&1+x(1+2x+3x^2+5x^3+\dots)\\

=&1+x(1+x+2x^2+3x^3+\dotsc+x(1+x+2x^2+\dots))\\

=&1+xF(x)+x^2F(x)\\

化簡後得

\[F(x)=\frac{1}{1-x-x^2}

然後可以在 \(O(n\log n)\) 的複雜度求解 Fib 辣

這個沒什麼用，如果有興趣可以把這個式子展開推一下通項。

Catalan 數列

設 Cat 數列 \(<1,2,5,14,42,\dots>\) 的 OGF 為 \(C(x)\)

我們知道 Cat 可以描述一個 \(n\) 個點構成的不同形态的二叉樹個數，是以存在遞推公式 \(c_n=\sum\limits_{0\le i< n}c_ic_{n-i-1}\)

是以有

C(x)&=\sum_{n\ge 0}c_nx^n\\

&=\sum_{n\ge 0}([n=0]+\sum_{0\le i\le n-1}c_ic_{n-i-1})x^n\\

&=1+x\sum_{n\ge 1}\sum_{0\le i\le n-1}c_ic_{n-i-1}x^{n-1}\\

&=1+xC(x)^2

化簡得

\[C(x)=\frac{1\pm \sqrt{1-4x}}{2x}

考慮代入 \(C(0)=1\) 得到正負号（這是通用方法）

這個其實也沒啥用，因為我們有 \(O(n)\) 求解卡特蘭數的方法，可以展開生成函數求得通項

\[C(x)=\sum_{n\ge 0}\frac{(2n)!}{[n!(n+1)!]}x^n

Bell 數

Bell 數 \(w_n\) 表示将大小為 \(n\) 的集合分割成若幹個非空不相交子集的方案數，定義 \(w_0=1\)

考慮枚舉第一個元素所在的子集大小進行遞推，有

\[w_n=\sum_{1\le i \le n-1}\binom{n-1}{i-1}w_{n-i}

設其的 EGF 為 \(B(x)\)

B(x)=&\sum_{n\ge 0}\frac{w_n}{n!}x^n\\

=&1+\sum_{n\ge 1}(\sum_{1\le i\le n}\binom{n-1}{i-1}w_{n-i})\frac{1}{n!}x^n\\

=&1+\sum_{n\ge 1}(\sum_{1\le i\le n}\frac{w_{n-i}}{(n-i)!}\frac{x^n}{(i-1)!n})\\

=&1+\sum_{n\ge 1}(\sum_{0\le i <n}\frac{w_i}{i!}\frac{x^n}{(n-i-1)!n})\\

=&1+\sum_{i\ge 0}\frac{w_i}{i!}\sum_{n>i}\frac{x^n}{(n-i-1)!n}\\

考慮到右邊分母的 \(n\) 不友好，那麼進行求導

B(x)'&=\sum_{i\ge 0}\frac{w_i}{i!}\sum_{n>i}\frac{x^{n-1}}{(n-i-1)!}\\

&=\sum_{i\ge 0}\frac{w_i}{i!}\sum_{n\ge 0}\frac{x^{n+i}}{n!}\\

&=\sum_{i\ge 0}\frac{w_i}{i!}x^ie^x\\

&=B(x)e^x

下面求解微分方程

&\frac{B(x)'}{B(x)}=e^x\\

&\int \frac{B(x)'}{B(x)} \mathbb dB(x)=\int e^x \mathbb dx\\

&\ln(B(x))=e^x+C\\

&B(x)=e^{e^x+C}

代入 \(B(0)=1\) 可以得到常數 \(C=-1\)

是以 \(B(x)=e^{e^x-1}\)

當然，也可以直接簡單粗暴的用組合意義來說明 Bell 數的 EGF，設 \(A(x)\) 表示 \(n\) 個數組成一個非空集合的方案數

那麼 \(A(x)=x+\frac{x^2}{2}+\frac{x^3}{3!}+\dots=e^x-1\)

然後我們可以發現 \(B(x)=\mathbf {SET}(A)=e^{e^x-1}\)

有向無環圖計數

給定正整數 \(n\) ，求恰好有 \(n\) 個點的帶标号有向無環圖的個數

有向無環圖 (DAG) 指的是一個無回路的有向圖

設 \(f_i\) 為 \(i\) 個點有向無環圖個數，一個簡單的想法是枚舉入度為 \(0\) 的點的大小

\[f_i=\sum_{i=1}^n\binom{n}{i}2^{i(n-i)}f_{n-i}

注意到這時候我們實際上枚舉的是至少有 \(i\) 個入度為 \(0\) 的點的大小，是以需要加上容斥系數

\[f_i=\sum_{i=1}^n\binom{n}{i}2^{i(n-i)}f_{n-i}(-1)^{i-1}

考慮到利用生成函數，我們需要湊出關于多項式方程，構造左邊有 \(n\) ，右邊有 \(n-i\) 的項放到 \(f(i)\) 上，具體的

&\frac{f_n}{n!}=\sum_{i=1}^n\frac{f_{n-i}}{(n-i)!}(\sqrt2)^{n^2-i^2-(n-i)^2}\frac{(-1)^{i-1}}{i!}\\

&\frac{f_n}{n!\sqrt2^{n^2}}=\sum_{i=1}^n\frac{f_{n-i}}{(n-i)!\sqrt2^{(n-i)^2}}\frac{1}{\sqrt2^{i^2}}

令

\[F(x)=\sum_{i\ge0}\frac{f_i}{i!\sqrt2^{n^2}}x^i,G(i)=\sum_{i\ge0}\frac{(-1)^{i-1}}{\sqrt2^{i^2}}x^i

可以得到 \(F=FG+1\) ，即 \(F=\frac{1}{G-1}\)

\(2\bmod p\) 的二次剩餘可以一開始暴力 \(O(mod)\) 求得

邊雙連通圖計數

給定正整數 \(n\) ，求恰好有 \(n\) 個有标号點的邊雙連通圖的個數。

邊雙聯通圖是一個不存在橋的無向連通圖

設 \(n\) 個點的邊雙聯通圖的數量為 \(b_n\) ，生成函數為 \(B(x)\) ，\(n\) 個點的有根聯通圖的數量為 \(c_n\) ，生成函數為 \(C(x)\)

顯然有根聯通圖的生成函數 \(C\) 可以通過一般聯通圖求解

對于任意有根連通圖，進行邊雙連通分量縮點以後可以得到一棵樹，不妨設原圖的根節點所在的連通分量就是樹的根節點，且這個連通分量的大小為 \(n\) ，則此聯通分量對應的生成函數為 \(\frac{b_{n}x^n}{n!}\)

然後根所在聯通分量連接配接出去的其他邊，邊的另一端是一個聯通圖，将與這個邊直接相連的點視為聯通圖的根，則這個聯通圖是一個有根聯通圖，由于邊在原圖根節點所在雙連通分量的大小為 \(n\) ，且都可以作為邊的一個端點，是以連出去的有根聯通圖的生成函數為 \(nC(x)\)

與根相連的邊可以自由的存在，本質上是一個 \(\mathbf{SET}\) ，是以所有與邊相連的連通圖的生成函數為 \(e^{nC(x)}\)

然後我們就可以建立 \(B\) 與 \(C\) 的關系了，枚舉根雙連通塊的大小，有

\[C(x)=\sum_{n\ge 1}b_ne^{nC(n)}x^n

是以

\[C(x)=B(xe^{c(x)})

設 \(D(x)=xe^{c(x)}\) ，\(D^{-1}(x)\) 的為其的複合逆

關于複合逆，回顧一下拉格朗日反演

若 \(G(F(x))=F(G(x))=x\) ，則 \(G\) 與 \(F\) 互為複合逆，由拉格朗日反演，我們有

\[[x^n]G(x)=\frac{1}{n}[x^{n-1}](\frac{x}{F(x)})^n\\

[x^n]A(G(x))=\frac{1}{n}[x^{n-1}]A'(x)(\frac{x}{F(x)})^n

\[B(x)=C(D^{-1}(x))