login
This site is supported by donations 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

Alois P. Heinz, Table of n, a(n) for n = 0..200

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, 2016

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.

Paul Tarau, On logic programming representations of lambda terms: de Bruijn indices, compression, type inference, combinatorial generation, normalization, 2015.

P. 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.

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 xrange(0, n) )

def a(n):  return T(n, 0)

[a(n) for n in xrange(0, 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. A135501, A114852.

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

Sequence in context: A194091 A186737 A020104 * A103467 A215661 A224776

Adjacent sequences:  A220891 A220892 A220893 * A220895 A220896 A220897

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 21 22:56 EST 2018. Contains 299427 sequences. (Running on oeis4.)