Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #35 Nov 16 2019 20:08:20
%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