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
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.
FORMULA
G.f.: A(x) satisfies A(x) = (x^2/(1+x))*exp( Sum_{k>=1} 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.1924225474701550354144525345664845514828912790855223729854471406053655209... - Vaclav Kotesovec, Jun 26 2014
a(n) = Sum_{i=2..n-2} A106179(i, n-1-i) for n >= 3. - Andrew Howroyd, Mar 29 2021
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
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.
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Additional comments from Michael Somos, Jun 05 2002
STATUS
approved