A007556 Number of 8-ary trees with n vertices.

1, 1, 8, 92, 1240, 18278, 285384, 4638348, 77652024, 1329890705, 23190029720, 410333440536, 7349042994488, 132969010888280, 2426870706415800, 44627576949364104, 826044435409399800, 15378186970730687400, 287756293703544823872, 5409093674555090316300

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• eigen

Comments

Shifts left when convolved three times.

From Wolfdieter Lang, Sep 14 2007: (Start)

a(n), n >= 1, enumerates octic (8-ary) trees (rooted, ordered, incomplete) with n vertices (including the root).

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.

Also 8-Raney sequence. See the Graham et al. reference, p. 346-7.

(End)

This is instance k = 8 of the generalized Catalan family {C(k, n)}A130564.%20-%20_Wolfdieter%20Lang">{n>=0} given in a comment of A130564. - _Wolfdieter Lang, Feb 05 2024

Examples

			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.
		

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 200, 347.
• 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.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Harvey P. Dale, Table of n, a(n) for n = 0..750
• M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv:math/0205301 [math.CO], 2002]
• M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
• Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner, Enumeration of Generalized Dyck Paths Based on the Height of Down-Steps Modulo k, arXiv:2204.14023 [math.CO], 2022.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 290
• Lajos Takács, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (5).

Crossrefs

Seventh column of triangle A062993.

Cf. A007318, A234461, A234462, A234463, A234464, A234465, A234466, A234467.

Cf. A130564.

Programs

Haskell

a007556 0 = 1
a007556 n = a007318' (8 * n) (n - 1) `div` n
-- Reinhard Zumkeller, Jul 30 2013

Magma

[Binomial(8*n, n)/(7*n+1): n in [0..20]]; // Vincenzo Librandi, Apr 02 2015

Maple

seq(binomial(8*n+1,n)/(8*n+1),n=0..30); # Robert FERREOL, Apr 01 2015
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

Mathematica

Table[Binomial[8n, n]/(7n + 1), {n, 0, 20}] (* Harvey P. Dale, Dec 24 2012 *)

PARI

vector(100, n, n--; binomial(8*n, n)/(7*n+1)) \\ Altug Alkan, Oct 14 2015

Formula

a(n) = binomial(8*n, n)/(7*n+1) = binomial(8*n+1, n)/(8*n+1) = A062993(n+6,6).

O.g.f.: A(x) = 1 + x*A(x)^8 = 1/(1-x*A(x)^7).

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

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

From Karol A. Penson, Mar 26 2015: (Start)

In Maple notation,

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

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

a(n) are special values of Jacobi polynomials, in Maple notation:

a(n) = JacobiP(n - 1, 7*n + 1, -n, 1)/n, n = 1, 2, ...

(End)

From Peter Bala, Oct 14 2015: (Start)

A(x)^2 is o.g.f. for A234461; A(x)^3 is o.g.f. for A234462;

A(x)^4 is o.g.f. for A234463; A(x)^5 is o.g.f. for A234464;

A(x)^6 is o.g.f. for A234465; A(x)^7 is o.g.f. for A234466;

A(x)^9 is o.g.f. for A234467. (End)

a(n) ~ 2^(24*n + 1)/(sqrt(Pi)*7^(7*n + 3/2)*n^(3/2)). - Ilya Gutkovskiy, Feb 07 2017

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

G.f. A(x) satisfies A(x) = 1/A(-x*A(x)^15). - Seiichi Manyama, Jun 16 2025