login
The number of distinct (up to alpha-equivalence) closed lambda calculus terms n characters long, assuming standard notational conventions.
1

%I #29 Jan 08 2018 01:58:32

%S 0,0,0,0,1,3,8,22,68,235,896,3700,16388,77424,388337,2058898,11494391,

%T 67345463,412884769,2641957682,17603708949,121891857559,875463364581,

%U 6511352351724,50074591410942,397627804820554,3256109939552809,27464891261741533,238366531369343096,2126510299723649140,19482346640311421722,183143139819128271540,1765079515780983078401

%N The number of distinct (up to alpha-equivalence) closed lambda calculus terms n characters long, assuming standard notational conventions.

%C "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).

%H Joerg Arndt, <a href="/A260661/b260661.txt">Table of n, a(n) for n = 0..100</a>

%H J. Jacobs, <a href="https://www.reddit.com/r/math/comments/4kftx8/how_many_closed_lambdacalculus_terms_are_there_of/d3f4b52">How many closed lambda-calculus terms are there of a given length?</a>

%H A. Nisnevich, <a href="https://github.com/AlexNisnevich/lambda-terms/blob/master/output.txt">List of entries and lambda terms for n = 1..10</a>

%H A. Nisnevich, <a href="https://github.com/AlexNisnevich/lambda-terms/blob/master/lambda_terms.rb">Code to generate list of entries</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lambda_calculus#Notation">Lambda calculus: Notation</a>

%e 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.

%o (Sage)

%o def a(n):

%o return term(n,0,0,0)

%o @CachedFunction

%o def term(n,k,L,R):

%o return var(n,k) + lam(n-2 if R else n, k) + app(n-2 if L else n, k, R and not L)

%o def var(n,k):

%o return k if n==1 else 0

%o @CachedFunction

%o def lam(n,k):

%o return sum(var(n-v-2,k+v) + app(n-v-2,k+v,0) for v in range(1,n-2))

%o @CachedFunction

%o def app(n,k,R):

%o return sum(term(u,k,0,1) * term(n-u,k,1,R) for u in range(1,n))

%o # (See Jacobs link for more details.) _Alex Nisnevich_, Jun 03 2016

%K nonn

%O 0,6

%A _Alex Nisnevich_, Nov 13 2015

%E Corrected a(10) and more terms added by _Alex Nisnevich_, Jun 03 2016