%I #71 Apr 18 2021 07:54:16
%S 0,0,1,1,2,2,4,5,10,14,27,41,78,126,237,399,745,1292,2404,4259,7915,
%T 14242,26477,48197,89721,164766,307294,568191,1061969,1974266,3698247,
%U 6905523,12964449,24295796,45711211,85926575,161996298,305314162,576707409,1089395667
%N Number of lambda calculus terms of size n, where size(lambda x.M) = 2 + size(M), size(M N) = 2 + size(M) + size(N), and size(V) = 1 + i for a variable V bound by the i-th enclosing lambda (corresponding to a binary encoding).
%C Let r be the root of the polynomial P(x) = x^5 + 3x^4 - 2x^3 + 2 x^2 + x - 1 that is closest to the origin. r is about 0.5093081270242373 and 1/r is about 1.963447954075964. Let P' be the derivative of P. Let C = sqrt(P'(r)/(1-r)) / (2 sqrt(pi) r^(3/2)); then C is about 1.0218740729. Then a(n) ~ (C / n^(3/2)) * (1/r)^n. - _Pierre Lescanne_, May 29 2013
%H Vincenzo Librandi, <a href="/A114851/b114851.txt">Table of n, a(n) for n = 0..1000</a>
%H Maciej Bendkowski, K. Grygiel, and 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.
%H K. Grygiel and P. Lescanne, <a href="http://arXiv.org/abs/1401.0379">Counting terms in the binary lambda calculus</a>, arXiv preprint arXiv:1401.0379 [cs.LO], 2014.
%H Katarzyna Grygiel and Pierre Lescanne, <a href="https://hal-ens-lyon.archives-ouvertes.fr/ensl-01229794">Counting and Generating Terms in the Binary Lambda Calculus (Extended version)</a>, HAL Id: ensl-01229794, 2015.
%H Pierre Lescanne, <a href="http://arxiv.org/abs/1312.4917">An exercise on streams: convergence acceleration</a>, arXiv preprint arXiv:1312.4917 [cs.NA], 2013.
%H P. Lescanne, <a href="http://arxiv.org/abs/1404.3875">Boltzmann samplers for random generation of lambda terms</a>, arXiv preprint arXiv:1404.3875 [cs.DS], 2014.
%H Paul Tarau, <a href="https://arxiv.org/abs/1608.03912">A Hiking Trip Through the Orders of Magnitude: Deriving Efficient Generators for Closed Simply-Typed Lambda Terms and Normal Forms</a>, arXiv preprint arXiv:1608.03912 [cs.PL], 2016.
%H John Tromp, <a href="https://tromp.github.io/cl/cl.html">John's Lambda Calculus and Combinatory Logic Playground</a>
%H John Tromp, <a href="https://tromp.github.io/cl/LC.pdf">Binary Lambda Calculus and Combinatory Logic</a>
%H John Tromp, <a href="/A114851/a114851.hs.txt">More efficient Haskell program</a>
%F a(n+2) = 1 + a(n) + Sum_{i=0..n} a(i)*a(n-i), with a(0) = a(1) = 0.
%F G.f.: ( 1 - x - x^2 + x^3 - sqrt((1 + x - x^2 - x^3)^2 - 4*(x - 2*x^3 + x^4)) ) / (2*(x^2 - x^3)). - _Michael Somos_, Jan 28 2014
%F G.f.: A(x) =: y satisfies 0 = 1 / (1 - x) + (1 - 1/x^2) * y + y^2. - _Michael Somos_, Jan 28 2014
%F Conjecture: (n+2)*a(n) + 2*(-n-1)*a(n-1) + (-n+2)*a(n-2) + 4*(n-2)*a(n-3) + (-5*n+18)*a(n-4) + 2*(n-4)*a(n-5) + (n-6)*a(n-6) = 0. - _R. J. Mathar_, Mar 04 2015
%e a(4) = 2 because lambda x.x and var3 (bound by 3rd enclosing lambda) are the only two lambda terms of size 4.
%e G.f. = x^2 + x^3 + x^4 + x^5 + 2*x^6 + 3*x^7 + 6*x^8 + 9*x^9 + 17*x^10 + ...
%t a[n_] := a[n] = 1 + a[n-2] + Sum[ a[i]*a[n-i-2], {i, 0, n-2}]; a[0] = a[1] = 0; Table[a[n], {n, 0, 32}] (* _Jean-François Alcover_, Dec 06 2011 *)
%t a[ n_] := SeriesCoefficient[ (1 - x - x^2 + x^3 - Sqrt[(1 + x - x^2 - x^3)^2 - 4 (x - 2 x^3 + x^4)]) / (2 (x^2 - x^3)), {x, 0, n}]; (* _Michael Somos_, Feb 25 2014 *)
%t CoefficientList[Series[(1 - x - x^2 + x^3 - Sqrt[(1 + x - x^2 - x^3)^2 -4 (x - 2 x^3 + x^4)])/(2 (x^2 - x^3)), {x, 0, 40}], x] (* _Vincenzo Librandi Mar 01 2014 *)
%o (Haskell)
%o a114851 = open where
%o open n = if n<2 then 0 else
%o 1 + open (n-2) + sum [open i * open (n-2-i) | i <- [0..n-2]]
%o -- See link for a more efficient version.
%o (PARI) x='x+O('x^66); concat( [0,0], Vec( (1-x-x^2+x^3-sqrt((1+x-x^2-x^3)^2-4*(x-2*x^3+x^4)))/(2*(x^2-x^3)) ) ) \\ _Joerg Arndt_, Mar 01 2014
%Y Cf. A114852, A195691, A236393.
%K nonn
%O 0,5
%A _John Tromp_, Feb 20 2006
%E More terms from _Vincenzo Librandi_, Mar 01 2014