なかけんの数学ノート

【応用】数珠順列

ここでは、数珠順列を考えます。円順列では「グルグル回転させて同じになるものを同一視」しましたが、数珠順列では、さらに「ひっくり返して同じになるものも同一視」という条件が入ります。詳しく見ていきましょう。

[広告]

数珠順列

例題
青、黄、黒、緑、赤の5色のビーズが1つずつある。この5つのビーズを使ってブレスレットを作る場合、何通りの作り方があるか。

「ビーズを使ったブレスレット」というのは、次のようなものです。


これは少し材料が多いですが、ビーズの真ん中に糸を通してつないで作る点は同じです。

これは、円順列と似ています。円順列では、「グルグル回転させて同じものは、同一視する」という点に注意が必要でした。今の場合も同様で、

  • 青黄黒緑赤と並べて、1番目と5番目が隣り合うように、時計回りにつなぐ
  • 黄黒緑赤青と並べて、1番目と5番目が隣り合うように、時計回りにつなぐ
  • 黒緑赤青黄と並べて、1番目と5番目が隣り合うように、時計回りにつなぐ
  • 緑赤青黄黒と並べて、1番目と5番目が隣り合うように、時計回りにつなぐ
  • 赤青黄黒緑と並べて、1番目と5番目が隣り合うように、時計回りにつなぐ

の5つが同じ結果になります。5つのものを並べ( $5!$ 通り)てから、それぞれ5つのものを同一視するから 5で割る必要があります。

しかし、実は、今の場合は、「時計回りにつなぐ」かわりに「反時計回りにつなぐ」としても、同じブレスレットが出来上がります。ひっくり返せば同じになりますね。よって、上の5つに加え

  • 青黄黒緑赤と並べて、1番目と5番目が隣り合うように、反時計回りにつなぐ
  • 黄黒緑赤青と並べて、1番目と5番目が隣り合うように、反時計回りにつなぐ
  • 黒緑赤青黄と並べて、1番目と5番目が隣り合うように、反時計回りにつなぐ
  • 緑赤青黄黒と並べて、1番目と5番目が隣り合うように、反時計回りにつなぐ
  • 赤青黄黒緑と並べて、1番目と5番目が隣り合うように、反時計回りにつなぐ

も同じ結果になることがわかります。つまり、同じものを10回ダブって数えることになるんですね。

「回転させて同じになるもの」と「ひっくり返して同じになるもの」をそれぞれ同一視した結果、「1列に並べてからブレスレットを作る」場合、同じものを10回数えることになるので\[ 5! \div 10 = 12 \]通り、と求められます。

一般に、「回転して同じになるもの」「ひっくり返して同じになるもの」を同一視する並べ方を、数珠順列(じゅずじゅんれつ、bracelet permutation)といいます。言いにくいですね。ちなみに、数珠とは、次のようなものです。


英語では、「ブレスレット順列」ということもありますが、どちらにしても、「回転して同じになるもの、ひっくり返して同じになるもの」を同一視する、という並べ方を指しています。

n 個の異なるものを使った数珠順列の総数は、例題での考え方を一般化することができます。まず、1列に並べる方法が $n!$ 通り。そのうち、回転して同じになるものを同一視するので、同じものを n 回数えてしまっていることから n で割ります。ここは円順列と同じですね。違うのは、「ひっくり返して同じになるもの」も同一視する点です。このため、さらに $2$ で割ります。これで求めることができます。

まとめると、こうなります。

数珠順列
$n\geqq 2$ のとき、異なる n 個のものを使った数珠順列の総数は、 $\displaystyle \frac{(n-1)!}{2}$ 通り。

$n=1$ のときだけ注意が必要です。 $n=1$ のときは、並べ方は1通りです。上の式にそのまま入れてしまうと、 $\displaystyle \frac{1}{2}$ 通りとなり、おかしいことになるので、上では $n\geqq 2$ のときだけ、としています。

なぜ $n=1$ のときに2で割るとおかしなことになるかというと、このときは、「ひっくり返して同じになるものを2回数えていない」からです。ダブルカウントしていないので、2で割るとおかしな結果になってしまいます。

円順列と数珠順列の違い

円順列と数珠順列は、似ていますが違うところもあります。

どちらも、「回転して同じになるものを同一視する」という点が同じです。丸テーブルに座るとか、みんなで輪になるとか、正多角形の頂点を選ぶとか、ネックレスを作るとか、どういう設定かによりますが、「回転して同じになるものを同一視する」という点は同じです。

違いは、「ひっくり返して同じになるものを同一視するかどうか」です。よって、ひっくり返せるかどうか、ひっくり返したときに見分けがつくかどうか、を考えます。

丸テーブルはひっくり返せません。輪になった人たちもひっくり返せません。正多角形は裏返せるかどうかは、問題の設定によるでしょう。ネックレスは、ひっくり返せると考えるのが普通です。

ひっくり返せない場合は、円順列(2で割らない)であり、ひっくり返して同じものを同一視する場合は、数珠順列(最後に2で割る)です。

問題文を読んで「何が同一視できるのか」を把握し、複数回ダブって数えている場合には、それを除外する、というのが基本的な流れです。

おわりに

ここでは、数珠順列について見てきました。入試ではそんなに出ないですが、「何を同一視するか」を考えるにはいい例です。

[広告]
対象者: 数学A
分野: 場合の数と確率
トピック: 場合の数
レベル: 応用
キーワード: 場合の数
更新日:2017/02/04