login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Joerg Arndt, Table of n, a(n) for n = 0..100

J. Jacobs, How many closed lambda-calculus terms are there of a given length?

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

Sequence in context: A000732 A092090 A011958 * A171841 A233449 A148770

Adjacent sequences:  A260658 A260659 A260660 * A260662 A260663 A260664

KEYWORD

nonn

AUTHOR

Alex Nisnevich, Nov 13 2015

EXTENSIONS

Corrected a(10) and more terms added by Alex Nisnevich, Jun 03 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 11 15:10 EDT 2022. Contains 356066 sequences. (Running on oeis4.)