MathLabs

10年生

順列と組合せ

順序を考える場合と考えない場合の選び方を数える公式 Pn=n!P_n = n!、AnkA_n^k、CnkC_n^k。

直観直感:順序は重要か?

3個の色付きビーズを一列に並べる場面を考えよう。2つを入れ替えると見た目が違う列になるので、順序が重要である——これが順列である。次に同じ3個のビーズを袋に入れる。袋を振っても新しい袋にはならないので、順序は重要でない——これが組合せである。この2つの極端の間にあるのが順列(一部を選んで並べる)で、多くの走者のうち3人に金・銀・銅メダルを授与するような場合である。以下の3つの数え上げの公式——順列、部分順列、組合せ——は、これら3つの状況に乗法の法則を適用したものにすぎない。

A、B、Cから順序あり／なしで選ぶ図。異なる結果を並べ、対応する P(n,r) または C(n,r) の数を示す。
各行は nn 個から rr 個を選ぶ一例を示す。順序を数える場合は並べ替えると別の行になり、組合せでは並べ替えを一度だけ数える。順序なしモードに切り替えて同じ例を比べてみよう。

中高3つの数え上げの公式

定義: 順列

nn 個の異なる対象の順列とは、その nn 個すべてを一列に並べる並べ方である。順列の数は PnP_n と書く。

Pn=n!P_n = n!

定義: 部分順列(chỉnh hợp)

nn 個の異なる対象から kk 個(0≤k≤n0 \le k \le n)を選び、その kk 個を一列に並べる並べ方を部分順列という。その数は AnkA_n^k と書く。

Ank=n!(n−k)!A_n^k = \frac{n!}{(n-k)!}

定義: 組合せ

nn 個の異なる対象から kk 個(0≤k≤n0 \le k \le n)を、順序を考えずに選ぶ選び方——すなわち大きさ kk の部分集合——を組合せという。その数は CnkC_n^k と書く。

Cnk=n!k!(n−k)!C_n^k = \frac{n!}{k!(n-k)!}

各組合せはちょうど k!k! 通りの部分順列に対応する(選んだ部分集合の並べ方それぞれに1つずつ)。だからこそ組合せの公式は部分順列の数を k!k! で割るのである。

順列・部分順列・組合せの比較
概念順序は重要か?選ぶ個数公式
順列はいnn 個すべてPn=n!P_n = n!
部分順列はいnn 個から kk 個Ank=n!(n−k)!A_n^k = \frac{n!}{(n-k)!}
組合せいいえnn 個から kk 個Cnk=n!k!(n−k)!C_n^k = \frac{n!}{k!(n-k)!}

大学厳密な主張と証明

定理: 部分順列の公式(定理)

整数 n≥1n \ge 1 と 0≤k≤n0 \le k \le n に対し、nn 個の異なる対象から kk 個を選んで順に並べる方法の数は Ank=n!(n−k)!A_n^k = \frac{n!}{(n-k)!} である。特に k=nk=n とすると順列の数 Pn=n!P_n = n! が得られる。

なぜ正しいのか?

k個の順序付きの枠を1つずつ埋めていき、条件を満たす残りの対象の数が枠を埋めるたびに1つずつ減っていくというのは、まさに独立した連続する手順に対する乗法の法則の設定そのものである。

証明

第1段階(位置の設定):埋めるべき kk 個の位置に、順に位置1から位置 kk まで名前を付ける。すでに置いた対象を再利用せずに、nn 個の対象のいずれかで各位置を埋めることは、kk 個の連続する手順から成る作業である。

第2段階(乗法の法則を適用する):位置1は nn 通りで埋められる。埋めた後は対象が1つ使われているので、位置2は位置1で何が選ばれたかに関係なく n−1n-1 通りで埋められる。これを続けると、位置 kk はすでに k−1k-1 個の対象が使われているので n−k+1n-k+1 通りとなる。乗法の法則により、総数は積 n(n−1)⋯(n−k+1)n(n-1)\cdots(n-k+1) である。

第3段階(階乗の商として書き直す):欠けている末尾 (n−k)!(n-k)! を掛けてから割ると n(n−1)⋯(n−k+1)=n(n−1)⋯(n−k+1)⋅(n−k)!(n−k)!=n!(n−k)!n(n-1)\cdots(n-k+1) = \frac{n(n-1)\cdots(n-k+1)\cdot (n-k)!}{(n-k)!} = \frac{n!}{(n-k)!} となり、これはまさに Ank=n!(n−k)!A_n^k = \frac{n!}{(n-k)!} である。

第4段階(特別な場合 k=nk=n):k=nk=n を代入すると、0!=10! = 1 を用いて Ann=n!0!=n!1=n!A_n^n = \frac{n!}{0!} = \frac{n!}{1} = n! となり、順列の数 Pn=n!P_n = n! が復元される。

定理: 組合せの公式(定理)

整数 n≥1n \ge 1 と 0≤k≤n0 \le k \le n に対し、nn 個の異なる対象から順序を考えずに kk 個を選ぶ方法の数は Cnk=n!k!(n−k)!C_n^k = \frac{n!}{k!(n-k)!} である。

なぜ正しいのか?

サイズkの順序なし部分集合はそれぞれ、ちょうどk!通りの方法で順序ありの部分順列に変換できる。そのため、順序ありの数え上げは各部分集合を同じ係数k!だけ重複して数えており、割ることでその重複を取り除く。

証明

第1段階(部分順列を元の部分集合ごとにまとめる):nn 個から kk 個を選ぶ部分順列はそれぞれ、まずある kk 個の部分集合を選び、それを並べ替えたものである。AnkA_n^k 個の部分順列を、可能な kk 個の部分集合ごとに1つのグループにまとめ、2つの部分順列が同じ対象の集合を使うときにちょうど同じグループに入るようにする。

第2段階(各グループの大きさ):ある kk 個の部分集合を1つ固定すると、それから作られる部分順列はその部分集合の並べ方にちょうど対応し、そのような並べ方は k!k! 通りある(kk 個の対象の順列)。したがって各グループはちょうど k!k! 個の部分順列を持つ。

第3段階(グループにわたる加法の法則):各グループは互いに素であり(1つの部分順列はちょうど1つのグループに属す)、定義によりグループは CnkC_n^k 個あり、それぞれの大きさは k!k! である。加法の法則(k!k! を CnkC_n^k 回足し合わせる)により Ank=Cnk⋅k!A_n^k = C_n^k \cdot k! が得られる。

第4段階(組合せの数について解く):両辺を k!k! で割り、Ank=n!(n−k)!A_n^k = \frac{n!}{(n-k)!} を代入すると Cnk=Ankk!C_n^k = \dfrac{A_n^k}{k!}、すなわち Cnk=n!k!(n−k)!C_n^k = \frac{n!}{k!(n-k)!} が得られる。

定理: パスカルの恒等式

整数 nn と kk が 1≤k≤n−11 \le k \le n-1 を満たすとき、Cnk=Cn−1k−1+Cn−1kC_n^k = C_{n-1}^{k-1} + C_{n-1}^k が成り立つ。

なぜ正しいのか?

これは加法の法則そのものである:サイズkのすべての部分集合を、ある固定した要素を含むかどうかで分けると、2つの互いに素な場合になり、その個数を足し合わせればよい。

証明

第1段階(1つの要素を固定し、含むかどうかで分ける):nn 個の対象のうち1つの対象 xx を固定する。kk 個の部分集合はそれぞれ xx を含むか含まないかのいずれかであり、この2つの場合は互いに素で、合わせて CnkC_n^k 個の部分集合すべてを覆う。

第2段階(xを含む部分集合を数える):xx を含む部分集合は、残りの n−1n-1 個の対象から k−1k-1 個を選ぶことで作られ、そのような部分集合は Cn−1k−1C_{n-1}^{k-1} 個ある。

第3段階(xを含まない部分集合を数える):xx を含まない部分集合は、残りの n−1n-1 個の対象から kk 個すべてを選ぶことで作られ、そのような部分集合は Cn−1kC_{n-1}^k 個ある。

第4段階(加法の法則を適用する):この2つの場合は互いに素であり、サイズkのすべての部分集合を尽くすので、加法の法則により Cnk=Cn−1k−1+Cn−1kC_n^k = C_{n-1}^{k-1} + C_{n-1}^k が得られる。

大学実世界での応用と具体例

順列・部分順列・組合せは、計算機科学(ソートアルゴリズムにおける可能な並べ方の数え上げ)、暗号理論(鍵の数え上げ)、スケジューリング(異なる時間枠の割り当て)、統計学(確率を計算する前に等確率な標本を数えること)における日常的な計算である。以下の2つの例は、順列の問題と組合せの問題を並べて示す。

例: 本棚に本を並べる

ある生徒は5冊の異なる教科書を持っており、それらすべてを本棚に一列に並べたいと考えている。異なる並べ方は何通りあるか。

解答

第1段階:5冊すべてが並べられ、どの2冊を入れ替えても本棚の見た目は変わるので、これは一部の選択ではなく5個すべての対象の順列である。

第2段階:本棚の5つの位置を1つずつ埋めていく:最初の位置には 55 通り、2番目の位置には残り 44 通り、というように続き、最後の位置では 11 通りとなり、n=5n=5 のときの順列の公式 Pn=n!P_n = n! と一致する。

第3段階:計算すると、異なる並べ方は 5!=5⋅4⋅3⋅2⋅1=1205! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120 通りである。

例: 委員会を選ぶ

10人の従業員のグループから、内部に区別された役割のない(全員が対等な)4人の委員会を選ぶ。異なる委員会は何通りあるか。

解答

第1段階:どの委員も特別な役割を持たないので、同じ4人を異なる順序で挙げた2つの選び方は同じ委員会になる。つまり順序は重要でない——これには部分順列の公式ではなく組合せの公式が必要である。

第2段階:n=10n=10 と k=4k=4 で Cnk=n!k!(n−k)!C_n^k = \frac{n!}{k!(n-k)!} を適用すると、C104=10!4!⋅6!C_{10}^4 = \frac{10!}{4! \cdot 6!} となる。

第3段階:簡約すると、残る因子は 10⋅9⋅8⋅74!=504024=210\frac{10 \cdot 9 \cdot 8 \cdot 7}{4!} = \frac{5040}{24} = 210 通りの異なる委員会となる。

4冊の異なる本を本棚に一列に並べる方法は何通りあるか。

8人の候補者から、会長、副会長、書記(3つの異なる役職で、1人が2つの役職を兼ねることはない)を選ぶ。異なる結果は何通りあるか。

9人のボランティアから、対等な(区別された役割のない)3人のグループを選んでイベントを運営する。異なるグループは何通りあるか。

ある教師が20人のクラスから2人の生徒を選び、1つの賞を一緒に受け取るペアを作る(リーダーはなく、2人の間に区別された立場もない)。可能なペアの数を数える公式はどれか。

参考文献

  1. Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science
  2. Richard A. Brualdi (2009). Introductory Combinatorics