lambda term の個数を数えてみる

上限を適当に決めて，サイズがそれ以下の lambda term の個数はいくつになるか計算してみました。

本当に項の個数を数えると変数の名前を変えるだけでいくらでもできるので，自由変数として使える変数の個数を制限します。この条件は都合のいいように設定しただけで，要するに de Bruijn index で表示して異なるものの個数を数えます。

高々 n 個の自由変数をもつ lambda term は

$\Lambda_n ::= 0 \,\mid\, \dots \,\mid\, n-1 \,\mid\, \lambda \Lambda_{n+1} \,\mid\, (\Lambda_n \Lambda_n)$

で定義できて，サイズは

$|n| = 1, \, |\lambda M| = 1 + |M|, \, |M N| = |M| + |N|$

と定義します。このとき求めるものは

$L(m, n) = \sharp\{ M \in \Lambda_n \,\mid\, |M| \leq m \}$

です。これは L(0, n) = 0 および漸化式

$L(m, n+1) = m + L(m+1, n) + \sum_{i = 1}^n (L(m, i) - L(m, i-1)) \cdot L(m, n-i+1)$

で求まります。実際に計算してみると

L(0, 5) = 100
L(0, 10) = 5663121
L(0, 15) = 3216567670420
L(0, 20) = 7662853289782963348
L(1, 5) = 635
L(1, 10) = 67888674
L(1, 15) = 54401154960253
L(1, 20) = 164464071792392717885
L(2, 5) = 3146
L(2, 10) = 710070585
L(2, 15) = 843053144301058
L(2, 20) = 3305348035629856757708

わりと多いけど，こんなものかもしれません。ほんとに合ってますか。