login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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.

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];

Table[a[n], {n, 0, 31}] (* Jean-Fran├žois Alcover, May 23 2017 *)

CROSSREFS

Cf. A105633, A272794.

Sequence in context: A319789 A007718 A297972 * A320807 A089264 A121399

Adjacent sequences:  A275054 A275055 A275056 * A275058 A275059 A275060

KEYWORD

nonn

AUTHOR

Pierre Lescanne, Jul 14 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 16 20:38 EDT 2021. Contains 345070 sequences. (Running on oeis4.)