組合せ論 50 本ノック

学部50 問。全問無料です。

対象読者: 本テーマの 3 つの章（母関数、Möbius 反転、行列木定理と Pfaffian）を読み、定理の仮定と結論を自分の言葉で言える学部生。章の証明を再現できる必要はありません。

テーマの目次へ（組合せ論）

執筆: Claude Code（Sonnet 5.5）・監査 2 回（Claude Code）・最終 2026-10-12

読み込んでいます…

この冊について（出典・構成・使う定理）

主な参考文献

• R. P. Stanley, Enumerative Combinatorics, Volume 1
• H. S. Wilf, generatingfunctionology
• A. Nica, R. Speicher, Lectures on the Combinatorics of Free Probability
• R. P. Stanley, Algebraic Combinatorics

問題はすべて Rikai の書き下ろしです。参考文献の演習や本文は転載していません。

構成

• 1〜6: 形式的冪級数と通常型母関数
• 7〜12: 指数型母関数と exp 公式
• 13〜17: Lagrange 反転・Cayley の公式・Fekete の補題
• 18〜24: 半順序集合・Möbius 反転・包除原理
• 25〜33: 分割束とキュムラント
• 34〜38: 行列木定理
• 39〜44: Pfaffian と Kasteleyn の定理
• 45〜47: Cauchy の行列式と Borchardt の恒等式
• 48〜50: Ihara–Bass の公式と Kac–Ward の公式

形式: 単一選択 16・複数選択 8・○× 6・数値 8・並べ替え 4・誤り探し 4・記述 4。難易度 ★〜★★★★: 6 / 21 / 21 / 2。

この冊で使う定義・定理（55）

• 定義 2.1 形式的冪級数環 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 1, 2, 5, 6 番
• 定義 2.3 形式的な収束と合成 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 2, 6 番
• 定義 2.5 形式的な exp と log 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 6 番
• 例 4.2 Bell 数・置換・乱列 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 7, 8, 9, 10 番
• 例 5.3 Catalan 数 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 13 番
• 例 3.1 合成の個数 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 3, 4 番
• 例 4.3 連結グラフと全グラフ 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 11 番
• 演習 9.3 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 14 番
• 補題 6.2 動物の数の優乗法性 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 17 番
• 補題 6.1 Fekete の補題 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 16, 17 番
• 命題 2.6 exp の基本性質 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 12 番
• 命題 2.2 逆元の存在 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 1, 3, 4, 5 番
• 定理 6.3 格子動物の成長率 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 17 番
• 定理 5.4 Cayley の公式 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 14, 15 番
• 定理 4.1 exp 公式 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 7, 8, 9, 10, 11, 12 番
• 定理 5.2 Lagrange 反転公式 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden → 13, 14, 15 番
• 定義 2.1 グラフ・全域木・閉路 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 35 番
• 定義 6.1 非後退行列と Ihara ゼータ関数 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 48 番
• 定義 4.4 Kasteleyn 向き グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 41, 42, 43 番
• 定義 2.3 重み付き Laplacian と向き付き接続行列 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 37, 38 番
• 定義 4.2 Pfaffian グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 39, 40, 44 番
• 例 7.6 多角形での検算 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 50 番
• 例 4.7 正方形：向きの条件が必要な理由 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 42 番
• 補題 2.2 森の辺の数と葉 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 35, 37 番
• 補題 3.1 接続行列の小行列式 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 34, 37 番
• 補題 4.5 閉路の時計回りの辺の偶奇 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 43 番
• 補題 2.4 Laplacian の分解 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 34, 36 番
• 命題 7.1 高温展開 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 50 番
• 命題 6.2 Ihara ゼータ関数は行列式の逆数 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 48, 49 番
• 命題 7.5 単純な閉路は正の寄与 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 50 番
• 定理 5.3 Borchardt の恒等式 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 45, 47 番
• 定理 5.1 Cauchy の行列式 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 45, 46, 47 番
• 定理 6.3 Ihara–Bass の公式 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 48, 49 番
• 定理 7.3 Kac–Ward 公式 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 50 番
• 定理 4.6 Kasteleyn の定理 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 41, 42 番
• 定理 3.2 行列木定理（Kirchhoff） グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 34, 36, 38 番
• 定理 4.3 Pfaffian の 2 乗は行列式 グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim → 40, 44 番
• 系 6.10 独立な確率変数の和のキュムラント 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 30 番
• 定義 6.1 混合キュムラント 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 32, 33 番
• 定義 2.5 Möbius 関数 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 21 番
• 定義 2.1 半順序集合・区間 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 18 番
• 例 6.3 低次のキュムラント 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 28, 29 番
• 例 4.2 乱列・Euler の関数・全射の個数 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 19, 23, 24 番
• 例 3.4 ブール束と約数の束 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 22 番
• 例 2.7 鎖の Möbius 関数 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 20 番
• 例 2.2 三つの基本的な半順序集合 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 18 番
• 例 6.5 無相関でも独立ではない：3 次の混合キュムラント 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 30 番
• 命題 6.8 キュムラントの多重線形性 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 33 番
• 命題 3.2 直積の Möbius 関数 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 20, 26 番
• 命題 5.1 分割束の区間の構造 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 26, 27 番
• 定理 4.1 包除原理 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 19, 22, 23, 24 番
• 定理 6.9 独立な変数の混合キュムラント 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 30, 32, 33 番
• 定理 3.1 Möbius 反転公式 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 21, 22, 31 番
• 定理 6.2 キュムラントの反転公式 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 28, 29, 31 番
• 定理 5.2 分割束の Möbius 関数 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで → 25, 26, 27, 31 番