MENU
  1. トップ
  2. 基礎体系
  3. 基礎数学
  4. 基礎 数学A
  5. 【基礎 数学(数学A)】Module 2：場合の数(2) 組合せ

【基礎 数学(数学A)】Module 2：場合の数(2) 組合せ

当ページのリンクには広告が含まれています。

本モジュールの目的と構成

前モジュール「順列」において、我々は物事を「並べる」という行為に潜む論理構造を解き明かし、体系的な計数のための基礎を築きました。本モジュールでは、その思考をさらに一歩進め、「順序」という制約を取り払った、より純粋な「選択」の技術である組合せ (Combination) の世界を探求します。順列が「誰を、どの順番で」並べるかという問いであったのに対し、組合せは「誰をメンバーとして選ぶか」という、構成そのものに焦点を当てます。

この「順序を問わない」という視点の転換は、単に計算式が変わる以上の、深い意味を持っています。それは、場合の数の問題解決における思考の自由度を格段に高め、確率論や統計学といった、より広範な数学分野の核心へと我々を導く扉となります。委員会を選ぶ、グループを分ける、カードの特定の役を揃えるといった、日常や学問の様々な場面で現れる「選択」の問題は、すべてこの組合せの概念によって数学的にモデル化されます。

本モジュールは、以下の学習項目を通じて、組合せの理論を基礎から応用まで、深く、そして有機的に学んでいくことを目的とします。

  1. 組合せ (nCr) の定義と計算: なぜ順列の計算結果を階乗で「割る」のか。その操作が「順序を無視する」という行為の本質であることを理解し、組合せの基本計算をマスターします。
  2. nCr = nCn-r の対称性: 「r個を選ぶ」ことと「n-r個を残す」ことが本質的に同じであることを学び、この美しい対称性が計算の効率化にいかに貢献するかを見ます。
  3. パスカルの三角形と組合せの数の性質: 組合せの数が織りなす神秘的なパターンであるパスカルの三角形を探検し、そこに秘められた漸化式や恒等式の組み合わせ論的な意味を解き明かします。
  4. 組分け問題（区別の有無）: 組合せの応用として最も重要かつ混乱しやすい「組分け」を徹底的に分析します。グループやモノの「区別」の有無が、いかにして計算方法を根本から変えるのかを体系的に整理します。
  5. 重複組合せ: 「同じ種類のものを繰り返し選んでも良い」という、より自由度の高い選択の方法を学びます。「仕切り棒」を用いた独創的なモデル化が、複雑な問題をいかにシンプルに解決するかを体験します。
  6. 最短経路問題: 順列としても捉えられた最短経路問題を、今回は組合せの視点から再解釈し、その二つのアプローチが本質的に同等であることを確認します。
  7. 図形の個数問題（三角形、対角線など）: 点や線といった幾何学的な要素から、特定の図形を「選び出す」問題に組合せの理論を適用し、数と図形の美しい融合を見ます。
  8. 二項定理: (a+b)^n という代数的な展開式の係数が、なぜ組合せの数 nCr で与えられるのか。その根源的な理由を組み合わせ論的に解明し、代数と場合の数の間の深い繋がりを探ります。
  9. 多項定理: 二項定理をさらに一般化し、3つ以上の項のべき乗の展開を考えます。その係数が「同じものを含む順列」と見事に一致することを確認します。
  10. 順列と組合せの戦略的選択: 本モジュールの締めくくりとして、問題文の僅かなニュアンスを読み取り、「これは並べるべきか、選ぶべきか」を的確に判断するための、実践的な思考の指針を確立します。

このモジュールを学び終えたとき、皆様は単なる計算手法を身につけるだけではありません。物事の本質的なグループ構造を見抜き、無駄なく重複なく対象を数え上げる「選択と構成の数学」を体得しているはずです。この能力は、皆様の論理的思考力を新たな高みへと引き上げる、確かな翼となるでしょう。

目次

1. 組合せ (nCr) の定義と計算

順列の世界では、「順序」が絶対的な意味を持っていました。A君が委員長でB君が副委員長の場合と、その逆では、全く異なる結果として区別されました。しかし、世の中には順序が問題にならない状況、つまり、単に「どのメンバーが選ばれたか」だけが重要な場面が無数に存在します。3人の掃除当番を選ぶとき、その3人がどのような順番で選ばれようと、最終的なメンバー構成は同じです。このような「順序を問わない選び方」を数学的に扱うのが組合せ (Combination) です。ここでは、組合せの概念を厳密に定義し、その計算方法が順列とどのように関連しているのかを深く探求します。

1.1. 組合せ (Combination) とは何か

組合せ (Combination) とは、いくつかの異なるものの中から、順序を考慮せずに、特定個数を取り出して作った**組（グループ）**の総数を指します。英語の “Combination” は「結びつけること」を意味し、要素を単に集めて一つのグループにする、というニュアンスを的確に表しています。

組合せの核心的な特徴は、以下の二点です。

  1. 異なるものから選ぶ: 順列と同様に、選ぶ元となる要素は、すべて互いに区別できるものであることが基本です。
  2. 順序を考慮しない: 選んだ要素の並び順は区別しません。例えば、{A, B, C} という集合から2つの要素を選ぶ場合、(A, B) を選ぶことと (B, A) を選ぶことは、組合せとしては全く同じ1通りの選び方と見なします。

この「順序を考慮しない」という一点が、順列 (Permutation) との決定的な違いです。順列が「整列したチーム」の数を数えるのに対し、組合せは「チームのメンバー構成」そのものの数を数える、と比喩的に理解することができます。

記号 \(_n\mathrm{C}_r\) の導入

異なる \(n\) 個のものから \(r\) 個を取り出して作る組合せの総数は、記号 \(_n\mathrm{C}_r\) または \(C(n, r)\)、あるいは \(\binom{n}{r}\) と表されます。

この C は Combination の頭文字です。

  • \(n\): 選ぶ元の総数
  • \(r\): 取り出す個数

\(_n\mathrm{C}_r\) と書かれたとき、それは「n個の区別できるアイテムのストックから、r個のアイテムを選び出して一つのグループを作る方法は、何通りあるか？」という問いを数学的に表現したものだと理解してください。順列と同様に、\(0 \le r \le n\) であり、\(n\) は非負整数、\(r\) は非負整数です。（\(r=0\) の場合、つまり1つも選ばないという組合せも1通りと考えるのが一般的です。）

具体例で見る組合せ

5人の生徒（A, B, C, D, E）の中から、3人の代表委員を選ぶとします。この委員たちに役職の区別はありません。この場合の総数は、\(_5\mathrm{C}_3\) と表されます。

例えば、{A, B, C} という3人が選ばれたとしましょう。

順列の世界では、この3人を一列に並べる方法は (A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), (C, B, A) の \(3! = 6\) 通りありましたが、組合せの世界では、これらはすべて「AとBとCが選ばれた」という単一の事象であり、1通りとして数えます。

組合せで区別されるのは、メンバー構成が異なる場合のみです。

  • {A, B, C}
  • {A, B, D}
  • {A, B, E}
  • … など

これらは、メンバーが異なるため、すべて異なる組合せとしてカウントされます。

1.2. 順列からの導出：「順序のキャンセル」

では、組合せの総数 \(_n\mathrm{C}_r\) はどのように計算すればよいのでしょうか。ここで、順列 \(_n\mathrm{P}_r\) との関係性を考えることが、最も本質的な理解に繋がります。

思考プロセス

  1. ステップ1：まず、順序を付けて \(r\) 個を選び出す（順列）異なる \(n\) 個のものから \(r\) 個を取り出して一列に並べる方法、すなわち順列の総数は \(_n\mathrm{P}_r\) 通りです。
  2. ステップ2：重複度を考えるこの \(_n\mathrm{P}_r\) 通りの順列の中には、選ばれたメンバーは同じなのに、並び順だけが異なるものが多数含まれています。例えば、\(r\) 個の特定の要素（例えば {a, b, …, r個の要素}）からなる一つの組合せを考えます。この \(r\) 個の要素を一列に並べる方法は、\(r!\) 通りあります。順列の計算 \(_n\mathrm{P}_r\) では、この \(r!\) 通りをすべて別々のものとして数え上げてしまっています。
  3. ステップ3：重複度で割る（順序のキャンセル）組合せでは、この \(r!\) 通りの並びをすべて「1通り」と見なしたいわけです。これは、\(_n\mathrm{P}_r\) という過剰なカウントを、各組に生じている重複度 \(r!\) で割ることで修正できることを意味します。この割り算の操作こそが、順列に付与されていた「順序」という情報をキャンセルする行為に相当します。

【\(_n\mathrm{C}_r\) の計算式】

\[

_n\mathrm{C}_r = \frac{_n\mathrm{P}_r}{r!}

\]この式は、組合せと順列の関係を最も直接的に示しています。

さらに、\(_n\mathrm{P}_r = \frac{n!}{(n-r)!}\) でしたから、これを代入すると、組合せの計算で最もよく使われる階乗の形が得られます。

\[

_n\mathrm{C}_r = \frac{n!}{r!(n-r)!}

\]この式は、「\(n\) 個の要素を、『選ばれる \(r\) 個のグループ』と『選ばれない \(n-r\) 個のグループ』に分ける方法」と解釈することもでき、前モジュールで学んだ「同じものを含む順列」の考え方（\(r\) 個の○と \(n-r\) 個の×を並べる順列）と一致しています。

具体例の計算

先ほどの5人の生徒から3人の代表委員を選ぶ問題（\(_5\mathrm{C}_3\)）を計算してみましょう。

  • 方法1：順列から割る

\[

\]_5\mathrm{C}_3 = \frac{_5\mathrm{P}_3}{3!} = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = \frac{60}{6} = 10

]

  • 方法2：階乗の公式で計算

\[

\]_5\mathrm{C}_3 = \frac{5!}{3!(5-3)!} = \frac{5!}{3!2!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1)(2 \times 1)} = \frac{120}{6 \times 2} = \frac{120}{12} = 10

]

どちらの方法でも、答えは 10通り となります。

実際の計算では、方法1のように、分子に \(n\) から \(r\) 個の数を掛けたもの、分母に \(r\) の階乗を書き、約分しながら計算するのが最も効率的です。

別の具体例：トランプの役

13枚のスペードのカードから、5枚のカードを任意に選ぶとき、何通りの選び方があるか。

カードを選ぶ際、どの順番で手札に加わったかは問題になりません。最終的な手札の構成が重要です。したがって、これは組合せの問題です。

13枚の異なるカードから5枚を選ぶ組合せなので、\(_13\mathrm{C}_5\) を計算します。

\[

_13\mathrm{C}_5 = \frac{13 \times 12 \times 11 \times 10 \times 9}{5 \times 4 \times 3 \times 2 \times 1}

\]約分を巧みに行います。

  • \(5 \times 2 = 10\) なので、分子の10と消去。
  • \(4 \times 3 = 12\) なので、分子の12と消去。

\[

= 13 \times 11 \times 9 = 1287

\]よって、1287通り の選び方があります。

1.3. 特殊な場合の組合せ

  • \(_n\mathrm{C}_n\): \(n\) 個の中から \(n\) 個すべてを選ぶ方法全員を選ぶしかないので、明らかに1通りです。公式で計算しても、\(_n\mathrm{C}_n = \frac{n!}{n!0!} = 1\) となります。（ここで \(0!=1\) が活きてきます）
  • \(_n\mathrm{C}_1\): \(n\) 個の中から1個を選ぶ方法\(n\) 個の選択肢があるので、\(n\) 通りです。公式では、\(_n\mathrm{C}_1 = \frac{n!}{1!(n-1)!} = \frac{n \times (n-1)!}{1 \times (n-1)!} = n\) となります。
  • \(_n\mathrm{C}_0\): \(n\) 個の中から1つも選ばない方法「選ばない」という選択が1通りある、と解釈します。これは空集合を選ぶことに相当します。公式では、\(_n\mathrm{C}_0 = \frac{n!}{0!(n-0)!} = \frac{n!}{1 \times n!} = 1\) となります。

組合せの概念は、順列から「順序」という情報を取り除く（キャンセルする）ことによって生まれる、より抽象的で本質的な「選択」のモデルです。この「割ることで順序を消す」という発想は、場合の数の様々な場面で応用される極めて重要な思考法であり、これをマスターすることが、より複雑な問題へ挑むための第一歩となります。

2. nCr = nCn-r の対称性

組合せの計算に少し慣れてくると、その数式の中に潜む美しい性質に気づき始めます。その中でも最も基本的かつ強力なものが、\(_n\mathrm{C}_r = n\mathrm{C}{n-r}\) という対称性の公式です。この性質は、単に計算を簡略化する便利なツールであるだけでなく、組合せという概念が持つ本質的な二面性を我々に教えてくれます。それは、「選ぶこと」と「残すこと」が、実は同じコインの裏表であるという深遠な事実です。

2.1. 対称性の直感的・組み合わせ論的な理解

この公式 \(_n\mathrm{C}_r = n\mathrm{C}{n-r}\) の正しさを理解するのに、複雑な数式は必要ありません。その意味を直接的に解釈することで、なぜこの等式が成り立たなければならないのかが直感的に分かります。

思考の核心：「選ぶ」 vs 「残す」

ここに、\(n\) 人の生徒がいると想像してください。この中から、\(r\) 人の掃除当番を選び出すことを考えます。

その選び方の総数が \(_n\mathrm{C}_r\) 通りであることは、既に学びました。

さて、ここで視点を180度変えてみましょう。

「\(r\) 人の掃除当番を選ぶ」という行為は、同時に「掃除当番ではない \((n-r)\) 人を決定する」という行為と全く同じことです。

A君、B君、C君を当番に選んだ瞬間、「残りの人々」というグループが自動的に確定します。逆に、「残りの人々」を確定させれば、当番のメンバーも一意に決まります。

つまり、

「\(n\) 人の中から当番になる \(r\) 人を選ぶ」という選択問題と、

「\(n\) 人の中から当番にならない \((n-r)\) 人を選ぶ」という選択問題は、

完全に一対一で対応しており、その場合の数は等しくなければなりません。

後者の「当番にならない \((n-r)\) 人を選ぶ」場合の数は、組合せの定義から \(n\mathrm{C}{n-r}\) 通りです。

したがって、この二つの場合の数は等しい、すなわち、

\[

_n\mathrm{C}_r = n\mathrm{C}{n-r}

\]が成り立つ、と結論付けることができます。

この組み合わせ論的な証明は、数式の操作に頼らず、組合せの意味そのものに根差しているため、非常に強力で忘れにくいものです。「\(r\) 個のボールを箱に入れる選び方」と「\((n-r)\) 個のボールを箱の外に残す選び方」が同じである、と考えても良いでしょう。

具体例

10人のクラスから、8人のパーティー参加者を選ぶ方法 (\(_10\mathrm{C}_8\)) を考えます。

これは、視点を変えれば、「パーティーに参加しない2人を選ぶ」方法 (\(_10\mathrm{C}_2\)) と全く同じです。

A, B, C, D, E, F, G, H の8人を選ぶことは、I, J の2人を留守番に選ぶことと完全に同義です。

したがって、\(_10\mathrm{C}_8 = _10\mathrm{C}_2\) が成り立ちます。

2.2. 数式による代数的証明

直感的な理解に加えて、階乗の定義式からこの対称性を代数的に証明することも重要です。これにより、我々の直感が数理的に堅固な基盤の上に成り立っていることを確認できます。

証明

まず、左辺 \(_n\mathrm{C}_r\) を階乗の公式で展開します。

\[

_n\mathrm{C}_r = \frac{n!}{r!(n-r)!} \quad \cdots ①

\]次に、右辺 \(n\mathrm{C}{n-r}\) を階乗の公式で展開します。

公式の \(r\) の部分に、\((n-r)\) を代入することになります。

\[

n\mathrm{C}{n-r} = \frac{n!}{(n-r)! (n – (n-r))!}

\]右辺の分母の \((n – (n-r))!\) の部分を計算すると、\((n – n + r)! = r!\) となります。

したがって、

\[

n\mathrm{C}{n-r} = \frac{n!}{(n-r)! r!} \quad \cdots ②

\]①と②の式を比較すると、分母の \(r!\) と \((n-r)!\) の順序が入れ替わっているだけで、両者は完全に同一の式であることが分かります。

よって、\(_n\mathrm{C}_r = n\mathrm{C}{n-r}\) が証明されました。

（証明終）

この代数的証明は、階乗の定義から機械的に導かれるものであり、組み合わせ論的な解釈の正しさを形式的に裏付けています。

2.3. 対称性の実践的活用

この公式の最大の利点は、組合せの計算を大幅に簡略化できる点にあります。

組合せ \(_n\mathrm{C}_r\) の計算では、\(r\) の値が大きいと、分子・分母に多くの項が並び、計算が煩雑になります。

この公式を使えば、\(r > n/2\) の場合に、計算する項がより少ない \(n\mathrm{C}{n-r}\) に変換することができます。

例題1：\(_10\mathrm{C}_8\) の計算

\(r=8\) であり、\(n/2 = 5\) よりも大きいので、公式を適用します。

\(n-r = 10-8=2\) なので、

\[

_{10}\mathrm{C}_8 = _{10}\mathrm{C}_2

\]\(_10\mathrm{C}_2\) の方が、はるかに計算が楽です。

\[

_{10}\mathrm{C}_2 = \frac{10 \times 9}{2 \times 1} = 45

\]もし、\(_10\mathrm{C}_8\) を直接計算しようとすると、

\[

_{10}\mathrm{C}_8 = \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3}{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}

\]となり、多くの約分が必要で、計算ミスのリスクも高まります。

例題2：\({100}\mathrm{C}{97}\) の計算

\(r=97\) は非常に大きな数ですが、\(n-r = 100-97=3\) となります。

\[

{100}\mathrm{C}{97} = _{100}\mathrm{C}_3 = \frac{100 \times 99 \times 98}{3 \times 2 \times 1}

\]計算を進めると、

\[

= 100 \times (33/1) \times (49/1) = 50 \times 33 \times 98 = 161700

\]このように、一見して圧倒されるような大きな組合せの計算も、この対称性を利用することで、現実的な範囲の計算に落とし込むことができるのです。

まとめ

\(_n\mathrm{C}_r = n\mathrm{C}{n-r}\) という対称性は、

  • 組み合わせ論的には、「\(r\) 個を選ぶ」ことと「\((n-r)\) 個を残す」ことの同値性を示し、
  • 代数的には、階乗の定義式から自然に導かれ、
  • 実践的には、\(r\) が \(n/2\) より大きい場合の計算を劇的に簡略化する

という、三つの重要な側面を持っています。この性質を深く理解し、自在に使いこなすことは、組合せの世界をより効率的かつエレガントに探求するための必須のスキルと言えるでしょう。

3. パスカルの三角形と組合せの数の性質

組合せの数 \(_n\mathrm{C}_r\) を、\(n\) と \(r\) を変えながら計算していくと、そこに驚くほど規則的で美しい模様が浮かび上がってきます。その模様を視覚的に表現したものがパスカルの三角形 (Pascal’s Triangle)です。この三角形は、単なる数の羅列ではなく、組合せの数が持つ様々な深い性質を内包した、数学的な宝の地図のようなものです。ここでは、パスカルの三角形の構造を解き明かし、そこに隠された重要な公式や性質を組み合わせ論的な視点から探求していきます。

3.1. パスカルの三角形の構築

パスカルの三角形は、組合せの数 \(_n\mathrm{C}_r\) (ただし \(n \ge 0, 0 \le r \le n\)) を、\(n\) を行、\(r\) を列として三角形状に配置したものです。

構築方法

  • 第0段 (n=0): \(_0\mathrm{C}_0 = 1\)
  • 第1段 (n=1): \(_1\mathrm{C}_0 = 1, _1\mathrm{C}_1 = 1\)
  • 第2段 (n=2): \(_2\mathrm{C}_0 = 1, _2\mathrm{C}_1 = 2, _2\mathrm{C}_2 = 1\)
  • 第3段 (n=3): \(_3\mathrm{C}_0 = 1, _3\mathrm{C}_1 = 3, _3\mathrm{C}_2 = 3, _3\mathrm{C}_3 = 1\)
  • 第4段 (n=4): \(_4\mathrm{C}_0 = 1, _4\mathrm{C}_1 = 4, _4\mathrm{C}_2 = 6, _4\mathrm{C}_3 = 4, _4\mathrm{C}_4 = 1\)

これを図として配置すると、以下のようになります。

1      (n=0)
1 1     (n=1)
1 2 1    (n=2)
1 3 3 1   (n=3)
1 4 6 4 1  (n=4)
1 5 10 10 5 1 (n=5)
...................

この三角形をよく観察すると、いくつかの単純な規則性が見えてきます。

  1. 各段の両端は必ず 1 である。（\(_n\mathrm{C}_0 = 1, _n\mathrm{C}_n = 1\) に対応）
  2. 各段は、中央に対して左右対称である。（\(_n\mathrm{C}_r = n\mathrm{C}{n-r}\) に対応）
  3. 両端以外の数は、その左上と右上の数の和に等しい。例えば、第4段の 6 は、その上の段の 3 と 3 の和（\(6 = 3+3\)）です。第5段の 10 は、その上の段の 4 と 6 の和（\(10 = 4+6\)）です。

この3番目の性質こそが、パスカルの三角形の最も根幹をなす生成規則であり、組合せの数における極めて重要な漸化式を表しています。

3.2. 中心的な性質：\(_n\mathrm{C}_r = {n-1}\mathrm{C}{r-1} + _{n-1}\mathrm{C}_r\)

パスカルの三角形の生成規則を、\(_n\mathrm{C}_r\) の記号を用いて数式で表現すると、以下のようになります。

【パスカルの三角形の漸化式】

\[

_n\mathrm{C}_r = {n-1}\mathrm{C}{r-1} + _{n-1}\mathrm{C}_r \quad (\text{ただし } 1 \le r \le n-1)

\]この公式は、\((n, r)\) の組合せの数を、より小さな \(n-1\) の世界の組合せの数から計算できることを示しています。この公式がなぜ成り立つのかを、代数的な証明と組み合わせ論的な証明の両面から理解することが重要です。

代数的な証明

右辺の \({n-1}\mathrm{C}{r-1} + _{n-1}\mathrm{C}_r\) を階乗の公式で展開し、通分して計算すると、左辺の \(_n\mathrm{C}_r\) に一致することを示すことができます。

\[

{n-1}\mathrm{C}{r-1} + _{n-1}\mathrm{C}_r = \frac{(n-1)!}{(r-1)!(n-r)!} + \frac{(n-1)!}{r!(n-r-1)!}

\]分母を \(r!(n-r)!\) に通分するために、第1項の分母・分子に \(r\) を、第2項の分母・分子に \((n-r)\) を掛けます。

\[

= \frac{r \cdot (n-1)!}{r!(n-r)!} + \frac{(n-r) \cdot (n-1)!}{r!(n-r)!}

\]\[

= \frac{(r + n-r) \cdot (n-1)!}{r!(n-r)!} = \frac{n \cdot (n-1)!}{r!(n-r)!} = \frac{n!}{r!(n-r)!} = _n\mathrm{C}_r

\]となり、左辺と一致します。（証明終）

組み合わせ論的な証明（より本質的）

数式による証明も重要ですが、この公式の魂は、その組み合わせ論的な意味にあります。

「\(n\) 人の異なる人々から \(r\) 人の代表を選ぶ」という状況を考えます。その総数が \(_n\mathrm{C}_r\) です。

ここで、\(n\) 人の中に特定の人物Aさんがいるとして、Aさんの処遇に注目して場合分けをします。（これは和の法則の考え方です）

  • 場合1：Aさんが代表に選ばれる場合\(r\) 人の代表団のメンバーのうち、1つの席はAさんで確定しています。残りの \((r-1)\) 個の席を、Aさんを除く \((n-1)\) 人の中から選ぶ必要があります。その選び方は \({n-1}\mathrm{C}{r-1}\) 通りです。
  • 場合2：Aさんが代表に選ばれない場合Aさんは最初から除外されます。\(r\) 人の代表団のメンバー全員を、Aさんを除く \((n-1)\) 人の中から選ぶ必要があります。その選び方は \(_{n-1}\mathrm{C}_r\) 通りです。

Aさんが選ばれるか選ばれないかの2つのケースは、互いに排反であり、すべての可能性を網羅しています。したがって、和の法則により、全体の総数 \(_n\mathrm{C}_r\) は、この2つのケースの和に等しくなります。

\[

_n\mathrm{C}_r = {n-1}\mathrm{C}{r-1} + _{n-1}\mathrm{C}_r

\]この証明は、「特定の要素に着目して場合分けする」という、組み合わせ論における非常に強力な問題解決テクニックそのものです。この考え方を理解することで、公式を単なる記号の羅列ではなく、生きた論理として捉えることができます。

3.3. パスカルの三角形に隠された他の性質

パスカルの三角形は、上記の中心的な漸化式の他にも、多くの美しい性質を秘めています。

性質1：各段の和は \(2^n\)

パスカルの三角形の第 \(n\) 段に並ぶ数の総和は、\(2^n\) になります。

  • n=0: 1 = \(2^0\)
  • n=1: 1+1 = 2 = \(2^1\)
  • n=2: 1+2+1 = 4 = \(2^2\)
  • n=3: 1+3+3+1 = 8 = \(2^3\)
  • n=4: 1+4+6+4+1 = 16 = \(2^4\)

数式で表現すると、

\[

\sum_{r=0}^{n} {_n\mathrm{C}_r} = _n\mathrm{C}_0 + _n\mathrm{C}_1 + _n\mathrm{C}_2 + \cdots + _n\mathrm{C}_n = 2^n

\]組み合わせ論的な意味:

この等式の左辺は、「\(n\) 個のものから0個選ぶ組合せ」+「1個選ぶ組合せ」+ … +「\(n\) 個選ぶ組合せ」の総和です。

これは、\(n\) 個の要素からなる集合の部分集合の総数を求めていることに他なりません。

一方、部分集合の総数は、各要素について「その部分集合に含めるか、含めないか」の2択を、\(n\) 個の要素それぞれに対して独立に行う重複順列の問題と考えることができました（前モジュール参照）。

したがって、その総数は \(2 \times 2 \times \cdots \times 2 = 2^n\) となります。

この二つの異なる数え方が同じものを指しているため、この等式が成り立ちます。

性質2：ホッケースティック・パターン

パスカルの三角形で、端の1から斜めに好きなだけ数を足していくと、その合計は、最後に足した数の隣の段の、内側に入った数に等しくなります。

その形がホッケースティックに似ていることから、この名で呼ばれます。

例：1 + 3 + 6 = 10

例：1 + 4 + 10 = 15

数式で表現すると、

\[

\sum_{i=r}^{n} {_i\mathrm{C}_r} = _{r}\mathrm{C}_r + _{r+1}\mathrm{C}_r + \cdots + _{n}\mathrm{C}_r = {n+1}\mathrm{C}{r+1}

\]この証明は、\(_k\mathrm{C}_r = {k+1}\mathrm{C}{r+1} – k\mathrm{C}{r+1}\) という関係式（中心的な漸化式を移項したもの）を利用して、途中の項が次々とキャンセルされることを示すことで可能です（数学的帰納法でも証明できます）。

パスカルの三角形は、組合せの数が持つ豊かな内部構造を視覚的に明らかにしてくれるだけでなく、そこに現れる様々な等式が、組み合わせ論的な思考法（特定の要素に着目した分割、異なる方法での同一対象の計数など）の絶好の訓練場となります。この三角形を眺め、その性質を味わうことは、組合せの世界の奥深さと美しさを実感する素晴らしい体験となるでしょう。

4. 組分け問題（区別の有無）

組合せの応用問題の中で、最も重要でありながら、多くの学習者がつまずきやすいのが「組分け問題」です。これは、いくつかの人や物を、複数のグループに分ける方法の総数を数え上げる問題です。この問題を難しくしている要因は、「分けるモノ」と「分けられる先の組（グループ）」に区別があるかないかという、わずかでありながら決定的な条件の違いです。この区別の有無を正確に見抜き、適切な計算モデルを適用する能力が、組分け問題を攻略する鍵となります。

4.1. 基本的な組分け：すべての組が区別される場合

最も基本的なパターンは、分ける先の組がすべて名前などで区別されている場合です。

思考プロセス

\(n\) 個の異なるものを、A組に \(p\) 個、B組に \(q\) 個、C組に \(r\) 個… と分ける（ただし \(p+q+r+\cdots = n\)）場合を考えます。

これは、一連の連続した選択プロセスと見なすことができます。

  1. まず、\(n\) 個の中からA組に入れる \(p\) 個を選びます。→ \(_n\mathrm{C}_p\) 通り
  2. 次に、残った \((n-p)\) 個の中からB組に入れる \(q\) 個を選びます。→ \(_{n-p}\mathrm{C}_q\) 通り
  3. さらに、残った \((n-p-q)\) 個の中からC組に入れる \(r\) 個を選びます。→ \(_{n-p-q}\mathrm{C}_r\) 通り
  4. …これを最後まで続けます。

これらの選択は連続して行われるので、積の法則により、すべてを掛け合わせます。

例題1：人数の異なる組への組分け

9人の生徒を、4人、3人、2人の3つの組 A, B, C に分ける方法は何通りか。

  • ステップ1 (A組): 9人からA組の4人を選ぶ → \(_9\mathrm{C}_4\) 通り
  • ステップ2 (B組): 残りの5人からB組の3人を選ぶ → \(_5\mathrm{C}_3\) 通り
  • ステップ3 (C組): 残りの2人からC組の2人を選ぶ → \(_2\mathrm{C}_2\) 通り

総数は、

\[

_9\mathrm{C}_4 \times _5\mathrm{C}_3 \times _2\mathrm{C}_2 = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1} \times \frac{5 \cdot 4 \cdot 3}{3 \cdot 2 \cdot 1} \times 1

\]\[

= (126) \times (10) \times 1 = 1260

\]答えは 1260通り となります。

ポイント: 組の人数がすべて異なっている場合、その「人数」自体が組の区別を与えているため、たとえ組にA, B, Cという名前がなくても、区別があるものとして扱います。「4人の組」「3人の組」「2人の組」は、明らかに異なる組だからです。

4.2. 難関：同じ人数の組があり、組が区別されない場合

組分け問題が真に難しくなるのは、同じ人数のグループが複数存在し、かつ、それらのグループ自体に区別がない（名前がついていない）場合です。

思考の核心：区別の仮定と重複の解消

この問題を解くための定石は、「一旦、組に区別があるものと仮定して計算し、その後で、組の区別をなくすことによって生じる重複分を割り算で消去する」というものです。これは、「同じものを含む順列」で使った思考法と全く同じ構造をしています。

例題2：同じ人数の区別ない組への組分け

9人の生徒を、3人ずつ3つの組に分ける方法は何通りか。

思考プロセス

  1. ステップ1：組に区別があると仮定して計算まず、3つの組に A, B, C という名前を付けて、区別があるものとして計算します。
  • A組の3人を選ぶ：\(_9\mathrm{C}_3\) 通り
  • B組の3人を選ぶ：\(_6\mathrm{C}_3\) 通り
  • C組の3人を選ぶ：\(_3\mathrm{C}_3\) 通り積の法則より、\(_9\mathrm{C}_3 \times _6\mathrm{C}_3 \times _3\mathrm{C}_3 = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} \times \frac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} \times 1 = 84 \times 20 \times 1 = 1680\) 通り。
  1. ステップ2：重複度を考えるこの1680通りの中には、実際には同じ組分けになるものが重複して数えられています。例えば、ある一つの組分けとして、グループ1: {a, b, c}グループ2: {d, e, f}グループ3: {g, h, i}という分け方があったとします。ステップ1の計算では、
  • A組が{a,b,c}, B組が{d,e,f}, C組が{g,h,i} の場合
  • A組が{d,e,f}, B組が{a,b,c}, C組が{g,h,i} の場合
  • …などというように、3つのグループ {a,b,c}, {d,e,f}, {g,h,i} の間で、A, B, C というラベルを付け替えるだけのものを、すべて別々にカウントしてしまっています。3つの区別された組 A, B, C の間でグループを入れ替える方法は \(3! = 6\) 通りあります。
  1. ステップ3：重複度で割るしたがって、ステップ1で得られた1680通りという数は、正しい組分けの数を \(3!\) 倍に過剰カウントしていることになります。正しい場合の数を求めるには、この重複度 \(3!\) で割る必要があります。

\[

\]\text{総数} = \frac{_9\mathrm{C}_3 \times _6\mathrm{C}_3 \times _3\mathrm{C}_3}{3!} = \frac{1680}{6} = 280

]

答えは 280通り となります。

一般化

\(n\) 個のものを分ける際に、同じ人数 \(p\) の組が \(k\) 個あり、それらの組に区別がない場合、区別があるとして計算した後に \(k!\) で割る必要があります。

例題3：一部の組だけ人数が同じ場合

8人の生徒を、2人、2人、2人、2人の4つの組に分ける方法は何通りか。

  • 区別ありと仮定：\(_8\mathrm{C}_2 \times _6\mathrm{C}_2 \times _4\mathrm{C}_2 \times _2\mathrm{C}_2 = 28 \times 15 \times 6 \times 1 = 2520\)
  • 同じ人数（2人）の組が4つあるので、重複度は \(4!\)
  • 総数 = \(\frac{2520}{4!} = \frac{2520}{24} = 105\) 通り。

例題4：人数の構成が混在している場合

10人の生徒を、3人、3人、2人、2人の4つの組に分ける方法は何通りか。

  • 区別ありと仮定：\(_{10}\mathrm{C}_3 \times _7\mathrm{C}_3 \times _4\mathrm{C}_2 \times _2\mathrm{C}_2 = 120 \times 35 \times 6 \times 1 = 25200\)
  • 重複度を考える：
  • 3人の組が2つある → \(2!\) の重複
  • 2人の組が2つある → \(2!\) の重複
  • 総数 = \(\frac{25200}{2! \times 2!} = \frac{25200}{4} = 6300\) 通り。

4.3. 「分けるモノ」と「組」の区別マトリックス

組分け問題を解く際には、常に以下の2つの問いを自問自答することが極めて重要です。

  1. 分けるモノ（人、ボールなど）は、区別できるか？
  • YES: これまで議論してきた組合せの世界。
  • NO: これは「重複組合せ」などで扱う、より高度な問題（後述）。高校数学の基本問題では、ほとんどの場合「区別できるモノ」を扱います。
  1. 分けられる組（部屋、グループなど）は、区別できるか？
  • YES: 単純な組合せの連続（積の法則）。
  • NO: 同じ人数の組がある場合、その組の数 \(k\) の階乗 \(k!\) で割る操作が必要。

思考のフローチャート

  1. 問題文を読む。対象（モノ）と行き先（組）を特定する。
  2. モノは区別できるか？ → YES (通常)
  3. 組は区別できるか？
  • 組に名前（A, B, C…）がついている → YES, 区別あり
  • 組の人数がすべて異なる → YES, 区別あり
  • 組に名前がなく、同じ人数の組が複数ある → NO, 区別なし
  1. 計算方法を決定する。
  • 区別あり → \(_n\mathrm{C}_p \times _{n-p}\mathrm{C}_q \times \cdots\)
  • 区別なし → 上記の計算結果を、同じ人数の組の個数の階乗で割る。

この体系的な思考プロセスを身につけることで、一見複雑に見える組分け問題も、その構造を冷静に分析し、正しい道筋で解き明かすことが可能になります。

5. 重複組合せ

これまでの組合せでは、「異なる \(n\) 個のものから」という前提があり、同じものを二度選ぶことはできませんでした。しかし、実社会には「繰り返し選ぶこと」が許される状況が溢れています。例えば、果物屋でリンゴ、ミカン、バナナの中から好きなものを合計5個買うとき、リンゴだけを5個買っても構いません。このように、いくつかの種類の中から、重複を許して特定個数を選ぶ方法の総数を扱うのが重複組合せ (Combination with Repetition) です。この問題は、一見すると複雑に思えますが、「仕切り棒」という独創的なアイデアを用いることで、驚くほどシンプルに解決することができます。

5.1. 重複組合せの概念

重複組合せとは、\(n\) 種類のものから、重複を許して \(r\) 個を取り出す組合せの総数を指します。

順序は問わないため、例えば「リンゴ2個、ミカン1個」と「ミカン1個、リンゴ2個」は同じ選び方と見なします。

記号では \(_n\mathrm{H}_r\) と表されます。H は Homogeneous product（同次積）に由来すると言われています。

具体例で考える

リンゴ、ミカン、バナナの3種類（\(n=3\)）の果物から、重複を許して5個（\(r=5\)）買う場合の数を考えてみましょう。

これを \(_3\mathrm{H}_5\) と書きます。

可能な買い方をいくつか書き出してみましょう。

  • {リ, リ, リ, リ, リ}
  • {リ, リ, リ, リ, ミ}
  • {リ, リ, リ, ミ, バ}
  • {リ, ミ, ミ, バ, バ}
  • …など

このように、場合の数が多く、体系的に数え上げるのが難しいことが分かります。単純な \(_n\mathrm{C}_r\) や \(n^r\) の公式は適用できそうにありません。ここで、全く新しい発想の転換が必要となります。

5.2. 「仕切り棒」モデルによる思考の転換

重複組合せの問題を解くための鍵は、問題を「モノを選ぶ」ことから、「記号を並べる」ことへと翻訳することです。この翻訳の道具となるのが「丸 (○) と仕切り棒 ( | )」です。

思考プロセス

\(n\) 種類のものから重複を許して \(r\) 個を選ぶ状況を、以下のようにモデル化します。

  1. 選ぶモノを「丸 (○)」で表現する:選ぶ \(r\) 個のモノを、区別のない \(r\) 個の「○」で表します。
  2. 種類の区切りを「仕切り棒 ( | )」で表現する:\(n\) 種類のものを区別するために、その間に仕切りを入れます。\(n\) 種類を分けるには、\((n-1)\) 本の「 | 」が必要です。

モデル化の具体例：\(_3\mathrm{H}_5\)

3種類の果物（リンゴ, ミカン, バナナ）から5個選ぶ場合を考えます。

  • 選ぶ5個の果物を、5個の「○○○○○」で表します。
  • 3種類の区切りとして、2本の「 | 」を用意します。

この「○」5個と「 | 」2個、合計7個の記号を一列に並べることを考えます。

この並べ方と、果物の買い方を一対一で対応させます。

  • ○○ | ○○ | ○これは、1番目の仕切りより左にある「○」をリンゴ、1番目と2番目の仕切りの間にある「○」をミカン、2番目の仕切りより右にある「○」をバナナの個数と解釈します。→ リンゴ 2個, ミカン 2個, バナナ 1個
  • ○○○○○ | |→ リンゴ 5個, ミカン 0個, バナナ 0個
  • | ○○○ | ○○→ リンゴ 0個, ミカン 3個, バナナ 2個
  • ○○ | | ○○○→ リンゴ 2個, ミカン 0個, バナナ 3個

このように、7個の場所（ポジション）に、5個の「○」と2本の「 | 」を並べるすべての並べ方が、3種類の果物から5個を選ぶすべての買い方と、一対一で完全に対応していることが分かります。

計算への落とし込み

この問題は、最終的に「合計 \((r+n-1)\) 個の場所から、○を置く \(r\) 個の場所を選ぶ組合せ」の問題に帰着します。（あるいは、| を置く \(n-1\) 個の場所を選ぶ組合せと考えても同じです。）

これは、前モジュールで学んだ「同じものを含む順列」の考え方そのものです。

合計 \((r+n-1)\) 個のもののうち、○が \(r\) 個、| が \((n-1)\) 個あるので、その並べ方は

\[

\frac{(r+n-1)!}{r!(n-1)!}

\]となり、これは組合せの記号を使えば \(_{r+n-1}\mathrm{C}_r\) と書けます。

【重複組合せの公式】

\(n\) 種類のものから重複を許して \(r\) 個を取り出す重複組合せの総数 \(_n\mathrm{H}_r\) は、

\[

_n\mathrm{H}_r = _{n+r-1}\mathrm{C}_r

\]と計算できる。

例題の計算

\(_3\mathrm{H}_5\) を計算してみましょう。

\(n=3, r=5\) なので、

\[

_3\mathrm{H}_5 = _{3+5-1}\mathrm{C}_5 = _7\mathrm{C}_5 = _7\mathrm{C}_2 = \frac{7 \times 6}{2 \times 1} = 21

\]したがって、3種類の果物から5個買う方法は 21通り あることが分かります。

5.3. 重複組合せの応用モデル

「仕切り棒」モデルの強力な点は、一見すると重複組合せには見えない様々な問題を、同じフレームワークで解決できることです。

モデル1：方程式の非負整数解

方程式 \(x + y + z = 7\) を満たす、非負整数（0以上の整数）の解 \((x, y, z)\) の組は、全部でいくつあるか。

思考の転換

この問題を、以下のように解釈し直します。

「\(x, y, z\) の3種類のものから、重複を許して合計7個を選ぶ方法」

  • \(x\) の値は、種類 \(x\) を選んだ個数
  • \(y\) の値は、種類 \(y\) を選んだ個数
  • \(z\) の値は、種類 \(z\) を選んだ個数

例えば、解 \((x, y, z) = (2, 3, 2)\) は、「種類xを2個、種類yを3個、種類zを2個選んだ」ことに対応します。

したがって、この問題は \(n=3\) 種類から \(r=7\) 個を選ぶ重複組合せ \(_3\mathrm{H}_7\) と等価です。

計算

\[

_3\mathrm{H}_7 = _{3+7-1}\mathrm{C}_7 = _9\mathrm{C}_7 = _9\mathrm{C}_2 = \frac{9 \times 8}{2 \times 1} = 36

\]答えは 36個 となります。

モデル2：方程式の正の整数解

方程式 \(x + y + z = 7\) を満たす、正の整数（1以上の整数）の解 \((x, y, z)\) の組は、全部でいくつあるか。

思考の転換

今度は、\(x, y, z\) は最低でも1でなければなりません。これは、重複組合せの言葉で言えば「各種類を、最低でも1つは選ばなければならない」という制約が付いた状況です。

この制約を処理するための定石は、「先に最低限の個数を配っておき、残りを自由に分配する」という方法です。

  1. 事前分配:まず、\(x, y, z\) に1ずつを割り当ててしまいます。\(x’ = x-1, y’ = y-1, z’ = z-1\) とおくと、\(x’, y’, z’\) は0以上の整数（非負整数）になります。元の式に代入すると、\((x’+1) + (y’+1) + (z’+1) = 7\)\(x’ + y’ + z’ = 4\)
  2. 残りの分配:この新しい方程式 \(x’ + y’ + z’ = 4\) の非負整数解を求めれば、それが元の問題の解と一対一で対応します。これは、\(n=3\) 種類から \(r=4\) 個を選ぶ重複組合せ \(_3\mathrm{H}_4\) の問題です。

計算

\[

_3\mathrm{H}_4 = _{3+4-1}\mathrm{C}_4 = _6\mathrm{C}_4 = _6\mathrm{C}_2 = \frac{6 \times 5}{2 \times 1} = 15

\]答えは 15個 となります。

モデル3：区別のないボールを、区別のある箱に入れる

\(r\) 個の区別できないボールを、\(n\) 個の区別できる箱に入れる方法（空の箱があってもよい）。

これも重複組合せの典型的なモデルです。

  • 箱が「種類」(\(n\) 種類)
  • ボールが「選ぶモノ」(\(r\) 個)と見なせます。\(n\) 種類の箱の中から、ボールを入れる先を重複を許して \(r\) 回選ぶ、と解釈できます。総数は \(_n\mathrm{H}_r = _{n+r-1}\mathrm{C}_r\) となります。

重複組合せは、その直感に反するような解法（仕切り棒モデル）を一度理解してしまえば、非常に広範な問題を統一的に解くことができる強力な武器となります。問題を「\(n\) 種類から \(r\) 個を繰り返し選ぶ」という基本モデルに翻訳する訓練が、この分野をマスターする鍵です。

6. 最短経路問題

格子状の道路を進む「最短経路問題」は、場合の数の分野で非常にポピュラーな題材です。前モジュールでは、この問題を「→」と「↑」の記号の順列、すなわち「同じものを含む順列」として解釈しました。そのアプローチは直感的で強力ですが、実はこの問題は「組合せ」の視点から見ると、さらにシンプルで本質的な構造が浮かび上がってきます。ここでは、最短経路問題を組合せの概念を用いて再定義し、その二つの解法がなぜ一致するのかを探求します。

6.1. 最短経路問題の組合せ的再解釈

問題設定

下図のような格子状の道路がある。地点Aから地点Bまで、遠回りしないで（右または上へのみ進む）行く最短経路は何通りあるか。

[図：横にmマス、縦にnマスの格子状の道路。左下隅がA、右上隅がB]

思考の核心：「どのステップで特定の動きをするか」の選択

AからBへ最短経路で到達するためには、どのようなルートをたどろうとも、必ず

  • 右に \(m\) 回
  • 上に \(n\) 回移動する必要があります。移動の総回数は、常に \((m+n)\) 回となります。

ここで、全 \((m+n)\) 回の移動ステップを一つの列と考えてみましょう。

[1回目] [2回目] [3回目] ... [m+n回目]

この \((m+n)\) 回のステップのうち、どの \(m\) 回を「右への移動」に割り当てるかを決めれば、残りの \(n\) 回は自動的に「上への移動」に決まります。

例えば、\(m=5, n=3\) の場合、全8回の移動のうち、

「1, 2, 4, 7, 8回目を右移動にする」と決めれば、

残りの「3, 5, 6回目」が上移動となり、一つの経路（→→↑→↑↑→→）が完全に確定します。

つまり、最短経路の総数を求める問題は、

「全 \((m+n)\) 回の移動ステップの中から、右に移動する \(m\) 回のステップを選ぶ組合せ」

の問題と、完全に等価なのです。

その場合の数は、組合せの定義から \(_{m+n}\mathrm{C}_m\) となります。

もちろん、視点を変えて、「全 \((m+n)\) 回の移動ステップの中から、上に移動する \(n\) 回のステップを選ぶ組合せ」と考えても全く同じです。

その場合の数は \(_{m+n}\mathrm{C}_n\) となります。

組合せの対称性 \(_n\mathrm{C}r = n\mathrm{C}{n-r}\) から、\({m+n}\mathrm{C}_m = {m+n}\mathrm{C}{(m+n)-m} = _{m+n}\mathrm{C}_n\) であるため、どちらの考え方でも結果は同じになります。

6.2. 「同じものを含む順列」との関係

前モジュールで学んだ解法を思い出してみましょう。

\(m\) 個の「→」と \(n\) 個の「↑」、合計 \((m+n)\) 個の記号を一列に並べる「同じものを含む順列」として解釈しました。

その総数は、

\[

\frac{(m+n)!}{m! n!}

\]でした。

一方、組合せの公式 \(_{m+n}\mathrm{C}_m\) を階乗で展開してみると、

\[

_{m+n}\mathrm{C}_m = \frac{(m+n)!}{m!((m+n)-m)!} = \frac{(m+n)!}{m!n!}

\]となり、両者が完全に一致することが分かります。

これは偶然の一致ではありません。

「\((m+n)\) 個の場所から \(m\) 個の場所を選んで『→』を置く」という組合せの考え方は、結果的に「\(m\) 個の『→』と \(n\) 個の『↑』を並べる」という順列の考え方と、数学的に全く同じ構造を持っていることを示しています。

この事実は、順列と組合せという二つの概念が、いかに密接に、そして深く結びついているかを象徴しています。どちらのアプローチを取るかは、その問題をどのようにモデル化するかという、解釈の仕方の違いに過ぎないのです。

具体例の計算

横に5マス、縦に3マスの格子路で、AからBへの最短経路を求めます。

\(m=5, n=3\) なので、総移動回数は \(5+3=8\) 回です。

  • 組合せによる解法:全8回の移動のうち、右に移動する5回を選ぶ組合せ。

\[

\]_8\mathrm{C}_5 = _8\mathrm{C}_3 = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56

]

または、全8回の移動のうち、上に移動する3回を選ぶ組合せと考えても同じです。

\[

\]_8\mathrm{C}_3 = 56

]

  • 同じものを含む順列による解法:5個の「→」と3個の「↑」を並べる順列。

\[

\]\frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56

]

どちらの解法でも、答えは 56通り となり、計算過程も実質的に同じになります。

6.3. 応用：制約条件のある最短経路

組合せの考え方は、経路に制約条件が付いた場合にも柔軟に対応できます。

モデル1：特定の点を通る経路

地点Aから地点Bへ行く途中で、必ず特定の点Cを通らなければならない場合。

[図：A(左下), C(中間点), B(右上)が示された格子路]

思考プロセス

この問題は、積の法則を用いて2つの独立した最短経路問題に分解できます。

  1. AからCへの最短経路:まず、AからCまでの移動を考えます。AからCまで右に \(m_1\) 回、上に \(n_1\) 回移動する必要があるなら、その経路数は \({m_1+n_1}\mathrm{C}{m_1}\) 通りです。
  2. CからBへの最短経路:次に、CからBまでの移動を考えます。CからBまで右に \(m_2\) 回、上に \(n_2\) 回移動する必要があるなら、その経路数は \({m_2+n_2}\mathrm{C}{m_2}\) 通りです。

AからCへのどの経路を選んだとしても、CからBへの経路の選択肢の数は変わりません。したがって、積の法則により、全体の経路数はこの二つの結果の積となります。

総数 = (A→Cの経路数) \(\times\) (C→Bの経路数) = \({m_1+n_1}\mathrm{C}{m_1} \times {m_2+n_2}\mathrm{C}{m_2}\)

モデル2：特定の領域が通行止めになっている経路

経路の途中に池や工事現場など、通れない領域がある場合。

[図：格子路の中央に通行不可の長方形領域が示されている]

思考プロセス

この問題は、直接数えるのが難しい場合、余事象の考え方が有効です。

  1. 全体の最短経路数を計算する:まず、通行止めの領域がないと仮定して、AからBへのすべての最短経路数を計算します。
  2. 通行止め領域を「必ず通る」経路数を計算する:次に、全体の経路の中から、数えてはいけない経路、すなわち「通行止めの領域を通過してしまう経路」の数を計算します。多くの場合、「通行止め領域を通る」は、「特定の辺や点を必ず通る」と言い換えられます。例えば、通行止め領域の入口となる点と出口となる点を特定し、それらの点を通る経路数をモデル1の方法で計算します。（※通行止め領域への入り方が複数ある場合は、それらを排反なケースとして和の法則で合計する必要があります）
  3. 全体から引く:全体の経路数から、通行止め領域を通る経路数を引くことで、目的の経路数を求めます。

総数 = (全体の経路数) – (通行止め領域を通る経路数)

最短経路問題は、そのシンプルな見た目とは裏腹に、順列、組合せ、積の法則、和の法則、余事象といった、場合の数の基本原理が凝縮された豊かな問題です。組合せの視点から捉えることで、その構造をより明快に理解し、複雑な条件にも対応する応用力を養うことができます。

7. 図形の個数問題（三角形、対角線など）

幾何学的な図形を数え上げる問題は、組合せの概念が非常に効果的に応用される分野の一つです。平面上に配置された点や線から、特定の図形（直線、三角形、対角線など）がいくつ作れるか、という問題は、一見すると図形のセンスが問われるように思えますが、その本質は「図形を構成するために必要な要素を、与えられた部品から選び出す組合せ」の問題です。この視点を持つことで、複雑な図形問題も体系的に解きほぐすことができます。

7.1. 直線と三角形の個数

基本原理

  • 直線: 1本の直線を決定するためには、異なる2つの点が必要です。
  • 三角形: 1つの三角形を決定するためには、同一直線上にない異なる3つの点が必要です。

この基本原理を組合せの言葉に翻訳すると、以下のようになります。

問題1：基本的な直線の個数

平面上に \(n\) 個の点があり、どの3点も同一直線上にないとき、これらの点のうち2点を通る直線は何本引けるか。

思考プロセス

\(n\) 個の異なる点から、直線を引くための2つの点を選ぶ組合せを考えればよい。選ぶ点の順序は関係ない（点Aと点Bを通る直線と、点Bと点Aを通る直線は同じ）ので、組合せです。

\[

\text{直線の数} = _n\mathrm{C}_2 = \frac{n(n-1)}{2}

\]問題2：基本的な三角形の個数

平面上に \(n\) 個の点があり、どの3点も同一直線上にないとき、これらの点を頂点とする三角形は何個作れるか。

思考プロセス

\(n\) 個の異なる点から、三角形の頂点となる3つの点を選ぶ組合せを考えればよい。

\[

\text{三角形の数} = _n\mathrm{C}_3 = \frac{n(n-1)(n-2)}{3 \cdot 2 \cdot 1}

\]注意点：同一直線上の点がある場合

問題が複雑になるのは、複数の点が同一直線上に並んでいる場合です。この場合、単純に \(_n\mathrm{C}_2\) や \(_n\mathrm{C}_3\) を計算すると、過剰なカウントや、そもそも図形をなさないケースが含まれてしまいます。

この場合の定石は、「一旦すべての点を区別なく選び、その後で問題となるケースを引く」という補正の考え方です。

例題：同一直線上の点を含む三角形の個数

平面上に10個の点があり、そのうち4個の点だけが同一直線上にある。このとき、これらの点を頂点とする三角形は何個作れるか。

思考プロセス

  1. 全体の組合せを計算する（仮）:まず、10個の点がどの3点も同一直線上にないと仮定して、三角形の総数を計算します。\(_{10}\mathrm{C}_3 = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120\) 個。
  2. 問題となるケースを特定し、引く:この120個の中には、同一直線上にある4つの点から3点を選んでしまったケースが含まれています。この4つの点から3点を選んでも、三角形は作れず、直線にしかなりません。したがって、この「作れないはずなのに数えてしまった」ケースの数を計算して、全体から引く必要があります。同一直線上の4点から3点を選ぶ組合せの数は、\(_4\mathrm{C}_3 = _4\mathrm{C}_1 = 4\) 個。
  3. 補正計算:求める三角形の個数は、

\[

\]_{10}\mathrm{C}_3 – _4\mathrm{C}_3 = 120 – 4 = 116

]

答えは 116個 となります。

直線の数を数える場合は、さらに注意が必要です。同一直線上の4点から2点を選んだ組合せ（\(_4\mathrm{C}_2=6\) 通り）は、すべて同じ1本の直線を与えます。したがって、「一旦すべてを引き、その後でその1本を足し戻す」という操作が必要になります。

7.2. 多角形の対角線の本数

正\(n\)角形（または一般の凸\(n\)角形）の対角線の本数を求める問題も、組合せの美しい応用例です。

思考プロセス

  1. 頂点の数: \(n\)角形には \(n\) 個の頂点があります。
  2. すべての線分の数を数える:まず、\(n\) 個の頂点から2つの頂点を選んで結ぶと、線分が1本できます。この線分には、多角形の辺と対角線の両方が含まれます。\(n\) 個の頂点から2点を選ぶ組合せなので、その総数は \(_n\mathrm{C}_2\) 本です。
  3. 辺の数を引く:\(_n\mathrm{C}_2\) の中から、対角線ではないもの、すなわち辺の数を引きます。\(n\)角形には \(n\) 本の辺があります。
  4. 計算:対角線の本数 = (すべての線分の数) – (辺の数)

\[

\]= _n\mathrm{C}_2 – n = \frac{n(n-1)}{2} – n

]

通分して整理すると、

\[

\]= \frac{n(n-1) – 2n}{2} = \frac{n^2 – n – 2n}{2} = \frac{n^2 – 3n}{2} = \frac{n(n-3)}{2}

]

となります。これは、中学校で学ぶ対角線の公式ですが、その背景には組合せの考え方があったのです。

具体例：八角形の対角線

\(n=8\) を代入すると、

\[

\frac{8(8-3)}{2} = \frac{8 \times 5}{2} = 20

\]対角線は 20本 となります。

組合せで計算すると、\(_8\mathrm{C}_2 – 8 = 28 – 8 = 20\) 本となり、一致します。

7.3. 平行線によって作られる平行四辺形の個数

格子状の図形問題も、組合せの応用として頻出します。

問題

\(m\) 本の平行な直線と、それに交わる \(n\) 本の平行な直線がある。これらの直線によって作られる平行四辺形は全部で何個あるか。

思考プロセス

  1. 平行四辺形の構成要素:1つの平行四辺形を決定するためには、
  • 最初のグループの平行線（\(m\) 本）から、2本 を選び（これが平行四辺形の左右の辺になる）、
  • もう一方のグループの平行線（\(n\) 本）から、2本 を選ぶ（これが平行四辺形の上下の辺になる）必要があります。
  1. 組合せへの翻訳:この問題は、2つの独立した選択プロセスに分解できます。
  • \(m\) 本の平行線から2本を選ぶ組合せ → \(_m\mathrm{C}_2\) 通り
  • \(n\) 本の平行線から2本を選ぶ組合せ → \(_n\mathrm{C}_2\) 通り
  1. 積の法則の適用:最初のグループの選び方の各々に対して、2番目のグループの選び方が考えられるため、積の法則を適用します。

\[

\]\text{平行四辺形の数} = _m\mathrm{C}_2 \times _n\mathrm{C}_2

]

具体例

5本の平行線と、それに交わる4本の平行線がある場合。

\(m=5, n=4\) です。

\[

_5\mathrm{C}_2 \times _4\mathrm{C}_2 = \left( \frac{5 \cdot 4}{2 \cdot 1} \right) \times \left( \frac{4 \cdot 3}{2 \cdot 1} \right) = 10 \times 6 = 60

\]平行四辺形は 60個 作られます。

図形の個数問題は、一見するとどこから手をつけていいか分からないように見えることがあります。しかし、その図形が「どのような要素の組合せによって一意に決定されるか」という本質を見抜くことで、問題は一気にクリアな組合せの計算へと姿を変えるのです。この「図形的状況を組み合わせ論的にモデル化する」能力は、応用力を測る上で非常に重要なスキルとなります。

8. 二項定理

代数学における式の展開と、これまで学んできた組合せの理論。一見すると全く異なる分野に見えるこの二つが、実は深いレベルで結びついていることを明らかにするのが二項定理 (Binomial Theorem) です。二項定理は、\((a+b)^n\) という単純な二項式のべき乗を展開したときに、その各項の係数がどのように決定されるかを記述した、極めて強力な定理です。そして驚くべきことに、その係数は、まさしく組合せの数 \(_n\mathrm{C}_r\) そのものなのです。この定理を学ぶことで、組合せの概念が単なる「場合の数」の計算ツールに留まらない、より普遍的な数学的構造の一部であることが理解できるでしょう。

8.1. 二項定理の組み合わせ論的な導入

なぜ \((a+b)^n\) の展開式に \(_n\mathrm{C}_r\) が現れるのでしょうか。具体的な例を通して、その根源的な理由を探ってみましょう。

\((a+b)^3\) の展開を考えます。

\[

(a+b)^3 = (a+b)(a+b)(a+b)

\]この展開式から一つの項（例えば \(ab^2\)）がどのようにして生まれるかを、分配法則のプロセスに立ち返って考えてみます。

積を作るためには、3つの括弧 (a+b) のそれぞれから、\(a\) または \(b\) のどちらか一方を選び出して、それらを掛け合わせる必要があります。

\(ab^2\) という項が作られるプロセス

この項は、\(a\) が1個、\(b\) が2個掛け合わさってできています。

これは、3つの括弧のうち、

  • 1つの括弧からは \(a\) を選び、
  • 残りの2つの括弧からは \(b\) を選ぶという操作に対応します。

具体的には、以下の3つのパターンが考えられます。

  1. 1番目の括弧から \(a\)、2番目と3番目の括弧から \(b\) を選ぶ → \(a \cdot b \cdot b = ab^2\)
  2. 2番目の括弧から \(a\)、1番目と3番目の括弧から \(b\) を選ぶ → \(b \cdot a \cdot b = ab^2\)
  3. 3番目の括弧から \(a\)、1番目と2番目の括弧から \(b\) を選ぶ → \(b \cdot b \cdot a = ab^2\)

最終的に、展開式における \(ab^2\) の係数は、これらの同類項がいくつあるか、すなわち3つのパターンを合計したものになります。したがって、係数は3です。

組合せとの接続

ここで、上記のプロセスを組合せの視点から見直してみましょう。

「3つの括弧の中から、\(a\) を取り出す括弧を1つ選ぶ」

あるいは、

「3つの括弧の中から、\(b\) を取り出す括弧を2つ選ぶ」

という問題と全く同じ構造をしています。

その場合の数は、

  • \(_3\mathrm{C}_1 = 3\) （\(a\) に着目した場合）
  • \(_3\mathrm{C}_2 = 3\) （\(b\) に着目した場合）となり、先ほどの係数3と見事に一致します。

この考え方を一般化してみましょう。

\((a+b)^n\) の展開式における \(a^{n-r}b^r\) の係数

\((a+b)^n = (a+b)(a+b)\cdots(a+b)\) （\(n\) 個の積）

この展開式において、\(a^{n-r}b^r\) という項は、

  • \(n\) 個の括弧の中から、\(b\) を取り出す括弧を \(r\) 個選び、
  • 残りの \((n-r)\) 個の括弧からは \(a\) を選ぶことによって作られます。

\(n\) 個の括弧から \(b\) を取り出す \(r\) 個の括弧を選ぶ組合せの総数は \(_n\mathrm{C}_r\) 通りです。

したがって、\(a^{n-r}b^r\) という項は \(_n\mathrm{C}_r\) 回現れることになり、その係数は \(_n\mathrm{C}_r\) となります。

8.2. 二項定理の公式

以上の考察から、二項定理は以下のように定式化されます。

【二項定理】

\(n\) を自然数とするとき、

\[

(a+b)^n = \sum_{r=0}^{n} {_n\mathrm{C}_r a^{n-r} b^r}

\]\[

= {_n\mathrm{C}_0 a^n} + {_n\mathrm{C}_1 a^{n-1}b} + {_n\mathrm{C}_2 a^{n-2}b^2} + \cdots + {_n\mathrm{C}_r a^{n-r}b^r} + \cdots + {_n\mathrm{C}_n b^n}

\]この定理において、係数 \(_n\mathrm{C}_r\) は二項係数 (Binomial Coefficient) と呼ばれます。パスカルの三角形の各段の数字が、まさにこの二項係数に対応していることは、言うまでもありません。

例題1：\((x+2y)^4\) の展開

二項定理を用いて展開してみましょう。\(a=x, b=2y, n=4\) です。

\[

(x+2y)^4 = {_4\mathrm{C}_0 x^4} + {_4\mathrm{C}_1 x^3 (2y)^1} + {_4\mathrm{C}_2 x^2 (2y)^2} + {_4\mathrm{C}_3 x (2y)^3} + {_4\mathrm{C}_4 (2y)^4}

\]二項係数を計算します。\(_4\mathrm{C}_0=1, _4\mathrm{C}_1=4, _4\mathrm{C}_2=6, _4\mathrm{C}_3=4, _4\mathrm{C}_4=1\)

\[

= 1 \cdot x^4 + 4 \cdot x^3 \cdot 2y + 6 \cdot x^2 \cdot 4y^2 + 4 \cdot x \cdot 8y^3 + 1 \cdot 16y^4

\]\[

= x^4 + 8x^3y + 24x^2y^2 + 32xy^3 + 16y^4

\]例題2：特定の項の係数を求める

\((2x – y^2)^7\) の展開式における \(x^4y^6\) の係数を求めよ。

思考プロセス

展開式における一般項は、二項定理から

\[

_7\mathrm{C}_r (2x)^{7-r} (-y^2)^r

\]と表せます。この式を整理して、文字の部分の指数を比較します。

\[

_7\mathrm{C}_r \cdot 2^{7-r} \cdot x^{7-r} \cdot (-1)^r \cdot y^{2r}

\]我々が求めたいのは \(x^4y^6\) の項なので、指数の部分が

  • \(x\) の指数: \(7-r = 4\)
  • \(y\) の指数: \(2r = 6\)となるような \(r\) を見つければよい。どちらの式を解いても \(r=3\) となります。

したがって、求める項は \(r=3\) の場合に現れます。

係数部分は \(_7\mathrm{C}_r \cdot 2^{7-r} \cdot (-1)^r\) なので、\(r=3\) を代入します。

\[

\text{係数} = _7\mathrm{C}_3 \cdot 2^{7-3} \cdot (-1)^3

\]\[

= \left( \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} \right) \cdot 2^4 \cdot (-1)

\]\[

= 35 \cdot 16 \cdot (-1) = -560

\]答えは -560 となります。

8.3. 二項定理を用いた等式の証明

二項定理は、組合せに関する様々な美しい等式を証明するための強力なツールでもあります。

証明1：\(\sum_{r=0}^{n} {_n\mathrm{C}_r} = 2^n\)

二項定理の公式 \((a+b)^n = \sum_{r=0}^{n} {_n\mathrm{C}_r a^{n-r} b^r}\) において、\(a=1, b=1\) とおいてみましょう。

  • 左辺: \((1+1)^n = 2^n\)
  • 右辺: \(\sum_{r=0}^{n} {_n\mathrm{C}r \cdot 1^{n-r} \cdot 1^r} = \sum{r=0}^{n} {_n\mathrm{C}r}\)したがって、\(\sum{r=0}^{n} {_n\mathrm{C}_r} = 2^n\) が成り立ちます。これは、パスカルの三角形の性質で組み合わせ論的に証明したものと一致します。

証明2：\(\sum_{r=0}^{n} {(-1)^r _n\mathrm{C}_r} = 0\)

二項定理の公式で、\(a=1, b=-1\) とおいてみましょう。

  • 左辺: \((1 + (-1))^n = 0^n = 0\) （ただし \(n \ge 1\)）
  • 右辺: \(\sum_{r=0}^{n} {_n\mathrm{C}r \cdot 1^{n-r} \cdot (-1)^r} = \sum{r=0}^{n} {(-1)^r _n\mathrm{C}_r}\)\(= {_n\mathrm{C}_0} – {_n\mathrm{C}_1} + {_n\mathrm{C}_2} – \cdots + (-1)^n {_n\mathrm{C}_n}\)したがって、\({_n\mathrm{C}_0} – {_n\mathrm{C}_1} + {_n\mathrm{C}_2} – \cdots = 0\) が成り立ちます。これは、「偶数個選ぶ組合せの総和」と「奇数個選ぶ組合せの総和」が等しいことを意味しており、非常に興味深い性質です。

二項定理は、組合せの理論が代数学の基本的な演算と深く結びついていることを示す、美しい架け橋です。展開式の各項が、なぜその係数を持つのかを「\(n\) 個の括弧からどの括弧を選ぶか」という組合せの問題として理解することが、この定理を本質的にマスターする鍵となります。

9. 多項定理

二項定理が \((a+b)^n\) という2つの項（二項）の和のべき乗を扱ったのに対し、その考え方をさらに拡張し、\((a+b+c)^n\) や \((x+y+z+w)^n\) といった3つ以上の項（多項）の和のべき乗を一般的に扱うのが多項定理 (Multinomial Theorem) です。多項定理は、一見すると非常に複雑に見えますが、その根底にある考え方は二項定理と全く同じです。そして、その係数は、我々が既に「同じものを含む順列」で学んだ形式と見事に一致します。この定理を学ぶことで、順列と組合せの概念がいかに統一的な枠組みの中に位置しているかを、より高い視点から理解することができます。

9.1. 多項定理の組み合わせ論的な導入

二項定理の時と同じように、具体的な例からその構造を考えてみましょう。

\((a+b+c)^4\) の展開を考えます。

\[

(a+b+c)^4 = (a+b+c)(a+b+c)(a+b+c)(a+b+c)

\]この展開式から、特定の項、例えば \(a^1b^2c^1\) (すなわち \(ab^2c\)) がどのようにして生まれるかを考えます。

\(ab^2c\) という項が作られるプロセス

この項は、\(a\) が1個、\(b\) が2個、\(c\) が1個掛け合わさってできています。

これは、4つの括弧 (a+b+c) のそれぞれから \(a, b, c\) のいずれかを選び出す際に、

  • 1つの括弧からは \(a\) を選び、
  • 2つの括弧からは \(b\) を選び、
  • 1つの括弧からは \(c\) を選ぶという操作に対応します。

問題は、この選び方が何通りあるかです。

これは、「4つの異なる括弧（1番目, 2番目, 3番目, 4番目）を、『\(a\) を選ぶ組』(1個)、『\(b\) を選ぶ組』(2個)、『\(c\) を選ぶ組』(1個) に組分けする」問題と考えることができます。

あるいは、もっと直接的に、「a, b, b, c という4つの文字を一列に並べる順列」の問題と考えることもできます。

例えば、abbc という順列は、

  • 1番目の括弧から \(a\)
  • 2番目の括弧から \(b\)
  • 3番目の括弧から \(b\)
  • 4番目の括弧から \(c\)を選んで掛け合わせることに対応します。babc という順列は、1番目からb, 2番目からa, 3番目からb, 4番目からcを選ぶことに対応します。

したがって、\(ab^2c\) という項は、a, b, b, c の並べ方の総数だけ現れることになります。

これはまさに「同じものを含む順列」の問題です。

その総数は、

\[

\frac{4!}{1!2!1!} = \frac{24}{2} = 12

\]となり、\(ab^2c\) の係数は12であることが分かります。

一般化への道

この考え方を一般化します。

\((a_1 + a_2 + \cdots + a_k)^n\) の展開式における

\(a_1^{p_1} a_2^{p_2} \cdots a_k^{p_k}\) という項の係数を考えます。

（ただし、\(p_1 + p_2 + \cdots + p_k = n\)）

この項は、\(n\) 個の括弧の中から、

  • \(a_1\) を取り出す括弧を \(p_1\) 個選び、
  • \(a_2\) を取り出す括弧を \(p_2\) 個選び、
  • …
  • \(a_k\) を取り出す括弧を \(p_k\) 個選ぶことによって生成されます。

この選び方の総数は、\(n\) 個のものを、\(p_1\) 個、\(p_2\) 個、…、\(p_k\) 個のグループに分ける組分け問題であり、また、\(p_1\) 個の \(a_1\)、\(p_2\) 個の \(a_2\)、…という「同じものを含む順列」の総数と等しくなります。

その係数は、

\[

\frac{n!}{p_1! p_2! \cdots p_k!}

\]となります。

9.2. 多項定理の公式

以上の考察から、多項定理は以下のように定式化されます。

【多項定理】

\(n\) を自然数とするとき、\((a_1 + a_2 + \cdots + a_k)^n\) の展開式における \(a_1^{p_1} a_2^{p_2} \cdots a_k^{p_k}\) (ただし \(p_1+p_2+\cdots+p_k=n\) を満たす非負整数) の項の係数は、

\[

\frac{n!}{p_1! p_2! \cdots p_k!}

\]である。

この係数 \(\frac{n!}{p_1! p_2! \cdots p_k!}\) は、多項係数 (Multinomial Coefficient) と呼ばれ、\(n\mathrm{C}{p_1, p_2, \dots, p_k}\) や \(\binom{n}{p_1, p_2, \dots, p_k}\) と表記されることもあります。

二項係数 \(_n\mathrm{C}_r\) は、\(k=2\) の場合の多項係数 \(\frac{n!}{r!(n-r)!}\) に他ならず、二項定理が多項定理の特殊なケースであることが分かります。

例題1：\((x-2y+3z)^6\) における \(x^2y^3z\) の係数

思考プロセス

  1. 指数の特定:求めたい項は \(x^2(-2y)^3(3z)^1\) の形をしています。各項の指数は \(p_1=2, p_2=3, p_3=1\) です。合計が \(2+3+1=6=n\) となっていることを確認します。
  2. 多項係数の計算:まず、\(x, y, z\) の組み合わせの部分の係数を計算します。

\[

\]\frac{6!}{2!3!1!} = \frac{720}{2 \cdot 6 \cdot 1} = \frac{720}{12} = 60

]

  1. 各項の係数を考慮:実際の項は \((x), (-2y), (3z)\) なので、それぞれの係数も考慮に入れる必要があります。\(x\) の係数は 1\(y\) の係数は -2\(z\) の係数は 3これらを、それぞれの指数でべき乗します。\(1^2 \cdot (-2)^3 \cdot 3^1 = 1 \cdot (-8) \cdot 3 = -24\)
  2. 最終的な係数の計算:ステップ2の多項係数と、ステップ3の各項の係数のべき乗を掛け合わせます。

\[

\]\text{最終係数} = 60 \times (-24) = -1440

]

答えは -1440 となります。

一般項の形

\((a+b+c)^n\) の一般項は、\(p+q+r=n\) を満たす非負整数 \(p, q, r\) を用いて、

\[

\frac{n!}{p!q!r!} a^p b^q c^r

\]と書くことができます。この形を覚えておくと、問題を解く際に非常に便利です。

9.3. 多項定理と組分け問題の関係

多項係数 \(\frac{n!}{p_1! p_2! \cdots p_k!}\) の形は、どこかで見覚えがないでしょうか。

これは、\(n\) 個の異なるものを、\(p_1\) 個、\(p_2\) 個、…、\(p_k\) 個の区別される \(k\) 個の組に分けるときの、組分けの総数と全く同じです。

\[

n\mathrm{C}{p_1} \times {n-p_1}\mathrm{C}{p_2} \times \cdots = \frac{n!}{p_1!(n-p_1)!} \times \frac{(n-p_1)!}{p_2!(n-p_1-p_2)!} \times \cdots = \frac{n!}{p_1!p_2!\cdots}

\]（途中の階乗が次々と約分されて消えていく）

この事実は、多項定理の組み合わせ論的な解釈が、組分け問題と深く結びついていることを示しています。

\((a+b+c)^n\) の \(a^p b^q c^r\) の係数を求めることは、

「\(n\) 個の括弧を、『\(a\) を選ぶ』\(p\) 個の組、『\(b\) を選ぶ』\(q\) 個の組、『\(c\) を選ぶ』\(r\) 個の組に分ける方法」

を数え上げることと、完全に同義なのです。

多項定理は、二項定理を一般化する強力なツールであると同時に、「同じものを含む順列」「組分け問題」「代数式の展開」といった、これまで学んできた複数の概念を一つの美しい数式の下に統合する、壮大な視点を提供してくれます。この定理を理解することで、場合の数の様々なトピックが、実は同じ山の異なる側面を見ているに過ぎない、という数学の統一的な美しさを感じ取ることができるでしょう。

10. 順列と組合せの戦略的選択

これまでに、我々は「順列 (Permutation)」と「組合せ (Combination)」という、場合の数を支配する二つの強力な概念を学びました。順列は「順序を考慮して並べる」技術であり、組合せは「順序を無視して選ぶ」技術です。しかし、実際の入試問題などでは、「この問題は順列です」「これは組合せです」と親切に教えてはくれません。問題文の僅かな言葉の違いや文脈を読み解き、どちらの道具を使うべきか、あるいは両者をどのように組み合わせるべきかを、自ら戦略的に判断する必要があります。この最終セクションでは、その判断能力を磨くための実践的な思考の指針を確立します。

10.1. 核心的差異の再確認：Order Matters?

すべての判断の出発点は、この問いに集約されます。

「順序は重要か？ (Does the order matter?)」

ある選択を行った結果として、その選ばれた要素の並び順を変えると、それが異なる結果としてカウントされるべき状況ならば、それは順列の問題です。

一方、並び順を変えても、結局は同じ結果と見なされる状況ならば、それは組合せの問題です。

思考を助けるキーワードと状況

状況順列 (Permutation) の可能性が高い組合せ (Combination) の可能性が高い
キーワード並べる、一列に、整列、順位をつける、配置する、割り当てる選ぶ、取り出す、グループを作る、チームを編成する、…組
具体例・リレーの走順を決める<br>・役職（会長、副会長など）を割り当てる<br>・異なる数字で暗証番号を作る<br>・座席に座らせる・代表委員を選ぶ<br>・掃除当番を選ぶ<br>・ポーカーの手札を作る<br>・単なるグループ分け
核心的な問い「誰がどのポジションか」が重要か？「誰がメンバーか」だけが重要か？

この表はあくまで目安ですが、問題の状況がどちらのシナリオに近いかを判断する上で、非常に有効な指針となります。

ミニケーススタディ：似て非なる問題

問題A: 10人の部員の中から、部長、副部長、会計を1人ずつ選ぶ。その選び方は何通りか。

  • 思考: 山田さんが部長で、佐藤さんが副部長の場合と、佐藤さんが部長で、山田さんが副部長の場合は、全く異なる人事です。順序（役職の割り当て）が重要です。
  • 結論: これは順列の問題。\(_10\mathrm{P}_3 = 10 \times 9 \times 8 = 720\) 通り。

問題B: 10人の部員の中から、大会に出場する代表選手を3人選ぶ。その選び方は何通りか。

  • 思考: {山田, 佐藤, 鈴木} という3人が選ばれれば、彼らがどのような順番で選ばれたとしても、最終的な代表メンバーは同じです。順序は重要ではありません。
  • 結論: これは組合せの問題。\(_{10}\mathrm{C}_3 = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120\) 通り。

このように、状況設定の僅かな違いが、適用すべき数学モデルを根本から変えてしまうのです。

10.2. 判断のための体系的フローチャート

より複雑な問題に対応するために、体系的な思考のフローチャートを持っておくことが有効です。問題に直面したとき、以下の質問を自分に投げかけてみてください。

ステップ1：基本モデルの選択

Q1: 順序は重要か？

  • YES → 順列 (P) ベースの思考へ
  • NO → 組合せ (C) ベースの思考へ

ステップ2：追加条件のチェック（順列ベースの場合）

Q2a: すべて異なるものか？

  • YES → 基本的な順列 \(_n\mathrm{P}_r\) または階乗 \(n!\)Q2b: 同じものが含まれるか？
  • YES → 同じものを含む順列 \(\frac{n!}{p!q!…}\)Q2c: 繰り返しを許すか？
  • YES → 重複順列 \(n^r\)Q2d: 円形に並べるか？
  • YES → 円順列 \((n-1)!\)

ステップ3：追加条件のチェック（組合せベースの場合）

Q3a: すべて異なるものから選ぶか？

  • YES → 基本的な組合せ \(_n\mathrm{C}_r\)Q3b: 繰り返しを許すか？
  • YES → 重複組合せ \(_n\mathrm{H}_r = _{n+r-1}\mathrm{C}_r\)

ステップ4：複数プロセスの組み合わせ

多くの上級問題は、単一のPやCでは解けません。

Q4: 問題全体は、複数のステップに分解できるか？

  • YES → 各ステップがPなのかCなのかを判断し、それらの結果を積の法則で繋ぐ。Q5: 問題全体は、互いに排反なケースに場合分けできるか？
  • YES → 各ケースをPやCで計算し、それらの結果を和の法則で合計する。

このフローチャートは、思考の羅針盤として機能します。闇雲に解法を試すのではなく、問題の構造をこれらの質問に沿って分析することで、最も合理的で効率的な解法への道筋が見えてきます。

10.3. 実践的演習：複合問題へのアプローチ

問題: 男子6人、女子4人の計10人の中から、4人の委員を選ぶ。次のような選び方は何通りあるか。

(1) すべての選び方

(2) 男子2人、女子2人を選ぶ

(3) 少なくとも1人は女子が選ばれる

(4) 4人を選んだ後、その4人の中から委員長と副委員長を選ぶ

思考プロセス

(1) すべての選び方

  • Q1: 委員に役職の区別はないので、順序は重要でない → 組合せ (C) ベース。
  • 10人から4人を選ぶので、\(_{10}\mathrm{C}_4 = \frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = 210\) 通り。

(2) 男子2人、女子2人を選ぶ

  • Q4: この問題は2つのステップに分解できる。
  • ステップA: 男子6人から2人を選ぶ。
  • ステップB: 女子4人から2人を選ぶ。
  • ステップA：順序は重要でない → 組合せ。\(_6\mathrm{C}_2 = 15\)
  • ステップB：順序は重要でない → 組合せ。\(_4\mathrm{C}_2 = 6\)
  • 両方のステップを連続して行うので、積の法則で繋ぐ。
  • 総数 = \(_6\mathrm{C}_2 \times _4\mathrm{C}_2 = 15 \times 6 = 90\) 通り。

(3) 少なくとも1人は女子が選ばれる

  • 「少なくとも1人」というキーワードは、余事象を考えるサイン。
  • 余事象：「4人とも女子が選ばれない」＝「4人全員が男子である」
  • 余事象の場合の数を計算する：男子6人から4人を選ぶ組合せ。\(_6\mathrm{C}_4 = _6\mathrm{C}_2 = 15\) 通り。
  • 全体の選び方（(1)で計算済み）から、余事象の場合の数を引く。
  • 総数 = (すべての選び方) – (全員が男子) = \(210 – 15 = 195\) 通り。

(4) 4人を選び、委員長と副委員長を選ぶ

  • Q4: 2つのステップに分解できる。
  • ステップA: まず10人から4人の委員を選ぶ。
  • ステップB: 次にその選ばれた4人の中から委員長と副委員長を割り当てる。
  • ステップA：順序は重要でない → 組合せ。10人から4人を選ぶので \(_{10}\mathrm{C}_4 = 210\) 通り。
  • ステップB：選ばれた4人の中から、委員長と副委員長を割り当てる。これは順序が重要 → 順列。4人から2人を選んで並べるので \(_4\mathrm{P}_2 = 12\) 通り。
  • 両方のステップを連続して行うので、積の法則で繋ぐ。
  • 総数 = \(_{10}\mathrm{C}_4 \times _4\mathrm{P}_2 = 210 \times 12 = 2520\) 通り。

別解 (4):

先に役職者を選んでしまう方法もある。

  • ステップA: 10人の中から委員長を選ぶ（10通り）。
  • ステップB: 残り9人から副委員長を選ぶ（9通り）。
  • ステップC: 残り8人から、残り2人の平委員を選ぶ（\(_8\mathrm{C}_2 = 28\) 通り）。
  • 総数 = \(10 \times 9 \times _8\mathrm{C}_2 = 90 \times 28 = 2520\) 通り。結果は一致する。

順列と組合せの選択は、固定的な知識ではなく、問題の文脈を深く読み解く読解力と、状況を適切な数学モデルに翻訳するモデル化能力が問われる、動的なスキルです。このスキルを磨く最良の方法は、多くの問題にあたり、その都度「なぜこの問題はPなのか？」「なぜCなのか？」「なぜPとCの組み合わせなのか？」と自問自答を繰り返すことです。その試行錯誤の先に、場合の数の問題を自由自在に操る力が待っています。

Module 2：場合の数(2) 組合せの総括：選択と構成の数学

本モジュールにおいて、我々は「順序」という束縛から思考を解放し、「選ぶ」という行為そのものを数学的に定式化する「組合せ」の広大な世界を探求しました。その旅は、順列の総数を並びの重複度 r! で割ることで「順序をキャンセルする」という、組合せの本質的な定義から始まりました。この単純な操作が、計数のパラダイムを「配置」から「構成」へとシフトさせる、決定的な一歩となったのです。

nCr = nCn-r という対称性は、「r個を選ぶ」ことと「n-r個を残す」ことが表裏一体であることを示し、我々の直観と数式の美しさが見事に一致することを教えてくれました。パスカルの三角形は、組合せの数が持つ内的な秩序を視覚的に明らかにし、特にその漸化式 nCr = n-1Cr-1 + n-1Cr は、「特定の要素に着目して場合分けする」という、組み合わせ論における強力な論理的武器を我々に与えてくれました。

そして、組合せの理論は、具体的な応用問題においてその真価を発揮しました。「組分け問題」では、グループの「区別」の有無という僅かな条件の違いが、計算に k! という階乗での除算を要求するか否かを決定するという、場合の数の繊細さと厳密さを学びました。「重複組合せ」では、「仕切り棒」という画期的なモデル化によって、複雑な選択問題を単純な記号の配列問題へと翻訳する、思考の飛躍を体験しました。最短経路や図形の個数問題は、幾何学的な状況が、いかにして組合せという代数的な言語で記述され得るかを示してくれました。

最終的に、「二項定理」と「多項定理」は、この組合せの概念が単なる場合の数の道具に留まらず、代数学の根幹をなす式の展開と本質的に結びついていることを明らかにしました。n個の括弧から特定の項をr個「選び出す」という行為が、展開式の係数nCrを決定するという事実は、数学の異なる分野が根底で繋がっていることの感動的な証左です。

本モジュールを通じて、我々は単に nCr の計算方法を学んだわけではありません。「順序は重要か」「区別はあるか」「繰り返しは許されるか」といった問いを自らに投げかけ、問題の構造を的確に分析し、最も適切な数学モデルを選択・構成する「選択と構成の数学」を実践してきました。この能力こそが、不確実な事象を扱う「確率論」の核心へと迫るための、不可欠な知的基盤となるのです。

基礎数学 基礎 数学A
目次