この記事は 37zigenさんによる以下の記事をもとに、お気持ちパートを自分にとってわかりやすいようにメモしたものです。
真面目な解説は書いていないので、そういうのを読みたい人は元記事の方をみてください。
37zigen.com
・物を数える
気持ち：「互いに区別できるN要素のものがあります。いい感じの条件を満たすような構造の個数を考えます」というタイプの問題を考えます
構造ってなんやねん。なんらかのなんかです。例をみて
自明１：互いに区別できるN要素のものからなる集合はいくつありますか？
1個。それはね、そう
自明２：互いに区別できるN要素のものからなる順列はいくつありますか？
N!個。はい
自明３：互いに区別できるN個の箱に互いに区別できるK個のボールを入れる方法はいくつありますか？
N^K はい
自明４：互いに区別できるN要素のものからなる有向サイクルはいくつありますか？
(N-1)! 円順列って知ってる？
非自明：互いに区別できるN要素のものからなる木はいくつありますか？
実はN^(N-2)なんですね
こういう各問題について、Nに対する答えをa_nとしたとき、というものを考えます。
これ{a_n}の指数型母関数(EGF)っていうらしいですよ。
以下では構造Aの指数型母関数をそのままA(x)と書きます。
・母関数の積
互いに区別できるN要素のものがあります。そのうちいくつかを使って構造Aのものを、残りの全部を使って構造Bのものを作ります。そのような方法は何通りありますか。
適当に計算をすると、こいつの指数型母関数はA(x)B(x)になることが示せます。
2種類以上の構造が登場するときに役に立ちます。
問題：互いに区別できるN個の要素を、aの倍数個の要素からなる集合とbの倍数個の要素からなる集合の2つに分ける方法はいくつありますか？ ただしa≠b
「互いに区別できるN要素のものからなる、aの倍数個の要素の集合はいくつありますか？」は、Nがaの倍数のとき1、そうでないとき0なのでEGFもそんな感じで求まる。
それぞれA(x)、B(x)としてA(x)B(x)が答え
他にも構造Bを「集合」にすると包除もできます。
問題：N要素の撹拌順列はいくつありますか？
撹拌順列のEGFをA(x)、集合のEGFをB(x)、順列のEGFをC(x)とすると、A(x)B(x)=C(x)です。
B(x)、C(x)の正体はわかっているので、A(x)は頑張ると計算できます。
問題：互いに区別できるK個のボールを互いに区別できるN個の箱に入れる方法はいくつありますか？ ただし、どの箱も空になってはいけない
Kを固定して、「i個の箱に入れる。空はダメ」というもののEGFをA(x)、集合のEGFをB(x)、「i個の箱に入れる。空でもOK」というもののEGFをC(x)とすると、A(x)B(x)=C(x)です。
B(x)、C(x)の正体はわかっているので、A(x)は頑張ると計算できます。
・母関数の合成
構造Aをなす各要素を、構造Bをなしているもので置き換えます。全体でN要素になるような方法は何通りありますか。
構造を「代入」しているように、実はEGFの方も代入してA(B(x))になるんですね。なにそれすごい
問題：互いに区別できるN頂点の連結functional graphの個数を求めよ
連結functional graphは、有向サイクルの各頂点を根付き木に置き換えたものです。
有向サイクルのEGFをA(x)、根付き木のEGFをB(x)とすると、求めるもののEGFはA(B(x))です。
問題：互いに区別できるN頂点の森の個数を求めよ
森は、集合の各要素を木に置き換えたものです。
集合のEGFをA(x)、木のEGFをB(x)とすると、求めるもののEGFはA(B(x))です。
問題：互いに区別できるN頂点の単純連結無向グラフの個数を求めよ
連結性の条件を落とすと、明らかに2^(N(N-1)/2)個です。EGFをC(x)とします。
連結とは限らない単純無向グラフは、集合の各要素を単純連結無向グラフに置き換えたものです。
集合のEGFをA(x)、求めるもののEGFをB(x)とすると、A(B(x))=C(x)です。
A(x)、C(x)の正体はわかっているので、B(x)は頑張ると計算できます。
・余談
重みつきで和をとりたかったら、当然係数に重みをつければいいわけですね。
問題：互いに区別できるN頂点の森について、「2^(連結成分の個数)」の和を求めよ
集合のEGFの代わりに a_n=2^n に関するEGF をA(x)、木のEGFをB(x)として、A(B(x))です。
問題：互いに区別できるN頂点の森について、「各連結成分の大きさの積」の和を求めよ
木の大きさをどうやってEGFに載せようかという話になるわけです、a_nの代わりにn*a_nを使いたいという話なので、木のEGF B(x)のかわりにx(d/dx)B(x) を使えばよくて、終わりです。
