3 つの例
S(0) = 0 かつ S(n + 1) = 1 + (n + 1)S(n) である
長さ n+1 の入力に対して子は n+1個できてそれぞれが長さ n の入力に対する木ができて
それに自分の節点の 1 を足して S(n + 1) = 1 + (n + 1)S(n) がでる。
S(1) = 1 なので S(0) = 0
長さ n の入力に対する木の最上位層節点の個数はルートの 1個。
第2階層節点の個数は n個(= n!/(n-1)!)。
その n個からそれぞれ n-1個の枝分かれするので第3階層節点の個数は n(n-1)個(= n!/(n-2)!)。 同様に第4階層節点の個数は n(n-1)(n-2)個(= n!/(n-3)!)。
…
同様にしていって最下位層節点の個数は n!個(= n!/1!)。
全部合わせると S(n) = n! Σ 1/k!。
n! Σ 1/k! が上記の漸化式を満たすことを確認する手もある。