A316471 Number of locally disjoint rooted identity trees with n nodes, meaning no branch overlaps any other branch of the same root.

1, 1, 1, 2, 3, 6, 11, 21, 43, 89, 185, 391, 840, 1822, 3975, 8727, 19280, 42841, 95661, 214490

Offset

1,4

Links

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

Gus Wiseman, The a(8) = 21 locally disjoint rooted identity trees.

Example

The a(7) = 11 locally disjoint 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)))

Mathematica

strut[n_]:=strut[n]=If[n===1, {{}}, Select[Join@@Function[c, Union[Sort/@Tuples[strut/@c]]]/@IntegerPartitions[n-1], UnsameQ@@#&&Select[Tuples[#, 2], UnsameQ@@#&&(Intersection@@#=!={})&]=={}&]];
Table[Length[strut[n]], {n, 20}]

Crossrefs

Cf. A000081, A004111, A276625, A277098, A302696, A303362, A304713, A316467, A316471, A316473, A316474, A316494.

Sequence in context: A164362 A329667 A026742 * A018268 A082616 A018613

Adjacent sequences: A316468 A316469 A316470 * A316472 A316473 A316474

Keyword

nonn,more

Author

Gus Wiseman, Jul 04 2018

Status

approved