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

%I #86 Nov 25 2019 03:31:03

%S 0,1,3,14,82,579,4741,43977,454283,5159441,63782411,851368766,

%T 12188927818,186132043831,3017325884473,51712139570022,

%U 933654684562038,17702959714232057,351535449888420187,7292626296788508624,157698798590301690864,3547597554377118966359

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

%H Alois P. Heinz, <a href="/A220894/b220894.txt">Table of n, a(n) for n = 0..200</a>

%H Maciej Bendkowski, K Grygiel, 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 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 Katarzyna Grygiel, 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 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 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 P. 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 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 T(n,0) where

%F T(0,m) = m;

%F T(n+1,m) = T(n,m+1) + sum_{i=0 to n} T(i,m) * T(n-i,m).

%F 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 c(n,0) where

%F c(0,1) = 1; c(0,i) if i!=1;

%F 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 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 a:= n-> T(n, 0):

%p T:= proc(n, m) option remember; `if`(n=0, m,

%p T(n-1, m+1) +add(T(i, m)*T(n-1-i, m), i=0..n-1))

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Mar 20 2013

%t 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 (Sage)

%o @CachedFunction

%o def T(n, m):

%o if n == 0: return m

%o return T(n-1, m+1) + sum(T(i, m) * T(n-1-i, m) for i in range(n))

%o def a(n):

%o return T(n,0)

%o [a(n) for n in range(66)]

%o # _Joerg Arndt_, Jan 01 2013

%o (Haskell)

%o t :: Int -> Int -> Integer

%o t 0 m = (fromIntegral m)

%o t n m = t (n-1) (m+1) + foldl (+) 0 (let tt = [t i m | i<- [0..(n-1)]] in

%o (map (uncurry (*)) (zip tt (reverse tt))))

%o # _Pierre Lescanne_, Mar 18 2013

%o # The following program is more efficient:

%o (Haskell)

%o with memoization

%o ttab :: [[Integer]]

%o ttab = [0..] : [[ttab !! (n-1) !! (m+1) + s n m | m <- [0..]] | n <- [1..]]

%o where s n m = let ti = [ttab !! i !! m | i <- [0..(n-1)]] in foldl (+) 0 (map (uncurry (*)) (zip ti (reverse ti)))

%o t :: Int -> Int -> Integer

%o t n m = ttab !! n !! m

%o # _Pierre Lescanne_, Mar 20 2013

%Y Cf. A135501, A114852.

%Y Cf. A220895 (one free variable), A220896 (two free variables), A220897 (three free variables).

%K nonn

%O 0,3

%A _N. J. A. Sloane_, Dec 31 2012

%E More terms from _Joerg Arndt_, Jan 01 2013

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 28 04:13 EDT 2024. Contains 371235 sequences. (Running on oeis4.)