円順列と数珠順列
本記事は,先にこちらの記事を読んでおくとより理解しやすいと思います。
さっそく例題からスタートします。
例題1
円卓の周りに席が席あります。A,B,C,D,Eの5人がこの席に人ずつ着席するとき,何通りの着席のしかたがありますか。ただし,つの席にはとくに違いはないものとします。
一直線に並べる順列と何か異なるでしょうか?
紙に書いて考えてみてください。
例題1の解答(?)
人でつくる順列の総数なので
(通り)。
……と,早合点してはいけません。
なぜなら例題1のように円形に並べる順列を考えるとき
回転させて同じになるものは,同じ順列として扱うからです。
このような性質をもつ順列を円順列といいます。
例題1は,たとえば次のように考えることができます。
まず人を一列に適当に並べ(この図ではA,B,C,D,Eの順)
両端の二人(この図ではAとE)が隣り合うように
人がテーブルを取り囲む形に移動します。
この方法で,ある順列を円順列に対応させます。
すると,回転させて同じになるものは同じ順列として扱うことに注意すれば
次のつの順列,A B C D E,B C D E A,C D E A B,D E A B C,E A B C Dは
すべて同じ順列になってしまうことがわかります。
通りすべての図で,テーブル周りに座った人が
Aから始めて時計回りにB,C,D,Eと並んでいることを確認してください。
これら通りを同じものとして扱うわけです。
このことから,つの円順列に対応する順列が通りずつ存在するとわかるので
人が円卓に着席するときの場合の数は
人でつくる順列の総数をで割った値になり
(通り)
と求めることができます。
一般に,異なる 個のものでつくる円順列の総数は
通り になります。
例題1の解答
つの円順列に対応する順列が通りずつ存在するので
人でつくる順列の総数をで割った値になります。
つまり, (通り)です。
では,例題1と似ていますが,次の問題はどうでしょう?
例題2
それぞれ異なる色のつの珠をつの円形になるように繋げてブレスレットをつくります。できるブレスレットは何通りあるでしょう。ただし種類の珠はいずれもちょうどつずつ使います。
もちろん例題1の考え方を参考にして良いです。
例題1と違うところはないか,考えてみましょう。
例題2は,たとえば次のように考えることができます。
まず,円形につくるということなので
ここは例題1と同様の考え方が使えそうです。
つの珠を円形に並べる場合の数は,円順列と考えて
(通り)。
しかし,ここで待ったをかけましょう。
例題1では席順を考えましたが,例題2ではブレスレットです。
円順列のように回転させられることに加えて裏返し(左右反転)が利きます。
裏返しにして同じになるものは,同じ順列とみなします。
このような性質をもつ順列を,数珠順列といいます。
左側はAから始めて時計回りに,右側はAから始めて反時計回りに
A,B,C,D,E,F,G,Hと並んでいることを確認してください。
そうすると,ある順列を裏返して同じになる順列は一つだけ存在するため
そのつを組にしてつとして数えれば
求めたい順列の総数は円順列のときのちょうど半分であるとわかります。
したがって,例題2の答えは
(通り)となります。
一般に,異なる 個のものでつくる数珠順列の総数は
通り になります。
例題2の解答
まずつの珠でつくる円順列を考えて
(通り)。
この中の順列に対して,裏返して同じものとみなせる順列がつだけ存在するため,このつをつの組として数えれば,求めたい順列の総数は先に求めた5040通りの半分とわかります。つまり,できるブレスレットは
(通り) あります。
補足
円順列の別の考え方を,次の記事で紹介しておきます。