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

Author

Gus Wiseman, Feb 03 2020

Keywords

• nonn

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.

Examples

			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)))
		

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.

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.

Programs

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}]

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

Formula

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

Extensions

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