組み合わせと母関数（続）

AT&T研究所に数列の最初のいくつかの項を入力すると、その数列に関する情報を検索してくれるというすごいサイトがある。

The On-Line Encyclopedia of Integer Sequences™ (OEIS™)

これを使って、先日「組み合わせと母関数」で書いた数列 A(n) の最初のいくつかの項 1,1,2,13,75,541,4683 を検索すると、

Also number of asymmetric generalized weak orders on n points.
Also called the ordered Bell numbers, i.e. the number of ordered partitions of {1,..,n}.

と出てくるのでありました。the orederd Bell numbers と覚えておけばいいみたい。
指数的母関数

E.g.f.: 1/(2-exp(x)). a(n)=Sum_{k>0} binomial(n, k)*a(n-k), a(0)=1.

と漸化式

Recurrence : a(n+1) = 1 + sum { j=1, n, binomial(n+1, j)*a(j) } - Jon Perry (perry(AT)globalnet.co.uk), Apr 25 2005

もしっかり求められていました。漸化式が得られたのは去年？意外と最近注目されるようになった数列なのかも。

おまけですが、ラベル付きノードn個を基点が1つのツリー構造にするときの場合の数って知っていますか？n=3のときは

• a→b→c
• b→c→a
• c→a→b
• a→c→b
• c→b→a
• b→a→c
• a→b,a→c (aを基点としてb,cが枝)
• b→c,b→a
• c→a,c→b

の9通り。階層構造とかオブジェクト指向のクラスの継承関係などを考えるときに出てきそう。

答えは
A000169 - OEIS
にあります。

初等的に導く方法が分からないので、ご存知でしたら教えてください*1。

*1:上のサイトのリンクを調べていけばいいのだけれど・・・・・