組合せ論 入門
場合の数と確率（高校数学レベル）
入門の概要
入門では、高校数学で学ぶ「場合の数」と「確率」の基礎を学ぶ。「数える」という基本的な操作を通じて、組合せ論的思考の入り口を理解する。
学習目標
- 和の法則・積の法則を理解し使いこなす
- 順列と組合せの違いを理解し計算できる
- 二項定理を理解し展開できる
- 確率の基本概念を理解する
目次
関連用語（用語集）
組合せ論入門に関連する個別の用語解説。
- パスカルの三角形 — 二項係数を三角形に並べた数表と隠れた規則
- 階乗 — $n!$ の定義・$0!=1$・順列との関係
- カタラン数 — 括弧列や三角形分割を数える数列
- 鳩の巣原理 — 存在証明の基本となる組合せ原理
- 二項係数 — $\binom{n}{k}$ の意味と計算
- 多項定理 — $(x_1+\cdots+x_m)^n$ の展開と多項係数
- 重複組合せ（仕切りと星） — 重複組合せ（stars and bars）の定義・仕切りと星の対応・公式 C(n+k-1,k) の導出と数値例を入門…
- ヴァンデルモンドの恒等式 — ヴァンデルモンドの恒等式 C(m+n,r)=sum C(m,k)C(n,r-k) の組合せ論的証明・代数的証明・数値…
- ホッケースティック恒等式 — ホッケースティック恒等式（パスカルの三角形の斜め方向の和）の定義・組合せ論的証明・数値例を入門レベルで解説する
- 投票問題（バロット問題） — 投票問題（バロット問題）：a票対b票で候補Aが勝つとき、開票中に常にAがリードし続ける確率 (a-b)/(a+b) …
- 魔方陣（定和の公式） — 魔方陣（magic square）の定義・n次魔方陣の魔数（定和）の公式 M=n(n^2+1)/2 の導出・3次・4…
- 整数の分割 $p(n)$ — 整数の分割 p(n) の定義・ヤング図形・母関数・オイラーの五角数定理・数値表を入門レベルで解説する
- ダイク経路とカタラン数 — ダイク経路（Dyck path）の定義・カタラン数との関係・反射原理による証明・数値例を入門レベルで解説する
- ケーキ数 — ケーキ数（Cake Number）は3次元空間を平面で切ったときの最大領域数
- 怠けた仕出し屋の数列 — 怠けた仕出し屋の数列（Lazy Caterer's Sequence）は円板や平面を n 本の直線で切る最大領域数
- モツキン数 — モツキン数（Motzkin Number）は円周上の n 点を交わらない弦で結ぶ方法の数
- シュレーダー数 — シュレーダー数（Schröder Number）は格子路・多角形三角分割・括弧列の数え上げに現れる数列
- ナラヤナ数 — ナラヤナ数 N(n,k) はカタラン数の細分化で、k 個のピークを持つ Dyck 路の数
- 電話数（対合の数） — 電話数（Telephone Number）は n 要素集合の対合（involution）の総数
- ゴリゴン — ゴリゴン（Golygon）は辺の長さが連続する整数 1,2,3,... であり直角に曲がって閉じる多角形
前提知識
- 中学数学の計算力
- 集合の基本概念
基本公式
順列（Permutation）
$$_nP_r = \dfrac{n!}{(n-r)!} = n(n-1)(n-2)\cdots(n-r+1)$$$n$個から$r$個を選んで並べる場合の数
組合せ（Combination）
$$_nC_r = \binom{n}{r} = \dfrac{n!}{r!(n-r)!}$$$n$個から$r$個を選ぶ場合の数（順序を考えない）
二項定理
$$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$$参考資料
読み物
-
数えずに数える
［読み物］
一つずつ書き出さずに「何通りか」を言い当てる。掛けて割って模様を読む、組合せ論の出発点を肩の力を抜いて語る。
-
パスカルの三角形にひそむ模様
［読み物］
上の二つを足すだけの素朴な三角形に、なぜ場合の数やフィボナッチ、フラクタルまでが現れるのか。ただ足すだけの不思議を気軽に語る。
-
鳩より巣が少なければ
［読み物］
箱より物が多ければ、同じ箱に入る物が必ずある。たったそれだけの当たり前から、同じ誕生日や同じ髪の本数の人の存在を言い当てる、鳩の巣原理の切れ味を気軽に語る。