|
|
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(n-k,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[n-k-1, m], {k, 0, n-1}] + L[n-1, m+1] + Boole[m >= n];
a[n_] := L[n, 0];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|