A220894 Number of closed lambda-terms of size n with size 0 for the variables.
0, 1, 3, 14, 82, 579, 4741, 43977, 454283, 5159441, 63782411, 851368766, 12188927818, 186132043831, 3017325884473, 51712139570022, 933654684562038, 17702959714232057, 351535449888420187, 7292626296788508624, 157698798590301690864, 3547597554377118966359
Offset: 0
Keywords
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.
Crossrefs
Programs
-
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
-
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 *) -
Sage
@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
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
Extensions
More terms from Joerg Arndt, Jan 01 2013