順列

ものの集まりからいくつかを選ぶとき、選ぶ順番が関係するなら、順列を使います。（チェコの教科書では、この順列を「ヴァリアツェ」と呼び、すべてを並べる場合だけを「順列（パーミュテーション）」と呼んで区別します。）

公式の導き方

順列の典型的な問題から始めましょう。ある村では、毎年おにぎりの早食い大会が開かれます。決勝には7人の選手が進みました。この7人のうち、1位から3位までの決まり方は、全部で何通りあるでしょうか。

この例では順番が関係する、という点が大切です。たとえば、上位3人が健太、翔太、大輝だとわかっているとき、この3人だけで6通りの順位ができます。

健太、翔太、大輝
健太、大輝、翔太
翔太、健太、大輝
翔太、大輝、健太
大輝、健太、翔太
大輝、翔太、健太

これらはすべて異なる順位です。選手が7人のとき、異なる順位が全部で何通りできるかを求めたいのです。

これには積の法則を使います。(x₁, x₂, x₃) の形の3つ組を選ぶと考えます。x₁ は1位になった選手、というようにします。x₁ にはどの選手を入れられるでしょうか。全員なので、x₁ には7人の選手を入れられます。x₂ にはだれを入れられるでしょうか。1位に入れた選手以外の全員なので、x₂ には 7 − 1 = 6 人の選手を入れられます。x₃ には、1位でも2位でもない選手を入れられるので、7 − 2 = 5 通りです。積の法則を使うと、全部で 7 · 6 · 5 = 210 通りになります。

上位4位までの決まり方の総数を知りたいなら、x₄ には 7 − 3 = 4 人の選手を入れられるので、全部で 7 · 6 · 5 · 4 = 840 通りになることがわかります。ここから何がわかるでしょうか。

n 個の要素からなる集合（この例では7人の選手）から、順番を考えて 3 個の要素を選ぶとき、答えは n · (n − 1) · (n − 2) になります。1位には全員がなれ、次は1人少なくなり、と続きます。ここから、n 個の要素からなる集合から k 個を選ぶときの一般の公式が導けます。選び方の総数は n · (n − 1) · (n − 2) · … · (n − k + 1) です。

この式は、階乗を使ってさらに変形できます。7の階乗 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 と、メダルの順位の数え方 7 · 6 · 5 を見比べると、似ていることがわかります。うしろの部分をとりのぞけばよいのです。つまり、7! を 4 · 3 · 2 · 1 で割れば、7 · 6 · 5 だけが残ります。では、式 4 · 3 · 2 · 1 は何に等しいでしょうか。4! です。

したがって、n 個の要素からなる集合から、順番を考えて k 個の要素を選ぶとき、選び方は全部で

$_{n} P_{k} = \frac{n!}{(n - k)!}$

通りあります。おにぎり大会の数をこの式に代入すると、次のようになります。

$_{7} P_{3} = \frac{7!}{(7 - 3)!} = \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{4 \cdot 3 \cdot 2 \cdot 1} = 7 \cdot 6 \cdot 5 = 210.$

計算ツール

与えられた n と k について、順列の総数を計算します。

例題

おにぎりの早食い大会の話を続けましょう。いつも優勝する名人の太郎さんが大会に来ているとわかっていたら、メダルの順位の決まり方の数はどう変わるでしょうか。つまり、選手が7人で、太郎さんがかならず優勝するとき、メダルの順位の決まり方は何通りあるでしょうか。

これも簡単な順列です。1位は決まっているので、残りの6人の選手で2位と3位がどう決まるかを求めればよいのです。つまり、6個の要素からなる集合から2個を選ぶので、次の順列になります。

$_{6} P_{2} = \frac{6!}{(6 - 2)!} = 30$

昔、太郎さんがまだそれほど名人ではなかったころは、いつも3位以内に入っていました。選手が7人で、太郎さんがかならず何かのメダルをとるとき、メダルの順位の決まり方は何通りあるでしょうか。

この例が前の例とちがうのは、太郎さんが何位なのかがわからないことです。2位だったかもしれないし、3位だったかもしれません（本人はいまだにそれを恥ずかしく思っています）。そこで、全部で3つの順列を計算しなければなりません。太郎さんが優勝した場合、銀メダルの場合、銅メダルの場合です。ただし、どの場合も、ほかの選手が入れるのは2つの順位だけです。たとえば太郎さんが2位なら、ほかの選手は1位か3位に入ります。つまり、ここでも6人から2人を選ぶ順列を、太郎さんの3つの順位について3回計算すればよいのです。順位の決まり方の総数は次のとおりです。

$3 \cdot_{6} P_{2} = 3 \cdot \frac{6!}{(6 - 2)!} = 3 \cdot 30 = 90$

順列の前の3は {}₃P₁ とも書けることに注目しましょう。実際には、3つの要素からなる集合（3つのメダルの順位）から1つの要素（1つの順位）を選んでいるからです。
ある学校には先生が全部で20人います。もうすぐ入学試験があり、面接委員を、委員長1人、やさしい委員1人、きびしい委員1人という構成で選ぶ必要があります。選び方は全部で何通りあるでしょうか。

まず、順番が関係するかどうかを考えなければなりません。関係します。3人の先生の役割は、やはり6通りに入れかえられるからです。あとは簡単で、20個の要素から3個を選ぶ順列です。

$_{20} P_{3} = \frac{20!}{17!} = 6840.$
数字 {0, 1, 2, 3, 4, 5} から、同じ数字をくり返さずに、3けたの数はいくつつくれるでしょうか。

順番は関係するでしょうか。関係します。123と321はちがう数です。異なる3つ組はいくつあるでしょうか。6個から3個を選ぶ簡単な順列です。

$_{6} P_{3} = \frac{6!}{3!} = 120.$

ただし、百の位が0の順列をひかなければなりません。012は3けたの数ではないからです。そこで、0から始まる3つ組がいくつあるかを考えます。その場合、数字が入れかわるのは残りの2つの位だけなので（3つ組は (0, x₂, x₃) の形）、数字 {1, 2, 3, 4, 5} を使って異なる2つ組がいくつつくれるかを求めます。これも簡単で、{}₅P₂ = 5!/3! = 20 です。つまり、0から始まる3つ組は20個あります。

したがって、数字 {0, 1, 2, 3, 4, 5} でできる3けたの数は、全部で 120 − 20 = 100 個です。
数字 {1, 2, 3, 4, 5} から、同じ数字をくり返さずに、奇数になる3けたの数はいくつつくれるでしょうか。

123と321はちがう数なので、順番は関係します。奇数の3けたの数をつくるので、百の位と十の位にはどの数字がきてもよいですが、一の位は数字 {1, 3, 5} のどれかでなければなりません。まず、5つの数字でつくれるすべての3つ組の数を計算します。{}₅P₃ = 5! / 2! = 60 です。

どの数字も、一の位に同じ回数ずつ現れます。数字は5つあるので、それぞれの数字が一の位に現れる回数は 60 / 5 = 12 回です。一の位にきてよい数字は {1, 3, 5} の3つなので、1で終わる数が 12 個、3で終わる数が 12 個、5で終わる数が 12 個あります。和の法則を使うと、全部で 12 + 12 + 12 = 36 通りです。
{}_xP₂ = 72 のとき、x を求めなさい。言いかえると、要素が x 個の集合から2個を選んで並べる並べ方が、全部で 72 通りあるとします。もとの集合の要素は何個だったでしょうか。式を書いてみましょう。

$_{x} P_{2} = \frac{x!}{(x - 2)!} = 72$

さらに変形します。

$\begin{array}{rcl} \frac{x!}{(x - 2)!} & = & 72 \\ \frac{x \cdot (x - 1) \cdot (x - 2)!}{(x - 2)!} & = & 72 \\ x \cdot (x - 1) & = & 72 \\ x^{2} - x & = & 72 \\ x^{2} - x - 72 & = & 0 \end{array}$

これはふつうの2次方程式なので、判別式を使って解くか、次の形に書きかえます。

$(x + 8) \cdot (x - 9) = 0$

ここから、解は x₁ = −8 と x₂ = 9 だとわかります。要素の個数は負にならないので、負の解は考えません。したがって、もとの方程式の解は x = 9 で、集合の要素は9個でした。

章: 場合の数, 順列, すべてを並べる順列（階乗）, 組合せ, 重複順列, 重複組合せ, 暗証番号は何通りあるか

« 前へ: 場合の数

次へ: すべてを並べる順列（階乗） »