数学A 第1章 場合の数 — 順列

この節の練習問題5問だけをまとめて見る・印刷する →

この節の前提数え上げの基本

この『順列』から『資源配分(配分先に区分がない)』までの8つのセクションでは、数え上げに関する応用的な手法をみていく。各セクションは、「ボールと箱のモデル」で体系的にまとめることができる。縦の欄にはボールと箱の区別の有無を、横の欄にはボールを箱にしまう際に、それが『写像』でいうところの何と対応するのかを示している。

順列について

順列nPrの定義

4枚のカード ［A］ 、 ［B］ 、 ［C］ 、 ［D］ から2枚のカードを引いて、これらを1列に 並べる場合の数は次のように求めることができる。

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

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

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

4×3=12 通り

となる。

次の図は、2枚のカードの並べ方12通りを、樹形図と、並びをすべて書き出したもので表している。

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

順列nPrの計算

区別する n 個のものから r 個取り出して1列に並べる順列の数 nPr は、上の例と同じように考えることができる。

1番目のものの取り方は n 通りあり、 2番目のものの取り方はそのそれぞれに対して n − 1 通りあり、 3番目のものの取り方はそのそれぞれに対して n − 2 通りあり、 … r 番目のものの取り方はそのそれぞれに対して n − (r − 1) 通りある。

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

nPr=n(n-1)…(n-r+1) ① r個の積

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

特に、 r が n に等しいとき、つまり r = n のときには、 nPn=n(n-1)(n-2)……3・2・1 となる。右辺は1から n までの すべての自然数の積であり、これを n の階乗(factorial)といい、記号 n! で表す。 つまり

n!= nPn=n(n-1)(n-2)……3・2・1

である。

また、 r < n のとき、 nPr の分母・分子に (n − r)! をかけることにより

nPr=nPr×(n-r)!/(n-r)! =n(n-1)…(n-r+1)(n-r)…2・1/(n-r)…2・1

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

nPr=n!/(n-r)! ②

となる。

r = n のとき、　② は形式的に nPn=n!/0! と表せるが、 nPn = n! となって欲しいので、 0! = 1 と定めることにする。 こうすれば、 ② は r = n のときにも成り立つ。

以上、 ① 、 ② をまとめると

§

定理2順列 nPr の計算

順列 nPr は

nPr= n(n-1)(n-2)……(n-r+1) =n!/(n-r)!

と計算できる。ただし、n、rは0以上の整数とし、 n≧r とする。

また、 ② の nPr=n!/(n-r)! は、ただ計算上で成り立つだけでなく

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

と考えることもできる。このことの具体例を示すため、以下には 4P4( = 4!) と 4P2 の対応を樹形図で表した。 4P2 通りは、 4P4 通りの順列において (4 − 2)! 通りで割って1束にしたものであることを確認しよう。

ボールと箱のモデル1

5P3 の定義は

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

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

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

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

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

としておく。

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

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

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

以上から、ボールの箱への配り方は 5×4×3 通りあり、これは 5P3 と一致する。

一般に、次のようにまとめることができる。

円順列

円順列cir(n)の定義

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

例えば、 ［A］ 、 ［B］ 、 ［C］ 、 ［D］ の4人が手をつないで1つの輪をつくるとき、輪のでき方には何通りあるか考えてみよう。

まず、この4人を1列に並べると下の樹形図のようになり、その並べ方は 4! 通りである。

ここで、例えば樹形図の①、②、③、④は、輪になった場合に下の図のようになると考えることができる。

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

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

よって、この4人の作る輪は 4!/4=3!=6 通りある。

ここで、円順列を定義しておこう。

円順列cir(n)の計算

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

§

定理5円順列 cir(n) の計算

n 個の円順列の総数 cir(n) は

cir(n)=n!/n=(n-1)!

と計算できる。

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

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

次の図のように、まず ［A］ を固定して、そこから円をつくるように残りの ［B］ 、 ［C］ 、 ［D］ を並べると考えて、 3! 通りとなり、これは cir(4) と一致する。

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

cir(n) = (n − 1)!

と考えることができる。

ネックレス順列neck(n)の定義・計算

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

このように表裏をひっくり返すことができる場合の円順列を、 ネックレス順列(necklace permutation) または 数珠順列(beads permutation) といい、 その総数を FTEXT では neck(n) と表す。 n≧3 のとき、 neck(n)=cir(n)/2=(n-1)!/2 である。

最終更新: 2026-09-03