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

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

Offset: 0

Author

Gus Wiseman, Dec 23 2019

Keywords

• nonn
• more

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

Examples

			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)))
		

Crossrefs

The case with all atoms different is A000311.

The case with all atoms equal is A196545.

The orderless version is A316652.

The unlabeled version is A330470.

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.

Programs

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[#]