| Displaying 1-4 of 4 results found.
page
1
Number of antichains of multisets with multiset-join a normal multiset of size n.
+10
9
1, 1, 3, 16, 198, 9890, 8592538
COMMENTS
An antichain of multisets is a finite set of finite nonempty multisets, none of which is a submultiset of any other. A multiset is normal if it spans an initial interval of positive integers. The multiset-join of a set of multisets has the same vertices with multiplicities equal to the maxima of the multiplicities in the edges.
EXAMPLE
The a(3) = 16 antichains of multisets:
(111),
(122), (12)(22), (1)(22),
(112), (11)(12), (2)(11),
(123), (13)(23), (12)(23), (12)(13), (12)(13)(23), (3)(12), (2)(13), (1)(23), (1)(2)(3).
MATHEMATICA
stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];
multijoin[mss__]:=Join@@Table[Table[x, {Max[Count[#, x]&/@{mss}]}], {x, Union[mss]}]
submultisetQ[M_, N_]:=Or[Length[M]==0, MatchQ[{Sort[List@@M], Sort[List@@N]}, {{x_, Z___}, {___, x_, W___}}/; submultisetQ[{Z}, {W}]]];
allnorm[n_]:=Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1];
auu[m_]:=Select[stableSets[Union[Rest[Subsets[m]]], submultisetQ], multijoin@@#==m&];
Table[Length[Join@@Table[auu[m], {m, allnorm[n]}]], {n, 5}]
Number of connected multiset partitions of normal multisets of size n.
+10
9
1, 1, 3, 8, 28, 110, 519, 2749, 16317, 106425, 755425, 5781956, 47384170, 413331955, 3818838624, 37213866876, 381108145231, 4088785729738, 45829237977692, 535340785268513, 6502943193997922, 81984445333355812, 1070848034863526547, 14467833457108560375, 201894571410270034773
COMMENTS
A multiset is normal if it spans an initial interval of positive integers.
EXAMPLE
The a(3) = 8 connected multiset partitions are (111), (1)(11), (1)(1)(1), (122), (2)(12), (112), (1)(12), (123).
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]]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Union[Append[Delete[s, List/@c[[1]]], multijoin@@s[[c[[1]]]]]]]]];
allnorm[n_]:=Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1];
Length/@Table[Join@@Table[Select[mps[m], Length[csm[#]]==1&], {m, allnorm[n]}], {n, 8}]
PROG
(PARI)
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
Connected(v)={my(u=vector(#v)); for(n=1, #u, u[n]=v[n] - sum(k=1, n-1, binomial(n-1, k)*v[k]*u[n-k])); u}
seq(n)={my(u=vector(n, k, x*Ser(EulerT(vector(n, i, binomial(i+k-1, i)))))); Vec(1+vecsum(Connected(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k, i)*u[i])))))} \\ Andrew Howroyd, Jan 16 2023
Number of antichains of multisets with multiset-join a strongly normal multiset of size n.
+10
5
COMMENTS
An antichain of multisets is a finite set of finite nonempty multisets, none of which is a submultiset of any other. A multiset is strongly normal if it spans an initial interval of positive integers with weakly decreasing multiplicities. The multiset-join of a multiset system has the same vertices with multiplicities equal to the maxima of the multiplicities in the edges.
EXAMPLE
The a(3) = 13 antichains of multisets:
(111),
(112), (11)(12), (2)(11),
(123), (13)(23), (12)(23), (12)(13), (12)(13)(23), (3)(12), (2)(13), (1)(23), (1)(2)(3).
MATHEMATICA
stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];
multijoin[mss__]:=Join@@Table[Table[x, {Max[Count[#, x]&/@{mss}]}], {x, Union[mss]}];
submultisetQ[M_, N_]:=Or[Length[M]==0, MatchQ[{Sort[List@@M], Sort[List@@N]}, {{x_, Z___}, {___, x_, W___}}/; submultisetQ[{Z}, {W}]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n];
auu[m_]:=Select[stableSets[Union[Rest[Subsets[m]]], submultisetQ], multijoin@@#==m&];
Table[Length[Join@@Table[auu[m], {m, strnorm[n]}]], {n, 5}]
Number of unlabeled connected antichains of multisets with multiset-join a multiset of size n.
+10
5
COMMENTS
An antichain of multisets is a finite set of finite nonempty multisets, none of which is a submultiset of any other. The multiset-join of a multiset system has the same vertices with multiplicities equal to the maxima of the multiplicities in the edges.
EXAMPLE
Non-isomorphic representatives of the a(3) = 6 connected antichains of multisets:
(111),
(122), (12)(22),
(123), (13)(23), (12)(13)(23).
MATHEMATICA
stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];
multijoin[mss__]:=Join@@Table[Table[x, {Max[Count[#, x]&/@{mss}]}], {x, Union[mss]}]
submultisetQ[M_, N_]:=Or[Length[M]==0, MatchQ[{Sort[List@@M], Sort[List@@N]}, {{x_, Z___}, {___, x_, W___}}/; submultisetQ[{Z}, {W}]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Union[Append[Delete[s, List/@c[[1]]], multijoin@@s[[c[[1]]]]]]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n];
sysnorm[m_]:=First[Sort[sysnorm[m, 1]]];
sysnorm[m_, aft_]:=If[Length[Union@@m]<=aft, {m}, With[{mx=Table[Count[m, i, {2}], {i, Select[Union@@m, #>=aft&]}]}, Union@@(sysnorm[#, aft+1]&/@Union[Table[Map[Sort, m/.{par+aft-1->aft, aft->par+aft-1}, {0, 1}], {par, First/@Position[mx, Max[mx]]}]])]];
cuu[m_]:=Select[stableSets[Union[Rest[Subsets[m]]], submultisetQ], And[multijoin@@#==m, Length[csm[#]]==1]&];
Table[Length[Union[sysnorm/@Join@@Table[cuu[m], {m, strnorm[n]}]]], {n, 5}]
Search completed in 0.006 seconds
|