A324979 Number of rooted trees with n vertices that are not identity trees but whose non-leaf terminal subtrees are all different.

0, 0, 1, 2, 5, 12, 29, 70, 168, 402, 959, 2284, 5434, 12923, 30727, 73055, 173678, 412830

Offset

1,4

Comments

An unlabeled rooted tree is an identity tree if there are no repeated branches directly under the same root.

Links

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

Example

The a(3) = 1 through a(6) = 12 trees:
  (oo)  (ooo)   (oooo)    (ooooo)
        ((oo))  ((ooo))   ((oooo))
                (o(oo))   (o(ooo))
                (oo(o))   (oo(oo))
                (((oo)))  (ooo(o))
                          (((ooo)))
                          ((o)(oo))
                          ((o(oo)))
                          ((oo(o)))
                          (o((oo)))
                          (oo((o)))
                          ((((oo))))

Mathematica

rits[n_]:=Join@@Table[Union[Sort/@Tuples[rits/@ptn]], {ptn, IntegerPartitions[n-1]}];
Table[Length[Select[rits[n], And[UnsameQ@@Cases[#, {__}, {0, Infinity}], !And@@Cases[mgtree[#], q:{__}:>UnsameQ@@q, {0, Infinity}]]&]], {n, 10}]

Crossrefs

The Matula-Goebel numbers of these trees are given by A324978.

Cf. A000081, A004111, A290689, A317713, A324850, A324922, A324923, A324924, A324931, A324935, A324936, A324970, A324971.

Sequence in context: A067687 A291235 A130009 * A048624 A176981 A215936

Adjacent sequences: A324976 A324977 A324978 * A324980 A324981 A324982

Keyword

nonn,more

Author

Gus Wiseman, Mar 21 2019

Status

approved