

A135501


Number of closed lambdaterms 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 lambdaterm is a term which is either a variable "x" (of size 1), an application of two lambdaterms (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?


REFERENCES

Paul Tarau, On logic programming representations of lambda terms: de Bruijn indices, compression, type inference, combinatorial generation, normalization, 2015; http://www.cse.unt.edu/~tarau/research/2015/dbx.pdf


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 unarybinary treelike structures with restrictions on the unary height, arXiv:1510.01167 [math.CO], 2015, see p. 4.
Katarzyna Grygiel and Pierre Lescanne, Counting and generating lambdaterms, arXiv preprint arXiv:1210.2610 [cs.LO], 20122013.
Pierre Lescanne, On counting untyped lambda terms, arXiv:1107.1327 [cs.LO], 20112012.
Paul Tarau, On Typedirected Generation of Lambda Terms, preprint, 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>2n1; f(n,k) = f(n1,k) + f(n1,k+1) + sum_{p=1 to n2} sum_{c=0 to k} sum_{l=0 to k  c} [C^c_k C^l_(kc) f(p,l+c) f(np1,kl)], 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 n11} [T(nk,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: A243107 A002771 A050624 * A001548 A193057 A115600
Adjacent sequences: A135498 A135499 A135500 * A135502 A135503 A135504


KEYWORD

nonn,changed


AUTHOR

Christophe Raffalli (christophe.raffalli(AT)univsavoie.fr), Feb 09 2008


STATUS

approved



