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!)
 A135501 Number of closed lambda-terms of size n and size 1 for the variables. 3
 1, 2, 4, 13, 42, 139, 506, 1915, 7558, 31092, 132170, 580466, 2624545, 12190623, 58083923, 283346273, 1413449148, 7200961616, 37425264180, 198239674888, 1069228024931, 5867587726222, 32736878114805, 185570805235978 (list; graph; refs; listen; history; text; internal format)
 OFFSET 2,2 COMMENTS A lambda-term is a term which is either a variable "x" (of size 1), an application of two lambda-terms (of size 1 + the sum of the sizes of the two subterms), or a lambda binding a new variable in a term (of size 1 + the size of the subterm). Is there a generating function? LINKS Christophe Raffalli, Table of n, a(n) for n = 2..63 Olivier Bodini, Danièle Gardy, Bernhard Gittenberger, Zbigniew Gołębiewski, On the number of unary-binary tree-like structures with restrictions on the unary height, arXiv:1510.01167 [math.CO], 2015, see p. 4. Katarzyna Grygiel and Pierre Lescanne, Counting and generating lambda-terms, arXiv preprint arXiv:1210.2610 [cs.LO], 2012-2013. Pierre Lescanne, On counting untyped lambda terms, arXiv:1107.1327 [cs.LO], 2011-2012. Paul Tarau, On Type-directed Generation of Lambda Terms, preprint, 2015. P. Tarau, A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations, arXiv preprint arXiv:1507.06944, 2015 Noam Zeilberger, Alain Giorgetti, A correspondence between rooted planar maps and normal planar lambda terms, arXiv:1408.5028 [cs.LO], 2014. FORMULA f(n,0) where f(1,1) = 1; f(0,k) = 0; f(n,k) = 0 if k>2n-1; f(n,k) = f(n-1,k) + f(n-1,k+1) + sum_{p=1 to n-2} sum_{c=0 to k} sum_{l=0 to k - c} [C^c_k C^l_(k-c) f(p,l+c) f(n-p-1,k-l)], where C^p_n are binomial coefficients (the last term is for the application where "c" is the number of common variables in both subterms). f(n,k) can be computed only using f(n',k') with n' < n and k' <= k + n - n'. f(n,k) is the number of lambda terms of size n (with size 1 for the variables) having exactly k free variables. T(n,0) where T(0,m) = 0; T(1,m) = m; T(n+1,m) = T(n,m+1) + sum{k=0 to n-11} [T(n-k,m) T(k,m)].   T(n,m) is the number of lambda terms of size n (with size 1 for the variables) having at most m free variables. [Pierre Lescanne, Nov 18 2012] CROSSREFS Cf. A220894. Sequence in context: A002771 A284159 A050624 * A001548 A193057 A115600 Adjacent sequences:  A135498 A135499 A135500 * A135502 A135503 A135504 KEYWORD nonn AUTHOR Christophe Raffalli (christophe.raffalli(AT)univ-savoie.fr), Feb 09 2008 STATUS approved

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.