問題

ラベル付き完全2部グラフ$K_{m,n}$の全域木の個数を求めてください．

答え

$m^{n-1}n^{m-1}$個です．

導出

根付き木を数えることにします．根を1つ目の部集合から選ぶ場合の数を$a_{m,n}$，2つ目の部集合から選ぶ場合の数を$b_{m,n}$とします．$\frac{a_{m,n}}{m}=\frac{b_{m,n}}{n}$が求める答えです．それぞれの指数型母関数を

$$f := \sum_{m,n} a_{m,n} \frac{x^m y^n}{m!n!} \\ g := \sum_{m,n} b_{m,n} \frac{x^m y^n}{m!n!}$$

とします．
1つ目の部集合から根を選ぶ場合，その根を取り除くことを考えると，根付き木は1つ目の部集合のある1頂点と2つ目の部集合に根を持ついくつかの根付き木からなることがわかります．これを式にすると，

$$\begin{aligned} f &= x \sum_k \frac{g^k}{k!} \\ &= x \exp \left( g \right) \end{aligned}$$

となります．$k$が根の子たちの個数に対応しています．子たちの順番は区別しないので$k!$で割る必要があることに注意してください．
同様に$g = y \exp \left( f \right)$が成り立つので$g$を消去すると$f = x \exp \left( y \exp \left( f \right) \right)$となります．ここで，$\phi(t) := \exp \left( y \exp \left( t \right) \right)$としてLagrangeの反転公式を用いると，

$$\begin{aligned} [x^m y^n]f &= [y^n][x^m]f \\ &= [y^n] \frac{1}{m} [t^{m-1}] \phi(t)^m \\ &= \frac{1}{m} [t^{m-1}][y^n] \exp \left( my \exp \left( t \right) \right) \\ &= \frac{1}{m} [t^{m-1}] \frac{\left( m \exp \left( t \right) \right)^n}{n!} \\ &= \frac{m^{n-1}}{n!} \frac{n^{m-1}}{(m-1)!} \end{aligned}$$

が成り立ちます．あとはこれに$m!n!$を掛けて$m$で割ると上記の答えに一致します．