木
主にこれを参考にしました。こっち読んだほうが良いと思います(これは自分用のメモ)。
http://www.i.kyushu-u.ac.jp/~eiji/GraphCombinatorics/graph-combinatorics5.pdf
ラベルつき木の数は 
証明の仕方も面白いですね。
辺ラベルが付いている根付き木を Un, ラベル付き木の数を Tn とする。
Tn をベースに Un を求める
ラベル付き木をひとつ決めるごとに, 根の決め方が n 通り, 辺のラベルの付け方が (n-1)! 通りなので, Un = n! * Tn
Un を普通に数える
辺を適当に貼っていく。
一度「u -> v」というように貼った場合, v に向かってもう一回 「w -> v」 というように辺を貼ることは許されない。それ以外は自由に辺を貼れるので, 場合の数は
以上より
順序木の数はカタラン数と等しい
カタラン数は, 「原点からスタートして, +1 進むか, -1 進むかを選べる。ただし, 現座標が負になるような移動は ng なときの, valid な移動の数」でよく使われます。順序木の場合も, 「頂点を一個先に進める, 一個戻る」という動作が許されますが, 根から一個戻るという動作は許されないので, 結局カタラン数と一致します(適当)。
母関数よくわからないですが valid な括弧列も同じ理論でカタラン数に一致することが言えそうです。
