生成函数的一种应用——指数族
LitDarkness
·
·
个人记录
浅谈指数族 \text{Exponential Family}
本文参考了 《Generating Functionology》Chapter 3 的内容
0.引入
某天，有人（不是我）问了如下问题（不用考虑任何置换），
- 如何求第一类、第二类斯特林数的生成函数？
- 如何求大小为 n 连通标号图的生成函数？
- 如何求大小为 n 的二分图数量的生成函数？
- ...
学习了 \text{Exponential Family} ，我们可以轻松解决上述问题。
1.一些定义
-
一个 \text{Card} \space C(S,p) 是一个包含有限集 S \subset \N_+ 和一个描述 S 的图片（包括图）的二元组。
它的权值为 |S| ，若 S = [n] ，则该 \text{Card} 被称为标准的。
-
一个 \text{Hand} \space 为一些 \text{Card} 的集合，满足对于给定的 n ，有 \sum |S_i| = n 且 \cup S_i = [n] ，即它们可以恰好凑成 [n] 。
它的权值为 \sum |S_i| 。
-
一个 \text{Deck} 是若干权值相同的标准 \text{Card} 集合，记 d_i= |D_i| ，
-
一个指数族（乱翻译的）\mathcal{F} 则包含了 D_1,D_2,... 。
令 $\large \mathcal{H}(x,y)=\sum_{n,k \geq 0}h(n,k)\frac{x^n}{n!}y^k $ 。
如果省略 $y$ 或 $k$ ，例如 $h(n)$ 、$\mathcal{H}(x)$ 表示所有合法的 $y$ 之和。
## 2. 一些性质
#### The exponential formula
对于一个 $\mathcal{F}$ ，有
$\large \mathcal{H}(x,y)= \exp\{yD(x)\} $.
为了证明上述定理，首先我们介绍如下引理：
#### The Fundamental Lemma of Labeled Counting
令 $\mathcal{F^{'}} ,F^{''}$ 为两个指数族，且它们的 $\text{Hand}$ 互不相同，$\mathcal{F} = \mathcal{F^{'}} \oplus F^{''}$ 为它们的合并，则有 $\mathcal{H}(x,y)=\mathcal{H}^{'}(x,y)\mathcal{H}^{''}(x,y)$。
证明：
注意到
$\large h(n,k)=\sum_{n_1,k_1 \geq 0} \binom{n}{n_1} h^{'}(n_1,k_1)h^{''}(n-n_1,k-k_1)
其意义为选定 n 的一个 n_1 大小子集，然后再从其中任选 k_1 个 \text{Card} 。
而右式 = [\frac{x^n}{n!}y^k] \mathcal{H}^{'}(x,y)\mathcal{H}^{''}(x,y) .
\square
接下来我们考虑仅有一个 D_i 非零，的情况，则 h(n,k) 只能在 h(ki,k) 处有值。
不妨令 n = ik，由于所有 \text{Card} 的都是从 D_i 当中选择，因此最后需要除以 k! 。
也就是说：
从而有
$$
\mathcal{H}(x,y) = \sum_{n,k \geq 0}h(n,k)\frac{x^n}{n!}y^k
= \sum_k h(n,k) \frac{x^{ik}}{n!}y^k
= \sum_k \frac{d_i^kx^{ik}y^k}{k!(i!)^k} = \exp\{\frac{y\times d_ix^i}{i!}\}
$$
然后，我们再考虑将不同的 $D_i$ 合并在一起，不妨认为仅由 $D_i$ 产生的 $\text{Hand}$ 的生成函数记作 $\mathcal{H}_i(x,y)$ ，有引理知，我们有：
$$
\mathcal{H}(x,y)=\prod_{i\geq1}H_i(x,y)= \exp\{y\sum_{i \geq 1} \frac{d_ix^i}{i!}\}=\exp\{yD(x)\}
$$
$\square
3. 应用
求第一类斯特林数
容易发现大小为 i 的圆排列 d_i = (i-1)! ，从而 D(x)=\sum_{i\geq1}\frac{x^n}{n}=\log\frac{1}{1-x}，
因此 \mathcal{H}(x,y)=e^{yD(x)}=\frac{1}{(1-x)^y}。
求第二类斯特林数
大小为 i 的子集只有 1 个，因此 D(x) = e^x-1 ，
从而 \mathcal{H}(x,y)=e^{y(e^x-1)}。
求连通图个数
如果一个 \text{Hand} 表示一个图，
那么一个 \text{Deck} 就表示一个连通图。
而显然，\mathcal{H}(x)=\sum_{n\geq0}2^{\binom{n}{2}}\frac{x^n}{n!}，
因此 D(x)=\log \mathcal{H}(x)，
二分图数量
首先考虑如果黑白两色可以区分，
则 h_i=\sum_{k\geq0}\binom{n}{k}2^{k(n-k)} ，
从而有 D(x)=\log \mathcal{H}_0(x) ，
但是不考虑颜色，我们会有 \mathcal{H}(x)=\exp \frac{D(x)}{2}=\sqrt{\mathcal{H_0}(x)}。
思考：如何计算每个点度数都为 2 的图的个数？