The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,9 REFERENCES Katarzyna Grygiel, Pierre Lescanne. Counting and Generating Terms in the Binary Lambda Calculus (Extended version). 2015. LINKS K. Grygiel, P. Lescanne, Counting terms in the binary lambda calculus, arXiv preprint arXiv:1401.0379, 2014 John Tromp, Binary Lambda Calculus and Combinatory Logic John Tromp, More efficient Haskell program 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 a114852 = closed 0 where   closed k n = if n<2 then 0 else     (if n-2

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 18 00:11 EST 2021. Contains 340249 sequences. (Running on oeis4.)