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
Joerg Arndt, Table of n, a(n) for n = 0..100
A. Nisnevich, List of entries and lambda terms for n = 1..10
A. Nisnevich, Code to generate list of entries
Wikipedia, Lambda calculus: Notation
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))
# (See Jacobs link for more details.) Alex Nisnevich, Jun 03 2016
CROSSREFS
KEYWORD
nonn
AUTHOR
Alex Nisnevich, Nov 13 2015
EXTENSIONS
Corrected a(10) and more terms added by Alex Nisnevich, Jun 03 2016
STATUS
approved