A316473 Number of locally disjoint rooted trees with n nodes, meaning no branch overlaps any other (unequal) branch of the same root.

1, 1, 2, 4, 9, 19, 44, 99, 233, 554, 1346, 3300, 8219, 20635, 52300, 133488, 343033, 886360, 2302133, 6005835

Offset

1,3

Links

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

Gus Wiseman, The a(6) = 19 locally disjoint rooted trees.

Example

The a(5) = 9 locally disjoint rooted trees:
((((o))))
(((oo)))
((o(o)))
((ooo))
(o((o)))
(o(oo))
((o)(o))
(oo(o))
(oooo)

Mathematica

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

Crossrefs

Cf. A000081, A285573, A302696, A304713, A316468, A316470, A316471, A316475, A316495.

Sequence in context: A247623 A084083 A036611 * A316501 A036612 A291648

Adjacent sequences: A316470 A316471 A316472 * A316474 A316475 A316476

Keyword

nonn,more

Author

Gus Wiseman, Jul 04 2018

Extensions

a(20) from Jinyuan Wang, Jun 20 2020

Status

approved