1. 高校数学の美しい物語
  2. 同じものを含む円順列の裏技公式

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

更新日時 2021/03/07

同じものを含む円順列の個数はバーンサイドの公式を使って求めることができる。

円順列の個数=1GgGϕ(g)=\dfrac{1}{|G|}\displaystyle\sum_{g\in G}\phi(g)

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

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

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

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

  • バーンサイドの公式を用いて解く

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

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

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

例題1

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

例えば図において,上の並べ方は区別しますが下の2つの並べ方は同じとみなすわけです。

円順列の問題

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

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

バーンサイドの公式を用いて解く

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

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

上記の例だと,操作は「何もしない,6060^{\circ} 回転,120120^{\circ} 回転 \cdots300300^{\circ} 回転」の6通りなので G=6|G|=6 です。

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

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

バーンサイドの公式

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

  • 「何もしない」操作で不動なのは 6464 通り全部
  • 6060^{\circ} 回転」「300300^{\circ} 回転」で不動なのはそれぞれ 22 通り(全部黒か全部白)
  • 120120^{\circ} 回転」「240240^{\circ} 回転」で不動なのはそれぞれ 22=42^2=4 通り(図に示す)→注
  • 180180^{\circ} 回転」で不動なのは同様に考えて 23=82^3=8 通り

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

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

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

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

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

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

バーンサイドの公式の証明には群論を用います。大学に入ってからのお楽しみということでm(__)m

人気記事
  1. 高校数学の美しい物語
  2. 同じものを含む円順列の裏技公式