

A275057


Numbers of closed lambda terms of natural size n.


2



0, 0, 1, 1, 3, 6, 17, 41, 116, 313, 895, 2550, 7450, 21881, 65168, 195370, 591007, 1798718, 5510023, 16966529, 52506837, 163200904, 509323732, 1595311747, 5013746254, 15805787496, 49969942138, 158396065350, 503317495573, 1602973785463, 5116010587910, 16360492172347
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

Natural size measure lambda terms as follows: all symbols are assigned size 1, namely applications, abstractions, successor symbols in de Bruijn indices and 0 symbol in de Bruijn indices (i.e., a de Bruijn index n is assigned size n+1).
Here we count the closed terms of natural size n, where "closed" means that there is no free index (no free bound variable).


LINKS



FORMULA

L(0,m) = 0.
L(n+1,m) = (Sum_{k=0..n} L(k,m)*L(nk,m)) + L(n,m+1) + [m >= n+1], where [p(n,m)] = 1 if p(n,m) is true and [p(n,m)] = 0 if p(n,m) is false then one considers the sequence (L(n,0)).


MATHEMATICA

L[0, _] = 0; L[n_, m_] := L[n, m] = Sum[L[k, m]*L[nk1, m], {k, 0, n1}] + L[n1, m+1] + Boole[m >= n];
a[n_] := L[n, 0];


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



