「何通りある？」○○順列まとめ

上野竜生です。○○順列についてまとめてみました。

順列

まず左端は1～nまでn個選べるのでn通り。

2番目は1番目に選んだもの以外のn-1個から選ぶのでn-1通り。

3番目は1,2番目以外から選ぶのでn-2通り。

・・・

最後n番目は残った1個からしか選べないので1通り。よって

n×(n-1)×(n-2)×・・・×2×1=n!通り

重複順列

１番左はn通り。
2番目もn通り
・・・
最後(r番目)もn通り。

よってn×n×・・・×n(r個)=n^r通り

円順列

円形に並べるということは回転して同じになれば同じとみなす。

「１」を真上に持ってきて考える。

「１」の右隣りにおく文字①は「２」～「n」までのn-1通り

その右隣りはn-1個から①で使った1個を除いたn-2通り

・・・

という風にすると(n-1)!とわかる。

じゅず順列

数珠は左右ひっくり返して同じになるものも同じとみなす。

よって左右分2回ずつ数えてることになる。（「１」の右隣りにＡ，その右にＢ・・・とおいているのと「１」の左隣にＡ，その左にＢ・・・とおいてるのを２回数えてるがじゅず順列では１回しか数えてはいけない）

なので円順列を2で割って得られる。

同じものを含むとき

このタイプは説明することもできますが覚えるほうが手っ取り早いです。詳しくは二項定理のページ（多項定理）で説明しています。答えのみを示します。

単純に9個をならべるのが9!通り。同じ数字がm個あればm!個ずつ重複して数えてるのでm!で割っていくことになります。まず1が4つあるので4!で割ります。次に2が3個あるのでさらに3!で割ります。最後に3も2個あるので2!で割ります。これを1つの分数で書いたものがこの公式です。

一定の順序を含む場合

完全順列

「１」「２」・・・「n」を並べ替えるとき左からi番目がiではないものを完全順列という。つまり，n択の記号問題n問に解答し（同じ記号を二度以上使わない）全部はずれるやり方である。

「１２４３」は１が左から１番目だから完全順列ではない。
「２４３１」は３が左から３番目だから完全順列ではない。
「３４１２」はどれも異なるので完全順列である。

完全順列の個数をa_nとすると次の漸化式が成り立つ。

基本的に覚えなくていいです。ほぼ出ません。ただしn=5ぐらいまでの具体的な数値で出題されることはまれにあるのでn=5までの場合において結果を書きだします。

n≦4なら(完全とは限らない)順列を書きだしてもn!≦24までなので全部書きだせばＯＫです。n=5が厄介で，この場合の問題を見たことがあります。漸化式から導くのではなく樹形図から全部書きだしてください。数え漏れが怖いですが，とりあえず44通りは頭のどこかに入れておいたほうがいいでしょう。そして漸化式の形よりa_nは必ずn-1の倍数になるということも知っていれば検算に使えるでしょう。

とりあえずここまででマニアックなものも含めてかなり順列は理解できたと思います。最後に例題を１つ紹介します。公式に代入するだけで終わりの問題ではなく，ここまでの考え方が問われる良問です。

例題（同じものを含む円順列）

円形に並べる基本は1つの文字を真上に固定でしたね。単純にＡを固定したいところですがＡは3つもあり，固定したところ以外にもＡが出てきて少し面倒です。確実なのは１つしかない「Ｃ」か「Ｄ」を固定するのがいいでしょう。解答では「Ｄ」を固定します。回転させて同じになるものは１つと数えるのが円順列の厄介なところですが１つを固定すると回転を封じることができ，単純な順列の問題になります。