Author: Gorenstein, Gryffindor, Class of 2024

  • 群作用
    • 群作用的轨道空间
    • Burnside 引理
  • 对称群及其计数
    • 对称群作用
    • 对称群的一些例子
    • 轮换与循环分解
    • 对同型号置换的计数：Cauchy 公式
    • 轮换指标及其 OGF
  • Pólya 计数定理
    • 染色集上的作用
    • Pólya 定理及其证明
    • Pólya 定理的一些例子
  • 带权的 Pólya 定理
    • 定理的证明
    • 有限制的染色同构计数
    • 组合类的 Cycle 构造

群作用

先来定义幺半群作用的概念，这是之后讨论对称群的计数的基础。

$\bf Definition\;1.\quad$设 $X$ 为集合，$M$ 为幺半群。称 $M$ 在 $X$ 上的一个左作用是映射

\[a:M\times X\to X,\]

满足以下条件：

  • $\forall m,m’\in M,\,x\in X$，满足 $a(m’,a(m,x))=a(m’m,x)$（结合律）。
  • $\forall x\in X,\;a(1,x)=x$。

将带有 $M$ 作用的集合称为 $M\text-$集。另将 $\forall m\in M,x\in X$ 都有 $a(m,x)=x$ 的作用称为平凡作用。

习惯上亦将 $a(m,x)$ 记作 $m\cdot x$ 或 $mx$。此时上述条件简写作

\[\begin{aligned} m'(mx)&=(m'm)x,\\ 1\cdot x&=x,\\ f(mx)&=mf(x). \end{aligned}\]

以上关于左作用的定义可逐条改写得到右作用。事实上，所谓右有作用无非就是 $M^{\operatorname{op}}$ 对其的左作用。

接下来定义 $M\text-$集同构的概念。

$\bf Definition\;2.\quad$设 $M\text-$集间的映射 $f:X\to Y$ 满足

\[f(a(m,x))=a(m,f(x)),\quad m\in M,\,x\in X,\]

则称该映射为 $\bf{M\text-}$等变映射；若等变映射 $M_1\xleftrightarrow[g]{f}M_2$ 满足

\[fg=\operatorname{id}_{M2},\,gf=\operatorname{id}_{M1},\]

则称 $f,g$ 互为同构。

$\bf Example.\quad$显然 $M_n(\mathbb R)$ 成一幺半群。若视 $\mathbb R^n$ 中的元素为一列向量，则 $M_n(\mathbb R)$ 在 $\mathbb R^n$ 上的作用 $(\boldsymbol A,\boldsymbol x)\mapsto \boldsymbol A\boldsymbol x$ 无非是矩阵乘法。

$\bf Proposition\;3.\quad$设群 $G$ 左作用于 $X$，设 $Y$ 是任意集合。则群 $G$ 对于集合 ${f:X\to Y}$ 有自然的左作用 $a(g,f)=[x\mapsto f(g^{-1}x)]$。

${Proof.}\quad$显然有 $a(1,f)=[x\mapsto f(1\cdot x)]=f$。对于 $g,h\in G$，有 \(\begin{aligned} \;\;\qquad\;\;\qquad a(h,a(g,x))&=\left[x\mapsto a(g,x)(h^{-1}x)\right]=\left[x\mapsto f(g^{-1}h^{-1}x)\right]=a(hg,x).\qquad\qquad\quad\square \end{aligned}\)

我们给出以下一项性质作为对群作用的笼统介绍的收尾。

$\bf Proposition\;4.\quad$对于一个群 $M$，全体 ${M\text-}$集连同等变映射构成一范畴，记作 $M\text-\mathsf{Set}$。

群作用的轨道空间

不动点、轨道与稳定化子

兹给出不动点、轨道和稳定化子的定义。

$\bf Definition\;5.\quad$设幺半群 $M$ 作用于 $X$。以下定义

  • 不动点集 $X^M:={x\in X:\forall m\in M,\,mx=x}$。
  • $\boldsymbol{m\text-}$不动点 $\psi(m):={x\in X:mx=x}$。
  • $x$ 的轨道 $Mx:={mx:m\in M}$。它是 $X$ 的 $M\text -$子集。
  • $x$ 的稳定化子 $\operatorname{Stab}_M(x):={m\in M:mx=x}$。不难验证它是 $M$ 的子幺半群。

对于群 $G$ 作用于 $X$ 上，$x$ 的稳定化子亦记作 $G_x$。它是 $G$ 的一个子群。

等价类的划分

群 $G$ 的作用的基本组成是形如 $G/H$ 的陪集空间。考虑以下引理。

$\bf Lemma.\quad$设群 $G$ 作用于 $X$，则

  • 对每个轨道选定代表元 $x$，就有轨道分解 \(X=\bigsqcup_x Gx\,.\)
  • $\forall x\in X$，以下映射乃同构： \(\begin{aligned} G/\operatorname{Stab}_G(x)&\longrightarrow Gx,\\ g\cdot\operatorname{Stab}_G(x)&\longmapsto gx. \end{aligned}\)
  • 对所有 $x\in X,\,g\in G$，有 \(\operatorname{Stab}_G(gx)=g\operatorname{Stab}_{G}(x)g^{-1}.\)
  • 存在基数的恒等式 $$|X|=\sum_x[G:\operatorname{Stab}_G(x)].$$

这给出了一个划分方式；它在下文会被略加解释。

$Proof.\quad$前两条的意义是明显的。对于第三条，设 $hx=x$，直接验证得 $ghg^{-1}gx=gx$。对于第四条，考察其轨道分解以及第二条引理给出的同构。$\square$

由此可以看出 $x,y$ 是否属于同一轨道可作为等价类划分的依据。相应的商集记作 $G\backslash X$，称为轨道空间。对于右作用，轨道空间对称地记作 $X/G$。

Burnside 引理

接下来给出我们熟知的 Burnside 引理。它给出了这样一个事实：轨道个数 $=$ 所有 $g\text-$不动点数目的均值。

$\bf Theorem\;6.\,(Burnside)\quad$群 $G$ 作用在 $X$ 上的轨道个数为

\[\frac{1}{|G|}\sum\_{g\in G}|\psi\(g)|.\]

$Proof.\quad$考察有序对 $(g,x)$ 的个数，满足 $gx=x$。一方面，它是 ${\large\sum\limits_{\tiny g!!!!\in!!!!G}\normalsize

\psi(g)

}$；另一方面，它是
\[\sum\_{x\in X}\operatorname{Stab}\_G\(x)=\sum\_{x\in X}|G|/|Gx|,\]

这是因为存在同构 $G/\operatorname{Stab}_G(x)\rightarrow Gx$。由此可得

\[\frac{1}{|G|}\sum\_{g\in G}|\psi\(g)|=\sum\_{x\in X}\frac{1}{|Gx|}=\sum\_{Gx}\sum\_{y\in Gx}\frac{1}{|Gy|}.\]

结合轨道分解的原理可知上式右端正是轨道数。$\square$

对称群及其计数

对于集合 $X$，其上的对称群是指全体双射 $X\xleftrightarrow{1:1}X$ 对映射合成构成的群，记作 $\mathfrak S_X$。双射 $\sigma\in\mathfrak S_X$ 称置换。

习惯上，我们常将 $X$ 等同于 $[n]:={1,2,\cdots,n}$，记 $\mathfrak S_{n}:=\mathfrak S_{[n]}$。

对称群的子群称为置换群。

对称群作用

对任意集合 $X$，显然有 $\mathfrak S_X$ 作用于 $X$ 上：$a:(\sigma,x)\mapsto\sigma(x)$。

另当留意到给定群 $G$ 在 $X$ 上的作用相当于给出了同态 $G\to\mathfrak S_X$，映 $g$ 为 $[x\mapsto gx]$。

对称群的一些例子

二面体群

$\bf Definition\;7.\quad$设 $a\in[n]$，定义

\[\begin{aligned} \sigma_i(a)&=a+i&\pmod n,\\ \tau_j(a)&=-a+j&\pmod n, \end{aligned}\]

并记

\[D_n=\{\sigma_i,\tau_j:i,j=1,2,\cdots,n\},\]

则 $D_n$ 是 $\mathfrak S_n$ 的一个子群，称其为 $[n]$ 上的二面体群。

$\bf Note.\quad$留意 ${\sigma_i:i=1,2,\cdots,n}$ 也是 $[n]$ 上的一个置换群，它是 $\sigma_1$ 生成的循环群。

自同构群

设 $G=(V,E)$ 是一个图，其上的一个自同构 $\sigma$ 是这样一个置换，满足

\[(x,y)\in V\iff(\sigma(x),\sigma(y))\in V,\quad\forall x,y\in V.\]

图的所有自同构在映射合成下构成群，称其为自同构群 $\operatorname{Aut}(G)$。

轮换与循环分解

为了更好地叙述对称群的性质，考虑如下引理。

$\bf Lemma.\quad$对 $X,Y$，存在自然嵌入

\[\mathfrak S_X\times\mathfrak S_Y\hookrightarrow \mathfrak S_{X\sqcup Y},\]

即 $\mathfrak S_n\times\mathfrak S_m\hookrightarrow \mathfrak S_{n+m}$。这是由置换挪动的元素的不交决定的。$\square$

以下给出轮换的定义。

$\bf Definition\;6.\quad$设 $a_1,\cdots,a_m$ 是 $X$ 中相异的元素，$\mathfrak S_X$ 中的一个 $\boldsymbol{m\text -}$轮换 $(a_1\cdots a_m)$ 是指映射 $\sigma:X\to X$ 满足

\[\begin{aligned} \sigma(a_{i})&=a_{i+1},&i\in\mathbb Z/m\mathbb Z,\,\\ \sigma(x)&=x,&x\notin\{a_1,\cdots,a_m\}. \end{aligned}\]

称两个轮换 $(a_1 \cdots a_m),(b_1 \cdots b_n)$ 不交，如果 ${a_1,\cdots,a_m}\cap{b_1,\cdots,b_n}=\varnothing$。

接下来给出著名的循环分解定理。

$\bf Theorem\;7.$（循环分解）$\quad$每个 $\sigma\in\mathfrak S_X$ 都能被唯一表成不交的循环之积

\[\sigma=(a_1a_2\cdots)(b_1b_2\cdots)\cdots\]

$Proof.\quad$这无非是 $\sigma$ 生成的有限循环群 $\langle\sigma\rangle$ 下的轨道分解。$\square$

不难看到，以上的一个循环分解可对应于整数的一种分拆方式。我们藉此引入轮换型号的概念。

$\bf Definition\;8.\quad$设 $l_i(\sigma)$ 为 $\sigma\in\mathfrak{S}_n$ 的循环分解中 $i\text-$轮换的个数，则记 $\operatorname{type}(\sigma):=(l_1(\sigma),\cdots,l_n(\sigma))$ 为 $\sigma$ 的轮换型号；亦简记其为 $(l_1,\cdots,l_n)$。

对同型号置换的计数：Cauchy 公式

$\bf Theorem\;9.\;(Cauchy)\quad$对称群 $\mathfrak S_n$ 中型号为 $(l_1,\cdots,l_n)$ 的置换个数为

\[\frac{n!}{l_1!l_2!\cdots l_n!1^{l_1}2^{l_2}\cdots n^{l_n}}.\]

公式的证明

今有不交的集族满足：

  • 由 $l_1$ 个 $1\text-$集，$l_2$ 个 $2\text-$集，$\cdots$，$l_n$ 个 $n\text-$集共同组成。
  • 集族所有元素之交为 $[n]$。
  • 集合大小单调不降，但相同大小的集合间无顺序。
  • 集合内的元素有标号但无顺序。

设此般集族的组合类为 $\mathcal U$。

显然，两个集族 $S,T\in\mathcal U$ 是不同的，当且仅当存在至少一对数不在相同集合内的数，交换 $S$ 中这两个数可以得到 $T$；交换相同大小集合的位置和一个集合内部的元素后，$S$ 仍然是 $S$。

考虑将一个集族 $S\in\mathcal U$ 从左到右读出其中每个元素，如此可以得到 $n$ 的一个排列。

集合内任意交换元素的方案数为 $(1!)^{l_1}\cdots(n!)^{l_n}$，相同大小的集合间交换元素的方案数为 $l_1!\cdots l_n!$。因此按上述方法规则，对于单个集族 $S\in\mathcal U$，它能够生成的排列数量是

\[l_1!l_2!\cdots l_n!(1!)^{l_1}(2!)^{l_2}\cdots(n!)^{l_n}.\]

记这样生成的排列为 $\mathcal C_S$。根据上述讨论，不同的 $\mathcal C_S$ 是不交的。由此设组合类

\[\mathcal A:=\bigcup_{S\in\mathcal U}\mathcal C_S.\]

注意到存在如下双射：

  • $\mathcal A$ 中每一个元素可单射到 $\mathfrak S_n$。
  • 对任意 $\sigma\in\mathfrak S_n$，考察序列 ${\sigma(i)}_{1}^n$将其从左到右分出个 $l_1$ 段长度为 $1$ 的子区间，$l_2$ 个长度为 $2$ 的子区间，$\cdots$，$l_n$ 个长度为 $n$ 的子区间。将每个子区间都作为一个集合，这样能够唯一形成一个 $\mathcal U$ 中的集族。

由此可得

\[|\mathcal A|=|\mathfrak S\_n|=n!\,.\]

故而将 $[n]$ 分为 $l_1$ 个 $1\text-$子集，$l_2$ 个 $2\text-$子集，$\cdots$，$l_n$ 个 $n\text-$子集的方案数为

\[\frac{n!}{l_1!l_2!\cdots l_n!(1!)^{l_1}(2!)^{l_2}\cdots(n!)^{l_n}}.\]

而每个 $t\text-$子集能够形成 $(t-1)!$ 个轮换。因此得到型号为 $(l_1,\cdots,l_n)$ 的置换个数为

\[\frac{n!}{l_1!l_2!\cdots l_n!1^{l_1}2^{l_2}\cdots n^{l_n}}.\]

$\square$

轮换指标及其 OGF

接下来引入轮换指标的概念。

$\bf Definition\;10.\quad$设 $G$ 是一个 $n$ 元置换群，$G$ 的轮换指标是一个 $n$ 元多项式

\[P\_G\(x\_1,\cdots,x\_n)=\frac{1}{|G|}\sum\_{\sigma\in G}x\_1^{l\_1\(\sigma)}x\_2^{l\_2\(\sigma)}\cdots x\_n^{l\_n\(\sigma)}\]

以下给出轮换指标的一个例子。

$n$ 阶循环群的轮换指标

设 $\sigma=(12\cdots n)$，考察 $\sigma$ 生成的 $n$ 阶循环群 $\langle\sigma\rangle$ 的轮换指标。

若 $k\mid n$，则 $\sigma^k$ 是 $k$ 个 $\dfrac{n}{k}\text-$轮换之积。否则，若 $\gcd(k,n)=1$，则它是一个 $n\text-$轮换。

对于一般情形，设 $d=\gcd(k,n)$，则 $\sigma^k=\left(\sigma^d\right)^{\frac{k}{d}}$。显然 $\sigma^d$ 是 $d$ 个$\dfrac{n}{d}\text-$轮换之积；而 $\gcd!\left(\frac{n}{d},\frac{k}{d}\right)=1$，从而 $\sigma^k$ 就是 $d$ 个$\dfrac{n}{d}\text-$轮换之积。故而

\[l_i\!\left(\sigma^k\right)=\begin{cases} 0,&i\neq \dfrac{n}{\gcd(k,n)},\\ \gcd(k,n),&i=\dfrac{n}{\gcd(k,n)}. \end{cases}\]

于是

\[\,\quad\qquad\qquad\begin{aligned} \quad\quad P_{\langle\sigma\rangle}(x_1,\cdots,x_n)&=\frac{1}{n}\sum_{k=1}^n\left(x_{n/\gcd(k,n)}\right)^{\gcd(k,n)}=\frac{1}{n}\sum_{d\mid n}\varphi(d)x_{d}^{n/d}.\qquad\qquad\qquad\blacksquare \end{aligned}\]

对称群轮换指标的 OGF

现在我们考察对称群轮换指标的 OGF，即 $\sum_{n\geqslant 0}P_{\mathfrak S_n}(x_1,\cdots,x_n)z^n$。

$\bf Theorem\;11.\quad$对称群轮换指标的 OGF 为

\[\sum_{n=0}^{\infty}P_{\mathfrak S_n}(x_1,\cdots,x_n)z^n=\prod_{t=0}^{\infty}\exp\!\left(\frac{x_t}{t}z^t\right)=e^{\frac{x_1}{1}z+\frac{x_2}{2}z^2+\cdots+\frac{x^n}{n}z^n+\cdots}.\]

$Proof.$

\[\begin{aligned} \;\qquad\,\;\quad\qquad\qquad\sum_{n=0}^{\infty}P_{\mathfrak S_n}&(x_1,\cdots,x_n)z^n\\&=\sum_{n=0}^{\infty}\left(\sum_{l_1+2l_2+\cdots+nl_n=n}\frac{x_1^{l_1}x_{2}^{l_2}\cdots x_{n}^{l_n}}{l_1!l_2!\cdots l_n!1^{l_1}2^{l_2}\cdots n^{l_n}}\right)z^n\\ &=\sum_{n=0}^{\infty}\sum_{l_1+2l_2+\cdots+nl_n=n}\prod_{t=0}^{n}\frac{1}{l_{t}!}\left(\frac{x_t}{t}z\right)^{l_t}\\ &=\sum_{l_1,l_2,\cdots,l_n,\cdots}\prod_{t=0}^{\infty}\frac{1}{l_{t}!}\left(\frac{x_t}{t}z\right)^{l_t}=\prod_{t=0}^{\infty}\sum_{l_t=0}^{\infty}\frac{1}{l_{t}!}\left(\frac{x_t}{t}z\right)^{l_t}\\ &=\prod_{t=0}^{\infty}\exp\!\left(\frac{x_t}{t}z^t\right)=e^{\frac{x_1}{1}z+\frac{x_2}{2}z^2+\cdots+\frac{x^n}{n}z^n+\cdots}.\qquad\quad\qquad\qquad\qquad\quad\;\square \end{aligned}\]

Pólya 计数定理

染色集上的作用

下面给出染色集的概念。

$\bf Definition\;12.\quad$设 $A,C$ 为 $n\text-$集合和 $m\text-$集合，记积集 $C^A:={f\mid f:A\to C}$，则称 $f\in C^A$ 为一种染色，并称 $c\in C$ 为一种颜色。

下面构造积集 $C^A$ 上的群作用。设 $G$ 是 $A$ 上的一个置换群，它可以诱导出一个 $G$ 在 $C^A$ 上的作用。考察

\[a(g,f)=f\circ g^{-1},\qquad g\in G,\,f\in C^A.\]

容易验证这般构造的确实是一个作用。在这个作用下，同属于一个轨道的染色 $f$ 被认为是等价的。因此，轨道个数就是互不等价的染色方案的数目。

Pólya 定理及其证明

$\bf\;Theorem\;13.\;(Pólya)\quad$设 $A,C$ 为 $n\text-$集合和 $m\text-$集合，设 $G$ 是 $A$ 上的置换群，设 $\mathcal F$ 为 $G$ 作用在 $C^A$ 上的轨道集合，则

\[|\mathcal F|=P\_{G}\(m,m,\cdots,m).\]

定理的证明

首先来看下面这个引理。

$\bf Lemma.\quad$设 $\operatorname{type}(g)=(l_1(g),\cdots,l_n(g))$ 为 $g$ 的轮换型号，则

\[\varphi\(g)=|C|^{l\_1\(g)+\cdots+l\_n\(g)}.\]

$Proof.\quad$不动点 $f\in C^A$ 要在 $g$ 的每一个轮换内部分别取相同值，而每一个轮换的取值都有 $

C

$ 种。$\square$

从而由 Burnside 引理可得

\[\begin{aligned} |\mathcal F|&=\frac{1}{|G|}\sum\_{g\in G}|\psi\(g)|\ &=\frac{1}{|G|}\sum\_{g\in G}|C|^{l\_1\(g)}|C|^{l\_2\(g)}\cdots|C|^{l\_n\(g)}\ &=P_{G}(m,m,\cdots,m). \end{aligned}\]

$\square$

Pólya 定理的一些例子

$\bf Example.\quad$求将苯环的六个氢原子中若干个（可以为 $0$）取代为甲基后所得的不同分子的种类数。

此处的置换群是二面体群 $D_6$。经计算得

\[P_{D_6}(x_1,x_2,\cdots,x_n)=\frac{1}{12}\!\left(x_1^6+3x_1^2x_2^2+4x_2^3+2x_3^2+x_6^1\right),\]

从而结果是 $P_{D_6}(2,2,\cdots,2)=2$。$\blacksquare$

$\bf Example.\quad$直接验证得正方形染色的置换群为四阶循环群，其染色方案数是

\[P_{C_4}(2,2,2,2)=\frac{1}{2}\big(2^4+2^2+2\cdot 2\big)=6.\]

$\bf Example.\quad$求用 $m$ 种颜色给长度为 $n$ 的圆周染色得到的不同可重圆周排列的方案数 $C_m(n)$。（P4980）

置换群 $G$ 就是由 $n\text-$轮换 $(12\cdots n)$ 生成的 $n$ 阶循环群，从而

\[\begin{aligned} C_m(n)&=P_{\langle(12\cdots n)\rangle}(m,m,\cdots,m)=\frac{1}{n}\sum_{d\mid n}\varphi(d)x_{m}^{m/d}. \end{aligned}\]

$\bf Example.\quad$第一类斯特林数的幂转换公式（P5408）与可重集组合问题。

设可重集 $S$ 有 $x$ 种元素，每种元素皆有无限个。则其间不同的 $n\text-$子集个数可视作一个集合 $A\to B$ 的映射，其中 $A$ 中元素全部相同，$B$ 中元素各自不同，$

A

=n,

B

=x$。经典地，它是
\[\binom{n+x-1}{n}.\]

考虑

\[B^{[n]}:=\{f\mid f:[n]\to B\},\]

则一个映射恰对应 $\mathfrak S_n$ 作用于积集 $B^{[n]}$ 的一条轨道。从而映射个数是

\[P_{\mathfrak S_n}(x,x,\cdots,x)=\frac{1}{n!}\sum_{\sigma\in\mathfrak S_n}x^{k(\sigma)}=\frac{1}{n!}\sum_{k=0}^n{n\brack k}x^k，\]

从而

\[\begin{aligned} \binom{n+x-1}{n}&=\frac{1}{n!}\sum_{k=0}^n{n\brack k}x^k，\\ \Longrightarrow\qquad x^{\overline n}&=\sum_{k=0}^n{n\brack k}x^k. \end{aligned}\]

带权的 Pólya 定理

设 $G$ 作用于 $X$，对于 $x\in X$，定义 $w(x)$ 为其权函数。当 $\forall y\in Gx$ 有 $w(y)=w(x)$ 时，又可将权函数记作 $w(Gx)$，视作对于一个轨道的权函数。

对于染色集上的作用，我们做一些额外的补充。设 $G$ 作用于 $A$，我们上面已经说明由此可诱导一个 $G$ 在 $C^A$ 上的作用。下面我们将说明 $C$ 上的一个权函数也可顺势诱导出 $C^A$ 上的权函数。

对于 $f\in C^A$，定义

\[w(f)=\prod_{a\in A}w(f(a)).\]

注意到当映射 $f_1,f_2$ 等价时，存在 $g\in G$ 使得 $f_2=f_1\circ g^{-1}$，从而

\[w(f_2)=\prod_{a\in A}w(f_2(a))=\prod_{a\in A}w\big(f_1\big(g^{-1}(a)\big)\big)=w(f_1),\]

故此般定义对于轨道而言是良好的：它在同一轨道上取相同的常数值。设 $\mathcal F$ 为 $G$ 作用于积集 $C^A$ 的轨道之集合，下面给出著名的带权 Pólya 定理。

$\bf Theorem\;14.\;(Pólya)\quad$设 $w$ 是 $C$ 上的一个权函数，并按如上方法得到 $C^A$ 上的权函数。则它也是 $\mathcal F$ 上的权函数，且有

\[\sum_{F\in\mathcal F}w(F)=P_G\left(\sum_{c\in C}w(c),\sum_{c\in C}w(c)^2,\cdots,\sum_{c\in C}w(c)^n\right).\]

定理的证明

我们先来看 Burnside 定理的带权形式；然后利用该引理，我们将证明 Pólya 定理。

带权 Burnside 定理

下面给出对轨道的权之和计数的带权 Burnside 引理。

$\bf Theorem\;15.\;(Burnside)\quad$设 $O_1,\cdots,O_N$ 是群 $G$ 作用于 $X$ 的全部轨道；设 $w$ 为其上的一个权函数，它对于同一轨道具有相同的常数值。则

\[\sum\_{i=1}^Nw\(O\_i)=\frac{1}{|G|}\sum\_{g\in G}\sum\_{x\in\varphi\(g)}w\(x).\]

$Proof.$

\[\begin{aligned} \qquad\qquad\qquad\qquad\qquad\quad\;\sum\_{i=1}^Nw\(O\_i)&=\sum\_{x\in X}\frac{w\(x)}{|O\_x|}=\frac{1}{|G|}\sum\_{x\in X}|G\_x|w\(x)\ &=\frac{1}{|G|}\sum\_{x\in X}|G\_x|\sum\_{g\in G\_x}1\ &=\frac{1}{|G|}\sum\_{g\in G}\sum\_{x\in\varphi\(g)}w\(x).\qquad\qquad\qquad\qquad\qquad\qquad\quad\qquad\square \end{aligned}\]

余下的工作

设 $k=l_1(g)+l_2(g)+\cdots+l_n(g)$。对任意 $(c_1,\cdots,c_k)\in C^k$，设 $f_{c_1,\cdots,c_k}$ 为 $C^A$ 中在符号集 $A_i$ 中取常数值 $c_i$ 的映射。则

\[w\(f\_{c\_1,\cdots,c\_k})=\prod\_{a\in A}w\(f\_{c\_1,\cdots,c\_k}\(a))=\prod\_{i=1}^kw\(c\_i)^{|A\_i|},\]

从而

\[\begin{aligned} \sum\_{f\in\psi\(g)}w\(f)&=\sum\_{\(c\_1,\cdots,c\_k)\in C^k}w\(f\_{c\_1,\cdots,c\_k})=\sum\_{\(c\_1,\cdots,c\_k)\in C^k}\prod\_{i=1}^kw\(c\_i)^{|A\_i|}\ &=\prod\_{i=1}^k\sum\_{c\in C}w\(c)^{|A\_i|}=\prod\_{j=1}^n\left\(\sum\_{c\in C}w\(c)^j\right)^{l\_j\(g)}, \end{aligned}\]

其中最后一个等号是由于 $

A_1

,\cdots,

A_k

$ 中等于 $l_j(g)$ 的恰有 $j$ 个。故运用带权的 Burnside 引理，得
\[\begin{aligned} \sum\_{F\in\mathcal F}w\(F)&=\frac{1}{|G|}\sum\_{g\in G}\sum\_{f\in\varphi\(g)}w\(f)\ &=\frac{1}{|G|}\sum\_{g\in G}\prod\_{j=1}^n\left\(\sum\_{c\in C}w\(c)^j\right)^{l\_j\(g)}\ &=P_G\left(\sum_{c\in C}w(c),\sum_{c\in C}w(c)^2,\cdots,\sum_{c\in C}w(c)^n\right). \end{aligned}\]

有限制的染色同构计数

有时我们会遇到这样一类染色问题，即不仅有置换群作用于染色的对象上，而且还要求每种颜色 $c_i$ 恰好给 $k_i$ 个元素染色。这就需要以下定理。

$\bf Theorem\;16.\quad$设 $C={c_1,\cdots,c_m}$，$G$ 为 $n\text-$集合上的一个置换群。对于 $k_1+\cdots+k_m=n$ 的非负整数 $k_1,\cdots,k_m$，记 $N(k_1,\cdots,k_m)$ 为 $C^A$ 中恰把 $A$ 中的 $k_i$ 个元素映成 $c_i$ 的轨道条数，则

\[P_G\left(\sum_{i=1}^mx_i,\sum_{i=1}^mx_i^2,\cdots,\sum_{i=1}^mx_i^n\right)=\sum_{k_1+\cdots+k_m=n}N(k_1,\cdots,k_m)x_1^{k_1}x_2^{k_2}\cdots x_m^{k_{m}},\]

换言之，限制为 $(k_1,\cdots,k_m)$ 的映射轨道 $N(k_1,\cdots,k_m)$ 的数量由下式决定：

\[N(k_1,\cdots,k_m)=\left[x_1^{k_1}x_2^{k_2}\cdots x_m^{k_{m}}\right]P_G\left(\sum_{i=1}^mx_i,\sum_{i=1}^mx_i^2,\cdots,\sum_{i=1}^mx_i^n\right).\]

$Proof.\quad$设 $\mathcal X:={x_1,x_2,\cdots,x_k}$ 为形式变元集，定义权函数 $w(c_i)=x_i$。则 $f$ 恰把 $A$ 中的 $k_i$ 个元素映成 $c_i$ 的充要条件是

\[w(f)=x_1^{k_1}x_2^{k_2}\cdots x_m^{k_{m}},\]

故 $N(k_1,\cdots,k_m)$ 就是这样的轨道条数。一方面

\[\sum_{F\in\mathcal F}w(F)=\sum_{k_1+\cdots+k_m=n}N(k_1,\cdots,k_m)x_1^{k_1}x_2^{k_2}\cdots x_m^{k_{m}},\]

另一方面

\[\sum_{F\in\mathcal F}w(F)=P_G\left(\sum_{i=1}^mx_i,\sum_{i=1}^mx_i^2,\cdots,\sum_{i=1}^mx_i^n\right),\]

由此就得到 $N(k_1,\cdots,k_m)=\left[x_1^{k_1}x_2^{k_2}\cdots x_m^{k_{m}}\right]P_G\left(\sum\limits_{i=1}^mx_i,\sum\limits_{i=1}^mx_i^2,\cdots,\sum\limits_{i=1}^mx_i^n\right)$。$\square$

$\bf Example.\quad$求苯的二甲基取代物个数。

我们已经知晓置换群是 $D_6$。运用带权的 Pólya 定理得其结果是

\[\begin{aligned} \left[x_1^2x_2^4\right]P_{D_6}(x_1+x_2,x_1^2+x_2^2,\cdots,x_1^6+x_2^6)=3. \end{aligned}\]

无标号简单图计数（图同构计数，P4727）

一张图是一个集合对 $([n],E)$，其中边集 $E\subseteq D$，且

\[D=\binom{[n]}{2}.\]

有标号的简单图被定义为映射

\[\begin{aligned} f_E:\quad\; D&\longrightarrow\{0,1\},\\ \{i,j\}&\longmapsto\begin{cases} 1,&\{i,j\}\in E,\\ 0,&\{i,j\}\notin E. \end{cases} \end{aligned}\]

对于 $g\in\mathfrak S_n$，其诱导出 $D$ 上的置换是

\[\pi_g(\{i,j\})=\{g(i),g(j)\}.\]

记 $G_n={\pi_g:g\in\mathfrak S_n}$，由 Pólya 定理，$n$ 个点的无标号简单图数量是

\[P_G(2,2,\cdots,2).\]

${\bf Theorem\;17.\quad}n$ 阶无标号简单图的个数是

\[\sum_{l_!+2l_2+\cdots+nl_n=n}\frac{2^{N(l_1,\cdots,l_n)}}{l_1!\cdots l_n!2^{l_1}\cdots2^{l_n}},\]

其中

\[N(l_1,\cdots,l_n)=\frac{1}{2}\left(\sum_{s,t}l_sl_t\gcd(s,t)-\sum_{2\nmid s}l_s\right).\]

组合类的 Cycle 构造

下面我们运用带权的 Burnside 引理证明

\[\begin{aligned} \mathcal A=\text{C}{\small\text{YC}}(\mathcal B)&:=\text{S}{\small\text{EQ}}(\mathcal B)/\mathbf S\\&\Longrightarrow A(z)=\sum_{k=1}^{\infty}\frac{\varphi(k)}{k}\log\frac{1}{1-B(z^k)}. \end{aligned}\]

证明

设 $\mathcal A=\text{C}{\small\text{YC}}(\mathcal B)$，那么

\[\mathcal A\cong\sum_{n\geq1}\mathcal B^n/\mathbf S,\]

其中 $\mathbf S$ 是 $\langle\sigma\rangle$ 轨道等价类。我们要证明

\[A(z)=\sum_{k=1}^{\infty}\frac{\varphi(k)}{k}\log\frac{1}{1-B(z^k)}.\]

求 $\sum_{i=1}^Nw(O_i)$，其中 $\langle\sigma\rangle$ 作用于 $\mathcal B^n$ 上。运用带权 Burnside 引理

\[\sum_{i=1}^Nw(O_i)=\frac{1}{n}\sum_{k=1}^n\sum_{(\beta_i)_{i\leq n}\in\psi(\sigma^k)}w((\beta_i)_{i\leq n}),\]

而 $\sigma^k$ 是 $(k,n)$ 个 $n/(k,n)\text -$轮换之积，所以就有

\[\sum_{i=1}^Nw(O_i)=\frac{1}{n}\sum_{k=1}^nB\big(z^{n/(k,n)}\big)^{(k,n)}=\frac{1}{n}\sum_{d\mid n}\varphi(d)B\big(z^d\big)^{n/d}.\]

于是

\[\begin{aligned} A(z)&=\sum_{n=1}^{\infty}\frac{1}{n}\sum_{d\mid n}\varphi(d)B\big(z^d\big)^{n/d}\\ &=\sum_{d=1}^{\infty}\frac{\varphi(d)}{d}\sum_{n\geq 1}\frac{B\big(z^d\big)^{n}}{n}\\ &=\sum_{d=1}^{\infty}\frac{\varphi(d)}{d}\log\frac{1}{1-B(z^d)}. \end{aligned}\]