login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001678 Number of series-reduced planted trees with n nodes.
(Formerly M0768 N0293)
87
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; refs; listen; history; text; internal format)
OFFSET

0,7

COMMENTS

The initial term is 0 by convention, though a good case can be made that it should be 1 instead.

Series-reduced trees contain no node with valency 2; see A000014 for the unrooted series-reduced trees. [Joerg Arndt, Mar 03 2015]

For n>=2, a(n+1) is the number of unordered rooted trees (see A000081) with n nodes where nodes cannot have out-degree 1, see example. Imposing the condition only at non-root nodes gives A198518. - Joerg Arndt, Jun 28 2014

For n>=3, a(n+1) is the number of unordered rooted trees with n nodes where all limbs are of length >= 2. Limbs are the paths from the leafs (towards the root) to the nearest branching point (with the root considered to be a branching point). - Joerg Arndt, Mar 03 2015

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.

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 and Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 501 terms from Christian G. Bower)

David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014)

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.

F. Harary, R. W. Robinson and A. J. Schwenk, Corrigenda: Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A 41 (1986), p. 325.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 404

Eric Weisstein's World of Mathematics, Series-reduced tree.

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. A(x) = Sum_{n>=2} a(n) * x^n = x^2 / ((1 + x) * Product_{k>0} (1 - x^k)^a(k+1)). - Michael Somos, Oct 06 2003

a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.189461985660850563... and c = 0.192422547470155036... . - Vaclav Kotesovec, Jun 26 2014

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

-----------------------------------------------------------------------------

G.f. = x^2 + x^4 + x^5 + 2*x^6 + 3*x^7 + 6*x^8 + 10*x^9 + 19*x^10 + ...

From Joerg Arndt, Jun 28 2014: (Start)

The a(8) = 6 rooted trees with 7 nodes as described in the comment are:

:           level sequence       out-degrees (dots for zeros)

:     1:  [ 0 1 2 3 3 2 1 ]    [ 2 2 2 . . . . ]

:  O--o--o--o

:        .--o

:     .--o

:  .--o

:

:     2:  [ 0 1 2 2 2 2 1 ]    [ 2 4 . . . . . ]

:  O--o--o

:     .--o

:     .--o

:     .--o

:  .--o

:

:     3:  [ 0 1 2 2 2 1 1 ]    [ 3 3 . . . . . ]

:  O--o--o

:     .--o

:     .--o

:  .--o

:  .--o

:

:     4:  [ 0 1 2 2 1 2 2 ]    [ 2 2 . . 2 . . ]

:  O--o--o

:     .--o

:  .--o--o

:     .--o

:

:     5:  [ 0 1 2 2 1 1 1 ]    [ 4 2 . . . . . ]

:  O--o--o

:     .--o

:  .--o

:  .--o

:  .--o

:

:     6:  [ 0 1 1 1 1 1 1 ]    [ 6 . . . . . . ]

:  O--o

:  .--o

:  .--o

:  .--o

:  .--o

:  .--o

:

(End)

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); # Ulrich Schimke (ulrschimke(AT)aol.com)

# second Maple program:

with(numtheory):

b:= proc(n) option remember; `if`(n=0, 1, add(add(

       d*a(d+1), d=divisors(j))*b(n-j), j=1..n)/n)

    end:

a:= proc(n) option remember; `if`(n<2, 0,

      `if`(n=2, 1, b(n-2)-a(n-1)))

    end:

seq(a(n), n=0..50);  # Alois P. Heinz, Jul 02 2014

MATHEMATICA

b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*a[d+1], {d, Divisors[j]}]*b[n-j], {j, 1, n}]/n]; a[n_] := a[n] = If[n < 2, 0, If[n == 2, 1, b[n-2] - a[n-1]]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Sep 24 2014, after Alois P. Heinz *)

terms = 38; A[_] = 0; Do[A[x_] = (x^2/(1+x))*Exp[Sum[A[x^k]/(k*x^k), {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms}]; CoefficientList[A[x], x] (* Jean-François Alcover, Jan 12 2018 *)

PROG

(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 Somos, 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, A246403.

Sequence in context: A054178 A005833 A247162 * A113292 A050291 A214002

Adjacent sequences:  A001675 A001676 A001677 * A001679 A001680 A001681

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Additional comments from Michael Somos, Jun 05 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 15 04:00 EST 2018. Contains 317225 sequences. (Running on oeis4.)