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

Author

Gus Wiseman, Sep 11 2022

Keywords

• nonn

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.

Examples

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

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

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.

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

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

Formula

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

Extensions

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