|
|
A326212
|
|
Number of sortable normal multiset partitions of weight n.
|
|
13
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|