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



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A275057 Numbers of closed lambda terms of natural size n. 2


%S 0,0,1,1,3,6,17,41,116,313,895,2550,7450,21881,65168,195370,591007,

%T 1798718,5510023,16966529,52506837,163200904,509323732,1595311747,

%U 5013746254,15805787496,49969942138,158396065350,503317495573,1602973785463,5116010587910,16360492172347

%N Numbers of closed lambda terms of natural size n.

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

%C Here we count the closed terms of natural size n, where "closed" means that there is no free index (no free bound variable).

%H Pierre Lescanne, <a href="/A275057/b275057.txt">Table of n, a(n) for n = 0..299</a>

%H Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, Marek Zaionc, <a href="http://www.sofsem.cz/sofsem16/files/presentations/Regular/Bendkowski.pdf">A Natural Counting of Lambda Terms</a>, SOFSEM 2016: 183-194.

%H Maciej Bendkowski, K Grygiel, P Tarau, <a href="http://arxiv.org/abs/1612.07682">Random generation of closed simply-typed lambda-terms: a synergy between logic programming and Boltzmann samplers</a>, arXiv preprint arXiv:1612.07682 [cs.LO], 2016-2017.

%F L(0,m) = 0.

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

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

%t a[n_] := L[n, 0];

%t Table[a[n], {n, 0, 31}] (* _Jean-Fran├žois Alcover_, May 23 2017 *)

%Y Cf. A105633, A272794.

%K nonn

%O 0,5

%A _Pierre Lescanne_, Jul 14 2016

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 August 4 02:24 EDT 2021. Contains 346441 sequences. (Running on oeis4.)