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!)
A331488 Number of unlabeled lone-child-avoiding rooted trees with n vertices and more than two branches (of the root). 9
0, 0, 0, 1, 1, 2, 3, 6, 10, 20, 36, 70, 134, 263, 513, 1022, 2030, 4076, 8203, 16614, 33738, 68833, 140796, 288989, 594621, 1226781, 2536532, 5256303, 10913196, 22700682, 47299699, 98714362, 206323140, 431847121, 905074333, 1899247187, 3990145833, 8392281473 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

COMMENTS

Also the number of lone-child-avoiding rooted trees with n vertices and more than two branches.

LINKS

Table of n, a(n) for n=1..38.

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

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

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

FORMULA

For n > 1, a(n) = A001679(n) - A001678(n).

EXAMPLE

The a(4) = 1 through a(9) = 10 trees:

  (ooo)  (oooo)  (ooooo)   (oooooo)   (ooooooo)    (oooooooo)

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

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

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

                                      (o(oo)(oo))  (ooooo(oo))

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

                                                   (oo(o(ooo)))

                                                   (oo(oo)(oo))

                                                   (oo(oo(oo)))

                                                   (ooo(o(oo)))

MATHEMATICA

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

Table[Length[Select[urt[n], Length[#]>2&&FreeQ[#, {_}]&]], {n, 10}]

CROSSREFS

The not necessarily lone-child-avoiding version is A331233.

The Matula-Goebel numbers of these trees are listed by A331490.

A000081 counts unlabeled rooted trees.

A001678 counts lone-child-avoiding rooted trees.

A001679 counts topologically series-reduced rooted trees.

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

A331489 lists Matula-Goebel numbers of series-reduced rooted trees.

Cf. A000014, A000669, A004250, A007097, A007821, A033942, A060313, A060356, A061775, A109082, A109129, A196050, A276625, A330943.

Sequence in context: A047131 A231331 A008927 * A052525 A006606 A120421

Adjacent sequences:  A331485 A331486 A331487 * A331489 A331490 A331491

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jan 20 2020

EXTENSIONS

a(37)-a(38) from Jinyuan Wang, Jun 26 2020

Terminology corrected (lone-child-avoiding, not series-reduced) by Gus Wiseman, May 10 2021

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 June 17 19:57 EDT 2021. Contains 345085 sequences. (Running on oeis4.)