高校で習う順列・組合せ

　今回から順列・組合せの求め方を紹介していきます。なぜそんな初歩的なところから始めるかというと、ベル数とスターリング数について書きたいと思ったのですが、それらが組合せにおいて意味を持つため、基礎から順を追った方が良いと思ったからです。

　今回は最後までは行かず、高校数学で扱う範囲を整理します。ただし、高校では使わない表現を一部含んでいます。

重複順列

　最も簡単な重複順列から始めます。重複順列は「n 種類のものを k 個並べる方法」です。たとえば「リンゴ、ミカン、ブドウを５個並べる方法は何通りか。ただし１個も並ばない果物や２個以上並ぶ果物があってもよい。」といった問題があります。これは１個目の選び方が３通り、２個目の選び方が３通りとなり、３個目、４個目、５個目も同様です。したがって、そのような並べ方は 3×3×3×3×3=243(通り) あります。

　一般に「n 種類のものを k 個並べる方法」が何通りあるかは次のように表されます。

　ただ、今回は重複順列の意味に沿った例を挙げましたが、一見重複順列に見えない問題が出題されることが多そうです。たとえば「５人を３個の部屋に入れる方法は何通りか。ただし０人の部屋があってもよい。」という問題は「並べる」という単語が出てきません。しかし５人を整列させて、部屋番号を書いた札を渡すと考え直すと「３種類の札を５枚並べる方法は何通りあるか。ただし一枚も並ばない札や２枚以上並ぶ札があってもよい。」という問題に読み直すことができます。

　恐らく重複順列は「n 種類のものを k 個並べる方法」という考え方との他に「n 個のものを k 個の状態のどれかにする方法」という考え方を持っておいた方がよさそうです。

順列

　今度は異なるものを並べることを考えます。つまり「n 個の中から k 個選び、並べる方法」です。重複順列では同じものを複数個選ぶことが許されるため「種類」という言葉を使いましたが、今回は一個しか選ぶことができないため「個」という言葉を使いました。

　問題の例としては「１から５の数字が書かれたカードが１枚ずつある。この中から３枚を並べて作れる数字は何通りか。」といったものがあります。これは一の位の選び方が５通り、十の位の選び方が（一の位で使ったものを除いた）４通り、百の位が（一の位、十の位で使ったものを除いた）３通りですので、5×4×3=60(通り) となります。

　一般に「n 個の中から k 個選び、並べる方法」は次のように表されます。

　n の k 乗の k に下線が引かれたようなものは下降階乗冪とよばれるもので、n から n-k+1 までの整数を書けたものです。１小さい整数を掛けるという階乗的な要素と、k 個の整数を掛けるという冪的な要素が融合しているので、このような名前なのでしょう。

　''下降''とあることから分かるように上昇階乗冪というのも存在します。ただ今回は必要ないので説明しません。

　少し発展的な内容に円順列というものがあります。「n 個の中から k 個選び、円状に並べる方法」です。よりイメージしやすい言い方をすると「n 人の中から k 人選び、円卓に座らせる方法」です。順列における並びの先頭と最後尾を繋げると円になりますが、このとき１人ずれても同じものと見なされます。そのため、回転させる方法が k 通りことあるから、順列を k で割る必要があります。

　さらに発展的な内容になると数珠順列というものがあります。これは「n 個の中から k 個選び、円状に並べる方法（ただし裏返すと一致するものは同じと見なす）」のように、円順列より条件が厳しくなったものです。ただしこれは、円順列を２で割ったものになります。

　一般に、円順列と数珠順列は次のように表されます。

組合せ

　次は組合せです。順列と何が違うかというと、順列では選んだものを並べたのに対し、組合せでは並べません。つまり「n 個の中から k 個選ぶ方法」です。

　たとえば「10人の中から代表を３人選ぶ。代表の選び方は何通りあるか。」といった問題があります。このままでは少し考えづらいので、一度順列の問題を経由します。つまり先に「10人の中から代表を３人選び、並ばせる。代表の並び方は何通りあるか。」という問題です。これなら ₁₀P₃ 通りだとすぐに分かります。しかし、元の問題では並べる必要はありません。ですので、それぞれの代表の選び方に対する代表の並び方の個数で割る必要があります。並び方は 3! 通りなので、最初の問題の答えは ₁₀P₃/3!=120(通り) だと分かります。

　一般に「n この中から k 個選ぶ方法」は次のように表されます。

　( ) の中に縦に２つの数を書いたものは二項係数とよばれ、(x+1)^n を展開した式の  x^k の係数として知られています。

重複組合せ

　最後に重複組合せです。これは「n 種類から k 個選ぶ方法」で、重複順列と異なり並べる必要はありません。例題は「リンゴ、ミカン、ブドウから５個選ぶとき、選び方は何通りあるか。ただし 1 個も選ばれない果物や 2 個以上選ばれる果物があってもよい。」という問題です。これは「〇 5 つと | 2 本を並べる方法は何通りあるか。」とい言い換えることができ、さらには「〇または | が入る 7 つの枠から、| が入る枠を 3 つ選ぶ。枠の選び方は何通りあるか。」という問題に言い換えることが出来ます。つまり、組合せの問題です。

　なぜ「〇 5 つと | 2 本を並べる方法は何通りあるか。」という問題に言い換えることができるかというと、たとえば「〇〇｜〇〇〇｜」という並びのとき、｜で仕切られた区間ごとの〇の個数を数えると２個、３個、０個となります。これらをそのままリンゴ、ミカン、ブドウの個数に当てはめるのです。そうすることで、この問題の答えは ₇C₂＝21(通り) と分かります。

　一般に「n 種類から k 個選ぶ方法」は次のように表されます。

おわりに

　今回はここまでにします。次回からベル数とスターリング数の紹介に入ります。これらを知ることで「n 人をグループ分けする方法」「n 人を''k 組に''グループ分けする方法」「n 人を k 組にグループ分けし、円卓に座らせる方法」が何通りあるか求めることが出来るようになります。

　ではまた～。