A382214 Number of normal multisets of size n that can be partitioned into a set of sets.

1, 1, 1, 3, 5, 11, 23, 48, 101, 210, 436, 894

Offset: 0

Author

Gus Wiseman, Mar 29 2025

Keywords

• nonn
• more

Comments

First differs from A382216 at a(9) = 210, A382216(9) = 208.

We call a multiset or multiset partition normal iff it covers an initial interval of positive integers. The size of a multiset is the number of elements, counting multiplicity.

Examples

			The normal multiset {1,1,1,1,2,2,3,3,3} has partition {{1},{3},{1,2},{1,3},{1,2,3}}, so is counted under a(9).
The a(1) = 1 through a(5) = 11 multisets:
  {1}  {1,2}  {1,1,2}  {1,1,2,2}  {1,1,1,2,3}
              {1,2,2}  {1,1,2,3}  {1,1,2,2,3}
              {1,2,3}  {1,2,2,3}  {1,1,2,3,3}
                       {1,2,3,3}  {1,1,2,3,4}
                       {1,2,3,4}  {1,2,2,2,3}
                                  {1,2,2,3,3}
                                  {1,2,2,3,4}
                                  {1,2,3,3,3}
                                  {1,2,3,3,4}
                                  {1,2,3,4,4}
                                  {1,2,3,4,5}
		

Crossrefs

Factorizations of this type are counted by A050326, distinct sums A381633.

Normal multiset partitions of this type are counted by A116539, distinct sums A381718.

The complement is counted by A292432.

Twice-partitions of this type are counted by A358914, distinct sums A279785.

The strong version is A381996, complement A292444.

For integer partitions we have A382077, ranks A382200, complement A382078, ranks A293243.

For distinct sums we have A382216, complement A382202.

The case of a unique choice is counted by A382458, distinct sums A382459.

A000670 counts patterns, ranked by A055932 and A333217, necklace A019536.

A001055 count factorizations, strict A045778.

Normal multiset partitions: A034691, A035310, A255906.

Set systems: A050342, A296120, A318361.

Set multipartitions: A089259, A270995, A296119, A318360.

Cf. A000110, A007716, A050320, A116540, A255903, A317532, A326517, A326519, A381990, A381992, A382428, A382460.

Programs

Mathematica

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]] /@ Subsets[Range[n-1]+1]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[mset_]:=Union[Sort[Sort/@(#/.x_Integer:>mset[[x]])]& /@ sps[Range[Length[mset]]]];
Table[Length[Select[allnorm[n],Select[mps[#], UnsameQ@@#&&And@@UnsameQ@@@#&]!={}&]],{n,0,5}]