A319286 - OEIS

A319286

Number of series-reduced locally disjoint rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.

1, 2, 9, 67, 573, 6933, 97147, 1666999

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is locally disjoint if no branch overlaps any other branch of the same root.

LINKS

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

EXAMPLE

The a(3) = 9 trees:

(1(11))

(111)

(1(12))

(2(11))

(112)

(1(23))

(2(13))

(3(12))

(123)

Examples of rooted trees that are not locally disjoint are ((11)(12)) and ((12)(13)).

MATHEMATICA

disjointQ[u_]:=Apply[And, Outer[#1==#2||Intersection[#1, #2]=={}&, u, u, 1], {0, 1}];

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

gro[m_]:=gro[m]=If[Length[m]==1, {m}, Select[Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m], Length[#]>1&])], disjointQ]];

Table[Sum[Length[gro[m]], {m, Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n]}], {n, 5}]

CROSSREFS

Cf. A000081, A007562, A316473, A316475, A316494, A316495, A316496, A316497.

Sequence in context: A020555 A243281 A091795 * A158952 A324167 A376125

Adjacent sequences: A319283 A319284 A319285 * A319287 A319288 A319289

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Sep 16 2018

STATUS

approved