login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A220894 Number of closed lambda-terms of size n with size 0 for the variables. 5
0, 1, 3, 14, 82, 579, 4741, 43977, 454283, 5159441, 63782411, 851368766, 12188927818, 186132043831, 3017325884473, 51712139570022, 933654684562038, 17702959714232057, 351535449888420187, 7292626296788508624, 157698798590301690864, 3547597554377118966359 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
LINKS
Maciej Bendkowski, K Grygiel, 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, 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.
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
(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
(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
# The following program is more efficient:
(Haskell)
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
Cf. A220895 (one free variable), A220896 (two free variables), A220897 (three free variables).
Sequence in context: A186737 A367972 A020104 * A103467 A355293 A215661
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Dec 31 2012
EXTENSIONS
More terms from Joerg Arndt, Jan 01 2013
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 06:53 EDT 2024. Contains 370953 sequences. (Running on oeis4.)