A260661 The number of distinct (up to alpha-equivalence) closed lambda calculus terms n characters long, assuming standard notational conventions.
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
Offset: 0
Keywords
Examples
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.
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
Programs
-
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
Extensions
Corrected a(10) and more terms added by Alex Nisnevich, Jun 03 2016
Comments