A356941 Number of multiset partitions of integer partitions of n such that all blocks are gapless.

1, 1, 3, 6, 13, 24, 49, 88, 166, 297, 534, 932, 1635, 2796, 4782, 8060, 13521, 22438, 37080, 60717, 98979, 160216, 258115, 413382, 659177, 1045636, 1651891, 2597849, 4069708, 6349677, 9871554, 15290322, 23604794, 36318256, 55705321, 85177643, 129865495

Offset

0,3

Comments

A multiset is gapless if it covers an interval of positive integers. For example, {2,3,3,4} is gapless but {1,1,3,3} is not.

Links

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

Gus Wiseman, Counting and ranking classes of multiset partitions related to gapless multisets

Formula

G.f.: 1/Product_{k>=1} (1 - x^k)^A034296(k). - Andrew Howroyd, Dec 30 2022

Example

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

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]]]];
nogapQ[m_]:=Or[m=={}, Union[m]==Range[Min[m], Max[m]]];
Table[Length[Select[Join@@mps/@IntegerPartitions[n], And@@nogapQ/@#&]], {n, 0, 5}]

Prog

(PARI) \\ Here G(n) gives A034296 as vector
G(N) = Vec(sum(n=1, N, x^n/(1-x^n) * prod(k=1, n-1, 1+x^k+O(x*x^(N-n))) ));
seq(n) = {my(u=G(n)); Vec(1/prod(k=1, n-1, (1 - x^k + O(x*x^n))^u[k])) } \\ Andrew Howroyd, Dec 30 2022

Crossrefs

A000041 counts integer partitions, strict A000009.

A000670 counts patterns, ranked by A333217, necklace A019536.

A001055 counts factorizations.

A011782 counts multisets covering an initial interval.

A356069 counts gapless divisors, initial A356224 (complement A356225).

Gapless multisets are counted by A034296, ranked by A073491.

Other types: A356233, A356942, A356943, A356944.

Other conditions: A001970, A006171, A007294, A089259, A107742, A356932.

Cf. A055887, A072233, A270995.

Sequence in context: A225198 A225199 A000219 * A191782 A358905 A027999

Adjacent sequences: A356938 A356939 A356940 * A356942 A356943 A356944

Keyword

nonn

Author

Gus Wiseman, Sep 11 2022

Extensions

Terms a(11) and beyond from Andrew Howroyd, Dec 30 2022

Status

approved