This site is supported by donations to The OEIS Foundation.

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

 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). 6
 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.