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

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

Author

Kellen Myers, Jun 15 2015

Keywords

• nonn
• easy

Links

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

Crossrefs

Cf. A086616, A105633, A114851, A360102.

Programs

Maple

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

Mathematica

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 *)

Maxima

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 */

PARI

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

Formula

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)

Extensions

More terms from Michel Marcus, Jun 30 2015