A275057 Numbers of closed lambda terms of natural size n.

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

Offset: 0

Author

Pierre Lescanne, Jul 14 2016

Keywords

• nonn

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

• Pierre Lescanne, Table of n, a(n) for n = 0..299
• Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, Marek Zaionc, A Natural Counting of Lambda Terms, SOFSEM 2016: 183-194.
• Maciej Bendkowski, K Grygiel, P Tarau, Random generation of closed simply-typed lambda-terms: a synergy between logic programming and Boltzmann samplers, arXiv preprint arXiv:1612.07682 [cs.LO], 2016-2017.

Crossrefs

Cf. A105633, A272794.

Programs

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];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, May 23 2017 *)

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)).