グラフ理論入門 ５ 数え上げ

５　数え上げ

5.1　1-因子の数え上げ

• 数え上げ問題(counting problem)
  
  • ある数学的な対象が幾つ存在し得るのかを調べること。
• nの階乗(n factorial, n!)
• 道は向きを無考慮の順列
• 組み合わせ
• 錯乱(derangements)

5.2　ケーリーの全域木公式

• プリューファーによるケーリーの全域木公式の証明
  
  • 1,2,...,nを要素とする長さn-2の数列と頂点数nの全域木は1対1対応である(プリューファーの証明)

5.3　全域木(続き)

• 完全2部グラフの全域木の個数は公式で表される。