|
| |
|
|
A135501
|
|
Number of closed lambda-terms of size n.
|
|
1
| |
|
|
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; 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 (christophe.raffalli(AT)univ-savoie.fr), Feb 09 2008, Table of n, a(n) for n = 2..63
Author?, Interesting results about counting lambda-terms
|
|
|
FORMULA
| 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'.
|
|
|
CROSSREFS
| Sequence in context: A087214 A002771 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
|
| |
|
|
