|
%I #29 Apr 18 2021 13:45:37
%S 0,0,0,0,1,0,1,1,2,1,6,5,13,14,37,44,101,134,298,431,883,1361,2736,
%T 4405,8574,14334,27465,47146,89270,156360,293840,522913,978447,
%U 1761907,3288605,5977863,11148652,20414058,38071898,70125402,130880047
%N 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).
%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 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="/A114852/a114852.hs.txt">More efficient Haskell program</a>
%F a(n) = N(0,n) with
%F N(k,0) = N(k,1) = 0
%F N(k,n+2) = (if k>n then 1 else 0) +
%F N(k+1,n) +
%F Sum_{i=0..n} N(k,i) * N(k,n-i)
%e 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.
%p A114852T := proc(k,n)
%p option remember;
%p local a;
%p if n = 0 or n = 1 then
%p 0;
%p else
%p a := procname(k+1,n-2) ;
%p if k > n-2 then
%p a := a+1 ;
%p fi ;
%p a := a+add(procname(k,i)*procname(k,n-i-2),i=0..n-2) ;
%p end if;
%p end proc:
%p A114852 := proc(n)
%p A114852T(0,n) ;
%p end proc: # _R. J. Mathar_, Feb 28 2015
%t 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}];
%t a[n_] := S[0, n];
%t Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, May 23 2017 *)
%o (Haskell)
%o a114852 = closed 0 where
%o closed k n = if n<2 then 0 else
%o (if n-2<k then 1 else 0) +
%o closed (k+1) (n-2) +
%o sum [closed k i * closed k (n-2-i) | i <- [0..n-2]]
%o -- See link for a more efficient version.
%Y Cf. A114851, A195691.
%K nonn
%O 0,9
%A _John Tromp_, Feb 20 2006
|
