数学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-08-12