A331964 Number of semi-lone-child-avoiding rooted identity trees with n vertices.

1, 1, 0, 1, 0, 1, 1, 2, 2, 4, 6, 10, 16, 27, 44, 74, 123, 209, 353, 602, 1026, 1760, 3019, 5203, 8977, 15538, 26930, 46792, 81415, 141939, 247795, 433307, 758672, 1330219, 2335086, 4104064, 7220937, 12718694, 22424283, 39574443, 69903759, 123584852, 218668323

Offset

1,8

Comments

A rooted tree is semi-lone-child-avoiding if there are no vertices with exactly one child unless that child is an endpoint/leaf. It is an identity tree if the branches of any given vertex are all distinct.

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 semi-lone-child-avoiding rooted identity trees with up to 13 vertices.

Example

The a(9) = 2 through a(12) = 10 semi-lone-child-avoiding rooted identity trees:
  ((o)(o(o(o))))  (o(o)(o(o(o))))   ((o)(o(o)(o(o))))  (o(o)(o(o)(o(o))))
  (o((o)(o(o))))  (o(o(o)(o(o))))   ((o)(o(o(o(o)))))  (o(o)(o(o(o(o)))))
                  (o(o(o(o(o)))))   ((o(o))(o(o(o))))  (o(o(o))(o(o(o))))
                  ((o)((o)(o(o))))  (o((o)(o(o(o)))))  (o(o(o)(o(o(o)))))
                                    (o(o)((o)(o(o))))  (o(o(o(o)(o(o)))))
                                    (o(o((o)(o(o)))))  (o(o(o(o(o(o))))))
                                                       ((o)((o)(o(o(o)))))
                                                       ((o)(o((o)(o(o)))))
                                                       ((o(o))((o)(o(o))))
                                                       (o((o)((o)(o(o)))))

Mathematica

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

Prog

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

Crossrefs

The non-semi version is A000007.

Matula-Goebel numbers of these trees are A331963.

Rooted identity trees are A004111.

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

Cf. A000081, A001678, A050381, A276625, A300660, A306200, A316694, A331872, A331875, A331933, A331935, A331936, A331937, A331966.

Sequence in context: A163733 A198834 A270925 * A084202 A300865 A053637

Adjacent sequences: A331961 A331962 A331963 * A331965 A331966 A331967

Keyword

nonn

Author

Gus Wiseman, Feb 04 2020

Extensions

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

Status

approved