login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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)
129
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

A rooted tree is lone-child-avoiding if no vertex has exactly one child, and topologically series-reduced if no vertex has degree 2. This sequence counts unlabeled lone-child-avoiding rooted trees with n - 1 vertices. Topologically series-reduced rooted trees are counted by A001679, which is essentially the same as A059123. - Gus Wiseman, Jan 20 2020

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.

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

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)

From Gus Wiseman, Jan 20 2020: (Start)

The a(2) = 1 through a(9) = 10 unlabeled lone-child-avoiding rooted trees with n - 1 nodes (empty n = 3 column shown as dot) are:

  o   .   (oo)  (ooo)  (oooo)   (ooooo)   (oooooo)    (ooooooo)

                       (o(oo))  (o(ooo))  (o(oooo))   (o(ooooo))

                                (oo(oo))  (oo(ooo))   (oo(oooo))

                                          (ooo(oo))   (ooo(ooo))

                                          ((oo)(oo))  (oooo(oo))

                                          (o(o(oo)))  ((oo)(ooo))

                                                      (o(o(ooo)))

                                                      (o(oo)(oo))

                                                      (o(oo(oo)))

                                                      (oo(o(oo)))

(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 *)

urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]], {ptn, IntegerPartitions[n-1]}];

Table[If[n<=1, 0, Length[Select[urt[n-1], FreeQ[#, {_}]&]]], {n, 0, 10}] (* Gus Wiseman, Jan 20 2020 *)

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

Unlabeled rooted trees are counted by A000081.

Topologically series-reduced rooted trees are counted by A001679.

Labeled lone-child-avoiding rooted trees are counted by A060356.

Labeled lone-child-avoiding unrooted trees are counted by A108919.

Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.

Singleton-reduced rooted trees are counted by A330951.

Cf. A000669, A004111, A198518, A254382, A331488, A331578.

Sequence in context: A054178 A005833 A247162 * A113292 A050291 A324739

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 11:26 EDT 2020. Contains 337879 sequences. (Running on oeis4.)