|
|
A260661
|
|
The number of distinct (up to alpha-equivalence) closed lambda calculus terms n characters long, assuming standard notational conventions.
|
|
1
|
|
|
0, 0, 0, 0, 1, 3, 8, 22, 68, 235, 896, 3700, 16388, 77424, 388337, 2058898, 11494391, 67345463, 412884769, 2641957682, 17603708949, 121891857559, 875463364581, 6511352351724, 50074591410942, 397627804820554, 3256109939552809, 27464891261741533, 238366531369343096, 2126510299723649140, 19482346640311421722, 183143139819128271540, 1765079515780983078401
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
"Standard notational conventions" here means that "lambda a.lambda b.M" must be simplified to "lambda ab.M", "(MN)" must be simplified to "MN", and "(MN)P" must be simplified to "MNP" (see the Wikipedia article for more details).
|
|
LINKS
|
|
|
EXAMPLE
|
For n=6, the a(6)=8 terms are: lambda a.aaa, lambda ab.aa, lambda ab.ab, lambda ab.ba, lambda ab.bb, lambda abc.a, lambda abc.b, lambda abc.c.
|
|
PROG
|
(Sage)
def a(n):
return term(n, 0, 0, 0)
@CachedFunction
def term(n, k, L, R):
return var(n, k) + lam(n-2 if R else n, k) + app(n-2 if L else n, k, R and not L)
def var(n, k):
return k if n==1 else 0
@CachedFunction
def lam(n, k):
return sum(var(n-v-2, k+v) + app(n-v-2, k+v, 0) for v in range(1, n-2))
@CachedFunction
def app(n, k, R):
return sum(term(u, k, 0, 1) * term(n-u, k, 1, R) for u in range(1, n))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|