A331933 Number of semi-lone-child-avoiding rooted trees with at most one distinct non-leaf branch directly under any vertex.

1, 1, 1, 2, 4, 6, 12, 18, 33, 52, 90, 142, 242, 384, 639, 1028, 1688, 2716, 4445, 7161, 11665, 18839, 30595, 49434, 80199, 129637, 210079, 339750, 550228, 889978, 1440909, 2330887, 3772845, 6103823, 9878357, 15982196, 25863454, 41845650, 67713550, 109559443

Offset

1,4

Comments

A rooted tree is semi-lone-child-avoiding if there are no vertices with exactly one child unless the child is an endpoint/leaf.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1000

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.

Gus Wiseman, The a(11) = 90 semi-lone-child-avoiding rooted trees with at most one distinct non-leaf branch directly under any vertex.

Formula

a(n) = 1 + Sum_{i=2..n-2} floor((n-1)/i)*a(i). - Andrew Howroyd, Feb 09 2020

Example

The a(1) = 1 through a(8) = 18 trees:
  o  (o)  (oo)  (ooo)   (oooo)    (ooooo)    (oooooo)
                (o(o))  (o(oo))   (o(ooo))   (o(oooo))
                        (oo(o))   (oo(oo))   (oo(ooo))
                        ((o)(o))  (ooo(o))   (ooo(oo))
                                  (o(o)(o))  (oooo(o))
                                  (o(o(o)))  ((oo)(oo))
                                             (o(o(oo)))
                                             (o(oo(o)))
                                             (oo(o)(o))
                                             (oo(o(o)))
                                             ((o)(o)(o))
                                             (o((o)(o)))

Mathematica

sseo[n_]:=Switch[n, 1, {{}}, 2, {{{}}}, _, Join@@Function[c, Select[Union[Sort/@Tuples[sseo/@c]], Length[Union[DeleteCases[#, {}]]]<=1&]]/@Rest[IntegerPartitions[n-1]]];
Table[Length[sseo[n]], {n, 10}]

Prog

(PARI) seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sum(i=2, n-2, ((n-1)\i)*v[i])); v} \\ Andrew Howroyd, Feb 09 2020

Crossrefs

Not requiring lone-child-avoidance gives A320222.

The non-semi version is A320268.

Matula-Goebel numbers of these trees are A331936.

Achiral trees are A003238.

Semi-identity trees are A306200.

Numbers S with at most one distinct prime index in S are A331912.

Semi-lone-child-avoiding rooted trees are A331934.

Cf. A000081, A001678, A004111, A050381, A214577, A291636, A320230, A320269, A331784, A331872, A331914, A331935, A331966.

Sequence in context: A259941 A007436 A052847 * A052823 A063516 A306315

Adjacent sequences: A331930 A331931 A331932 * A331934 A331935 A331936

Keyword

nonn

Author

Gus Wiseman, Feb 03 2020

Extensions

Terms a(31) and beyond from Andrew Howroyd, Feb 09 2020

Status

approved