浅谈指数族 \(\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|\) ，
\(D(x)\) 为 \(\{d_i\}\) 的 \(EGF\) 。
-
一个指数族（乱翻译的）\(\mathcal{F}\) 则包含了 \(D_1,D_2,...\) 。
\(h(n,k)\) 表示权值为 \(n\) 且恰好有\(k\) 个数 \(\text{Card}\) 的 \(\text{Hand}\) 个数，
令 $$ \large \mathcal{H}(x,y)=\sum_{n,k \geq 0}h(n,k)\frac{xn}{n!}yk $$ 。
如果省略 \(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!$ 。 也就是说： $$\large h(ki,k)=d_i^k\frac{n!}{i!^k}\frac{1}{k!}$$ ， 从而有 \]\mathcal{H}(x,y) &= \sum_{n,k \geq 0}h(n,k)\frac{xn}{n!}yk \
&= \sum_k h(n,k) \frac{x{ik}}{n!}yk \
&= \sum_k \frac{d_ikxyk}{k!(i!)k} = \exp{\frac{y\times d_ix^i}{i!}}
\mathcal{H}(x,y)=\prod_{i\geq1}H_i(x,y)= \exp{y\sum_{i \geq 1} \frac{d_ix^i}{i!}}=\exp
\[$\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)}$。 > $ \mathcal{H} (x)=e^{e^x-1}$ 其实就是著名的贝尔数的 $EGF$。 #### 求连通图个数 如果一个 $\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}(x)}$。 > 思考：如何计算每个点度数都为 2 的图的个数？ ##\] 标签：frac,函数,text,sum,生成,科技,mathcal,Hand,Card From： https://www.cnblogs.com/LitDarkness/p/17069167.html