A382428 Number of normal multiset partitions of weight n into sets with distinct sizes.

1, 1, 1, 6, 8, 35, 292, 673, 2818, 16956, 219772, 636748, 3768505, 20309534, 183403268, 3227600747, 12272598308, 81353466578, 561187259734, 4416808925866, 50303004612136, 1238783066956740, 5566249468690291, 44970939483601100, 330144217684933896, 3131452652308459402

Offset: 0

Author

Gus Wiseman, Mar 29 2025

Keywords

• nonn

Comments

We call a multiset or multiset partition normal iff it covers an initial interval of positive integers. The weight of a multiset partition is the sum of sizes of its blocks.

Examples

			The a(1) = 1 through a(4) = 8 multiset partitions:
  {{1}}  {{1,2}}  {{1,2,3}}    {{1,2,3,4}}
                  {{1},{1,2}}  {{1},{1,2,3}}
                  {{1},{2,3}}  {{1},{2,3,4}}
                  {{2},{1,2}}  {{2},{1,2,3}}
                  {{2},{1,3}}  {{2},{1,3,4}}
                  {{3},{1,2}}  {{3},{1,2,3}}
                               {{3},{1,2,4}}
                               {{4},{1,2,3}}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200

Crossrefs

For distinct sums instead of sizes we have A116539, see A050326.

Without distinct lengths we have A116540 (normal set multipartitions).

Without strict blocks we have A326517, for sum instead of size A326519.

For equal instead of distinct sizes we have A331638.

Twice-partitions of this type are counted by A358830.

For distinct sums instead of sizes we have A381718.

For equal instead of distinct sizes we have A382429.

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

A001055 count factorizations, strict A045778.

Normal multiset partitions: A034691, A035310, A255906.

Set multipartitions: A089259, A270995, A296119, A318360.

Cf. A000110, A007716, A050320, A255903, A275780, A279785, A317532, A326518, A381633, A382214, A382216.

Programs

Mathematica

allnorm[n_Integer]:=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[Join@@(Select[mps[#],UnsameQ@@Length/@#&&And@@UnsameQ@@@#&]&/@allnorm[n])],{n,0,5}]

PARI

R(n, k)={Vec(prod(j=1, n, 1 + binomial(k, j)*x^j + O(x*x^n)))}
seq(n)={sum(k=0, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)))} \\ Andrew Howroyd, Mar 31 2025

Extensions

a(10) onwards from Andrew Howroyd, Mar 31 2025