cp's OEIS Frontend

A220894 Number of closed lambda-terms of size n with size 0 for the variables.

%I A220894 #94 Nov 17 2024 15:45:23
%S A220894 0,1,3,14,82,579,4741,43977,454283,5159441,63782411,851368766,
%T A220894 12188927818,186132043831,3017325884473,51712139570022,
%U A220894 933654684562038,17702959714232057,351535449888420187,7292626296788508624,157698798590301690864,3547597554377118966359
%N A220894 Number of closed lambda-terms of size n with size 0 for the variables.
%H A220894 Alois P. Heinz, <a href="/A220894/b220894.txt">Table of n, a(n) for n = 0..200</a>
%H A220894 Maciej Bendkowski, K. Grygiel, and P. Tarau, <a href="http://arxiv.org/abs/1612.07682">Random generation of closed simply-typed lambda-terms: a synergy between logic programming and Boltzmann samplers</a>, arXiv preprint arXiv:1612.07682 [cs.LO], 2016-2017.
%H A220894 Katarzyna Grygiel and Pierre Lescanne, <a href="http://arxiv.org/abs/1210.2610">Counting and generating lambda-terms</a>, arXiv preprint arXiv:1210.2610 [cs.LO], 2012.
%H A220894 Katarzyna Grygiel and Pierre Lescanne, <a href="https://hal-ens-lyon.archives-ouvertes.fr/ensl-01229794">Counting and Generating Terms in the Binary Lambda Calculus (Extended version)</a>, HAL Id: ensl-01229794, 2015.
%H A220894 Paul Tarau, <a href="http://www.cse.unt.edu/~tarau/research/2015/dbt.pdf">On Type-directed Generation of Lambda Terms</a>, preprint, 2015.
%H A220894 Paul Tarau, <a href="http://www.cse.unt.edu/~tarau/research/2015/dbx.pdf">On logic programming representations of lambda terms: de Bruijn indices, compression, type inference, combinatorial generation, normalization</a>, 2015.
%H A220894 Paul Tarau, <a href="http://arxiv.org/abs/1507.06944">A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations</a>, arXiv preprint arXiv:1507.06944 [cs.LO], 2015.
%H A220894 Paul Tarau, <a href="https://arxiv.org/abs/1608.03912">A Hiking Trip Through the Orders of Magnitude: Deriving Efficient Generators for Closed Simply-Typed Lambda Terms and Normal Forms</a>, arXiv preprint arXiv:1608.03912 [cs.PL], 2016.
%F A220894 T(n,0) where
%F A220894     T(0,m) = m;
%F A220894     T(n+1,m) = T(n,m+1) + sum_{i=0 to n} T(i,m) * T(n-i,m).
%F A220894 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.
%F A220894 c(n,0) where
%F A220894   c(0,1) = 1; c(0,i) if i!=1;
%F A220894   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).
%F A220894 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
%p A220894 a:= n-> T(n, 0):
%p A220894 T:= proc(n, m) option remember; `if`(n=0, m,
%p A220894       T(n-1, m+1) +add(T(i, m)*T(n-1-i, m), i=0..n-1))
%p A220894     end:
%p A220894 seq(a(n), n=0..30);  # _Alois P. Heinz_, Mar 20 2013
%t A220894 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 *)
%o A220894 (Sage)
%o A220894 @CachedFunction
%o A220894 def T(n, m):
%o A220894     if n == 0: return m
%o A220894     return T(n-1, m+1) + sum(T(i, m) * T(n-1-i, m) for i in range(n))
%o A220894 def a(n):
%o A220894     return T(n,0)
%o A220894 [a(n) for n in range(66)]
%o A220894 # _Joerg Arndt_, Jan 01 2013
%o A220894 (Haskell)
%o A220894 t :: Int -> Int -> Integer
%o A220894 t 0 m = (fromIntegral m)
%o A220894 t n m = t (n-1) (m+1) + foldl (+) 0 (let tt = [t i m | i<- [0..(n-1)]] in
%o A220894                                       (map (uncurry (*)) (zip tt (reverse tt))))
%o A220894 -- _Pierre Lescanne_, Mar 18 2013
%o A220894 (Haskell)
%o A220894 -- The following program is more efficient:
%o A220894 with memoization
%o A220894 ttab :: [[Integer]]
%o A220894 ttab = [0..] : [[ttab !! (n-1) !! (m+1) + s n m | m <- [0..]] | n <- [1..]]
%o A220894   where s n m  = let ti = [ttab !! i !! m | i <- [0..(n-1)]] in foldl (+) 0 (map (uncurry (*)) (zip ti (reverse ti)))
%o A220894 t :: Int -> Int -> Integer
%o A220894 t n m = ttab !! n !! m
%o A220894 -- _Pierre Lescanne_, Mar 20 2013
%Y A220894 Cf. A135501, A114852.
%Y A220894 Cf. A220895 (one free variable), A220896 (two free variables), A220897 (three free variables).
%K A220894 nonn
%O A220894 0,3
%A A220894 _N. J. A. Sloane_, Dec 31 2012
%E A220894 More terms from _Joerg Arndt_, Jan 01 2013