2014/05/24

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

分野: 場合の数  レベル: 最難関大学

同じものを含む円順列の個数はバーンサイドの公式を使って求めることができる。
円順列の個数$=\dfrac{1}{|G|}\displaystyle\sum_{g\in G}\phi(g)$


バーンサイドの補題,バーンサイドの定理,コーシー・フロベニウスの定理とも呼ばれます。記号の説明はおいおいしていきます。

一般的なバーンサイドの公式は難しい(大学で学ぶ群論を用いる)ので,ここでは円順列の問題の場合に限定して説明します。円順列の場合に理解できればより難しい問題(数珠順列,立方体の塗り分け問題など)に応用することもできる素敵な定理です。

まずは問題設定を確認しつつ記号を説明していきます。

同じものを含む円順列の問題

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

例題1

黒石と白石を合わせて6個。円形に並べる並べ方は何通りあるか。ただし,回転により重なるものは同じものとみなす。

例えば図において,上の並べ方は区別しますが下の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$ 通りとなります。

バーンサイドの公式に関するコメント

  • 慣れれば慣れるほど,複雑になればなるほどバーンサイドの公式が輝きます。
  • 入試では数え上げで解いて時間が余ればバーンサイドの公式を用いて検算しましょう。両者の答えが一致すればかなり強い確信を持てます。
  • 数珠順列の場合は上記の「操作」に回転だけでなく折り返しも考える事になります。
バーンサイドの公式の証明には群論を用います。大学に入ってからのお楽しみということでm(__)m
分野: 場合の数  レベル: 最難関大学