|
%I #47 Jan 15 2020 22:47:26
%S 1,3,10,40,181,884,4539,24142,131821,734577,4160626,23881695,
%T 138610418,812104884,4796598619,28529555072,170733683579,
%U 1027293807083,6211002743144,37713907549066,229894166951757,1406310771154682,8630254073158599,53117142215866687,327800429456036588
%N The number of plain lambda terms presented by de Bruijn indices, see Bendkowski et al. where zeros have no weight.
%H Alois P. Heinz, <a href="/A258973/b258973.txt">Table of n, a(n) for n = 0..1000</a>
%H Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, Marek Zaionc, <a href="http://arxiv.org/abs/1609.08106">Combinatorics of λ-terms: a natural approach</a>, arXiv:1609.08106 [cs.LO], 2016.
%H Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, 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 Maciej Bendkowski, 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 K. Grygiel, 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 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 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 a(n) = 1+a(n-1)+Sum_{i=0..n-1} a(i)*a(n-1-i). - _Vladimir Kruchinin_, May 03 2018
%F 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 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
%p a:= proc(n) option remember; `if`(n<4, [1, 3, 10, 40][n+1],
%p ((8*n-3)*a(n-1)-(10*n-13)*a(n-2)
%p +(4*n-11)*a(n-3)-(n-4)*a(n-4))/(n+1))
%p end:
%p seq(a(n), n=0..25); # _Alois P. Heinz_, Jun 30 2015
%p a := n -> add(hypergeom([(i+1)/2, i/2+1, i-n+1], [1, 2], -4), i=0..n-1):
%p seq(simplify(a(n)), n=0..25); # _Peter Luschny_, May 03 2018
%t 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 (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 (Maxima)
%o 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 Cf. A105633, A114851.
%K nonn
%O 0,2
%A _Kellen Myers_, Jun 15 2015
%E More terms from _Michel Marcus_, Jun 30 2015
|
