組合せ論

数学学部無料 3 章有料 0 章

数え上げと母関数、半順序集合と Möbius 反転、グラフと行列式を扱う。

想定読者: 大学生（理系）

前提テーマ:代数学（群・環・体）、線形代数学

このテーマの 100 本ノック（50 問）

目次

1. 第 1 章数え上げと母関数無料形式的冪級数から exp 公式と Lagrange 反転を証明し Cayley の公式を導く。Fekete の補題、二項定理と鳩の巣原理、二項係数の単峰性（Newton の不等式）、van der Waerden の定理も扱う。
2. 第 2 章半順序集合と Möbius 反転無料接続代数で Möbius 関数を定義して反転公式・包除原理・分割束の Möbius 関数を証明し、キュムラントへ応用する。束と分配束・連続束、Dilworth の定理、Whitney 数も扱う。
3. 第 3 章グラフと行列式無料全域木の数を Laplacian の小行列式で数える行列木定理、Pfaffian と Kasteleyn の定理、Cauchy・Borchardt の行列式、Ihara–Bass 公式、Kac–Ward 公式を証明する。マトロイドと貪欲法、Nim と Sprague–Grundy の定理も扱う。