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!)
A198518 G.f. satisfies: A(x) = exp( Sum_{n>=1} A(x^n)/(1+x^n) * x^n/n  ). 7
1, 1, 1, 2, 3, 5, 9, 16, 29, 54, 102, 194, 375, 730, 1434, 2837, 5650, 11311, 22767, 46023, 93422, 190322, 389037, 797613, 1639878, 3380099, 6983484, 14459570, 29999618, 62357426, 129843590, 270807835, 565674584, 1183301266, 2478624060, 5198504694, 10916110768, 22948299899 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

For n>=1, a(n) is the number of rooted trees (see A000081) with n non-root nodes where non-root nodes cannot have out-degree 1, see the note by David Callan and the example. Imposing the condition also for the root node gives A001678. - Joerg Arndt, Jun 28 2014

Compare definition to G(x) = exp( Sum_{n>=1} G(x^n)*x^n/n ), where G(x) is the g.f. of A000081, the number of rooted trees with n nodes.

Number of forests of lone-child-avoiding rooted trees with n unlabeled vertices. - Gus Wiseman, Feb 03 2020

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

David Callan, Rooted trees with no out-degree = 1, (7-July-2014).

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

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

FORMULA

Euler transform of coefficients in A(x)/(1+x), where g.f. A(x) = Sum_{n>=0} a(n)*x^n.

a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711..., c = 1.3437262442171062526771597... . - Vaclav Kotesovec, Sep 03 2014

a(n) = A001678(n + 1) + A001678(n + 2). - Gus Wiseman, Jan 22 2020

Euler transform of A001678(n + 1). - Gus Wiseman, Feb 03 2020

EXAMPLE

G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 9*x^6 + 16*x^7 + 29*x^8 +...

where

log(A(x)) = A(x)/(1+x)*x + A(x^2)/(1+x^2)*x^2/2 + A(x^3)/(1+x^3)*x^3/3 +...

The coefficients in A(x)/(1+x) begin:

[1, 0, 1, 1, 2, 3, 6, 10, 19, 35, 67, 127, 248, 482, 952, 1885, 3765, ...]

(this is, up to offset, A001678),

from which g.f. A(x) may be generated by the Euler transform:

A(x) = 1/((1-x)^1*(1-x^2)^0*(1-x^3)^1*(1-x^4)^1*(1-x^5)^2*(1-x^6)^3*(1-x^7)^6*(1-x^8)^10*(1-x^9)^19*(1-x^10)^35*...).

From Joerg Arndt, Jun 28 2014: (Start)

The a(6) = 9 rooted trees with 6 non-root nodes as described in the comment are:

:           level sequence       out-degrees (dots for zeros)

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

:  O--o--o--o

:        .--o

:        .--o

:     .--o

:

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

:  O--o--o--o

:        .--o

:     .--o

:     .--o

:

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

:  O--o--o--o

:        .--o

:     .--o

:  .--o

:

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

:  O--o--o

:     .--o

:     .--o

:     .--o

:     .--o

:

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

:  O--o--o

:     .--o

:     .--o

:     .--o

:  .--o

:

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

:  O--o--o

:     .--o

:     .--o

:  .--o

:  .--o

:

:     7:  [ 0 1 2 2 1 2 2 ]    [ 2 2 . . 2 . . ]

:  O--o--o

:     .--o

:  .--o--o

:     .--o

:

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

:  O--o--o

:     .--o

:  .--o

:  .--o

:  .--o

:

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

:  O--o

:  .--o

:  .--o

:  .--o

:  .--o

:  .--o

(End)

From Gus Wiseman, Jan 22 2020: (Start)

The a(0) = 1 through a(6) = 9 rooted trees with n + 1 nodes where non-root vertices cannot have out-degree 1:

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

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

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

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

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

                                            ((o(ooo)))

                                            ((oo)(oo))

                                            ((oo(oo)))

                                            (o(o(oo)))

(End)

MAPLE

with(numtheory):

b:= proc(n) b(n):= `if`(n=0, 1, a(n)-b(n-1)) end:

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

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

    end:

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

MATHEMATICA

b[n_] := b[n] = If[n==0, 1, a[n] - b[n-1]];

a[n_] := a[n] = If[n==0, 1, Sum[Sum[d*b[d-1], {d, Divisors[j]}]*a[n-j], {j, 1, n}]/n];

Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 21 2017, after Alois P. Heinz *)

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

Table[Length[Select[urt[n], FreeQ[Z@@#, {_}]&]], {n, 10}] (* Gus Wiseman, Jan 22 2020 *)

PROG

(PARI) {a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n, subst(A/(1+x), x, x^m+x*O(x^n))*x^m/m))); polcoeff(A, n)}

CROSSREFS

Cf. A052855, A246403.

The labeled version is A254382.

Unlabeled rooted trees are A000081.

Lone-child-avoiding rooted trees are A001678(n+1).

Topologically series-reduced rooted trees are A001679.

Labeled lone-child-avoiding rooted trees are A060356.

Cf. A000669, A004111, A108919, A291636, A330951, A331488, A331934.

Sequence in context: A000049 A000050 A050253 * A182558 A298204 A265581

Adjacent sequences:  A198515 A198516 A198517 * A198519 A198520 A198521

KEYWORD

nonn

AUTHOR

Paul D. Hanna, Oct 26 2011

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 August 4 09:03 EDT 2020. Contains 336201 sequences. (Running on oeis4.)