組合せ nCr | コンビネーションの公式証明を理解
組合せ nCr の公式を証明します。この証明ができれば、nPr と何が違うのかということが明確になります。
そこから、さらに一般的な公式の証明へと発展させます。
nCr の公式の証明の背後には、大学数学でよく使う基礎的な内容があり、合わせて理解ができます。
どこまで理解が必要なのかは、読者の方それぞれかと思いますので、段階的に説明をしています。
まずは、異なる 4 個から 異なる 3 個のものを選び一列に並べた順列をつくることと、異なる 3 個のものを選ぶ組合せの違いを説明します。
一般的な nCr の公式の証明を解説します。その後で、この公式の証明を司っている大学数学の基礎となる内容について述べます。
組合せ nCr :nPrとの違い
【nPr の定義】
異なる n 個のものから異なる r 個を選び、それら r 個を一列に並べた順列をつくったときに、できる順列のつくりかたの総数を nPr と定義します。
【nCr の定義】
異なる n 個のものから異なる r 個を選ぶときの選び方の総数を nCr 通りと定義します。ただし、選んだ r 個のものの順序は考慮しません。
定義だけを見ていると、抽象的で難しい感じがしますので、まずは具体例を通じて内容を確認します。
シンプルな例で、異なる 4 個から異なる 3 個のものを選び順列をつくる方法が何通りあるのかを説明します。
その後で、選んだ 3 個のものの順序を考慮しない組合せについて説明をします。
小さな数で違いを理解
1, 2, 3, 4 と異なる 4 個のものに印をつけておきます。この 4 個の中から異なる 3 個を選んで一列に並べます。順列を次のように表すことにします。
1-2-3 で、1 と 2 と 3 を選んだということを表しています。
ここで、順列については、選んだ順番を考慮します。1-2-3 だと、1番目に 1 を選び、2 番目に 2 を選んで、3 番目に 3 を選んだということです。
選んだ 3 個が同じものでも、選ぶ順番が異なると、異なる順列と考えるというのが定義です。
1-3-2 は、1 と 2 と 3 を選んでいますが、2 番目に 3 を選んでいます。
1-2-3 だと 2 番目に 2 を選んでいるので、選ぶ順番が違っています。
順列に使われている 3 個が同じものでも、順番が異なると違う順列と考えるので、「1-2-3 と 1-3-2」だと 2 通りの順列をつくったことになります。
※ 「1-2-3 と 1-3-2」は組合せだと選ぶ順番を考えないので、どちらも同じです。
異なる 4 個から 3 個を選んで順列をつくる方法が何通りかを考えるには、樹形図の考え方が大切になります。
1 番目に選ぶ数は、1 か 2 か 3 か 4 の 4 パターンがあります。まず、1 番目に選ぶ数が 1 のときにできる順列をすべて考えます。
【 1 番目が 1 のとき】
1-2-3, 1-2-4, 1-3-2, 1-3-4, 1-4-2, 1-4-3,
3 × 2 = 6 より、6 通りの順列が出現します。
樹形図の考え方です。2 番目に選ぶ数の可能性は、1 番目に選ばなかった 2 か 3 か 4 の 3 通りです。
最後の 3 番目の数は 1 番目と 2 番目に選ばなかった数を選ぶことから、2 通りの分岐が考えられます。
したがって、まず 3 通りに枝分かれをして、それぞれの枝が 2 通りに枝分かれすることになります。
算数の考え方で、3 × 2 で 6 通りの枝別れになります。
これで、1-2-3 から 1-4-3 までの 6 通りの順列が得られることが分かりました。
今、1 番目の数が 1 のときを考えましたが、他に 2 や 3 や 4 を 1 番目に選ぶ可能性があります。1 ではない数を 2 番目に選んだとしても、やはり同様の樹形図を描き 6 通りです。
よって、1 番目に選ぶ可能性が 4 通りなので、
4 × 3 × 2 = 24 通りとなります。
これが、異なる 4 個から 3 個を選んで順列をつくるときの総数で 4P3 = 24 通りです。
一般に、異なる n 個から
r 個を選び順列をつくる方法は
nPr = n×(n – 1)× … ×(n – r + 1) となります。
異なる n 個から r 個を選び順列をつくるときの総数は定義から nPr 通りでした。
n と r を使って、
n × (n －1) × … × (n － r + 1) 通りとなるのは樹形図の考え方です。
1 番目に選ぶ可能性が n 通りで、2 番目に選ぶ可能性が (n － 1) 通りです。そして、3 番目に選ぶ可能性が (n － 2) 通りです。
この規則から r 番目に選ぶ可能性が 、
(n － r + 1) 通りとなります。
規則をよく見ると、
3 番目だと (n － 3 + 1) です。
□ 番目だと (n － □ + 1) という規則なので、r 番目だと □ に r を当てはめて (n － r + 1) 通りとなります。
具体的に全て書き出す
一般的な証明を述べましたが、この順列の総数 nPr 個 (n パーミュテーション r という読み方) を具体的に書き出すことで組合せとの違いが明確になります。
先ほど論理的に計算した4P3 = 24 通りの順列を全て書き出しました。
ここから、異なる 4 個から 異なる 3 個を選ぶ組合せの総数 4C3 通りについて説明をします。
組合せのときだと、定義から選んだ 3 個の順番を考慮にいれません。
そのため、1-2-3 と 1-3-2 や 3-2-1 たちは、同じ 1 通りと数えます。どれも 1 と 2 と 3 を使っているので、選んだ 3 個が「1 と 2 と 3」となっています。
この順番を考慮しないということから、4P3 = 24 通りの順列たちから、組合せの総数の方が小さくなります。
ここから、重複カウントしている順列たちを整理します。1-2-3 と等しい重複している順列は、1 と 2 と 3 の数字が使われていて、これらを並び替えた順列たちです。
【1, 2, 3 のクラス】
1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1,
1, 2, 3 の 3 個を並び替えるので、
3! = 6 通りの順列が 1 つのクラスになります。
1 と 2 と 3 を並び替えた順列なので、3 × 2 × 1 = 6 通りが考えられます。
これら 6 個の順列は、どれも 1-2-3 と同じ順列と組合せでは考えるので、1 通りの選び方になってしまいます。
※ n! = n × (n － 1) × … × 2 × 1 という記号を導入しました。
重複している 6 個の順列からできているクラス（部分集合）を考え、このクラスが 1 通りあるとします。この 1 つのクラスが 1 通りの組み合わせになります。
まず 4P3 通りの順列の総数を考え全体集合とし、そこから重複しているものたちでクラスをつくり、組合せを、最終的に何クラスあるのかということで確定させます。
組合せ → クラスに分けて数える
今、1-2-3 を含んでいるクラスを考えました。
このクラスを C(1) と置いておき、残りの 18 通りの順列たちについても重複を調べます。
1-2-3 を含んでいるクラスに入っていない順列を 1 つ指定します。
1-2-4 だと、4 があるため、「1 と 2 と 3」でつくられた順列ではありません。他のクラスたちを書き出して、4P3 通りの順列から成る全体集合を整理します。
左から 2 番目のクラスが「1 と 2 と 4」から成る順列を全て含んでいるクラスです。
このクラスを C(2) と置くことにします。
クラス C(1) は「1 と 2 と 3」を並び替えてつくった順列を全て集めたものです。
C(2) は「1 と 2 と 4」を並び替えてつくった順列を全て集めたものです。
「1 と 2 と 3」をどのように並び替えても 4 を使った順列は出てきません。
そのため、C(1) と C(2) に共通して含まれている順列は存在しません。
※ C(1) ∩ C(2) は空集合ということです。
また、「1 と 2 と 4」を並び替えた順列全体が C(2) なので、C(2) に含まれている順列は 3! = 6 通りです。
これで、C(1) ∪ C(2) の 合計 12 通りです。
4P3 = 24 通りの順列がありましたから、
C(1) ∪ C(2) の中に含まれていない順列が、まだ存在します。
1-3-4 という順列が C(1) ∪ C(2) に含まれていない順列です。
※「1 と 3 と 4」を使った順列は、
C(1) ∪ C(2) には含まれていないということになります。
もし、「1 と 3 と 4」を使った順列が C(i) (i は 1 または 2) に含まれていたとすると、それらを並び替えた 1-3-4 が C(i) に入っているということになります。
しかし、C(1) ∪ C(2) に含まれていない順列として、1-3-4 を指定したので、これは矛盾です。
こういうわけで、C(1) ∪ C(2) には「1 と 3 と 4」を使った順列が 1 つも含まれていないということが分かりました。
「1 と 3 と 4」を並び替えてできる順列をすべて集めたクラスを C(3) とします。
C(1) ∪ C(2) には「1 と 3 と 4」を使った順列が 1 つも含まれていないため、C(3) と C(1) や C(2) の共通部分は空集合です。
※ 論理が難しいと感じられたら上の図で見比べて頂けると、左から 3 番目のクラスは、前の 2 つのクラスと共通して含まれている順列がありません。
また、C(3) は「1 と 3 と 4」という異なる 3 個を並び替えた順列を全て集めた集合です。
そのため、3! = 6 通りの順列を含んでいることになります。
C(1) ∪ C(2) ∪ C(3) に 2-3-4 は含まれていないので、「2 と 3 と 4」を並び替えてできる順列を全て集めた集合を C(4) とします。
C(4) も 3! = 6 通りの順列でできています。
先ほどと同じ考察で、「2 と 3 と 4」は、C(1) や C(2) や C(3) には含まれていません。そのため、C(4) は、これら 3 つのどのクラスとも共通部分が空集合となっています。
これで、4P3 = 24 通りの順列から成る全体集合は、C(1) ∪ C(2) ∪ C(3) ∪ C(4) という和集合となります。
どの二つも共通部分が空集合となっています。i ≠ j のとき、C(i) ∩ C(j) = Φ です。そして、どのクラスに含まれている順列は 3! = 6 通りでした。
以上より、
24 = 3!+3!+3!+3!
= 4×3! となります。
この等式から、24 ÷ 3! = 24 ÷ 6 が割り切れて、4 となります。
この 4 はクラスが 4 個あるということです。もともと、重複してする順列たちをクラスに整理して、1 クラスを 1 通りの組合せと数えることを目指していました。
これで、異なる 4 個から異なる 3 個を選ぶ組合せの総数が 4 通りと分かりました。
ここまでの内容は、一般化することができます。
実は、大学数学で学習する同値関係で類別するという発想が根本にあります。
その考え方に触れつつ、組合せの公式を証明することができます。
組合せ nCr :具体から抽象へ
4P3 = 24 個の順列を、1 つが 3! 個（6 個）から成るクラスたちに分けたので、
4C3 = 4P3 ÷ 3! = 4 と割り切れます。
この 4 個が、異なる 4 個から 3 個を選び取る方法の総数になります。
異なる 4 個から異なる 3 個を選ぶ組合せを 4C3 と定義していました。ただ、これは定義しただけで、具体的にどんな数字になるのかは不明でした。そこで、具体的に考察をしたわけです。
クラスに分けていき、1 つのクラスに含まれている順列が必ず 3! 通りで、3! 通りからできているクラスたちに分割できました。
全体の順列 4P3 個を 3! 個ずつでちょうど分けられたので、4P3 ÷ 3! が割り切れました。
この商 4 がクラスの個数です。クラスの個数が組合せの個数ということで、4P3 ÷ 3! が求める組合せの総数となっていました。
ここまでの考え方を一般化すると次のようになります。
組合せ → 総数を数式化
異なる n 個から r 個を選ぶ組合せの総数は、
nCr = nPr ÷ r! という数式となります。
分母に書かれている r! は 1 つのクラスに含まれている順列の個数です。どのクラスも同じ個数の順列が含まれています。
そして、nPr 通りの 順列が、r! 個の順列から成るクラスたちに、ぴったりと分けられます。
そのため、nPr ÷ r ! が割り切れ、この商が クラスたちの個数です。
1 つクラスがあれば、1 通りの組み合わせということだったので、組合せの総数が、
nCr = nPr ÷ r ! となっているわけです。
※ n 個の連続整数の積が n! の倍数となっているというように、階乗「!」は整数の証明問題でも使われます。
コンビネーションやパーミュテーションの式で使われる階乗の計算に慣れておくと、数学の幅広い分野で使われるので、役立つかと思います。
それでは、一般的な n と r を使って、この等式を証明します。
組合せの公式を証明
異なる n 個ものから、異なる r 個を選んで一列に並んだ順列全体から成る集合を A とします。樹形図の発想から、A は nPr 個の順列でできています。
A から 1 つ順列を指定し、それを
a1-a2– … -ar とします。
a1, a2, … , ar という異なる r 個を並び替えてできる順列をすべて集めて C(1) とします。
この A の部分集合 C(1) に含まれている順列の個数は r! 個です。
※ 先ほどは 1-2-3 などと書いていた順列を一般的に表しているだけです。
もし C(1) に含まれていない A の順列があれば、それを 1 つ指定して、
b1-b2– … -br とします。
b1, b2, … , br の異なる r 個を並び替えてできる順列をすべて集めて C(2) とします。この A の部分集合 C(2) に含まれている順列の個数は r! 個です。
b1-b2– … -br が C(1) に含まれていないため、
b1, b2, … , br のうち、
少なくとも 1 つは a1, a2, … , ar のどれとも異なっています。
もし、C(1) ∪ C(2) が A に一致していなければ、C(1) ∪ C(2) に含まれていない順列が存在することになります。
そのときは、C(1) ∪ C(2) に含まれていない順列を 1 つ指定し、c1-c2– … -cr とします。
c1, c2, … , cr の異なる r 個を並び替えてできる順列をすべて集めて C(3) とします。この A の部分集合 C(3) に含まれている順列の個数は r! 個です。
c1-c2– … -cr が C(1) に含まれていないため、
c1, c2, … , cr のうち、
少なくとも 1 つは a1, a2, … , ar のどれとも異なっています。また、C(2) にも含まれていないため、b1, b2, … , br のどれとも異なっています。
そのため、
C(3) ∩ C(1) = Φ, C(3) ∩ C(2) = Φ となっています。
C(1) ∪ C(2) ∪ C(3) に含まれていない A の順列が存在すれば、同様の操作を繰り返します。
A には有限個の順列しかないので、これらの操作は有限回で終了します。
そのため、A = C(1) ∪ … ∪ C(k) と有限個のクラスたちの和集合に分割されます。
それぞれのクラス C(i) に含まれている順列の個数は、どれも r! 個です。
そして i ≠ j だと C(i) ∩ C(j) = Φ となっています。
※ 1 つのクラスが 1 通りの組み合わせなので、組み合わせの総数 nCr が k 通りということです。
今、異なるクラスが k 個あり、それぞれのクラスに含まれている順列の個数が r! 個なので、r! 個を k 倍すると、A に含まれている順列の総数 nPr と一致します。
よって、k × r! = nPr
左辺は r! で割り切れるので、右辺も r! で割り切れないといけません。
※ 左辺の式は k も r! も整数なので、
r! が整数 nPr の約数ということを示しています。
したがって、組合せの総数 k は nPr ÷ r! となり、組合せの公式が示せました。【証明完了】
この組合せの公式は、有限体など、大学の数学でも使われます。
最後に、よく使う組合せに関する公式を証明しておきます。
組合せ nCr :よく使う公式
【公式】
2 以上の自然数 n と 1 以上 n 以下の自然数 r について、
nCr = n-1Cr-1 + n-1Cr
＜証明＞
r = 1 のときは、nC1 = n です。
n-1C0 + n-1C1 = 1 + (n － 1) = n となっています。
よって、r = 1 のときには成立しています。
※ C の右下が 0 のときに 1 と定義しておいたことが効いています。
r = 1 のときに成立しているので、r ≧ 2 のときを以下で扱います。
異なる n 個から異なる r 個を選ぶ組合せの総数は、nCr です。
この n 個のうち、1 つの印をつけておきます。r 個を選ぶときに、印をつけた 1 つを選ぶか選ばないかのいずれかになります。
印をつけた 1 つを選ぶ場合の総数と印をつけた 1 つを選ばない場合の総数の和が nCr となります。
【印をつけた 1 つを選ぶ場合】
印をつけた 1 つを選んだので、印をつけていない (n － 1) 個から (r － 1) 個を選ぶことになります。
組合せの定義から、この場合の総数は、
n-1Cr-1 通り。
【印をつけた 1 つを選ばない場合】
印をつけていない (n － 1) 個から r 個を選ぶことになります。
組合せの定義から、この場合の総数は、
n-1Cr 通り。
よって、
nCr = n-1Cr-1 + n-1Cr【証明完了】
二項展開についての証明で、この【公式】を使います。
大学の数学でも、しばしば組合せの式を変形するときに使われるので、高校の段階から慣れておくと良いかと思います。
高校数学の記事として、個数定理という記事も投稿しています。
それでは、これで今回のブログ記事を終了します。
読んで頂き、ありがとうございました。