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,4

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.

Links

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

Example

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

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}]

Prog

(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

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.

Sequence in context: A025091 A356742 A303156 * A028321 A166642 A077709

Adjacent sequences: A382425 A382426 A382427 * A382429 A382430 A382431

Keyword

nonn

Author

Gus Wiseman, Mar 29 2025

Extensions

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

Status

approved