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

%I #9 Dec 30 2022 21:38:23

%S 1,1,3,6,13,24,49,88,166,297,534,932,1635,2796,4782,8060,13521,22438,

%T 37080,60717,98979,160216,258115,413382,659177,1045636,1651891,

%U 2597849,4069708,6349677,9871554,15290322,23604794,36318256,55705321,85177643,129865495

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

%C 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.

%H Andrew Howroyd, <a href="/A356941/b356941.txt">Table of n, a(n) for n = 0..1000</a>

%H Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vR-C_picqWlu0KOguRGWaPjhS2HY7m43aGXGDcolDh4Qtyy-pu2lkq5mbHAbiMSyQoiIESG2mCGtc2j/pub">Counting and ranking classes of multiset partitions related to gapless multisets</a>

%F G.f.: 1/Product_{k>=1} (1 - x^k)^A034296(k). - _Andrew Howroyd_, Dec 30 2022

%e The a(1) = 1 through a(4) = 13 multiset partitions:

%e {{1}} {{2}} {{3}} {{4}}

%e {{1,1}} {{1,2}} {{2,2}}

%e {{1},{1}} {{1,1,1}} {{1,1,2}}

%e {{1},{2}} {{1},{3}}

%e {{1},{1,1}} {{2},{2}}

%e {{1},{1},{1}} {{1,1,1,1}}

%e {{1},{1,2}}

%e {{2},{1,1}}

%e {{1},{1,1,1}}

%e {{1,1},{1,1}}

%e {{1},{1},{2}}

%e {{1},{1},{1,1}}

%e {{1},{1},{1},{1}}

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

%t nogapQ[m_]:=Or[m=={},Union[m]==Range[Min[m],Max[m]]];

%t Table[Length[Select[Join@@mps/@IntegerPartitions[n],And@@nogapQ/@#&]],{n,0,5}]

%o (PARI) \\ Here G(n) gives A034296 as vector

%o 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))) ));

%o 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

%Y A000041 counts integer partitions, strict A000009.

%Y A000670 counts patterns, ranked by A333217, necklace A019536.

%Y A001055 counts factorizations.

%Y A011782 counts multisets covering an initial interval.

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

%Y Gapless multisets are counted by A034296, ranked by A073491.

%Y Other types: A356233, A356942, A356943, A356944.

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

%Y Cf. A055887, A072233, A270995.

%K nonn

%O 0,3

%A _Gus Wiseman_, Sep 11 2022

%E Terms a(11) and beyond from _Andrew Howroyd_, Dec 30 2022