cp's OEIS Frontend

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

%I A260661 #29 Jan 08 2018 01:58:32
%S A260661 0,0,0,0,1,3,8,22,68,235,896,3700,16388,77424,388337,2058898,11494391,
%T A260661 67345463,412884769,2641957682,17603708949,121891857559,875463364581,
%U A260661 6511352351724,50074591410942,397627804820554,3256109939552809,27464891261741533,238366531369343096,2126510299723649140,19482346640311421722,183143139819128271540,1765079515780983078401
%N A260661 The number of distinct (up to alpha-equivalence) closed lambda calculus terms n characters long, assuming standard notational conventions.
%C A260661 "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 A260661 Joerg Arndt, <a href="/A260661/b260661.txt">Table of n, a(n) for n = 0..100</a>
%H A260661 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 A260661 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 A260661 A. Nisnevich, <a href="https://github.com/AlexNisnevich/lambda-terms/blob/master/lambda_terms.rb">Code to generate list of entries</a>
%H A260661 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lambda_calculus#Notation">Lambda calculus: Notation</a>
%e A260661 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 A260661 (Sage)
%o A260661 def a(n):
%o A260661     return term(n,0,0,0)
%o A260661 @CachedFunction
%o A260661 def term(n,k,L,R):
%o A260661     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 A260661 def var(n,k):
%o A260661     return k if n==1 else 0
%o A260661 @CachedFunction
%o A260661 def lam(n,k):
%o A260661     return sum(var(n-v-2,k+v) + app(n-v-2,k+v,0) for v in range(1,n-2))
%o A260661 @CachedFunction
%o A260661 def app(n,k,R):
%o A260661     return sum(term(u,k,0,1) * term(n-u,k,1,R) for u in range(1,n))
%o A260661 # (See Jacobs link for more details.) _Alex Nisnevich_, Jun 03 2016
%K A260661 nonn
%O A260661 0,6
%A A260661 _Alex Nisnevich_, Nov 13 2015
%E A260661 Corrected a(10) and more terms added by _Alex Nisnevich_, Jun 03 2016