|
| |
|
|
A007556
|
|
Number of 8-ary trees with n vertices.
(Formerly M4565)
|
|
9
| |
|
|
1, 1, 8, 92, 1240, 18278, 285384, 4638348, 77652024, 1329890705, 23190029720, 410333440536, 7349042994488, 132969010888280, 2426870706415800, 44627576949364104, 826044435409399800, 15378186970730687400
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Shifts left when convolved thrice.
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\'olya-Szeg\"o reference.
Also 8-Raney sequence. See the Graham et al. reference, p. 346-7.
|
|
|
REFERENCES
| R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 200, 347.
G. P\'olya and G. Szeg\"o, 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).
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (5).
|
|
|
LINKS
| M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 290
|
|
|
FORMULA
| C(8n, n)/(7n+1).
O.g.f. A(x)= 1 + x*A(x)^8 = 1/(1-x*A(x)^7).
a(n)=binomial(8*n,n-1)/n, n>=1, a(0)=1. From the Lagrange series of the o.g.f. A(x) with its above given implicit equation.
|
|
|
EXAMPLE
| There are a(2)=8 octic trees (vertex degree <=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.
|
|
|
CROSSREFS
| Seventh column of triangle A062993.
Sequence in context: A133271 A180903 A099142 * A194042 A027395 A113353
Adjacent sequences: A007553 A007554 A007555 * A007557 A007558 A007559
|
|
|
KEYWORD
| nonn,nice,eigen
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Pfaff-Fuss-Catalan, Raney, o.g.f. and 8-ary tree comments from W. Lang, Sep 14 2007.
|
| |
|
|
