login
Number of series/singleton-reduced rooted trees on strongly normal multisets of size n.
8

%I #9 Apr 30 2020 09:34:15

%S 1,1,2,9,69,623,7803,110476,1907428

%N Number of series/singleton-reduced rooted trees on strongly normal multisets of size n.

%C A multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.

%C 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).

%e The a(0) = 1 through a(3) = 9 trees:

%e () (1) (11) (111)

%e (12) (112)

%e (123)

%e ((1)(11))

%e ((1)(12))

%e ((1)(23))

%e ((2)(11))

%e ((2)(13))

%e ((3)(12))

%e The a(4) = 69 trees, with singleton leaves (x) replaced by just x:

%e (1111) (1112) (1122) (1123) (1234)

%e (1(111)) (1(112)) (1(122)) (1(123)) (1(234))

%e (11(11)) (11(12)) (11(22)) (11(23)) (12(34))

%e ((11)(11)) (12(11)) (12(12)) (12(13)) (13(24))

%e (1(1(11))) (2(111)) (2(112)) (13(12)) (14(23))

%e ((11)(12)) (22(11)) (2(113)) (2(134))

%e (1(1(12))) ((11)(22)) (23(11)) (23(14))

%e (1(2(11))) (1(1(22))) (3(112)) (24(13))

%e (2(1(11))) ((12)(12)) ((11)(23)) (3(124))

%e (1(2(12))) (1(1(23))) (34(12))

%e (2(1(12))) ((12)(13)) (4(123))

%e (2(2(11))) (1(2(13))) ((12)(34))

%e (1(3(12))) (1(2(34)))

%e (2(1(13))) ((13)(24))

%e (2(3(11))) (1(3(24)))

%e (3(1(12))) ((14)(23))

%e (3(2(11))) (1(4(23)))

%e (2(1(34)))

%e (2(3(14)))

%e (2(4(13)))

%e (3(1(24)))

%e (3(2(14)))

%e (3(4(12)))

%e (4(1(23)))

%e (4(2(13)))

%e (4(3(12)))

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

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

%t strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];

%t mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p],{p,Select[mps[m],Length[#]>1&&Length[#]<Length[m]&]}],m];

%t Table[Sum[Length[mtot[s]],{s,strnorm[n]}],{n,0,5}]

%Y The case with all atoms different is A000311.

%Y The case with all atoms equal is A196545.

%Y The orderless version is A316652.

%Y The unlabeled version is A330470.

%Y The case where the leaves are sets is A330628.

%Y The version for just normal (not strongly normal) is A330654.

%Y Cf. A000669, A004114, A005121, A005804, A281118, A318812, A318848, A319312, A330465, A330467, A330475.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Dec 23 2019