A331934 Number of semi-lone-child-avoiding rooted trees with n unlabeled vertices.

1, 1, 1, 2, 4, 7, 15, 29, 62, 129, 279, 602, 1326, 2928, 6544, 14692, 33233, 75512, 172506, 395633, 911108, 2105261, 4880535, 11346694, 26451357, 61813588, 144781303, 339820852, 799168292, 1882845298, 4443543279, 10503486112, 24864797324, 58944602767, 139918663784

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(7) = 15 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)(oo))  (oooo(o))
                                  (o(o)(o))  ((o)(ooo))
                                  (o(o(o)))  ((oo)(oo))
                                             (o(o)(oo))
                                             (o(o(oo)))
                                             (o(oo(o)))
                                             (oo(o)(o))
                                             (oo(o(o)))
                                             ((o)(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.

Crossrefs

The same trees counted by leaves are A050381.

The locally disjoint version is A331872.

Matula-Goebel numbers of these trees are A331935.

Lone-child-avoiding rooted trees are A001678.

Cf. A000081, A000669, A198518, A289501, A291636, A306200, A320268, A330465, A330951, A331873, A331874, A331933, A331966.

Programs

Mathematica

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

PARI

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=[1,1]); for(n=2, n-1, v=concat(v, EulerT(v)[n] - v[n])); v} \\ Andrew Howroyd, Feb 09 2020

Formula

Product_{k > 0} 1/(1 - x^k)^a(k) = A(x) + A(x)/x - x where A(x) = Sum_{k > 0} x^k a(k).

Euler transform is b(1) = 1, b(n > 1) = a(n) + a(n + 1).

Extensions

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