A326212 Number of sortable normal multiset partitions of weight n.

1, 1, 4, 15, 59, 230, 901, 3522, 13773, 53847, 210527, 823087, 3218002, 12581319, 49188823, 192312112, 751877137, 2939592383, 11492839729, 44933224559, 175674134309, 686828104551, 2685272063984, 10498530869151, 41045803846015, 160475597429847

Offset

0,3

Comments

A multiset partition is normal if it covers an initial interval of positive integers. It is sortable if some permutation has an ordered concatenation. For example, the multiset partition {{1,2},{1,1,1},{2,2,2}} is sortable because the permutation ((1,1,1),(1,2),(2,2,2)) has concatenation (1,1,1,1,2,2,2,2), which is weakly increasing.

Links

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

Formula

A255906(n) = a(n) + A326211(n).

G.f.: ((1 - x)*(1 - 2*x) - x^2*P(x))/(2*(1 - x)*(1 - 2*x) - (1 - 3*x + 4*x^2)*P(x)) where P(x) is the g.f. of A000041. - Andrew Howroyd, May 11 2023

Example

The a(0) = 1 through a(3) = 15 multiset partitions:
  {}  {{1}}  {{1,1}}    {{1,1,1}}
             {{1,2}}    {{1,1,2}}
             {{1},{1}}  {{1,2,2}}
             {{1},{2}}  {{1,2,3}}
                        {{1},{1,1}}
                        {{1},{1,2}}
                        {{1,1},{2}}
                        {{1},{2,2}}
                        {{1,2},{2}}
                        {{1},{2,3}}
                        {{1,2},{3}}
                        {{1},{1},{1}}
                        {{1},{1},{2}}
                        {{1},{2},{2}}
                        {{1},{2},{3}}

Mathematica

lexsort[f_, c_]:=OrderedQ[PadRight[{f, c}]];
allnorm[n_]:=If[n<=0, {{}}, 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[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
Table[Length[Select[Sort[#, lexsort]&/@Join@@mps/@allnorm[n], OrderedQ[Join@@#]&]], {n, 0, 5}]

Prog

(PARI) seq(n) = my(p=1/eta(x + O(x*x^n))); Vec(((1 - x)*(1 - 2*x) - x^2*p)/(2*(1 - x)*(1 - 2*x) - (1 - 3*x + 4*x^2)*p)) \\ Andrew Howroyd, May 11 2023

Crossrefs

Sortable set partitions are A011782.

Unsortable normal multiset partitions are A326211.

Crossing normal multiset partitions are A326277.

Cf. A000041, A000108, A058681, A255906, A324170, A324171.

Cf. A326209, A326237, A326255, A326256, A326257, A326258.

Sequence in context: A128714 A007342 A017951 * A199210 A129155 A219312

Adjacent sequences: A326209 A326210 A326211 * A326213 A326214 A326215

Keyword

nonn

Author

Gus Wiseman, Jun 19 2019

Extensions

Terms a(10) and beyond from Andrew Howroyd, May 11 2023

Status

approved