|
|
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
|
|
|
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:
|
|
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)]
(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))))
# 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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|