同じものを含む円順列の裏技公式

このページで解説するのは以下のような問題です。

例えば図において，3つの並べ方があるように見えますが，下の2つの並べ方は同じとみなします。

同じものを含まない $n$ 個の円順列の個数は $(n-1)!$ 通りで，数珠順列の個数は $\dfrac{(n-1)!}{2}$ と簡単に求めることができます。しかし，同じものを含むと一気に難しくなります。

一般的な正攻法はただただ数え上げる手法です。実際に例題1を数え上げで解くと，14通りになります（使う黒石の数で場合分けして頑張って数える）。

まず，バーンサイドの公式中の記号を解説します。

$G$ というのは同一のものか判定するための「操作」の集合を表します。何もしないという操作（恒等置換）も含まれます。

上記の例だと，操作は「何もしない，$60^{\circ}$ 回転，$120^{\circ}$ 回転 $\cdots$ ，$300^{\circ}$ 回転」の6通りなので $|G|=6$ です。

次に $\phi(g)$ について。

各操作 $g$ に対して「操作をほどこしても変わらない並べ方の個数」つまり，不動点の数を表します。ここでいう「並べ方」は重なりを無視した全ての並べ方を表しており，簡単に数えられます。

上記の例で考えてみます。 重なりを無視した全ての数え方は $2^6=64$ 通り。そのうち，

• 「何もしない」操作で不動なのは $64$ 通り全部
• 「$60^{\circ}$ 回転」「$300^{\circ}$ 回転」で不動なのはそれぞれ $2$ 通り（全部黒か全部白）
• 「$120^{\circ}$ 回転」「$240^{\circ}$ 回転」で不動なのはそれぞれ $2^2=4$ 通り（下図）→注
• 「$180^{\circ}$ 回転」で不動なのは同様に考えて $2^3=8$ 通り

よって，求める場合の数はバーンサイドの公式より，

$\dfrac{1}{6}(64+2+2+4+4+8)=14$ 通りとなりさきほど求めた答えと一致している。

注：「図より $4$ 通り」という説明でもよいのですが，$2^2$ のように数えたのは以下の理由によります。$6$ つの位置を順番に $ABCDEF$ と書きます。$120^{\circ}$ 回転で不変のとき，$A,\:C,\:E$ の色は同じで，$B,\:D,\:F$ の色も同じなのでそれぞれどちらの色に塗るかで $2^2=4$ 通りあります。

同様に，$180^{\circ}$ 回転で不変なのは，$A,D$ が同じ色，$B,E$ も同じ色，$C,F$ も同じ色なのでそれぞれどちらの色に塗るかで $2^3$ 通りとなります。

• 慣れれば慣れるほど，複雑になればなるほどバーンサイドの公式が輝きます。
• 入試では数え上げで解いて時間が余ればバーンサイドの公式を用いて検算しましょう。両者の答えが一致すればかなり強い確信を持てます。
• 数珠順列の場合は上記の「操作」に回転だけでなく折り返しも考える事になります。