|
Search: id:A001678
|
|
|
| A001678 |
|
Number of series-reduced planted trees with n nodes.
(Formerly M0768 N0293)
|
|
+0
7
|
|
| 0, 0, 1, 0, 1, 1, 2, 3, 6, 10, 19, 35, 67, 127, 248, 482, 952, 1885, 3765, 7546, 15221, 30802, 62620, 127702, 261335, 536278, 1103600, 2276499, 4706985, 9752585, 20247033, 42110393, 87733197, 183074638, 382599946, 800701320, 1677922740, 3520581954
(list; graph; listen)
|
|
|
OFFSET
|
0,7
|
|
|
COMMENT
|
The initial term is 0 by convention, though a good case can be made that it should be 1 instead.
|
|
REFERENCES
|
D. G. Cantor, personal communication.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 525.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62.
F. Harary and E. M. Palmer, Probability that a point of a tree is fixed, Math. Proc. Camb. Phil. Soc. 85 (1979) 407-415.
F. Harary and G. Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.
F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503. Errata: Vol. A 41 (1986), p. 325.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
Christian G. Bower, Table of n, a(n) for n = 0..500
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 404
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees
|
|
FORMULA
|
G.f. A(x) satisfies A(x) = (x^2/(1+x))*exp( sum_{k=1..infinity} A(x^k)/(k*x^k) ) [Harary and E. M. Palmer, 1973, p. 62, Eq. (3.3.8).
G.f. Sum a(n)*x^n = x^2/((1+x)*Product_{k>0}(1-x^k)^a(k+1)). - Michael Somos, Oct 06 2003
|
|
EXAMPLE
|
--------------- Examples (i=internal,e=external): ---------------------------
|.n=2.|..n=4..|..n=5..|...n=6.............|....n=7..........................|
|.....|.......|.......|.............e...e.|................e.e.e......e...e.|
|.....|.e...e.|.e.e.e.|.e.e.e.e...e...i...|.e.e.e.e.e...e....i....e.e...i...|
|..e..|...i...|...i...|....i........i.....|.....i..........i..........i.....|
|..e..|...e...|...e...|....e........e.....|.....e..........e..........e.....|
-----------------------------------------------------------------------------
|
|
MAPLE
|
with (powseries): with (combstruct): n := 30: sys := {B = Prod(C, Z), S = Set(B, 1 <= card), C = Union(Z, S)}: A001678 := 1, 0, 1, seq(count([S, sys, unlabeled], size=i), i=1..n); # from UlrSchimke(AT)aol.com
|
|
PROGRAM
|
(PARI) a(n)=if(n<4, n==2, T(n-2, n-3)) where T(n, k)=if(n<1|k<1, (n==0)&(k>=0), sum(j=1, k, sum(i=1, n\j, T(n-i*j, min(n-i*j, j-1))*binomial(a(j+1)+i-1, i)))) /* Michael SOos Jun 04 2002 */
(PARI) {a(n)=local(A); if(n<3, n==2, A=x/(1-x^2)+O(x^n); for(k=3, n-2, A/=(1-x^k+O(x^n))^polcoeff(A, k)); polcoeff(A, n-1))} /* Michael Somos Oct 06 2003 */
|
|
CROSSREFS
|
Cf. A000014, A007827.
Sequence in context: A000693 A054178 A005833 this_sequence A113292 A050291 A135452
Adjacent sequences: A001675 A001676 A001677 this_sequence A001679 A001680 A001681
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
Additional comments from Michael Somos, Jun 05, 2002.
|
|
|
Search completed in 0.002 seconds
|
