1. バーンサイドの補題

有限群 $G$ が有限集合 $X$ に作用しているとき、軌道の数 $\lvert X/G\rvert$ について以下が成り立つ。

$$ \lvert X/G \rvert = \frac{1}{\lvert G \rvert} \sum_{g\in G} \lvert X^g\rvert $$

ここで、$X^g = \{ x\in X \mid g\cdot x = x\}$ である。

$X$ よりも $G$ の方が小さいときに有効($G$ が対称群とかの大きい群の場合は使いにくい気がする)

2. バーンサイドの補題の使用例

動かしたら一致するものを同一視する場合は軌道の数を数えればよい。

2.1 立方体の回転で区別しない数え上げ

ABC 198 F - Cube

Untitled

2.2. 円順列