GF 基础

· · 算法·理论

本文讲解 WC 中 EI 讲义第一次课间休息前的部分，即 GF 基础知识。

把组合对象中我们所关心的东西提取出来！

\begin{array}{c} \mathscr A=\{\alpha_1,\alpha_2,\cdots,\alpha_n,\cdots\}\\ a_n=\#\{\alpha_i:|\alpha_i|=n\}\\ A(x)=\sum\limits_{\alpha\in \mathscr A}x^{|\alpha|}=\sum\limits_{n=0}^{+\infty}a_nx^n\\ \end{array}
\mathscr A A(x) a_n
不交并 \mathscr C=\mathscr A\sqcup \mathscr B C(x)=A(x)+B(x) c_n=a_n+b_n
笛卡尔积 \mathscr C=\mathscr A\times \mathscr B C(x)=A(x)B(x) c_n=\sum\limits_{k=0}^na_kb_{n-k}
序列（a_0=0） \mathscr B=\textsf{Seq }\mathscr A=\epsilon\sqcup\mathscr A\times \mathscr B B(x)=\dfrac{1}{1-A(x)} b_n=\sum\limits_{k=1}^na_kb_{n-k}
多重集（a_0=0） \mathscr B=\textsf{MSet }\mathscr A=\prod\limits_{\alpha\in\mathscr A}\textsf{Seq }\{\alpha\} B(x)=\prod\limits_{n=1}^{+\infty}(1-x^n)^{-a_n} /
幂集 \mathscr B=\textsf{Set }\mathscr A=\prod\limits_{\alpha\in\mathscr A}\epsilon\sqcup\{\alpha\} B(x)=\prod\limits_{n=0}^{+\infty}(1+x^n)^{a_n} /

注：\sum\limits_{n=0}^{+\infty}x^n=(1-x)^{-1}

若 \mathscr B=\textsf{MSet }\mathscr A，则

\begin{array}{ll} B(x)&=\prod\limits_{n=1}^{+\infty}(1-x)^{-a_n}\\ &=\exp\left(\sum\limits_{n=1}^{+\infty}-a_n\ln(1-x^n)\right)\\ &=\exp\left(\sum\limits_{n=1}^{+\infty}a_n\sum\limits_{k=1}^{+\infty}\dfrac{x^{nk}}{k}\right)\\ &=\exp\left(\sum\limits_{k=1}^{+\infty}\dfrac{1}{k}\sum\limits_{n=1}^{+\infty}a_n(x^k)^n\right)\\ &=\exp\left(\sum\limits_{k=1}^{+\infty}\dfrac{A(x^k)}{k}\right) \end{array}

反演可得

\begin{array}{rl} B(x)&=\exp\left(\sum\limits_{k=1}^{+\infty}\dfrac{A(x^k)}{k}\right)\\ \ln B(x)&=\sum\limits_{k=1}^{+\infty}\dfrac{A(x^k)}{k}\\ \dfrac{\ln B(x^n)}{n}&=\sum\limits_{k=1}^{+\infty}\dfrac{A(x^{nk})}{nk}\\ A(x)&=\sum\limits_{n=1}^{+\infty}\dfrac{\mu(n)}{n}\ln B(x^n) \end{array}

注：\ln(1-x)=-\sum\limits_{n=1}^{+\infty}\dfrac{x^n}{n}

考虑生成函数

B(x)=\dfrac{1}{1-qx}=\sum\limits_{n=0}^{+\infty}q^nx^n

则 \mathscr B 的两种解释为：字符集为 |\Sigma|=q 的字符串，大小为其长度；有限域 \mathbb F_q 上的首 1 多项式，大小为其次数。

对应 \mathscr A 的解释为：字符集为 |\Sigma|=q 的 Lyndon 串；有限域 \mathbb F_q 上的首 1 不可约多项式。

则

\begin{array}{rl} A(x)&=\sum\limits_{n=1}^{+\infty}\dfrac{\mu(n)}{n}\ln B(x^n)\\ &=\sum\limits_{n=1}^{+\infty}\dfrac{\mu(n)}{n}\ln\dfrac{1}{1-qx^n}\\ a_k&=\sum\limits_{n|k}\dfrac{\mu(n)}{n}\cdot\dfrac{q^{k/n}}{k/n}\\ &=\dfrac{1}{k}\sum\limits_{n|k}\mu(n)q^{k/n} \end{array}

Q：从 Lyndon 串和不可约多项式的组合意义上解释上式。

Q：构造字符集为 |\Sigma|=q 的长 n Lyndon 串和有限域 \mathbb F_q 上的首 1 不可约 n 次多项式的双射。

（这两个问题不 trivial）

考虑组合对象 \alpha 和 \beta。若组合时它们可以互相融合（如 \texttt{AAAAA}+\texttt{BBB}\to\texttt{ABABAABA}），打乱顺序，有 \dbinom{|\alpha|+|\beta|}{|\alpha|} 种组合方式，考虑指数生成函数。

\begin{array}{c} \mathscr A=\{\alpha_1,\alpha_2,\cdots,\alpha_n,\cdots\}\\ a_n=\#\{\alpha_i:|\alpha_i|=n\}\\ A(x)=\sum\limits_{\alpha\in \mathscr A}\dfrac{x^{|\alpha|}}{|\alpha|!}=\sum\limits_{n=0}^{+\infty}\dfrac{a_nx^n}{n!}\\ \end{array}
\mathscr A A(x) a_n
不交并 \mathscr C=\mathscr A\sqcup \mathscr B C(x)=A(x)+B(x) c_n=a_n+b_n
笛卡尔积 \mathscr C=\mathscr A\times \mathscr B C(x)=A(x)B(x) c_n=\sum\limits_{k=0}^n\binom{n}{k}a_kb_{n-k}
k 元集 \mathscr B=\textsf{Mset}_k\mathscr A B(x)=A(x)^k/k! /
多重集（a_0=0） \mathscr B=\textsf{Mset }\mathscr A B(x)=\exp(A(x)) /

注：在 k 元（多重）集中，k 个元素总是能找到顺序（它们内部融合后，按照顺序找到第一次出现的位置，如 \texttt{AAA}+{\color{red}\texttt{AAA}}+\texttt{BB}=\texttt{aAb}{\color{red}\texttt{a}}\texttt{BA}{\color{red}\texttt{AA}}，小写指示第一次出现），因此总是除以 k! 是对的。如果无法理解考虑手算 A(x)=x+\dfrac{x^2}{2},k=2,B(x)=\dfrac{x^2}{2}+\dfrac{x^3}{2}+\dfrac{x^4}{8}，组合对象为 \mathscr A=\{\texttt{A},\texttt{AA}\}\to \mathscr B=\{\texttt{Aa},\texttt{Aaa},\texttt{aAa},\texttt{aaA},\texttt{AaAa},\texttt{AaaA},\texttt{AAaa}\}，大小写指示融合方式。

注：\exp(x)=\sum\limits_{k=0}^{+\infty}\dfrac{x^k}{k}。

定义 \partial \left(\sum\limits_{n=0}^{+\infty}a_nx^n\right)=\sum\limits_{n=1}^{+\infty}a_n\cdot nx^{n-1}。

对于普通生成函数，相当于从组合对象中选择一个东西拿出来。

对于指数生成函数，相当于从组合对象中拿出那个钦定的东西。（特别小心大小为 0 的对象，它不见了）

\partial(A+B)=\partial A+\partial B

普通：从 \mathscr A 或 \mathscr B 中的一个对象拿出一个东西，就是从 \mathscr A 中的一个对象拿出一个东西，或从 \mathscr B 中的一个对象拿出一个东西。

指数：从 \mathscr A 或 \mathscr B 中的一个对象拿出那个东西，就是从 \mathscr A 中的一个对象拿出那个东西，或从 \mathscr B 中的一个对象拿出那个东西。

\partial(AB)=(\partial A)B+A(\partial B)

普通：从 \mathscr A 和 \mathscr B 中的组合对象的组合中拿出一个东西，要么从 \mathscr A 的组合对象中拿出一个东西和 \mathscr B 中的组合，要么从 \mathscr B 的组合对象中拿出一个东西和 \mathscr A 中的组合。

指数：从 \mathscr A 和 \mathscr B 中的组合对象的融合中拿出一个东西，若是 \mathscr A 中的在前就把 \mathscr A 中的那个拿出，剩下的拼在一起，否则就把 \mathscr B 中的那个拿出，剩下的拼在一起。

定义复合：

A(x)\circ B(x)=A(B(x))=\sum\limits_{n=0}^{+\infty}a_nB(x)^n

一般要求 b_0=0。组合意义为把 \mathscr B 中的组合对象当做 \mathscr A 中的单位个体（大小为 1 的元素）。

\partial (A\circ B)=(\partial A)\circ B\cdot \partial B

普通：从 \mathscr B 组成的 \mathscr A 中拿出一个东西，先从普通的 \mathscr A 中拿出一个东西，再从那个东西代表的 \mathscr B 中的元素拿出一个东西。

指数：从 \mathscr B 组成的 \mathscr A 中拿出一个东西，先从普通的 \mathscr A 中拿出那个东西，再从那个东西代表的 \mathscr B 中的元素拿出那个东西。

对于指数生成函数：

\mathscr B=\textsf{MSet }\mathscr A\Rightarrow B=\exp A\Rightarrow B'=B\cdot A'\Rightarrow b_n=\sum\limits_{k=1}^n\dbinom{n-1}{k-1}a_kb_{n-k} $b_n=\sum\limits_{k=1}^n\dbinom{n-1}{k-1}a_kb_{n-k}$ 的组合意义：元素大小和为 $n$ 的多重集，钦定第一个位置是最新的元素，相对位置就确定了，有 $\dbinom{n-1}{k-1}$ 种融合方式，以及对应大小为 $k$ 的元素和总大小为 $n-k$ 的多重集。 例：连通图 设 $\mathscr G$ 为简单无向图构成的组合类，$\mathscr C$ 为简单无向连通图构成的组合类，大小为点数。则 $\mathscr G=\textsf{MSet }\mathscr C$。显然有 $g_n=2^{n(n-1)/2}$。 从组合意义和代数推导的角度解释如下递推式： $$ c_n=2^{n(n-1)/2}-\sum_{k=1}^{n-1}\dbinom{n-1}{k-1}c_k2^{(n-k)(n-k-1)/2} $$ 组合意义：$n$ 个点的简单无向连通图的个数，为所有简单无向图的个数，减去不连通的图的个数。不妨枚举 $1$ 所在连通块大小，该连通块的点有 $\dbinom{n-1}{k-1}$ 中选择（除去 $1$），剩下的点随便连。 代数推导：上知若 $\mathscr B=\textsf{Mset }\mathscr A$ 则 $b_n=\sum\limits_{k=1}^n\dbinom{n-1}{k-1}a_kb_{n-k}$ 。略。 $$ c_n=\sum\limits_{k=1}^{n-1}\dbinom{n-2}{k-1}c_kc_{n-k}(2^k-1) $$ 组合意义：断开 $1$ 连的所有边，枚举此时 $n$ 所在连通块的大小 $k$。剩下的点重新连上边，组成一大小为 $n-k$ 的连通块，再重新让 $1$ 向这 $k$ 个点连至少一条边，方案数为 $2^k-1$。 代数推导： $$ \begin{array}{rl} G(x)&=\sum\limits_{n=0}^{+\infty}2^{n(n-1)/2}\dfrac{x^n}{n!}\\ G'(x)&=\sum\limits_{n=0}^{+\infty}2^{n(n+1)/2}{x^n}{n!}\\ G'(x)&=G(2x)\\ C(x)&=\ln G(x)\\ C'(x)&=\dfrac{G(2x)}{G(x)}\\ C''(x)&=\dfrac{2G(4x)G(x)-G(2x)^2}{G^2(x)}\\ C''(x)&=C'(x)(2C'(2x)-C'(x))\\ c_{n+2}&=\sum\limits_{k=0}^nc_{n-k+1}(2\cdot 2^{k}c_{k+1}-c{k+1})\\ c_n&=\sum\limits_{k=1}^{n-1}c_{n-k}c_k(2^k-1) \end{array} $$ 例：$n$ 王问题 有多少 $n$ 阶排列 $\sigma$ 满足 $\forall i,|\sigma_i-\sigma_{i+1}|\neq 1$？ 设 $T=x-2x^2+2x^3-2x^4+\cdots=\dfrac{x-x^2}{1+x}$，则 $T'=\dfrac{1-2x-x^2}{1+2x+x^2}$，答案的普通生成函数 $S(x)=\sum\limits_{n=0}^{+\infty}n!T^n$。 原理：对相邻关系容斥。若需要若干个连续段，一旦它们的升降（在 $T$ 中有 $2$ 的系数）和相对大小关系（有 $n!$ 种）确定，就能确定排列。这是普通容斥（子集容斥），系数为 $\pm 1$。 记 $s(x)=\sum\limits_{n=0}^{+\infty}n!x^n$，则容易证明 $s'x^2+sx+1=s$，即 $S=1+ST+S'\dfrac{T^2}{T'}$。 $$ \begin{array}{rll} S&=1+ST+S'\dfrac{T^2}{T'}\\ S&=1+S\dfrac{x-x^2}{1+x}+S'\dfrac{x^2-2x^3+x^4}{1-2x-x^2}\\ S\cdot(1-2x-2x^3-x^4)&=1-x-3x^2-x^3+S'\cdot(x^2-x^3-x^4+x^5)\\ s_n-2s_{n-1}-2s_{n-3}-s_{n-4}&=(n-1)s_{n-1}-(n-2)s_{n-2}-(n-3)s_{n-3}+(n-4)s_{n-4}&n\ge4\\ s_n&=(n+1)s_{n-1}-(n-2)s_{n-2}-(n-5)s_{n-3}+(n-3)s_{n-4} \end{array} $$ 例：$2\text{-}$正则图 记 $\mathscr A$ 为 $2\text{-}$正则图构成的组合类，求其指数型生成函数。 $\mathscr A=\textsf{MSet }(\mathscr C)$，其中 $\mathscr C$ 为 $n(n\ge 3)$ 元环的组合类。 因为 $$ C(x)=\sum\limits_{n=3}^{+\infty}\dfrac{(n-1)!}{2}\dfrac{x^n}{n!}=\dfrac{1}{2}\sum_{n=3}^{+\infty}\dfrac{x^n}{n}=\dfrac{1}{2}\left(\ln \dfrac{1}{1-x}\right)-\dfrac{x}{2}-\dfrac{x^2}{4} $$ 所以 $$ A(x)=\exp(C(x)))=\exp\left(\dfrac{1}{2}\left(\ln \dfrac{1}{1-x}\right)-\dfrac{x}{2}-\dfrac{x^2}{4}\right)=\exp\left(-\dfrac{x}{2}-\dfrac{x^2}{4}\right)\dfrac{1}{\sqrt{1-x}} $$