VOOZH about

URL: https://oeis.org/A114852

⇱ A114852 - OEIS

login
A114852
The number of closed 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).
8
0, 0, 0, 0, 1, 0, 1, 1, 2, 1, 6, 5, 13, 14, 37, 44, 101, 134, 298, 431, 883, 1361, 2736, 4405, 8574, 14334, 27465, 47146, 89270, 156360, 293840, 522913, 978447, 1761907, 3288605, 5977863, 11148652, 20414058, 38071898, 70125402, 130880047
OFFSET
0,9
COMMENTS
a(n) grows asymptotically as C*n^{-3/2}*rho^(-n), where rho~0.509308 is the smallest positive root of (1-z) * (1-z^2)^2 - 4*z^4, and 0.01252417 <= C <= 0.01254594, as shown in the Bodini et al. paper.
LINKS
Olivier Bodini, Bernhard Gittenberger, and Zbigniew Gołębiewski, Enumerating lambda terms by weighted length of their De Bruijn representation, Discrete Applied Mathematics, Volume 239, 20 April 2018, pages 45-61.
Katarzyna Grygiel and Pierre Lescanne, Counting terms in the binary lambda calculus, arXiv preprint arXiv:1401.0379 [cs.LO], 2014.
Katarzyna Grygiel and Pierre Lescanne, Counting and Generating Terms in the Binary Lambda Calculus (Extended version), HAL Id: ensl-01229794, 2015.
FORMULA
a(n) = N(0,n) with
N(k,0) = N(k,1) = 0
N(k,n+2) = (if k>n then 1 else 0) +
N(k+1,n) +
Sum_{i=0..n} N(k,i) * N(k,n-i)
EXAMPLE
a(8) = 2 because lambda x.lambda y.lambda z.z and lambda x.(x x) are the only two closed lambda terms of size 8.
MAPLE
A114852T := proc(k, n)
option remember;
local a;
if n = 0 or n = 1 then
0;
else
a := procname(k+1, n-2) ;
if k > n-2 then
a := a+1 ;
fi ;
a := a+add(procname(k, i)*procname(k, n-i-2), i=0..n-2) ;
end if;
end proc:
A114852 := proc(n)
A114852T(0, n) ;
end proc: # R. J. Mathar, Feb 28 2015
MATHEMATICA
S[_, 0] = 0; S[_, 1] = 0; S[m_, n_] := S[m, n] = Boole[m >= n-1] + S[m+1, n-2] + Sum[S[m, k] S[m, n-k-2], {k, 0, n-2}];
a[n_] := S[0, n];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, May 23 2017 *)
PROG
(Haskell)
a114852 = closed 0 where
closed k n = if n<2 then 0 else
(if n-2<k then 1 else 0) +
closed (k+1) (n-2) +
sum [closed k i * closed k (n-2-i) | i <- [0..n-2]]
-- See link for a more efficient version.
CROSSREFS
Sequence in context: A307048 A188652 A333958 * A188048 A191529 A095132
KEYWORD
nonn
AUTHOR
John Tromp, Feb 20 2006
STATUS
approved