順列

並べ方の樹形図

4枚のカード $\fbox{A}$ ， $\fbox{B}$ ， $\fbox{C}$ ， $\fbox{D}$ から2枚のカードを引いて，これらを1列に 並べる場合の数は次のように求めることができる．

まず，1枚目のカードの取り方は，4枚のカードのどれを取ってもよいから4通りある．

そして，1枚目のカードが決まれば，2枚目のカードの取り方は，残りの3枚のカードの中から1枚取るから3通りある．

つまり，1枚目のカードの取り方4通りに対して，2枚目のカードの取り方が3通りに定まるから， 2枚のカードの並べ方は『積の法則』より

$4\times3=12$ 通り

となる．

右の図は，2枚のカードの並べ方12通りを樹形図と平図を用いて表したものである．

ここで，n個のものからr個とって並べる順列を定義しておこう．

上の例では， $_{4}\mathrm{P}_{2}=4\times3=12$ である．

区別する $n$ 個のものから $r$ 個取り出して1列に並べる順列の数 $_{n}\mathrm{P}_{r}$ は，上の例と同じように考えることができる．

1番目のものの取り方は $n$ 通りあり， 2番目のものの取り方はそのそれぞれに対して $n − 1$ 通りあり， 3番目のものの取り方はそのそれぞれに対して $n − 2$ 通りあり， $\cdots$ $r$ 番目のものの取り方はそのそれぞれに対して $n − (r − 1)$ 通りある．

したがって，『積の法則』より

と計算できることがわかる．

特に， $r$ が $n$ に等しいとき，つまり $r = n$ のときには， $_{n}\mathrm{P}_{n}=n(n-1)(n-2)\cdots\cdots3\cdot2\cdot1$ となる．右辺は1から $n$ までの すべての自然数の積であり，これを $n$ の階乗(factorial)といい，記号 $\boldsymbol{n!}$ で表す． つまり

である．

また， $r < n$ のとき， $_{n}\mathrm{P}_{r}$ の分母・分子に $(n − r)!$ をかけることにより

と変形なるので，分子は $n!$ で表すことができ

となる．

$r = n$ のとき，　$\eqref{zyunretunPrnokeisan2}$ は形式的に $_{n}\mathrm{P}_{n}=\frac{n!}{0!}$ と表せるが， $_{n}\mathrm{P}_{n} = n!$ となって欲しいので， $0! = 1$ と定めることにする． こうすれば， $\eqref{zyunretunPrnokeisan2}$ は $r = n$ のときにも成り立つ．

以上， $\eqref{zyunretunPrnokeisan1}$ ， $\eqref{zyunretunPrnokeisan2}$ をまとめると

吹き出し無題

よくあるまちがいとして， $_{n}\mathrm{P}_{0}=0$ としてしまうというのがある． 上の式によれば，

$_{n}\mathrm{P}_{0}=\dfrac{n!}{(n-0)!}=1$ である． このことは， $_{n}\mathrm{P}_{0}$ すなわち「区別する $n$ 個のものから $0$ 個取り出して1列に並べる場合の数」は， 「1個も並べない」という1通りである，と

こじつけ

で覚えてしまうとよい．

また， $\eqref{zyunretunPrnokeisan2}$ の $_{n}\mathrm{P}_{r}=\frac{n!}{(n-r)!}$ は，ただ計算上で成り立つだけでなく

とりあえず， $n$ 個の区別するものをすべて並べて $n!$ 通りの樹形図を作ってから，（左から $r$ 個のものにしか着目しないので）関係のない 右から $n − r$ 個の並べ方の違いについては無視するため， $(n − r)!$ 通りで1束にして数えたもの

と考えることもできる．このことの具体例を示すため，以下には $_{4}\mathrm{P}_{4}( = 4!)$ と $_{4}\mathrm{P}_{2}$ の対応を樹形図で表した． $_{4}\mathrm{P}_{2}$ 通りは， $_{4}\mathrm{P}_{4}$ 通りの順列において $(4 − 2)!$ 通りで割って1束にしたものであることを確認しよう．

$_{4}\mathrm{P}_{4}$ と $_{4}\mathrm{P}_{2}$ の樹形図

吹き出し無題

ものを並べる問題で，“隣り合う”ものを考える場合には，その隣り合うものをひとまとめにして考えるとよい．

$_{5}\mathrm{P}_{3}$ の定義は

「区別する5個のものから3個とりだして1列に並べるときの並べ方の総数」

であったが，これは以下に示すボールと箱のモデルを使って

「区別する3個のボールを，区別する5個の箱に多くても1個配る場合の総数」

といいかえることができる．

準備として，ボールは区別するので番号をつけ，それを①，②，③とし， 箱も区別するので番号をつけ，それを

としておく．

まず，ボール①を箱に配ることを考えると，箱は5つあるので5通りの場合がある．

次に，ボール②を箱に配ることを考えると，すでにボール①は箱に配られていて 残りの箱は4つあるので，4通りの場合がある．

さらに，ボール③を箱に配ることを考えると，すでにボール①と②は 箱に配られていて残りの箱は3つあるので，3通りの場合がある．

以上から，ボールの箱への配り方は $5\times4\times3$ 通りあり，これは $_{5}\mathrm{P}_{3}$ と一致する．

一般に，次のようにまとめることができる．

無題

先程の『順列』では，区別するものを１列に並べる場合を考えたが，ここでは円形に並べる場合について考えてみる．

例えば， $\fbox{A}$ ， $\fbox{B}$ ， $\fbox{C}$ ， $\fbox{D}$ の4人が手をつないで1つの輪をつくるとき，輪のでき方には何通りあるか考えてみよう．

まず，この4人を1列に並べると右図のようになり，その並べ方は $4!$ 通りである．

ここで，例えば右図の①，②，③，④は，輪になった場合に下の図のようになると考えることができる．

これら4つの並び方は，回転させることによって重なるので，どれも同じ1つの並び方だと考えられる．

つまり，右図の①，②，③，④のように，“順送り”に並ぶ4つの順列は，円形に並べた場合には同一視するのである．

よって，この4人の作る輪は $\frac{4!}{4}=3!=6$ 通りある．

ここで，円順列を定義しておこう．

この例では， $cir(4)=\frac{4!}{4}=3!=6$ である．

一般に，区別する $n$ 個のものを円形に並べた場合の総数も，先程の例と同じように考えることができ， 次のようにまとめられる．

無題

また，円順列が $(n − 1)!$ と計算される理由は，次のように説明することもできる．

簡単のため，先程の $cir(4)$ が $3!$ で計算できることについて考えてみよう．

右図のように，まず $\fbox{A}$ を固定して，そこから円をつくるように残りの $\fbox{B}$ ， $\fbox{C}$ ， $\fbox{D}$ を並べると考えて， $3!$ 通りとなり，これは $cir(4)$ と一致する．

一般の $cir(n)$ の場合も，1つを固定して，その周りに残りの $n − 1$ 個のものを並べると考えて

と考えることができる．

無題

右図のように，円順列としては区別される2つの順列も，表裏をひっくり返すことができる場合には同一視して1通りと数える．

このように表裏をひっくり返すことができる場合の円順列を， ネックレス順列(nacklace permutation) または 数珠じゅず順列(beads permutation) といい， その総数を $FTEXT$ では $neck(n)$ と表す． $neck(n)=\dfrac{cir(n)}{2}=\frac{(n-1)!}{2}$ である．