本文共 8148 字，大约阅读时间需要 27 分钟。

写在前面

介绍De Bruijn定理的母函数形式，由此《（组合数学笔记）Pólya计数理论》系列完结。

引入

与Pólya定理的母函数形式的推导类似，首先引入模式清单$(\mathrm{I}\mathrm{n}\mathrm{v})$的概念，并介绍两个引理。

模式清单

• 假设：颜色集$C$上的权函数$w(\cdot )$在颜色置换群$H$的每条轨道上是常数，即若$\mathrm{O}\mathrm{r}\mathrm{b}(c)$是颜色置换群$H$在颜色集$C$上的一条轨道，则对$\forall c_1,c_2\in \mathrm{O}\mathrm{r}\mathrm{b}(c)$，有$w(c_1)=w(c_2)$.

设方案集$C^X$关于幂群$H^G$的模式清单$\mathrm{I}\mathrm{n}\mathrm{v}(C^X/H^G)$，并假定轨道集
$$C^X/H^G=\{\mathrm{O}\mathrm{r}\mathrm{b}({\phi }_1),\mathrm{O}\mathrm{r}\mathrm{b}({\phi }_2),\cdots ,\mathrm{O}\mathrm{r}\mathrm{b}({\phi }_k)\},$$
那么有
$$\mathrm{I}\mathrm{n}\mathrm{v}(C^X/H^G)=\sum _{\mathrm{O}\mathrm{r}\mathrm{b}(\phi )\in C^X/H^G}w(\phi )=\sum _{j=1}^{k}w({\phi }_j).$$

引理1

设$C$为颜色集，$X$是染色对象集，$w(\cdot )$是定义在$C$上的权函数，且$w(\cdot )$在群$H$的每条轨道上是常数。对于给定的${\tau }^{\sigma }\in H^G$，令 F i x ( τ σ ) = { φ ∣ φ ∈ C X ,   τ σ ( φ ) = φ } \mathrm{Fix}(\tau^{\sigma})=\{\varphi|\varphi\in C^X,\ \tau^{\sigma}(\varphi)=\varphi\} Fix(τσ)={ φ∣φ∈CX, τσ(φ)=φ}, $w(\mathrm{F}\mathrm{i}\mathrm{x}({\tau }^{\sigma }))$表示${\tau }^{\sigma }$的所有不动点的权和，则有
$$\mathrm{I}\mathrm{n}\mathrm{v}(C^X/H^G)=\frac{1}{|H^G|}\sum _{{\tau }^{\sigma }\in H^G}w(\mathrm{F}\mathrm{i}\mathrm{x}({\tau }^{\sigma })).$$

引理2

对于${\tau }^{\sigma }\in H^G$,$\mathrm{F}\mathrm{i}\mathrm{x}({\tau }^{\sigma })$表示置换${\tau }^{\sigma }$不动点的集合，$w(\mathrm{F}\mathrm{i}\mathrm{x}({\tau }^{\sigma }))$表示${\tau }^{\sigma }$的所有不动点的权和，则有
$$w(\mathrm{F}\mathrm{i}\mathrm{x}({\tau }^{\sigma }))=\prod _{j=1}^n[\sum _{{\tau }^j(n=b)=b}w(b^j){]}^{{\lambda }_j(\sigma )}=\prod _{j=1}^n{M}_j(\tau {)}^{{\lambda }_j(\sigma )},$$
其中
$$M_j(\tau )=\sum _{{\tau }^j(b)=b}w(b{)}^j.$$
$M_j(\tau )$是用$\tau$的所有$d$循环中的颜色循环顺序地染色$\sigma$的一个$j$循环中的对象由此得到的所有染色方案的权和，其中$d|j$.

由上述引理1，2可以得到下面的定理。

母函数型的De Bruijn定理

设$(G,\ast )$和$(H,\bullet )$分别是$n$元对象集$X$和$m$元颜色集$C$上的置换群，$w(\cdot )$是定义在$C$上的权函数，且$w(\cdot )$在群$H$的每条轨道上是常数，则
$$\mathrm{I}\mathrm{n}\mathrm{v}\left(C^X/H^G\right)=\frac{1}{|H|}\sum _{\tau \in H}{\mathrm{C}\mathrm{I}}_G(M_1(\tau ),M_2(\tau ),\cdots ,M_n(\tau )),$$
其中${\mathrm{C}\mathrm{I}}_G(x_1,x_2,\cdots ,x_n)$是置换群$G$的循环指数，$M_j(\tau )=\sum _{{\tau }^j(b)=b}w(b{)}^j$.

定理的特殊情况

$X$上没有置换群

即置换群$G$只包含单位元$\iota$, 此时有${\mathrm{C}\mathrm{I}}_G(x_1,x_2,\cdots ,x_n)=x_1^n$.
$$\mathrm{I}\mathrm{n}\mathrm{v}\left(C^X/H^G\right)=\mathrm{I}\mathrm{n}\mathrm{v}\left(C^X/H\right)=\frac{1}{|H|}\sum _{\tau \in H}\left[w\right(\mathrm{F}\mathrm{i}\mathrm{x}(\tau )){]}^n.$$

$Y$上没有置换群

即置换群$H$只包含单位元$\iota$.

$$\mathrm{I}\mathrm{n}\mathrm{v}\left(C^X/H^G\right)=\mathrm{I}\mathrm{n}\mathrm{v}\left(C^X/G\right)={\mathrm{C}\mathrm{I}}_G(w_1(C),w_2(C),\cdots ,w_n(C)),$$

上式即为母函数型的Pólya定理(Pólya基本定理)。

$X,Y$上均没有置换群

即置换群$G,H$均只包含单位元$\iota$.

直接由De Bruijn定理，可以得到

$$\begin{array}{rl}\mathrm{I}\mathrm{n}\mathrm{v}\left(C^X/H^G\right)& =\mathrm{I}\mathrm{n}\mathrm{v}\left(C^X\right)=\frac{1}{|H|}\sum _{\tau \in H}{\left[w(\mathrm{F}\mathrm{i}\mathrm{x}(\tau ))\right]}^n\\ & ={\left[\sum _{c\in C}w(c)\right]}^n=(x_1+x_2+\cdots +x_m{)}^n\\ & =\sum _{n_i⩾0,i=1,2,\cdots ,m}\left(\genfrac{}{}{0ex}{}{n_1+n_2+\cdots +n_m}{n_1,n_2,\cdots ,n_m}\right)x_1^{n_1}{x}_2^{n_2}\cdots x_m^{n_m}\end{array}$$
此即在没有任何群的作用下$n$元集到$m$元集的所有映射方案的枚举，亦即$n$个不同的球放入$m$个不同的盒子且允许空盒的放入方案数的枚举。

例题

将3个白球和1个黑球放入2个方形盒子和1个圆形盒子且允许空盒的模式清单(假定3个白球、2个方形盒子均不可区分)。

分析

令 X = { b ,   w 1 ,   w 2 ,   w 3 } X=\{b,\,w_1,\,w_2,\,w_3\} X={ b,w1​,w2​,w3​}为对象集， C = { r ,   s 1 ,   s 2 } C=\{r,\,s_1,\,s_2\} C={ r,s1​,s2​}为颜色集。显然$X$与$C$上的置换群分别为$G={\mathcal{S}}_1\oplus {\mathcal{S}}_3,H={\mathcal{S}}_1\oplus {\mathcal{S}}_2$.即
H = { ( r ) ( s 1 ) ( s 2 ) ,   ( r ) ( s 1 s 2 ) } ≜ { τ 1 ,   τ 2 } G = { ( b ) ( w 1 ) ( w 2 ) ( w 3 ) ,   ( b ) ( w 1 w 2 w 3 ) ,   ( b ) ( w 1 w 3 w 2 ) , ( b ) ( w 1 ) ( w 2 w 3 ) ,   ( b ) ( w 2 ) ( w 1 w 3 ) ,   ( b ) ( w 3 ) ( w 1 w 2 ) } \begin{aligned} H=\{&(r)(s_1)(s_2),\,(r)(s_1s_2)\}\triangleq\{\tau_1,\,\tau_2\}\\ G=\{&(b)(w_1)(w_2)(w_3),\,(b)(w_1w_2w_3),\,(b)(w_1w_3w_2),\\ &(b)(w_1)(w_2w_3),\,(b)(w_2)(w_1w_3),\,(b)(w_3)(w_1w_2)\} \end{aligned} H={ G={ ​(r)(s1​)(s2​),(r)(s1​s2​)}≜{ τ1​,τ2​}(b)(w1​)(w2​)(w3​),(b)(w1​w2​w3​),(b)(w1​w3​w2​),(b)(w1​)(w2​w3​),(b)(w2​)(w1​w3​),(b)(w3​)(w1​w2​)}​
所以
$${\mathrm{C}\mathrm{I}}_G(x_1,x_2,x_3,x_4)=\frac{1}{6}(x_1^4+2x_1{x}_3+3x_1^2{x}_2),$$
定义$C$上的权函数为
$$w(r)=x,w(s_1)=w(s_2)=y,$$
显然满足权函数在$H$的每一条轨道上是常数。

由定义$M_j(\tau )=\sum _{{\tau }^j(b)=b}w(b{)}^j$, 得到
$$\{\begin{array}{l}{M}_1({\tau }_1)=x+2y,\\ M_2({\tau }_1)=x^2+2y^2,\\ M_3({\tau }_1)=x^3+2y^3,\\ M_4({\tau }_1)=x^4+2y^4,\end{array}\{\begin{array}{l}{M}_1({\tau }_2)=x,\\ M_2({\tau }_2)=x^2+2y^2,\\ M_3({\tau }_2)=x^3,\\ M_4({\tau }_2)=x^4+2y^4.\end{array}$$
由此得到
$$\begin{array}{rl}& {\mathrm{C}\mathrm{I}}_G(M_1({\tau }_1),M_2({\tau }_1),M_3({\tau }_1),M_4({\tau }_1))\\ =& \frac{1}{6}\left[(x+2y{)}^4+2(x+2y)(x^3+2y^3)+3(x+2y{)}^2(x^2+2y^2)\right]\\ =& x^4+4x^{3}y+7x^2{y}^2+10x{y}^3+8y^4,\\ & \\ & \\ & {\mathrm{C}\mathrm{I}}_G(M_1({\tau }_2),M_2({\tau }_2),M_3({\tau }_2),M_4({\tau }_2))\\ =& \frac{1}{6}\left[x^4+2x^4+3x^2(x^2+2y^2)\right]\\ =& x^4+x^2{y}^2,\end{array}$$
于是根据母函数型的De Bruijn定理，有
$$\begin{array}{rl}\mathrm{I}\mathrm{n}\mathrm{v}\left(C^X/H^G\right)& =\frac{1}{|H|}\sum _{\tau \in H}{\mathrm{C}\mathrm{I}}_G(M_1(\tau ),M_2(\tau ),M_3(\tau ),M_4(\tau ))\\ & =\frac{1}{2}\left(x^4+4x^{3}y+7x^2{y}^2+10x{y}^3+8y^4+x^4+x^2{y}^2\right)\\ & =x^4+2x^{3}y+4x^2{y}^2+5x{y}^3+4y^4.\end{array}$$

转载地址：http://rpzg.baihongyu.com/