login
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

%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