|
|
A330471
|
|
Number of series/singleton-reduced rooted trees on strongly normal multisets of size n.
|
|
8
|
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.
A series/singleton-reduced rooted tree on a multiset m is either the multiset m itself or a sequence of series/singleton-reduced rooted trees, one on each part of a multiset partition of m that is neither minimal (all singletons) nor maximal (only one part). This is a multiset generalization of singleton-reduced phylogenetic trees (A000311).
|
|
LINKS
|
|
|
EXAMPLE
|
The a(0) = 1 through a(3) = 9 trees:
() (1) (11) (111)
(12) (112)
(123)
((1)(11))
((1)(12))
((1)(23))
((2)(11))
((2)(13))
((3)(12))
The a(4) = 69 trees, with singleton leaves (x) replaced by just x:
(1111) (1112) (1122) (1123) (1234)
(1(111)) (1(112)) (1(122)) (1(123)) (1(234))
(11(11)) (11(12)) (11(22)) (11(23)) (12(34))
((11)(11)) (12(11)) (12(12)) (12(13)) (13(24))
(1(1(11))) (2(111)) (2(112)) (13(12)) (14(23))
((11)(12)) (22(11)) (2(113)) (2(134))
(1(1(12))) ((11)(22)) (23(11)) (23(14))
(1(2(11))) (1(1(22))) (3(112)) (24(13))
(2(1(11))) ((12)(12)) ((11)(23)) (3(124))
(1(2(12))) (1(1(23))) (34(12))
(2(1(12))) ((12)(13)) (4(123))
(2(2(11))) (1(2(13))) ((12)(34))
(1(3(12))) (1(2(34)))
(2(1(13))) ((13)(24))
(2(3(11))) (1(3(24)))
(3(1(12))) ((14)(23))
(3(2(11))) (1(4(23)))
(2(1(34)))
(2(3(14)))
(2(4(13)))
(3(1(24)))
(3(2(14)))
(3(4(12)))
(4(1(23)))
(4(2(13)))
(4(3(12)))
|
|
MATHEMATICA
|
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]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p], {p, Select[mps[m], Length[#]>1&&Length[#]<Length[m]&]}], m];
Table[Sum[Length[mtot[s]], {s, strnorm[n]}], {n, 0, 5}]
|
|
CROSSREFS
|
The case with all atoms different is A000311.
The case with all atoms equal is A196545.
The case where the leaves are sets is A330628.
The version for just normal (not strongly normal) is A330654.
Cf. A000669, A004114, A005121, A005804, A281118, A318812, A318848, A319312, A330465, A330467, A330475.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|