場合の数と樹形図（組み合わせの初歩）

Q: 場合の数と樹形図（組み合わせの初歩）とは何ですか？

ある事柄Aの起こり方が m 通りあり、そのそれぞれに対して事柄Bの起こり方が n 通りずつあるとき、AとBがともに起こる場合の数は次の式で求められる（積の法則）。 m \times n \text{ 通り} この数え上げを図で表したものが「樹形図（じゅけいず）」であり、最初の分岐がAの m 通り、それぞれの枝からさらにBの n 通りに枝分かれし、末端（葉）の総数がちょうど m \times n 個になる。

Q: 場合の数と樹形図（組み合わせの初歩）は社会やプログラミングでどのように使われていますか？

全探索（ブルートフォース）アルゴリズムによる組み合わせの列挙: 樹形図の考え方をそのままコードにすると、二重ループ（あるいは再帰）によってすべての組み合わせを漏れなく生成する「全探索」のアルゴリズムになる。小規模な組み合わせ最適化問題や、テストケースの網羅、パスワード総当たりなどの基礎となる考え方。

「もれなく、重複なく」数え上げるための樹形図と積の法則

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 起こりうるすべての場合を、枝分かれする木の形に整理して数える図を「樹形図」と呼ぶ
2: 「Aの選び方がm通り、Bの選び方がn通りあるとき、両方をあわせた選び方は m×n 通り」という考え方を積の法則と呼ぶ
3: 積の法則はコンピュータがすべての組み合わせを漏れなく調べる「全探索（ブルートフォース）」アルゴリズムの土台になっている

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

起こりうるすべての場合を、枝分かれする木の形に整理して数える図を「樹形図」と呼ぶ

身につく武器・思考力

「Aの選び方がm通り、Bの選び方がn通りあるとき、両方をあわせた選び方は m×n 通り」という考え方を積の法則と呼ぶ

実社会・ITでの活躍現場

•全探索（ブルートフォース）アルゴリズムによる組み合わせの列挙
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

シャツの枚数とズボンの本数をそれぞれ増減させてみよう。樹形図が自動で描き直され、シャツの選び方から枝分かれしてズボンの選び方が続く様子と、末端に並ぶ「全組み合わせ」の総数がリアルタイムに変化するのを確認できる。

シャツの枚数3 枚

ズボンの本数2 本

樹形図（すべての組み合わせ）末端の数 = 3 × 2 = 6 通り

シャツ1

ズボン1

シャツ1+ズボン1

ズボン2

シャツ1+ズボン2

シャツ2

ズボン1

シャツ2+ズボン1

ズボン2

シャツ2+ズボン2

シャツ3

ズボン1

シャツ3+ズボン1

ズボン2

シャツ3+ズボン2

💡 積の法則:

シャツの選び方が $3$ 通り、そのそれぞれに対してズボンの選び方が $2$ 通りあるので、全体の組み合わせは $3 \times 2 = 6$ 通りになります。

直感チェック！ミニクイズ

シャツが3枚、ズボンが2本あるとき、シャツとズボンの組み合わせは何通りあるか？

Layer 2 — 定義・受験・証明

定義

ある事柄Aの起こり方が $m$ 通りあり、そのそれぞれに対して事柄Bの起こり方が $n$ 通りずつあるとき、AとBがともに起こる場合の数は次の式で求められる（積の法則）。

m \times n \text{ 通り}

この数え上げを図で表したものが「樹形図（じゅけいず）」であり、最初の分岐がAの $m$ 通り、それぞれの枝からさらにBの $n$ 通りに枝分かれし、末端（葉）の総数がちょうど $m \times n$ 個になる。

公式・数理モデル

N = m \times n

証明・導出

樹形図による証明（帰納的な数え上げ）： Aの選び方が $m$ 通りあるとする。Aの1つの選び方を固定するごとに、Bの選び方が独立に $n$ 通り存在する。樹形図で表すと、根から $m$ 本の枝が伸び（Aの各選択肢）、それぞれの枝の先からさらに $n$ 本の枝が伸びる（Bの各選択肢）。したがって、末端の葉（すべての組み合わせ）の数は、

\underbrace{n + n + \cdots + n}_{m個} = m \times n

となり、これは「 $m$ を $n$ 回足す」= 掛け算の定義そのものと一致する。この考え方は3つ以上の事柄にも自然に拡張でき、事柄がA, B, Cとそれぞれ $m, n, p$ 通りあるなら、全体では $m \times n \times p$ 通りになる。

押さえておきたいポイント

樹形図の利点は「もれなく・重複なく（MECE）」すべての場合を機械的に列挙できること
積の法則が使えるのは、Aの選び方とBの選び方が互いに独立している（Aを選んでもBの選択肢の数が変わらない）場合に限る
選択肢が増えるほど組み合わせ数は掛け算的（指数的）に爆発するため、樹形図を手で描くのは数個〜十数個が限界
順列・組み合わせ（permutation-combination）は、この積の法則を「同じものを何度も選べない」「順番を区別しない」といった条件付きの場合に発展させたもの

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

全探索（ブルートフォース）アルゴリズムによる組み合わせの列挙

樹形図の考え方をそのままコードにすると、二重ループ（あるいは再帰）によってすべての組み合わせを漏れなく生成する「全探索」のアルゴリズムになる。小規模な組み合わせ最適化問題や、テストケースの網羅、パスワード総当たりなどの基礎となる考え方。

1// 樹形図をそのままコード化した「全探索」による組み合わせ列挙
2function enumerateCombinations<A, B>(itemsA: A[], itemsB: B[]): Array<[A, B]> {
3  const result: Array<[A, B]> = [];
4
5  // 外側のループ = 樹形図の第1階層の枝 (Aの選択)
6  for (const a of itemsA) {
7    // 内側のループ = それぞれの枝からさらに分岐 (Bの選択)
8    for (const b of itemsB) {
9      result.push([a, b]);
10    }
11  }
12
13  // 結果の総数は必ず itemsA.length * itemsB.length に一致する (積の法則)
14  return result;
15}
16
17const shirts = ["白シャツ", "青シャツ", "赤シャツ"];
18const pants = ["黒ズボン", "紺ズボン"];
19
20const outfits = enumerateCombinations(shirts, pants);
21console.log(`組み合わせの総数: ${outfits.length}`); // 3 * 2 = 6
22outfits.forEach(([s, p]) => console.log(`${s} + ${p}`));
23
24// 3種類以上に拡張する場合は再帰関数でネストしたループを表現する
25function enumerateAll(choices: string[][]): string[][] {
26  if (choices.length === 0) return [[]];
27  const [first, ...rest] = choices;
28  const restCombos = enumerateAll(rest);
29  const combos: string[][] = [];
30  for (const item of first) {
31    for (const combo of restCombos) {
32      combos.push([item, ...combo]);
33    }
34  }
35  return combos;
36}