cp's OEIS Frontend

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

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