|
%I M4565 #84 Feb 05 2024 08:24:40
%S 1,1,8,92,1240,18278,285384,4638348,77652024,1329890705,23190029720,
%T 410333440536,7349042994488,132969010888280,2426870706415800,
%U 44627576949364104,826044435409399800,15378186970730687400
%N Number of 8-ary trees with n vertices.
%C Shifts left when convolved three times.
%C From _Wolfdieter Lang_, Sep 14 2007: (Start)
%C a(n), n >= 1, enumerates octic (8-ary) trees (rooted, ordered, incomplete) with n vertices (including the root).
%C Pfaff-Fuss-Catalan sequence C^{m}_n for m = 8. See the Graham et al. reference, p. 347. eq. 7.66. See also the Pólya-Szegő reference.
%C Also 8-Raney sequence. See the Graham et al. reference, p. 346-7.
%C (End)
%C This is instance k = 8 of the generalized Catalan family {C(k, n)}_{n>=0} given in a comment of A130564. - _Wolfdieter Lang_, Feb 05 2024
%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 200, 347.
%D G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, Heidelberg, New York, 2 vols., 1972, Vol. 1, problem 211, p. 146 with solution on p. 348.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Harvey P. Dale, <a href="/A007556/b007556.txt">Table of n, a(n) for n = 0..750</a>
%H M. Bernstein and N. J. A. Sloane, <a href="https://arxiv.org/abs/math/0205301">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv:math/0205301 [math.CO], 2002]
%H M. Bernstein and N. J. A. Sloane, <a href="/A003633/a003633_1.pdf">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
%H Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner, <a href="https://arxiv.org/abs/2204.14023">Enumeration of Generalized Dyck Paths Based on the Height of Down-Steps Modulo k</a>, arXiv:2204.14023 [math.CO], 2022.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=290">Encyclopedia of Combinatorial Structures 290</a>
%H Lajos Takács, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/18_1_1.pdf">Enumeration of rooted trees and forests</a>, Math. Scientist 18 (1993), 1-10, esp. Eq. (5).
%F a(n) = binomial(8*n, n)/(7*n+1) = binomial(8*n+1, n)/(8*n+1) = A062993(n+6,6).
%F O.g.f.: A(x) = 1 + x*A(x)^8 = 1/(1-x*A(x)^7).
%F a(0) = 1; a(n) = Sum_{i1 + i2 + .. i8 = n - 1} a(i1)*a(i2)*...*a(i8) for n >= 1. - _Robert FERREOL_, Apr 01 2015
%F a(n) = binomial(8*n, n - 1)/n for n >= 1, a(0) = 1 (from the Lagrange series of the o.g.f. A(x) with its above given implicit equation).
%F From _Karol A. Penson_, Mar 26 2015: (Start)
%F In Maple notation,
%F e.g.f.: hypergeom([1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8], [2/7, 3/7, 4/7, 5/7, 6/7, 1, 8/7],(2^24/7^7)*z);
%F o.g.f.: hypergeom([1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8], [2/7, 3/7, 4/7, 5/7, 6/7, 8/7],(2^24/7^7)*z);
%F a(n) are special values of Jacobi polynomials, in Maple notation:
%F a(n) = JacobiP(n - 1, 7*n + 1, -n, 1)/n, n = 1, 2, ...
%F (End)
%F From _Peter Bala_, Oct 14 2015: (Start)
%F A(x)^2 is o.g.f. for A234461; A(x)^3 is o.g.f. for A234462;
%F A(x)^4 is o.g.f. for A234463; A(x)^5 is o.g.f. for A234464;
%F A(x)^6 is o.g.f. for A234465; A(x)^7 is o.g.f. for A234466;
%F A(x)^9 is o.g.f. for A234467. (End)
%F a(n) ~ 2^(24*n + 1)/(sqrt(Pi)*7^(7*n + 3/2)*n^(3/2)). - _Ilya Gutkovskiy_, Feb 07 2017
%F D-finite with recurrence: 7*n*(7*n-3)*(7*n+1)*(7*n-2)*(7*n-5)*(7*n-1)*(7*n-4)*a(n) -128*(8*n-5)*(4*n-1)*(8*n-7)*(2*n-1)*(8*n-1)*(4*n-3)*(8*n-3)*a(n-1)=0. - _R. J. Mathar_, Feb 20 2020
%e There are a(2) = 8 octic trees (vertex degree less than or equal to 8 and 8 possible branchings) with 2 vertices (one of them the root). Adding one more branch (one more vertex) to these 8 trees yields 8*8 + binomial(8, 2) = 92 = a(3) such trees.
%p seq(binomial(8*n+1,n)/(8*n+1),n=0..30); # _Robert FERREOL_, Apr 01 2015
%p n:=30: G:=series(RootOf(g = 1+x*g^8, g),x=0,n+1): seq(coeff(G,x,k),k=0..n); # _Robert FERREOL_, Apr 01 2015
%t Table[Binomial[8n, n]/(7n + 1), {n, 0, 20}] (* _Harvey P. Dale_, Dec 24 2012 *)
%o (Haskell)
%o a007556 0 = 1
%o a007556 n = a007318' (8 * n) (n - 1) `div` n
%o -- _Reinhard Zumkeller_, Jul 30 2013
%o (Magma) [Binomial(8*n, n)/(7*n+1): n in [0..20]]; // _Vincenzo Librandi_, Apr 02 2015
%o (PARI) vector(100, n, n--; binomial(8*n, n)/(7*n+1)) \\ _Altug Alkan_, Oct 14 2015
%Y Seventh column of triangle A062993.
%Y Cf. A007318, A234461, A234462, A234463, A234464, A234465, A234466, A234467.
%Y Cf. A130564.
%K nonn,nice,eigen
%O 0,3
%A _N. J. A. Sloane_
|
