Skip to content →

37zigenのHP Posts

Prüfer コード

この記事ではラベル付き木を全単射な方法で数列に変換する、Prüfer コード(Prüfer 列)と呼ばれるテクニックを解説する。Prüfer コードを使えば、ラベル付き木を数えやすい対象に変換することができ、木の数え上げに威力を発揮する。

指数型母関数入門

形式的冪級数を \(\sum a_n\frac{x^n}{n!}\) の形で取ると意味のある畳込みが計算できてなぜか上手くいくことがある。この指数型母関数と呼ばれる形で上手くいくのはどんな場合か、またその性質を積極的に利用して考察に生かせないのか。解説しよう。

Turán の定理

\(r\) 頂点完全グラフ \(K^r\) を含まない辺の数が最大のグラフとは何か。この疑問に答える Turán の定理を解説しよう。