cp's OEIS Frontend

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

%I A258973 #59 Sep 05 2024 14:13:38
%S A258973 1,3,10,40,181,884,4539,24142,131821,734577,4160626,23881695,
%T A258973 138610418,812104884,4796598619,28529555072,170733683579,
%U A258973 1027293807083,6211002743144,37713907549066,229894166951757,1406310771154682,8630254073158599,53117142215866687,327800429456036588
%N A258973 The number of plain lambda terms presented by de Bruijn indices, see Bendkowski et al., where zeros have no weight.
%H A258973 Alois P. Heinz, <a href="/A258973/b258973.txt">Table of n, a(n) for n = 0..1000</a>
%H A258973 Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, and Marek Zaionc, <a href="http://arxiv.org/abs/1609.08106">Combinatorics of λ-terms: a natural approach</a>, arXiv:1609.08106 [cs.LO], 2016.
%H A258973 Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, and Marek Zaionc, <a href="http://arxiv.org/abs/1506.02367">A Natural Counting of Lambda Terms</a>, arXiv preprint arXiv:1506.02367 [cs.LO], 2015.
%H A258973 Maciej Bendkowski and Pierre Lescanne, <a href="https://doi.org/10.23638/LMCS-15(4:3)2019">On the enumeration of closures and environments with an application to random generation</a>, Logical Methods in Computer Science (2019) Vol. 15, No. 4, 3:1-3:21.
%H A258973 K. Grygiel and P. Lescanne, <a href="http://perso.ens-lyon.fr/pierre.lescanne/PUBLICATIONS/natural_counting.pdf">A natural counting of lambda terms</a>, Preprint 2015.
%F A258973 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
%F A258973 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
%F A258973 a(n) = 1 + a(n-1) + Sum_{i=0..n-1} a(i)*a(n-1-i). - _Vladimir Kruchinin_, May 03 2018
%F A258973 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
%F A258973 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
%F A258973 From _Peter Bala_, Sep 02 2024: (Start)
%F A258973 a(n) = Sum_{k = 0..n} 1/(k + 1) * binomial(2*k, k)*binomial(n+2*k+1, 3*k+1).
%F A258973 Partial sums of A360102. Cf. A086616.
%F A258973 a(n) = (n + 1)*hypergeom([1/2, -n, (n+2)/2, (n+3)/2], [2, 2/3, 4/3], -16/27).
%F A258973 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.
%F A258973 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)
%p A258973 a:= proc(n) option remember; `if`(n<4, [1, 3, 10, 40][n+1],
%p A258973       ((8*n-3)*a(n-1)-(10*n-13)*a(n-2)
%p A258973      +(4*n-11)*a(n-3)-(n-4)*a(n-4))/(n+1))
%p A258973     end:
%p A258973 seq(a(n), n=0..25);  # _Alois P. Heinz_, Jun 30 2015
%p A258973 a := n -> add(hypergeom([(i+1)/2, i/2+1, i-n+1], [1, 2], -4), i=0..n-1):
%p A258973 seq(simplify(a(n)), n=0..25); # _Peter Luschny_, May 03 2018
%t A258973 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_ *)
%o A258973 (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
%o A258973 (Maxima)
%o A258973 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 */
%Y A258973 Cf. A086616, A105633, A114851, A360102.
%K A258973 nonn,easy
%O A258973 0,2
%A A258973 _Kellen Myers_, Jun 15 2015
%E A258973 More terms from _Michel Marcus_, Jun 30 2015