OI 中的计数:本质不同的方案数

All one needs for mathematics is a pencil and paper.
- George Pólya

也许这会成为一个系列?我不知道。

关于树的一些计数方法,请参考51Nod1252: 桥与海港

置换

定义

一个集合 S (有限或无限)的置换是一个从 S 到它自己的双射。因此,置换可以被认为是个可以相互复合的函数,组成了置换群。

记号

Cauchy’s two-line notation

$$
\sigma=\left(\begin{matrix}
x_1 & x_2 & x_3 & \cdots & x_n\\
\sigma(x_1) & \sigma(x_2) & \sigma(x_3) & \cdots & \sigma(x_n)\\
\end{matrix}\right)
$$

很好理解,就是第一行每个输入 $x_i$ 对应的输出就是 $\sigma(x_i)$。

Cycle notation

由于上述记号实在是太过占空间,所以人们在上述记号的基础上发明了另一种记号。

由集合 S 中的某个元素 $x$ 开始,写下序列 $(x\ \sigma(x)\ \sigma(\sigma(x))\ \cdots)$ 直到回到 $x$ 的前一个元素。这表现了一个置换中的循环。

对于一个置换,我们将其可以记为其中所有的循环。比如:
$$
\left(\begin{matrix}
1 & 2 & 3 & 4 & 5 \\
2 & 5 & 4 & 3 & 1 \\
\end{matrix}
\right)
=\left(\begin{matrix}1 & 2 & 5\end{matrix}\right)\left(\begin{matrix}3 & 4\end{matrix}\right)
=\left(\begin{matrix}3 & 4\end{matrix}\right)\left(\begin{matrix}1 & 2 & 5\end{matrix}\right)
=\left(\begin{matrix}3 & 4\end{matrix}\right)\left(\begin{matrix}5 & 1 & 2\end{matrix}\right)
$$

运算

其实就是复合

设 $\sigma_{P}(x_i)$ 表示 $x_i$ 在置换 $P$ 中的对应输出,则有:
$$
Q\cdot P=\left(\begin{matrix}
x_1 & x_2 & x_3 & \cdots & x_n\\
\sigma_{P}(\sigma_{Q}(x_1)) & \sigma_{P}(\sigma_{Q}(x_2)) & \sigma_{P}(\sigma_{Q}(x_3)) & \cdots & \sigma_{P}(\sigma_{Q}(x_n))\\
\end{matrix}\right)
$$

可以说 $Q\cdot P=P\circ Q$,所以 $Q\cdot P\ne P\cdot Q$

类似求逆元。当然在置换中求逆很简单,只需要上下两行互换就行。【为什么……为什么会这样呢?到底是【打死。

即:
$$
P^{-1}=\left(\begin{matrix}
\sigma(x_1) & \sigma(x_2) & \sigma(x_3) & \cdots & \sigma(x_n)\\
x_1 & x_2 & x_3 & \cdots & x_n\\
\end{matrix}\right)
$$
或者说
$$
\left(\begin{matrix}x& \sigma(x)& \sigma(\sigma(x))& \cdots\end{matrix}\right)^{-1}=\left(\begin{matrix}\cdots& \sigma(\sigma(x))& \sigma(x)& x\end{matrix}\right)
$$

定义

一个群是一个集合 $G$ 和一个二元运算符 $\cdot$ 组成,必须满足以下四条规则,也被称作群公理。

  1. 封闭性
    $\forall a,b\in G,a\cdot b \in G$。
  2. 结合律
    $\forall a,b,c\in G,(a\cdot b)\cdot c=a\cdot(b\cdot c)$。
  3. 单位元
    $\exists e\in G,e\cdot a=a\dot e=a$ 且 $e$ 唯一。
  4. 逆元
    $\forall a\in G,\exists b\in G,a\cdot b=b\cdot a=e$。

群作用

定义

在集合 $X$ 上群 $G$ 作用 $\phi$ 是一个二元函数
$
\varphi:G\times X\rightarrow:(g,x)\mapsto\varphi(g,x)
$
满足以下两条公理。

  1. 单位元
    $\forall x\in X,\varphi(e,x)=x$。
  2. 兼容性
    $\forall g,h\in G,x\in X,\varphi(gh,x)=\varphi(g,\varphi(h,x))$

记号

$\varphi(g,x)$ 记作 $g\cdot x$。

轨道

定义

对于一个作用在集合 $X$ 上的群 $G$,$x\in X$ 的轨道是 $x$ 能通过群 $G$ 中的元素作用得到的元素的集合,记作 $G\cdot x$,所以有
$$G\cdot x=\{g\cdot x\ |\ g\in G\}$$。

集合 $X$ 的轨道是 $X$ 中所有元素的轨道的集合,记作 $X/G$。

不动点与稳定子集

对于一个作用在集合 $X$ 上的群 $G$,$x\in X$ 是 $g\in G$ 下的不动点当 $g\cdot x=x$,也叫做 $g$ 固定 $x$。

对于每一个 $x\in X$,定义 $G$ 关于 $x$ 的稳定子集为固定 $x$ 的所有 $G$ 中的元素的集合,即
$$G_x=\{g\in G\ |\ g\cdot x=x\}$$

置换群

元素是置换,运算是函数复合的群叫置换群。

Pólya 计数定理

接下来把话筒交给 Yonda