login
Number of sortable normal multiset partitions of weight n.
12

%I #10 May 11 2023 12:21:49

%S 1,1,4,15,59,230,901,3522,13773,53847,210527,823087,3218002,12581319,

%T 49188823,192312112,751877137,2939592383,11492839729,44933224559,

%U 175674134309,686828104551,2685272063984,10498530869151,41045803846015,160475597429847

%N Number of sortable normal multiset partitions of weight n.

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

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

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

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

%e The a(0) = 1 through a(3) = 15 multiset partitions:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

%t lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];

%t allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-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 Table[Length[Select[Sort[#,lexsort]&/@Join@@mps/@allnorm[n],OrderedQ[Join@@#]&]],{n,0,5}]

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

%Y Sortable set partitions are A011782.

%Y Unsortable normal multiset partitions are A326211.

%Y Crossing normal multiset partitions are A326277.

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

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

%K nonn

%O 0,3

%A _Gus Wiseman_, Jun 19 2019

%E Terms a(10) and beyond from _Andrew Howroyd_, May 11 2023