理論計算機科学を読むための数学・証明・アルゴリズム基礎

第7章 組合せと数え上げ

章間ナビゲーション

この章で使う記号

記号 意味
|A| 集合 A の要素数
n! n の階乗
C(n,k) / \binom{n}{k} n 個から k 個を選ぶ組合せ数
P(n,k) n 個から k 個を順に選ぶ順列数
2^A 集合 A の冪集合を表すことがある記号
Σ / Π 総和 / 総積

この章で解消する詰まりどころ

理論計算機科学では、数え上げは「場合の数を求める」ためだけに使うのではありません。主な用途は次の4つです。

  1. 入力空間や状態空間の大きさを見積もる。
  2. アルゴリズムが全探索できるかを判断する。
  3. 情報量・符号・確率の式を読めるようにする。
  4. 存在証明や下界証明の直観を作る。

たとえば、長さ n のビット列は 2^n 個あります。この事実だけで、全ビット列を列挙するアルゴリズムは入力長 n に対して指数時間になることが分かります。数え上げは、計算量理論と情報理論の入口です。

本体教科書で使う箇所

  • 計算量理論: 入力数、候補解数、探索空間、証明の大きさ。
  • アルゴリズム解析: 全探索、バックトラック、動的計画法の状態数。
  • グラフ理論: パス、辺集合、部分集合、マッチング候補。
  • 情報理論: ビット列、符号語、エントロピーの直観。
  • 暗号: 鍵空間、衝突確率、ブルートフォース耐性。

1. 和の法則

互いに重ならない選択肢の集合 A と B があるとき、どちらか一方から選ぶ方法の数は、

|A ∪ B| = |A| + |B|

です。ただし、これは A ∩ B = ∅ のときだけです。

例

3個の赤い玉と5個の青い玉があり、赤または青の玉を1個選ぶ方法は 3 + 5 = 8 通りです。

非例

「2で割り切れる数」または「3で割り切れる数」を、1から10までの整数から選ぶ場合、単純に足してはいけません。6は両方に含まれます。

A = {2,4,6,8,10}
B = {3,6,9}
A ∩ B = {6}
|A ∪ B| = 5 + 3 - 1 = 7

重なりがある場合は包除原理を使います。

2. 積の法則

手順1の選び方が a 通りあり、各選択に対して手順2の選び方が b 通りあるなら、合計は ab 通りです。

例

長さ3のビット列は、各位置に 0 または 1 を置けるため、

2 × 2 × 2 = 2^3 = 8

通りです。

一般に、長さ n のビット列は 2^n 個です。

状態空間の例

長さ n の配列の各要素が 0..m-1 のいずれかなら、配列全体の状態数は

m^n

です。ここから、全状態を走査する設計が容易に破綻することが分かります。

3. 順列

n 個の相異なる要素を並べる方法の数は

n! = n(n-1)(n-2)...2·1

です。

例

{a,b,c} を並べる方法は、

abc, acb, bac, bca, cab, cba

の6通りです。

k個だけ並べる場合

n 個から重複なしで k 個を選び、順序付きで並べる方法は

P(n,k) = n(n-1)...(n-k+1) = n! / (n-k)!

です。

4. 組合せ

n 個の相異なる要素から、順序を無視して k 個を選ぶ方法は

C(n,k) = n! / (k!(n-k)!)

です。これは二項係数とも呼ばれ、次のように書きます。

(n choose k)

本教材では Markdown 上の可読性を優先し、C(n,k) とも表記します。

順列との違い

{a,b,c} から2個選ぶ組合せは、

{a,b}, {a,c}, {b,c}

の3通りです。

一方、2個を順序付きで並べる場合は、

ab, ba, ac, ca, bc, cb

の6通りです。

組合せでは ab と ba を同じ選択とみなします。

5. 二項係数の基本性質

対称性

C(n,k) = C(n,n-k)

k 個を選ぶことは、選ばない n-k 個を決めることと同じです。

パスカルの恒等式

C(n,k) = C(n-1,k) + C(n-1,k-1)

証明の考え方は、特定の要素 x に注目することです。

  • x を選ばない場合: 残り n-1 個から k 個選ぶ。C(n-1,k) 通り。
  • x を選ぶ場合: 残り n-1 個から k-1 個選ぶ。C(n-1,k-1) 通り。

この2つは重ならないので、和の法則により成立します。

全部分集合の数

n 個の要素を持つ集合の部分集合の数は

2^n

です。各要素について「入れる」「入れない」の2択があるためです。

また、サイズ別に数えると

Σ_{k=0}^{n} C(n,k) = 2^n

です。

6. 重複ありの数え上げ

重複あり・順序あり

m 種類の値から長さ n の列を作る方法は

m^n

です。ビット列は m=2 の場合です。

重複なし・順序あり

n 個から k 個を重複なく順に選ぶ方法は

P(n,k) = n! / (n-k)!

です。

重複なし・順序なし

n 個から k 個を重複なく順序を無視して選ぶ方法は

C(n,k) = n! / (k!(n-k)!)

です。

重複あり・順序なし

n 種類のものから重複を許して k 個選ぶ方法は

C(n+k-1,k)

です。これは「仕切りと玉」の考え方で説明できます。

例として、3種類 a,b,c から重複を許して4個選ぶことは、

x_a + x_b + x_c = 4
x_a, x_b, x_c >= 0

を満たす非負整数解を数えることと同じです。

7. 鳩ノ巣原理

n+1 個の物を n 個の箱に入れると、少なくとも1つの箱には2個以上入ります。

これは単純ですが、存在証明で頻繁に使います。

例

13人いれば、同じ誕生月の人が少なくとも2人います。

理論CSでの使い道

有限個の状態しか持たない機械が、より多くの異なる入力状況を区別しなければならない場合、どこかで衝突が起きます。この直観は、オートマトン、圧縮、ハッシュ、暗号、複雑性の議論に現れます。

8. 包除原理

2つの集合では、

|A ∪ B| = |A| + |B| - |A ∩ B|

3つの集合では、

|A ∪ B ∪ C|
= |A| + |B| + |C|
  - |A∩B| - |A∩C| - |B∩C|
  + |A∩B∩C|

です。

例

1から30までの整数のうち、2または3で割り切れるものの数を求めます。

A = 2で割り切れる整数: 15個
B = 3で割り切れる整数: 10個
A∩B = 6で割り切れる整数: 5個

したがって、

|A∪B| = 15 + 10 - 5 = 20

です。

9. 再帰的な数え上げ

数え上げでは、直接公式を使うだけでなく、再帰式を立てることもあります。

Fibonacci 型

長さ n のビット列で、連続する 1 を含まないものの数を a_n とします。

末尾で場合分けします。

  • 末尾が 0: その前は長さ n-1 の任意の有効列。a_{n-1} 通り。
  • 末尾が 1: 直前は 0 でなければならないので、末尾2文字は 01。その前は長さ n-2 の任意の有効列。a_{n-2} 通り。

よって、

a_n = a_{n-1} + a_{n-2}

となります。

これは、動的計画法の状態設計にも直結します。

10. 入力サイズと候補数

長さ n の入力に対して候補解が 2^n 個ある場合、単純な全探索は指数時間です。

ただし、候補が 2^n 個あることは、必ず指数時間が必要であることを意味しません。より賢いアルゴリズムで避けられる場合もあります。数え上げは、下界証明ではなく、まず設計上の警告として使います。

例: 部分集合問題

n 個の要素から任意の部分集合を選ぶ候補数は 2^n です。

部分集合全探索は、入力長 n に対して少なくとも 2^n 個の候補を調べる設計になります。

11. 証明の型

型1: 積の法則で数える

各ステップの選択肢数を列挙する。
それらが独立に選べることを確認する。
積を取る。

型2: 分類して足す

全体を互いに重ならない場合に分割する。
各場合を数える。
和を取る。

型3: 重複を引く

単純に足すと重複する集合を特定する。
重複部分を引く。
必要なら3重以上の重複を戻す。

型4: 対応を作る

数えたい集合 A と、数えやすい集合 B の間に全単射を作る。
|A| = |B| と結論する。

全単射による数え上げは、理論CSでは特に重要です。

12. よくある誤り

誤り1: 順序を区別するかを明示しない

ab と ba を同じとみなすかで答えが変わります。

誤り2: 重複を許すかを明示しない

同じ要素を複数回選べるかで答えが変わります。

誤り3: 足し算と掛け算を混同する

「どちらかを選ぶ」は足し算、「両方の手順を行う」は掛け算です。

誤り4: 重なりを無視して足す

集合が重なる場合、単純な和では過大計数になります。

誤り5: 具体例で確認して証明した気になる

n=1,2,3 で合っても、一般の n で成立するとは限りません。

13. 接続問題

接続1: オートマトンの状態数

k 状態の有限オートマトンは、入力を読む過程で高々 k 種類の内部状態しか区別できません。区別すべき状況が k 個を超えるなら、鳩ノ巣原理により異なる状況が同じ状態に押し込められます。

接続2: 符号語

長さ l のビット列は 2^l 個です。したがって、固定長 l ビットで区別できる記号は最大 2^l 種類です。

接続3: 証明候補

命題論理式の変数が n 個あるとき、真理値割当は 2^n 個です。真理値表で充足可能性を判定する単純アルゴリズムは指数時間になります。

章末チェック

次を説明できれば、この章の最低ラインは満たしています。

  • 和の法則と積の法則の違い。
  • 順列と組合せの違い。
  • C(n,k) の意味。
  • 2^n が部分集合数になる理由。
  • 鳩ノ巣原理の内容。
  • 包除原理を2集合で使えること。
  • 候補数と計算量の関係。

次に読む章

Edit this page on GitHub