A114851 -id:A114851 - cp's OEIS frontend

A114852 The number of closed lambda calculus terms of size n, where size(lambda x.M)=2+size(M), size(M N)=2+size(M)+size(N), and size(V)=1+i for a variable V bound by the i-th enclosing lambda (corresponding to a binary encoding).

0, 0, 0, 0, 1, 0, 1, 1, 2, 1, 6, 5, 13, 14, 37, 44, 101, 134, 298, 431, 883, 1361, 2736, 4405, 8574, 14334, 27465, 47146, 89270, 156360, 293840, 522913, 978447, 1761907, 3288605, 5977863, 11148652, 20414058, 38071898, 70125402, 130880047

Offset: 0

John Tromp, Feb 20 2006

nonn

			a(8) = 2 because lambda x.lambda y.lambda z.z and lambda x.(x x) are the only two closed lambda terms of size 8.

K. Grygiel and P. Lescanne, Counting terms in the binary lambda calculus, arXiv preprint arXiv:1401.0379 [cs.LO], 2014.
Katarzyna Grygiel and Pierre Lescanne, Counting and Generating Terms in the Binary Lambda Calculus (Extended version), HAL Id: ensl-01229794, 2015.
John Tromp, John's Lambda Calculus and Combinatory Logic Playground
John Tromp, Binary Lambda Calculus and Combinatory Logic
John Tromp, More efficient Haskell program

Cf. A114851, A195691.

a114852 = closed 0 where
  closed k n = if n<2 then 0 else
    (if n-2

A114852T := proc(k,n)
    option remember;
    local a;
    if n = 0 or n = 1 then
        0;
    else
        a := procname(k+1,n-2) ;
        if k > n-2 then
            a := a+1 ;
        fi ;
        a := a+add(procname(k,i)*procname(k,n-i-2),i=0..n-2) ;
    end if;
end proc:
A114852 := proc(n)
    A114852T(0,n) ;
end proc: # R. J. Mathar, Feb 28 2015

S[, 0] = 0; S[, 1] = 0; S[m_, n_] := S[m, n] = Boole[m >= n-1] + S[m+1, n-2] + Sum[S[m, k] S[m, n-k-2], {k, 0, n-2}];
a[n_] := S[0, n];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, May 23 2017 *)

a(n) = N(0,n) with
  N(k,0) = N(k,1) = 0
  N(k,n+2) = (if k>n then 1 else 0) +
             N(k+1,n) +
             Sum_{i=0..n} N(k,i) * N(k,n-i)

A195691 The number of closed normal form lambda calculus terms of size n, where size(lambda x.M)=2+size(M), size(M N)=2+size(M)+size(N), and size(V)=1+i for a variable V bound by the i-th enclosing lambda (corresponding to a binary encoding).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 1, 1, 2, 1, 4, 4, 8, 7, 18, 23, 42, 50, 105, 153, 271, 385, 721, 1135, 1992, 3112, 5535, 9105, 15916, 26219, 45815, 77334, 135029, 229189, 399498, 685710, 1198828, 2070207, 3619677, 6286268, 11024475, 19241836, 33795365, 59197968, 104234931

Offset: 0

John Tromp, Sep 22 2011

nonn

			This sequence first differs from A114852 at n=10, where it excludes the two reducible terms (lambda x.x)(lambda x.x) and lambda x.(lambda x.x)x, so normal 10 = (closed 10)-2 = 6-2 = 4.

Wikipedia, Binary lambda calculus
John Tromp, A195691.hs

Cf. A114851, A114852.

Cf. A224345 for another way of counting normal forms in lambda-calculus.

a195691 = normal True 0 where
  normal qLam k n = if n<2 then 0 else
    (if n-2

A[, , 0] = A[, , 1] = 0; A[q_, k_, n_] := A[q, k, n] = Boole[k > n-2] + q*A[1, k+1, n-2] + Sum[A[0, k, i]*A[1, k, n-i-2], {i, 0, n-2}];
a[n_] := A[1, 0, n];
Table[a[n], {n, 0, 44}] (* Jean-François Alcover, May 23 2017 *)

a(n) = N(1,0,n) with
  N(q,k,0) = N(q,k,1) = 0
  N(q,k,n+2) = (if k>n then 1 else 0) +
               q * N(1,k+1,n) +
               Sum_{i=0..n} N(0,k,i) * N(1,k,n-i)

A236393 Number of typable lambda terms of size n with size 0 for the variables.

Original entry on oeis.org

0, 0, 1, 1, 2, 2, 3, 5, 8, 13, 22, 36, 58, 103, 177, 307, 535, 949, 1645, 2936, 5207, 9330, 16613, 29921, 53588, 96808, 174443, 316267, 572092, 1040596, 1888505, 3441755, 6268500, 11449522, 20902152, 38256759, 70004696, 128336318, 235302612, 432050796, 793513690, 1459062947, 2683714350

Offset: 0

N. J. A. Sloane, Jan 27 2014

nonn

For definition see Appendix A of Grygiel and Lescanne, arXiv 2014.

Katarzyna Grygiel, Pierre Lescanne. Counting and Generating Terms in the Binary Lambda Calculus (Extended version). 2015.

Katarzyna Grygiel, Pierre Lescanne, Counting and generating lambda terms, arXiv:1210.2610 [cs.LO], 2012.
Katarzyna Grygiel, Pierre Lescanne, Counting Terms in the Binary Lambda Calculus, arXiv:1401.0379 [cs.LO], 2014.
Pierre Lescanne, An exercise on streams: convergence acceleration, arXiv preprint arXiv:1312.4917 [cs.NA], 2013.
P. Lescanne, Boltzmann samplers for random generation of lambda terms, arXiv preprint arXiv:1404.3875 [cs.DS], 2014.

Cf. A114851, A114852, A236405.

Name clarified by Pierre Lescanne, Jul 13 2016

A258973 The number of plain lambda terms presented by de Bruijn indices, see Bendkowski et al., where zeros have no weight.

Original entry on oeis.org

1, 3, 10, 40, 181, 884, 4539, 24142, 131821, 734577, 4160626, 23881695, 138610418, 812104884, 4796598619, 28529555072, 170733683579, 1027293807083, 6211002743144, 37713907549066, 229894166951757, 1406310771154682, 8630254073158599, 53117142215866687, 327800429456036588

Offset: 0

Kellen Myers, Jun 15 2015

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, and Marek Zaionc, Combinatorics of λ-terms: a natural approach, arXiv:1609.08106 [cs.LO], 2016.
Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, and Marek Zaionc, A Natural Counting of Lambda Terms, arXiv preprint arXiv:1506.02367 [cs.LO], 2015.
Maciej Bendkowski and Pierre Lescanne, On the enumeration of closures and environments with an application to random generation, Logical Methods in Computer Science (2019) Vol. 15, No. 4, 3:1-3:21.
K. Grygiel and P. Lescanne, A natural counting of lambda terms, Preprint 2015.

Cf. A086616, A105633, A114851, A360102.

a:= proc(n) option remember; `if`(n<4, [1, 3, 10, 40][n+1],
      ((8*n-3)*a(n-1)-(10*n-13)*a(n-2)
     +(4*n-11)*a(n-3)-(n-4)*a(n-4))/(n+1))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 30 2015
a := n -> add(hypergeom([(i+1)/2, i/2+1, i-n+1], [1, 2], -4), i=0..n-1):
seq(simplify(a(n)), n=0..25); # Peter Luschny, May 03 2018

a[n_] := a[n] = If[n<4, {1, 3, 10, 40}[[n+1]], ((8*n-3)*a[n-1] - (10*n-13)*a[n-2] + (4*n-11)*a[n-3] - (n-4)*a[n-4])/(n+1)]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jul 22 2015, after Alois P. Heinz *)

a(n):=sum(sum((binomial(k+i-1,k-1)*binomial(2*k+i-2,k+i-1)*binomial(n-i-1,n-k-i))/k,k,1,n-i),i,0,n); /* Vladimir Kruchinin, May 03 2018 */

lista(nn) = {z = y + O(y^nn); Vec(((1-z)^2 - sqrt((1-z)^4-4*z*(1-z))) / (2*z*(1-z)));} \\ Michel Marcus, Jun 30 2015

G.f. G(z) satisfies z*G(z)^2 - (1-z)*G(z) + 1/(1-z) = 0 (see Bendkowski link Appendix B, p. 23). - Michel Marcus, Jun 30 2015
a(n) ~ 3^(n+1/2) * sqrt(43/(2*((43*(3397 - 261*sqrt(129)))^(1/3) + (43*(3397 + 261*sqrt(129)))^(1/3) - 86)*Pi)) / (3 - (2*6^(2/3)) / (sqrt(129)-9)^(1/3) + (6*(sqrt(129)-9))^(1/3))^n / (2*n^(3/2)). - Vaclav Kotesovec, Jul 01 2015
a(n) = 1 + a(n-1) + Sum_{i=0..n-1} a(i)*a(n-1-i). - Vladimir Kruchinin, May 03 2018
a(n) = Sum_{i=0..n} Sum_{k=1..n-i} binomial(k+i-1,k-1)*binomial(2*k+i-2,k+i-1)*binomial(n-i-1,n-k-i)/k. - Vladimir Kruchinin, May 03 2018
a(n) = Sum_{i=0..n-1} hypergeom([(i+1)/2, i/2+1, i-n+1], [1, 2], -4). - Peter Luschny, May 03 2018
From Peter Bala, Sep 02 2024: (Start)
a(n) = Sum_{k = 0..n} 1/(k + 1) * binomial(2*k, k)*binomial(n+2*k+1, 3*k+1).
Partial sums of A360102. Cf. A086616.
a(n) = (n + 1)*hypergeom([1/2, -n, (n+2)/2, (n+3)/2], [2, 2/3, 4/3], -16/27).
P-recursive: (n + 1)*a(n) = (8*n - 3)*a(n-1) - (10*n - 13)*a(n-2) + (4*n - 11)*a(n-3) - (n - 4)*a(n-4) with a(0) = 1, a(1) = 3, a(2) = 10 and a(3) = 40.
G.f. A(x) = 1/(1 - x)^2 * c(x/(1-x)^3) = (1 - x - sqrt((1 - 7*x + 3*x^2 - x^3)/(1 - x)))/(2*x), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. (End)

More terms from Michel Marcus, Jun 30 2015

A236405 Number of closed typable lambda terms of size n with size 0 for the variables.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 5, 4, 9, 13, 23, 29, 67, 94, 179, 285, 503, 795, 1503, 2469, 4457, 7624, 13475, 23027, 41437, 72165, 128905, 227510, 405301, 715078, 1280127, 2279393, 4086591, 7316698, 13139958, 23551957, 42383667, 76278547, 137609116, 248447221, 449201368, 812315229, 1470997501

Offset: 0

N. J. A. Sloane, Jan 31 2014

nonn

For definition see Appendix A of Grygiel and Lescanne, arXiv 2014.

Katarzyna Grygiel, Pierre Lescanne. Counting and Generating Terms in the Binary Lambda Calculus (Extended version). 2015.

K. Grygiel, P. Lescanne, Counting terms in the binary lambda calculus, arXiv preprint arXiv:1401.0379 [cs.LO], 2014.

Cf. A114851, A114852, A236393.

Name clarified by Pierre Lescanne, Jul 13 2016

cp's OEIS Frontend

A114852 The number of closed lambda calculus terms of size n, where size(lambda x.M)=2+size(M), size(M N)=2+size(M)+size(N), and size(V)=1+i for a variable V bound by the i-th enclosing lambda (corresponding to a binary encoding).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A195691 The number of closed normal form lambda calculus terms of size n, where size(lambda x.M)=2+size(M), size(M N)=2+size(M)+size(N), and size(V)=1+i for a variable V bound by the i-th enclosing lambda (corresponding to a binary encoding).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A236393 Number of typable lambda terms of size n with size 0 for the variables.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A258973 The number of plain lambda terms presented by de Bruijn indices, see Bendkowski et al., where zeros have no weight.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A236405 Number of closed typable lambda terms of size n with size 0 for the variables.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions