OFFSET
0,3
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..200
Maciej Bendkowski, K. Grygiel, and P. Tarau, Random generation of closed simply-typed lambda-terms: a synergy between logic programming and Boltzmann samplers, arXiv preprint arXiv:1612.07682 [cs.LO], 2016-2017.
Katarzyna Grygiel and Pierre Lescanne, Counting and generating lambda-terms, arXiv preprint arXiv:1210.2610 [cs.LO], 2012.
Katarzyna Grygiel and Pierre Lescanne, Counting and Generating Terms in the Binary Lambda Calculus (Extended version), HAL Id: ensl-01229794, 2015.
Paul Tarau, On Type-directed Generation of Lambda Terms, preprint, 2015.
Paul Tarau, On logic programming representations of lambda terms: de Bruijn indices, compression, type inference, combinatorial generation, normalization, 2015.
Paul Tarau, A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations, arXiv preprint arXiv:1507.06944 [cs.LO], 2015.
Paul Tarau, A Hiking Trip Through the Orders of Magnitude: Deriving Efficient Generators for Closed Simply-Typed Lambda Terms and Normal Forms, arXiv preprint arXiv:1608.03912 [cs.PL], 2016.
Stephen Wolfram, The Ruliology of Lambdas, September 15, 2025
FORMULA
T(n,0) where
T(0,m) = m;
T(n+1,m) = T(n,m+1) + sum_{i=0 to n} T(i,m) * T(n-i,m).
f(n,0) where f(0,1) = 1; f(0,k) = 0 if k!=1; f(n,k) = 0 if k>2n-1; f(n,k) = f(n-1,k) + f(n-1,k+1) + sum_{p=1 to n-2} sum_{c=0 to k} sum_{l=0 to k - c} [C^c_k C^l_(k-c) f(p,l+c) f(n-p-1,k-l)], where C^p_n are binomial coefficients (the last term is for the application where "c" is the number of common variables in both subterms). f(n,k) can be computed only using f(n',k') with n' < n and k' <= k + n - n'. f(n,k) is the number of lambda terms of size n (with size 0 for the variables) having exactly k free variables.
c(n,0) where
c(0,1) = 1; c(0,i) if i!=1;
c(n+1,i) sum{j=i to n+1} binomial(j,i) * c(n,j) + sum{j=0 to i} sum{k=0..n} c(k,j)* c(n-k,i-j).
G.f.: L(z,0) where L(z,u) = u + z*L(z,u+1) + z*L(z,u)^2. - Pierre Lescanne, Mar 14 2013
MAPLE
a:= n-> T(n, 0):
T:= proc(n, m) option remember; `if`(n=0, m,
T(n-1, m+1) +add(T(i, m)*T(n-1-i, m), i=0..n-1))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Mar 20 2013
MATHEMATICA
Clear[t]; t[0, m_] := m; t[n_, m_] := t[n, m] = t[n-1, m+1] + Sum[t[i, m]*t[n-1-i, m], {i, 0, n-1}]; a[n_] := t[n, 0]; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Apr 04 2013 *)
PROG
(SageMath)
@CachedFunction
def T(n, m):
if n == 0: return m
return T(n-1, m+1) + sum(T(i, m) * T(n-1-i, m) for i in range(n))
def a(n):
return T(n, 0)
[a(n) for n in range(66)]
# Joerg Arndt, Jan 01 2013
(Haskell)
t :: Int -> Int -> Integer
t 0 m = (fromIntegral m)
t n m = t (n-1) (m+1) + foldl (+) 0 (let tt = [t i m | i<- [0..(n-1)]] in
(map (uncurry (*)) (zip tt (reverse tt))))
-- Pierre Lescanne, Mar 18 2013
(Haskell)
-- The following program is more efficient:
with memoization
ttab :: [[Integer]]
ttab = [0..] : [[ttab !! (n-1) !! (m+1) + s n m | m <- [0..]] | n <- [1..]]
where s n m = let ti = [ttab !! i !! m | i <- [0..(n-1)]] in foldl (+) 0 (map (uncurry (*)) (zip ti (reverse ti)))
t :: Int -> Int -> Integer
t n m = ttab !! n !! m
-- Pierre Lescanne, Mar 20 2013
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Dec 31 2012
EXTENSIONS
More terms from Joerg Arndt, Jan 01 2013
STATUS
approved