Partitioning a multiset into multisets of fixed sizes












4












$begingroup$


Say we have a multiset $S(mathbf{d}$) where $mathbf{d}$ is a list of $l$ numbers and the multiplicity of the $i$th element of $S$ is $d_i$. The cardinality $N$ of $S$ is $sum d_i$.



We want to partition $S$ into $m$ multisets of size $k_i$ respectively, so that $sum k_i = sum d_i = N$. How many ways can we do this?



In my mind this is a generalization of the multinomial coefficient $binom{n}{k_1,k_2,ldots,k_m}$ representing the number of ways to partition a set of $n=sum k_i$ objects into $m$ bins of sizes $k_i$, to a sort of number like $binom{mathbf{d}}{k_1,k_2,ldots,k_m}$ or $binom{mathbf{d}}{mathbf{k}}$ representing the number of ways to partition a multiset of $n=sum k_i = sum d_i$ into $m$ bins of sizes $k_i$.



There are a few special cases that are simpler to calculate:




  • If $m=1$, then clearly $k_1 = N$ and you're choosing the whole multiset. So $binom{mathbf{d}}{(N)} = 1$

  • If $m=2$, then you only have to handle choosing $k_1$ or $k_2$ elements from a multiset, because the rest will be the other set. So, as mentioned below, you can use a generating function and $binom{mathbf{d}}{(k_1,k_2)}$ is equal to the coefficient of $x^{k_1}$ or $x^{k_2}$ in $prodlimits_{i=1}^l 1 + x^2 + cdots + x^{d_i} = prodlimits_{i=1}^l frac{1-x^{d_i - 1}}{1 - x}$. But then you also need to account for the fact that order doesn't matter, which I'm not sure how to do. Like in the first example below, you would find that there are $3$ ways to choose $2$ elements, but there are only $2$ ways to split the multiset because you have to choose 2 of them that are compatible.


Examples



Let's say that $mathbf{d} = (2, 2)$, so $S(mathbf{d})$ might be ${a, a, b, b}$. Let $k_1 = k_2 = 2$, so we need to find all the ways of splitting $S$ into two sub-multisets of size $2$. There are exactly $2$ ways of doing this: ${{a,a},{b,b}}$ and ${{a,b},{a,b}}$, so $binom{(2,2)}{(2,2)} = 2$.



Another example: $mathbf{d} = (2,2)$, so $S(mathbf{d})$ could be ${a,a,b,b}$. Let $k_1 = 1$, $k_2 = 1$, and $k_3 = 2$. There are $3$ ways of doing this: ${{a},{a},{b,b}}$, ${{b},{b},{a,a}}$, and ${{a},{b},{a,b}}$. So $binom{(2,2)}{(1,1,2)}=3$.



My Attempts



I've tried to figure this out two ways. The first was to find a recurrence relation and some base cases, kind of how Stirling numbers of the second kind can be computed using the identity $S(n,k) = kS(n-1,k) + S(n-1,k-1)$. I tried to think about what happens if you already have a partition and want to add an element to the original multiset, but then you have to decide which bin that element will go into or whether or not to add a new bin.



I also tried to derive it in the way that multinomial coefficients are derived, by counting the number of ways to fill the first bin, and then the second, and so on. The number of ways to choose $k_1$ elements from the multiset to put in the first bin can be computed by finding the coefficient of $x^{k_1}$ in $prodlimits_{i=1}^l 1+x+x^2+cdots+x^{d_i}$, which isn't explicit but it's a start. But then, depending on which elements you chose, you don't know how to adjust your multiset to reflect the remaining elements.










share|cite|improve this question











$endgroup$












  • $begingroup$
    Partitioning of a set of $n$ distinguished members is counted by the exponential Bell polynomial (and by Stirling number of the second kind and Bell number). This is the set partition problem. Maybe there is a possibility to change the calculation algorithm of this combinatorial numbers to consider multisets.
    $endgroup$
    – IV_
    Jul 20 '18 at 14:46
















4












$begingroup$


Say we have a multiset $S(mathbf{d}$) where $mathbf{d}$ is a list of $l$ numbers and the multiplicity of the $i$th element of $S$ is $d_i$. The cardinality $N$ of $S$ is $sum d_i$.



We want to partition $S$ into $m$ multisets of size $k_i$ respectively, so that $sum k_i = sum d_i = N$. How many ways can we do this?



In my mind this is a generalization of the multinomial coefficient $binom{n}{k_1,k_2,ldots,k_m}$ representing the number of ways to partition a set of $n=sum k_i$ objects into $m$ bins of sizes $k_i$, to a sort of number like $binom{mathbf{d}}{k_1,k_2,ldots,k_m}$ or $binom{mathbf{d}}{mathbf{k}}$ representing the number of ways to partition a multiset of $n=sum k_i = sum d_i$ into $m$ bins of sizes $k_i$.



There are a few special cases that are simpler to calculate:




  • If $m=1$, then clearly $k_1 = N$ and you're choosing the whole multiset. So $binom{mathbf{d}}{(N)} = 1$

  • If $m=2$, then you only have to handle choosing $k_1$ or $k_2$ elements from a multiset, because the rest will be the other set. So, as mentioned below, you can use a generating function and $binom{mathbf{d}}{(k_1,k_2)}$ is equal to the coefficient of $x^{k_1}$ or $x^{k_2}$ in $prodlimits_{i=1}^l 1 + x^2 + cdots + x^{d_i} = prodlimits_{i=1}^l frac{1-x^{d_i - 1}}{1 - x}$. But then you also need to account for the fact that order doesn't matter, which I'm not sure how to do. Like in the first example below, you would find that there are $3$ ways to choose $2$ elements, but there are only $2$ ways to split the multiset because you have to choose 2 of them that are compatible.


Examples



Let's say that $mathbf{d} = (2, 2)$, so $S(mathbf{d})$ might be ${a, a, b, b}$. Let $k_1 = k_2 = 2$, so we need to find all the ways of splitting $S$ into two sub-multisets of size $2$. There are exactly $2$ ways of doing this: ${{a,a},{b,b}}$ and ${{a,b},{a,b}}$, so $binom{(2,2)}{(2,2)} = 2$.



Another example: $mathbf{d} = (2,2)$, so $S(mathbf{d})$ could be ${a,a,b,b}$. Let $k_1 = 1$, $k_2 = 1$, and $k_3 = 2$. There are $3$ ways of doing this: ${{a},{a},{b,b}}$, ${{b},{b},{a,a}}$, and ${{a},{b},{a,b}}$. So $binom{(2,2)}{(1,1,2)}=3$.



My Attempts



I've tried to figure this out two ways. The first was to find a recurrence relation and some base cases, kind of how Stirling numbers of the second kind can be computed using the identity $S(n,k) = kS(n-1,k) + S(n-1,k-1)$. I tried to think about what happens if you already have a partition and want to add an element to the original multiset, but then you have to decide which bin that element will go into or whether or not to add a new bin.



I also tried to derive it in the way that multinomial coefficients are derived, by counting the number of ways to fill the first bin, and then the second, and so on. The number of ways to choose $k_1$ elements from the multiset to put in the first bin can be computed by finding the coefficient of $x^{k_1}$ in $prodlimits_{i=1}^l 1+x+x^2+cdots+x^{d_i}$, which isn't explicit but it's a start. But then, depending on which elements you chose, you don't know how to adjust your multiset to reflect the remaining elements.










share|cite|improve this question











$endgroup$












  • $begingroup$
    Partitioning of a set of $n$ distinguished members is counted by the exponential Bell polynomial (and by Stirling number of the second kind and Bell number). This is the set partition problem. Maybe there is a possibility to change the calculation algorithm of this combinatorial numbers to consider multisets.
    $endgroup$
    – IV_
    Jul 20 '18 at 14:46














4












4








4


1



$begingroup$


Say we have a multiset $S(mathbf{d}$) where $mathbf{d}$ is a list of $l$ numbers and the multiplicity of the $i$th element of $S$ is $d_i$. The cardinality $N$ of $S$ is $sum d_i$.



We want to partition $S$ into $m$ multisets of size $k_i$ respectively, so that $sum k_i = sum d_i = N$. How many ways can we do this?



In my mind this is a generalization of the multinomial coefficient $binom{n}{k_1,k_2,ldots,k_m}$ representing the number of ways to partition a set of $n=sum k_i$ objects into $m$ bins of sizes $k_i$, to a sort of number like $binom{mathbf{d}}{k_1,k_2,ldots,k_m}$ or $binom{mathbf{d}}{mathbf{k}}$ representing the number of ways to partition a multiset of $n=sum k_i = sum d_i$ into $m$ bins of sizes $k_i$.



There are a few special cases that are simpler to calculate:




  • If $m=1$, then clearly $k_1 = N$ and you're choosing the whole multiset. So $binom{mathbf{d}}{(N)} = 1$

  • If $m=2$, then you only have to handle choosing $k_1$ or $k_2$ elements from a multiset, because the rest will be the other set. So, as mentioned below, you can use a generating function and $binom{mathbf{d}}{(k_1,k_2)}$ is equal to the coefficient of $x^{k_1}$ or $x^{k_2}$ in $prodlimits_{i=1}^l 1 + x^2 + cdots + x^{d_i} = prodlimits_{i=1}^l frac{1-x^{d_i - 1}}{1 - x}$. But then you also need to account for the fact that order doesn't matter, which I'm not sure how to do. Like in the first example below, you would find that there are $3$ ways to choose $2$ elements, but there are only $2$ ways to split the multiset because you have to choose 2 of them that are compatible.


Examples



Let's say that $mathbf{d} = (2, 2)$, so $S(mathbf{d})$ might be ${a, a, b, b}$. Let $k_1 = k_2 = 2$, so we need to find all the ways of splitting $S$ into two sub-multisets of size $2$. There are exactly $2$ ways of doing this: ${{a,a},{b,b}}$ and ${{a,b},{a,b}}$, so $binom{(2,2)}{(2,2)} = 2$.



Another example: $mathbf{d} = (2,2)$, so $S(mathbf{d})$ could be ${a,a,b,b}$. Let $k_1 = 1$, $k_2 = 1$, and $k_3 = 2$. There are $3$ ways of doing this: ${{a},{a},{b,b}}$, ${{b},{b},{a,a}}$, and ${{a},{b},{a,b}}$. So $binom{(2,2)}{(1,1,2)}=3$.



My Attempts



I've tried to figure this out two ways. The first was to find a recurrence relation and some base cases, kind of how Stirling numbers of the second kind can be computed using the identity $S(n,k) = kS(n-1,k) + S(n-1,k-1)$. I tried to think about what happens if you already have a partition and want to add an element to the original multiset, but then you have to decide which bin that element will go into or whether or not to add a new bin.



I also tried to derive it in the way that multinomial coefficients are derived, by counting the number of ways to fill the first bin, and then the second, and so on. The number of ways to choose $k_1$ elements from the multiset to put in the first bin can be computed by finding the coefficient of $x^{k_1}$ in $prodlimits_{i=1}^l 1+x+x^2+cdots+x^{d_i}$, which isn't explicit but it's a start. But then, depending on which elements you chose, you don't know how to adjust your multiset to reflect the remaining elements.










share|cite|improve this question











$endgroup$




Say we have a multiset $S(mathbf{d}$) where $mathbf{d}$ is a list of $l$ numbers and the multiplicity of the $i$th element of $S$ is $d_i$. The cardinality $N$ of $S$ is $sum d_i$.



We want to partition $S$ into $m$ multisets of size $k_i$ respectively, so that $sum k_i = sum d_i = N$. How many ways can we do this?



In my mind this is a generalization of the multinomial coefficient $binom{n}{k_1,k_2,ldots,k_m}$ representing the number of ways to partition a set of $n=sum k_i$ objects into $m$ bins of sizes $k_i$, to a sort of number like $binom{mathbf{d}}{k_1,k_2,ldots,k_m}$ or $binom{mathbf{d}}{mathbf{k}}$ representing the number of ways to partition a multiset of $n=sum k_i = sum d_i$ into $m$ bins of sizes $k_i$.



There are a few special cases that are simpler to calculate:




  • If $m=1$, then clearly $k_1 = N$ and you're choosing the whole multiset. So $binom{mathbf{d}}{(N)} = 1$

  • If $m=2$, then you only have to handle choosing $k_1$ or $k_2$ elements from a multiset, because the rest will be the other set. So, as mentioned below, you can use a generating function and $binom{mathbf{d}}{(k_1,k_2)}$ is equal to the coefficient of $x^{k_1}$ or $x^{k_2}$ in $prodlimits_{i=1}^l 1 + x^2 + cdots + x^{d_i} = prodlimits_{i=1}^l frac{1-x^{d_i - 1}}{1 - x}$. But then you also need to account for the fact that order doesn't matter, which I'm not sure how to do. Like in the first example below, you would find that there are $3$ ways to choose $2$ elements, but there are only $2$ ways to split the multiset because you have to choose 2 of them that are compatible.


Examples



Let's say that $mathbf{d} = (2, 2)$, so $S(mathbf{d})$ might be ${a, a, b, b}$. Let $k_1 = k_2 = 2$, so we need to find all the ways of splitting $S$ into two sub-multisets of size $2$. There are exactly $2$ ways of doing this: ${{a,a},{b,b}}$ and ${{a,b},{a,b}}$, so $binom{(2,2)}{(2,2)} = 2$.



Another example: $mathbf{d} = (2,2)$, so $S(mathbf{d})$ could be ${a,a,b,b}$. Let $k_1 = 1$, $k_2 = 1$, and $k_3 = 2$. There are $3$ ways of doing this: ${{a},{a},{b,b}}$, ${{b},{b},{a,a}}$, and ${{a},{b},{a,b}}$. So $binom{(2,2)}{(1,1,2)}=3$.



My Attempts



I've tried to figure this out two ways. The first was to find a recurrence relation and some base cases, kind of how Stirling numbers of the second kind can be computed using the identity $S(n,k) = kS(n-1,k) + S(n-1,k-1)$. I tried to think about what happens if you already have a partition and want to add an element to the original multiset, but then you have to decide which bin that element will go into or whether or not to add a new bin.



I also tried to derive it in the way that multinomial coefficients are derived, by counting the number of ways to fill the first bin, and then the second, and so on. The number of ways to choose $k_1$ elements from the multiset to put in the first bin can be computed by finding the coefficient of $x^{k_1}$ in $prodlimits_{i=1}^l 1+x+x^2+cdots+x^{d_i}$, which isn't explicit but it's a start. But then, depending on which elements you chose, you don't know how to adjust your multiset to reflect the remaining elements.







combinatorics set-partition multisets






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jul 20 '18 at 14:45







JJW5432

















asked Jul 19 '18 at 4:17









JJW5432JJW5432

167111




167111












  • $begingroup$
    Partitioning of a set of $n$ distinguished members is counted by the exponential Bell polynomial (and by Stirling number of the second kind and Bell number). This is the set partition problem. Maybe there is a possibility to change the calculation algorithm of this combinatorial numbers to consider multisets.
    $endgroup$
    – IV_
    Jul 20 '18 at 14:46


















  • $begingroup$
    Partitioning of a set of $n$ distinguished members is counted by the exponential Bell polynomial (and by Stirling number of the second kind and Bell number). This is the set partition problem. Maybe there is a possibility to change the calculation algorithm of this combinatorial numbers to consider multisets.
    $endgroup$
    – IV_
    Jul 20 '18 at 14:46
















$begingroup$
Partitioning of a set of $n$ distinguished members is counted by the exponential Bell polynomial (and by Stirling number of the second kind and Bell number). This is the set partition problem. Maybe there is a possibility to change the calculation algorithm of this combinatorial numbers to consider multisets.
$endgroup$
– IV_
Jul 20 '18 at 14:46




$begingroup$
Partitioning of a set of $n$ distinguished members is counted by the exponential Bell polynomial (and by Stirling number of the second kind and Bell number). This is the set partition problem. Maybe there is a possibility to change the calculation algorithm of this combinatorial numbers to consider multisets.
$endgroup$
– IV_
Jul 20 '18 at 14:46










2 Answers
2






active

oldest

votes


















3





+50







$begingroup$

It would appear that these are multisets of multisets which may be
enumerated using the Polya Enumeration Theorem (PET). Let the multiset
that is being drawn have factorization



$$prod_{k=1}^m B_k^{sigma_{k}}$$



where $k$ is the value of a term and $sigma_k$ the number of times it
ocurs and recall that we have $l$ types of items forming the source
multiset



$$prod_{k=1}^l A_k^{tau_{k}}.$$



The answer is then given by



$$left[prod_{k=1}^l A_k^{tau_{k}}right]
prod_{k=1}^m
Zleft(S_{sigma_k};
Zleft(S_k; sum_{k'=1}^l A_{k'}right)right).$$



In terms of combinatorial classes we have made use of the unlabeled
class



$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}
textsc{MSET}_{=sigma_k}
left(textsc{MSET}_{=k}
left(sum_{k'=1}^l mathcal{A}_{k'}right)right).$$



As an example for ${2,2choose 1,1,2} = 3$ we get



$$textsc{MSET}_{=2}
(textsc{MSET}_{=1}(mathcal{A_1}+mathcal{A}_2))
times textsc{MSET}_{=1}
(textsc{MSET}_{=2}(mathcal{A_1}+mathcal{A}_2)).$$



As an additional example we find for ${2,2,4choose 1,1,3,3} = 16$



$$textsc{MSET}_{=2}
(textsc{MSET}_{=1}(mathcal{A_1}+mathcal{A}_2+mathcal{A}_3))
times textsc{MSET}_{=2}
(textsc{MSET}_{=3}(mathcal{A_1}+mathcal{A}_2+mathcal{A}_3)).$$



Here we have used the cycle index of the symmetric group $Z(S_n)$,
which is computed from the recurrence by Lovasz which says that



$$Z(S_n) = frac{1}{n} sum_{l=1}^n a_l Z(S_{n-l})
quadtext{where}quad
Z(S_0) = 1.$$



For this to be effective we need to compute the iterated cycle index
when $Z(S_k)$ is substituted into $Z(S_{sigma_k}).$ This is
accomplished with the substitution rule for substitution of the former
into the latter:



$$a_q = Z(S_k;; a_1=a_q, ; a_2=a_{2q}, ; a_3=a_{3q}, ; ldots).$$



We have used the notation $Z(S_k; F)$ for substitution of a generating
function and on the previous line, the notation for substitution into
the variables of the cycle index. This is in fact all we need and we
can start computing some of these multiset coefficients. For example
we find for the example given by OP the cycle index



$$Z(B_1^2 B_2) =
1/4,{a_{{1}}}^{4}+1/2,{a_{{1}}}^{2}a_{{2}}+1/4,{a_{{2}}}^{2}.$$



Continuing with the example we get



$$Z(B_1^2 B_2; A_1+A_2) =
1/4, left( A_{{1}}+A_{{2}} right) ^{4}
+1/2, left( A_{{1}}+A_{{2}} right) ^{2}
left( {A_{{1}}}^{2}+{A_{{2}}}^{2} right)
\ +1/4, left( {A_{{1}}}^{2}+{A_{{2}}}^{2}
right) ^{2} \ = {A_{{1}}}^{4}+2,{A_{{1}}}^{3}A_{{2}}
+3,{A_{{1}}}^{2}{A_{{2}}}^{2}+2,A_{{1}}{A_{{2}}
}^{3}+{A_{{2}}}^{4}$$



and we confirm the value $3$ obtained by OP. This algorithm will make
it possible to compute cycle indices not obtainable by enumeration. As
an extra example we find the following excerpt from the cycle index
for $[2,2,2,3,5,5]:$



$$Z(B_2^3 B_3 B_5^2) = ldots
+{frac {11,{a_{{1}}}^{8}a_{{2}}a_{{4}}a_{{5}}}{7200}}
+{frac {49,{a_{{1}}}^{7}{a_{{2}}}^{2}a_{{3}}a_{{5}}}{14400}}
\ +{frac {5,{a_{{1}}}^{7} a_{{2}}{a_{{3}}}^{2}a_{{4}}}{1152}}
+{frac {1021,{a_{{1}}}^{6}{a_{{2}}}^{3}a_{{3}}a_{{4}}}{69120}}
+{frac {43,{a_{{1}}}^{7}a_{{2}}a_{{4}}a_{{6}}}{17280}}+ldots$$



Here are some additional values that may assist the reader who is
investigating this problem to verify the results of their approach:



$${1,3,3choose 3,4} = 7, ;
{2,3,3choose 4,4} = 5, ;
{2,3,3choose 2,2,4} = 16
quadtext{and}quad
{1,2,3,3choose 2,3,4} = 87.$$



The Maple code for this problem was as follows.




with(combinat);


pet_cycleind_symm :=
proc(n)
option remember;

if n=0 then return 1; fi;

expand(1/n*
add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

res := ind;

polyvars := indets(poly);
indvars := indets(ind);

for v in indvars do
pot := op(1, v);

subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];

subs2 := [v=subs(subs1, poly)];

res := subs(subs2, res);
od;

res;
end;

pet_cycleind_comp :=
proc(idxtrg, idx)
local varstrg, vars, vt, sbstrg, sbs, len;

varstrg := indets(idxtrg);
vars := indets(idx);

sbstrg := ;

for vt in varstrg do
len := op(1, vt);

sbs :=
[seq(v = a[op(1, v)*len], v in vars)];

sbstrg :=
[op(sbstrg),
a[len] = subs(sbs, idx)];
od;

expand(subs(sbstrg, idxtrg));
end;

pet_cycleind_mset :=
proc(msetlst)
option remember;
local mset, res, ent, idxtrg, idx;

mset := convert(msetlst, `multiset`);

res := 1;

for ent in mset do
idx := pet_cycleind_symm(ent[1]);
idxtrg := pet_cycleind_symm(ent[2]);

res := res *
pet_cycleind_comp(idxtrg, idx);
od;

expand(res);
end;


GENF :=
proc(src, msetlst)
local vars, srcp, res, gf, term;

vars := add(A[q], q=1..nops(src));
srcp := mul(A[q]^src[q], q=1..nops(src));

gf := expand(pet_varinto_cind
(vars, pet_cycleind_mset(msetlst)));

if not type(gf, `+`) then
gf := [gf];
fi;

res := 0;

for term in gf do
if type(srcp/term, `polynom`) then
res := res + term;
fi;
od;

res;
end;


The syntax to compute ${mathrm{A}choose mathrm{B}}$ is documented
by the following examples:




> GENF([1,2,3,3], [2,3,4]);

2 3 3
87 A[1] A[2] A[3] A[4]

> GENF([1,2,3,3], [2,2,5]);

2 3 3
33 A[1] A[2] A[3] A[4]

> GENF([1,1,1,1], [2,2]);

3 A[1] A[2] A[3] A[4].


The last one is $frac{1}{2} {4choose 2}.$



Addendum. There is a slight improvement on this algorithm at the following MSE link.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    This is fantastic! I'm having some trouble understanding why this works, and specifically why this is a multiset of multisets, which I think is related to why we're itersting the cycle index of the symmetric group. What do you mean by a factorization of a multiset, and source multiset?
    $endgroup$
    – JJW5432
    Jul 26 '18 at 0:14










  • $begingroup$
    Thank you. The cycle index of the symmetric group implements the multiset operator in the symbolic method. Now your subsets are multisets and since we may choose them more than once we get multisets of multisets. The support of a multiset is a partition and in cycle indices these are usually written in factorized form, hence I chose to use this notation here as well.
    $endgroup$
    – Marko Riedel
    Jul 26 '18 at 9:22










  • $begingroup$
    For more information consult Wikipedia on the symbolic method.
    $endgroup$
    – Marko Riedel
    Jul 26 '18 at 9:31










  • $begingroup$
    I've read the first chapter of Flajolet and Sedgewick's "Analytic Combinatorics" on the symbolic method, so now I understand more about combinatorial classes and generator functions. Can you explain why the construction $$deftextsc#1{dosc#1csod} defdosc#1#2csod{{rm #1{small #2}}} textsc{MSET}_{=sigma_k} left(textsc{MSET}_{=k} left(sum_{k'=1}^l mathcal{A}_{k'}right)right)$$ is the correct one?
    $endgroup$
    – JJW5432
    Jul 28 '18 at 3:39










  • $begingroup$
    This part follows by inspection for the user of the symbolic method. I have added two examples to clarify the notation. The book by Harary and Palmer Graphical Enumeration is a useful reference for the nested cycle indices. I also checked my work using several enumeration routines for cycle indices and multisets.
    $endgroup$
    – Marko Riedel
    Jul 28 '18 at 12:50



















0












$begingroup$

I'm posting an implementation of Marko Riedel's algorithm in Sage because Sage is open source and widely available. It works on all the examples he posted, but for larger examples like $binom{49, 49, 1, 1}{10, 10, 10, 10, 10, 10, 10, 10, 10, 10}$ it's hanging.





#!/usr/bin/env sage

import sys
from sage.all import *

Sym = SymmetricFunctions(QQ)
p = Sym.powersum()

def sub_cycle_index(Zout, Zin):
"""Substitutes Zin into Zout to produce Zout evaluated at Zin.

This is accomplished by replacing p[i] in Zout with Zin, but with
every p[j] in Zin replaced with p[i*j].
"""

return p.sum(c * p.prod(Zin.frobenius(i) for i in mu) for mu, c in Zout)

def multiset_cycle_index(ms):
"""The cycle index of the given multiset, given by the formula

.. math:: prod_{{k}}left( Z(S_{sigma_k}; Z(S_k))right)

where :math:`{k}` are the elements of the multiset and
:math:`sigma_k` is the multiplicity of the element :math:`k`.
"""

Z = lambda i: SymmetricGroup(i).cycle_index()
return p.prod(sub_cycle_index(Z(sk), Z(k)) for k, sk in ms.items())

def list_to_multiset(els):
"""Converts a list of elements representing a multiset to a dictionary
where the keys are the elements of the multiset and the values are
the multiplicities.
"""

ms = {}
for x in els:
ms[x] = ms.get(x,0) + 1
return ms

def mset_choose(s, d):
"""Compute the "multiset coefficient" :math:`binom{s}{d}`."""

A = PolynomialRing(QQ, len(s), 'A').gens()
mono = prod(a^i for a, i in zip(A, s))
Z = multiset_cycle_index(list_to_multiset(d))
return Z.expand(len(A), A).coefficient(mono)

if __name__ == '__main__':
if len(sys.argv) != 3:
print("Usage: %s 's_1, s_2, ..' 'd_1, s_2, ..'" % sys.argv[0])
print("Outputs the number of ways the multiset s can be partitioned into multisets of sizes d_i.")
sys.exit(1)

s = map(int, sys.argv[1].split(' '))
d = map(int, sys.argv[2].split(' '))

if sum(s) != sum(d):
print("The sum of the elements of s must equal the sum of the elements of d")
sys.exit(1)

print(mset_choose(s, d))





share|cite|improve this answer









$endgroup$













    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856255%2fpartitioning-a-multiset-into-multisets-of-fixed-sizes%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    3





    +50







    $begingroup$

    It would appear that these are multisets of multisets which may be
    enumerated using the Polya Enumeration Theorem (PET). Let the multiset
    that is being drawn have factorization



    $$prod_{k=1}^m B_k^{sigma_{k}}$$



    where $k$ is the value of a term and $sigma_k$ the number of times it
    ocurs and recall that we have $l$ types of items forming the source
    multiset



    $$prod_{k=1}^l A_k^{tau_{k}}.$$



    The answer is then given by



    $$left[prod_{k=1}^l A_k^{tau_{k}}right]
    prod_{k=1}^m
    Zleft(S_{sigma_k};
    Zleft(S_k; sum_{k'=1}^l A_{k'}right)right).$$



    In terms of combinatorial classes we have made use of the unlabeled
    class



    $$deftextsc#1{dosc#1csod}
    defdosc#1#2csod{{rm #1{small #2}}}
    textsc{MSET}_{=sigma_k}
    left(textsc{MSET}_{=k}
    left(sum_{k'=1}^l mathcal{A}_{k'}right)right).$$



    As an example for ${2,2choose 1,1,2} = 3$ we get



    $$textsc{MSET}_{=2}
    (textsc{MSET}_{=1}(mathcal{A_1}+mathcal{A}_2))
    times textsc{MSET}_{=1}
    (textsc{MSET}_{=2}(mathcal{A_1}+mathcal{A}_2)).$$



    As an additional example we find for ${2,2,4choose 1,1,3,3} = 16$



    $$textsc{MSET}_{=2}
    (textsc{MSET}_{=1}(mathcal{A_1}+mathcal{A}_2+mathcal{A}_3))
    times textsc{MSET}_{=2}
    (textsc{MSET}_{=3}(mathcal{A_1}+mathcal{A}_2+mathcal{A}_3)).$$



    Here we have used the cycle index of the symmetric group $Z(S_n)$,
    which is computed from the recurrence by Lovasz which says that



    $$Z(S_n) = frac{1}{n} sum_{l=1}^n a_l Z(S_{n-l})
    quadtext{where}quad
    Z(S_0) = 1.$$



    For this to be effective we need to compute the iterated cycle index
    when $Z(S_k)$ is substituted into $Z(S_{sigma_k}).$ This is
    accomplished with the substitution rule for substitution of the former
    into the latter:



    $$a_q = Z(S_k;; a_1=a_q, ; a_2=a_{2q}, ; a_3=a_{3q}, ; ldots).$$



    We have used the notation $Z(S_k; F)$ for substitution of a generating
    function and on the previous line, the notation for substitution into
    the variables of the cycle index. This is in fact all we need and we
    can start computing some of these multiset coefficients. For example
    we find for the example given by OP the cycle index



    $$Z(B_1^2 B_2) =
    1/4,{a_{{1}}}^{4}+1/2,{a_{{1}}}^{2}a_{{2}}+1/4,{a_{{2}}}^{2}.$$



    Continuing with the example we get



    $$Z(B_1^2 B_2; A_1+A_2) =
    1/4, left( A_{{1}}+A_{{2}} right) ^{4}
    +1/2, left( A_{{1}}+A_{{2}} right) ^{2}
    left( {A_{{1}}}^{2}+{A_{{2}}}^{2} right)
    \ +1/4, left( {A_{{1}}}^{2}+{A_{{2}}}^{2}
    right) ^{2} \ = {A_{{1}}}^{4}+2,{A_{{1}}}^{3}A_{{2}}
    +3,{A_{{1}}}^{2}{A_{{2}}}^{2}+2,A_{{1}}{A_{{2}}
    }^{3}+{A_{{2}}}^{4}$$



    and we confirm the value $3$ obtained by OP. This algorithm will make
    it possible to compute cycle indices not obtainable by enumeration. As
    an extra example we find the following excerpt from the cycle index
    for $[2,2,2,3,5,5]:$



    $$Z(B_2^3 B_3 B_5^2) = ldots
    +{frac {11,{a_{{1}}}^{8}a_{{2}}a_{{4}}a_{{5}}}{7200}}
    +{frac {49,{a_{{1}}}^{7}{a_{{2}}}^{2}a_{{3}}a_{{5}}}{14400}}
    \ +{frac {5,{a_{{1}}}^{7} a_{{2}}{a_{{3}}}^{2}a_{{4}}}{1152}}
    +{frac {1021,{a_{{1}}}^{6}{a_{{2}}}^{3}a_{{3}}a_{{4}}}{69120}}
    +{frac {43,{a_{{1}}}^{7}a_{{2}}a_{{4}}a_{{6}}}{17280}}+ldots$$



    Here are some additional values that may assist the reader who is
    investigating this problem to verify the results of their approach:



    $${1,3,3choose 3,4} = 7, ;
    {2,3,3choose 4,4} = 5, ;
    {2,3,3choose 2,2,4} = 16
    quadtext{and}quad
    {1,2,3,3choose 2,3,4} = 87.$$



    The Maple code for this problem was as follows.




    with(combinat);


    pet_cycleind_symm :=
    proc(n)
    option remember;

    if n=0 then return 1; fi;

    expand(1/n*
    add(a[l]*pet_cycleind_symm(n-l), l=1..n));
    end;

    pet_varinto_cind :=
    proc(poly, ind)
    local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
    pot := op(1, v);

    subs1 :=
    [seq(polyvars[k]=polyvars[k]^pot,
    k=1..nops(polyvars))];

    subs2 := [v=subs(subs1, poly)];

    res := subs(subs2, res);
    od;

    res;
    end;

    pet_cycleind_comp :=
    proc(idxtrg, idx)
    local varstrg, vars, vt, sbstrg, sbs, len;

    varstrg := indets(idxtrg);
    vars := indets(idx);

    sbstrg := ;

    for vt in varstrg do
    len := op(1, vt);

    sbs :=
    [seq(v = a[op(1, v)*len], v in vars)];

    sbstrg :=
    [op(sbstrg),
    a[len] = subs(sbs, idx)];
    od;

    expand(subs(sbstrg, idxtrg));
    end;

    pet_cycleind_mset :=
    proc(msetlst)
    option remember;
    local mset, res, ent, idxtrg, idx;

    mset := convert(msetlst, `multiset`);

    res := 1;

    for ent in mset do
    idx := pet_cycleind_symm(ent[1]);
    idxtrg := pet_cycleind_symm(ent[2]);

    res := res *
    pet_cycleind_comp(idxtrg, idx);
    od;

    expand(res);
    end;


    GENF :=
    proc(src, msetlst)
    local vars, srcp, res, gf, term;

    vars := add(A[q], q=1..nops(src));
    srcp := mul(A[q]^src[q], q=1..nops(src));

    gf := expand(pet_varinto_cind
    (vars, pet_cycleind_mset(msetlst)));

    if not type(gf, `+`) then
    gf := [gf];
    fi;

    res := 0;

    for term in gf do
    if type(srcp/term, `polynom`) then
    res := res + term;
    fi;
    od;

    res;
    end;


    The syntax to compute ${mathrm{A}choose mathrm{B}}$ is documented
    by the following examples:




    > GENF([1,2,3,3], [2,3,4]);

    2 3 3
    87 A[1] A[2] A[3] A[4]

    > GENF([1,2,3,3], [2,2,5]);

    2 3 3
    33 A[1] A[2] A[3] A[4]

    > GENF([1,1,1,1], [2,2]);

    3 A[1] A[2] A[3] A[4].


    The last one is $frac{1}{2} {4choose 2}.$



    Addendum. There is a slight improvement on this algorithm at the following MSE link.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      This is fantastic! I'm having some trouble understanding why this works, and specifically why this is a multiset of multisets, which I think is related to why we're itersting the cycle index of the symmetric group. What do you mean by a factorization of a multiset, and source multiset?
      $endgroup$
      – JJW5432
      Jul 26 '18 at 0:14










    • $begingroup$
      Thank you. The cycle index of the symmetric group implements the multiset operator in the symbolic method. Now your subsets are multisets and since we may choose them more than once we get multisets of multisets. The support of a multiset is a partition and in cycle indices these are usually written in factorized form, hence I chose to use this notation here as well.
      $endgroup$
      – Marko Riedel
      Jul 26 '18 at 9:22










    • $begingroup$
      For more information consult Wikipedia on the symbolic method.
      $endgroup$
      – Marko Riedel
      Jul 26 '18 at 9:31










    • $begingroup$
      I've read the first chapter of Flajolet and Sedgewick's "Analytic Combinatorics" on the symbolic method, so now I understand more about combinatorial classes and generator functions. Can you explain why the construction $$deftextsc#1{dosc#1csod} defdosc#1#2csod{{rm #1{small #2}}} textsc{MSET}_{=sigma_k} left(textsc{MSET}_{=k} left(sum_{k'=1}^l mathcal{A}_{k'}right)right)$$ is the correct one?
      $endgroup$
      – JJW5432
      Jul 28 '18 at 3:39










    • $begingroup$
      This part follows by inspection for the user of the symbolic method. I have added two examples to clarify the notation. The book by Harary and Palmer Graphical Enumeration is a useful reference for the nested cycle indices. I also checked my work using several enumeration routines for cycle indices and multisets.
      $endgroup$
      – Marko Riedel
      Jul 28 '18 at 12:50
















    3





    +50







    $begingroup$

    It would appear that these are multisets of multisets which may be
    enumerated using the Polya Enumeration Theorem (PET). Let the multiset
    that is being drawn have factorization



    $$prod_{k=1}^m B_k^{sigma_{k}}$$



    where $k$ is the value of a term and $sigma_k$ the number of times it
    ocurs and recall that we have $l$ types of items forming the source
    multiset



    $$prod_{k=1}^l A_k^{tau_{k}}.$$



    The answer is then given by



    $$left[prod_{k=1}^l A_k^{tau_{k}}right]
    prod_{k=1}^m
    Zleft(S_{sigma_k};
    Zleft(S_k; sum_{k'=1}^l A_{k'}right)right).$$



    In terms of combinatorial classes we have made use of the unlabeled
    class



    $$deftextsc#1{dosc#1csod}
    defdosc#1#2csod{{rm #1{small #2}}}
    textsc{MSET}_{=sigma_k}
    left(textsc{MSET}_{=k}
    left(sum_{k'=1}^l mathcal{A}_{k'}right)right).$$



    As an example for ${2,2choose 1,1,2} = 3$ we get



    $$textsc{MSET}_{=2}
    (textsc{MSET}_{=1}(mathcal{A_1}+mathcal{A}_2))
    times textsc{MSET}_{=1}
    (textsc{MSET}_{=2}(mathcal{A_1}+mathcal{A}_2)).$$



    As an additional example we find for ${2,2,4choose 1,1,3,3} = 16$



    $$textsc{MSET}_{=2}
    (textsc{MSET}_{=1}(mathcal{A_1}+mathcal{A}_2+mathcal{A}_3))
    times textsc{MSET}_{=2}
    (textsc{MSET}_{=3}(mathcal{A_1}+mathcal{A}_2+mathcal{A}_3)).$$



    Here we have used the cycle index of the symmetric group $Z(S_n)$,
    which is computed from the recurrence by Lovasz which says that



    $$Z(S_n) = frac{1}{n} sum_{l=1}^n a_l Z(S_{n-l})
    quadtext{where}quad
    Z(S_0) = 1.$$



    For this to be effective we need to compute the iterated cycle index
    when $Z(S_k)$ is substituted into $Z(S_{sigma_k}).$ This is
    accomplished with the substitution rule for substitution of the former
    into the latter:



    $$a_q = Z(S_k;; a_1=a_q, ; a_2=a_{2q}, ; a_3=a_{3q}, ; ldots).$$



    We have used the notation $Z(S_k; F)$ for substitution of a generating
    function and on the previous line, the notation for substitution into
    the variables of the cycle index. This is in fact all we need and we
    can start computing some of these multiset coefficients. For example
    we find for the example given by OP the cycle index



    $$Z(B_1^2 B_2) =
    1/4,{a_{{1}}}^{4}+1/2,{a_{{1}}}^{2}a_{{2}}+1/4,{a_{{2}}}^{2}.$$



    Continuing with the example we get



    $$Z(B_1^2 B_2; A_1+A_2) =
    1/4, left( A_{{1}}+A_{{2}} right) ^{4}
    +1/2, left( A_{{1}}+A_{{2}} right) ^{2}
    left( {A_{{1}}}^{2}+{A_{{2}}}^{2} right)
    \ +1/4, left( {A_{{1}}}^{2}+{A_{{2}}}^{2}
    right) ^{2} \ = {A_{{1}}}^{4}+2,{A_{{1}}}^{3}A_{{2}}
    +3,{A_{{1}}}^{2}{A_{{2}}}^{2}+2,A_{{1}}{A_{{2}}
    }^{3}+{A_{{2}}}^{4}$$



    and we confirm the value $3$ obtained by OP. This algorithm will make
    it possible to compute cycle indices not obtainable by enumeration. As
    an extra example we find the following excerpt from the cycle index
    for $[2,2,2,3,5,5]:$



    $$Z(B_2^3 B_3 B_5^2) = ldots
    +{frac {11,{a_{{1}}}^{8}a_{{2}}a_{{4}}a_{{5}}}{7200}}
    +{frac {49,{a_{{1}}}^{7}{a_{{2}}}^{2}a_{{3}}a_{{5}}}{14400}}
    \ +{frac {5,{a_{{1}}}^{7} a_{{2}}{a_{{3}}}^{2}a_{{4}}}{1152}}
    +{frac {1021,{a_{{1}}}^{6}{a_{{2}}}^{3}a_{{3}}a_{{4}}}{69120}}
    +{frac {43,{a_{{1}}}^{7}a_{{2}}a_{{4}}a_{{6}}}{17280}}+ldots$$



    Here are some additional values that may assist the reader who is
    investigating this problem to verify the results of their approach:



    $${1,3,3choose 3,4} = 7, ;
    {2,3,3choose 4,4} = 5, ;
    {2,3,3choose 2,2,4} = 16
    quadtext{and}quad
    {1,2,3,3choose 2,3,4} = 87.$$



    The Maple code for this problem was as follows.




    with(combinat);


    pet_cycleind_symm :=
    proc(n)
    option remember;

    if n=0 then return 1; fi;

    expand(1/n*
    add(a[l]*pet_cycleind_symm(n-l), l=1..n));
    end;

    pet_varinto_cind :=
    proc(poly, ind)
    local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
    pot := op(1, v);

    subs1 :=
    [seq(polyvars[k]=polyvars[k]^pot,
    k=1..nops(polyvars))];

    subs2 := [v=subs(subs1, poly)];

    res := subs(subs2, res);
    od;

    res;
    end;

    pet_cycleind_comp :=
    proc(idxtrg, idx)
    local varstrg, vars, vt, sbstrg, sbs, len;

    varstrg := indets(idxtrg);
    vars := indets(idx);

    sbstrg := ;

    for vt in varstrg do
    len := op(1, vt);

    sbs :=
    [seq(v = a[op(1, v)*len], v in vars)];

    sbstrg :=
    [op(sbstrg),
    a[len] = subs(sbs, idx)];
    od;

    expand(subs(sbstrg, idxtrg));
    end;

    pet_cycleind_mset :=
    proc(msetlst)
    option remember;
    local mset, res, ent, idxtrg, idx;

    mset := convert(msetlst, `multiset`);

    res := 1;

    for ent in mset do
    idx := pet_cycleind_symm(ent[1]);
    idxtrg := pet_cycleind_symm(ent[2]);

    res := res *
    pet_cycleind_comp(idxtrg, idx);
    od;

    expand(res);
    end;


    GENF :=
    proc(src, msetlst)
    local vars, srcp, res, gf, term;

    vars := add(A[q], q=1..nops(src));
    srcp := mul(A[q]^src[q], q=1..nops(src));

    gf := expand(pet_varinto_cind
    (vars, pet_cycleind_mset(msetlst)));

    if not type(gf, `+`) then
    gf := [gf];
    fi;

    res := 0;

    for term in gf do
    if type(srcp/term, `polynom`) then
    res := res + term;
    fi;
    od;

    res;
    end;


    The syntax to compute ${mathrm{A}choose mathrm{B}}$ is documented
    by the following examples:




    > GENF([1,2,3,3], [2,3,4]);

    2 3 3
    87 A[1] A[2] A[3] A[4]

    > GENF([1,2,3,3], [2,2,5]);

    2 3 3
    33 A[1] A[2] A[3] A[4]

    > GENF([1,1,1,1], [2,2]);

    3 A[1] A[2] A[3] A[4].


    The last one is $frac{1}{2} {4choose 2}.$



    Addendum. There is a slight improvement on this algorithm at the following MSE link.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      This is fantastic! I'm having some trouble understanding why this works, and specifically why this is a multiset of multisets, which I think is related to why we're itersting the cycle index of the symmetric group. What do you mean by a factorization of a multiset, and source multiset?
      $endgroup$
      – JJW5432
      Jul 26 '18 at 0:14










    • $begingroup$
      Thank you. The cycle index of the symmetric group implements the multiset operator in the symbolic method. Now your subsets are multisets and since we may choose them more than once we get multisets of multisets. The support of a multiset is a partition and in cycle indices these are usually written in factorized form, hence I chose to use this notation here as well.
      $endgroup$
      – Marko Riedel
      Jul 26 '18 at 9:22










    • $begingroup$
      For more information consult Wikipedia on the symbolic method.
      $endgroup$
      – Marko Riedel
      Jul 26 '18 at 9:31










    • $begingroup$
      I've read the first chapter of Flajolet and Sedgewick's "Analytic Combinatorics" on the symbolic method, so now I understand more about combinatorial classes and generator functions. Can you explain why the construction $$deftextsc#1{dosc#1csod} defdosc#1#2csod{{rm #1{small #2}}} textsc{MSET}_{=sigma_k} left(textsc{MSET}_{=k} left(sum_{k'=1}^l mathcal{A}_{k'}right)right)$$ is the correct one?
      $endgroup$
      – JJW5432
      Jul 28 '18 at 3:39










    • $begingroup$
      This part follows by inspection for the user of the symbolic method. I have added two examples to clarify the notation. The book by Harary and Palmer Graphical Enumeration is a useful reference for the nested cycle indices. I also checked my work using several enumeration routines for cycle indices and multisets.
      $endgroup$
      – Marko Riedel
      Jul 28 '18 at 12:50














    3





    +50







    3





    +50



    3




    +50



    $begingroup$

    It would appear that these are multisets of multisets which may be
    enumerated using the Polya Enumeration Theorem (PET). Let the multiset
    that is being drawn have factorization



    $$prod_{k=1}^m B_k^{sigma_{k}}$$



    where $k$ is the value of a term and $sigma_k$ the number of times it
    ocurs and recall that we have $l$ types of items forming the source
    multiset



    $$prod_{k=1}^l A_k^{tau_{k}}.$$



    The answer is then given by



    $$left[prod_{k=1}^l A_k^{tau_{k}}right]
    prod_{k=1}^m
    Zleft(S_{sigma_k};
    Zleft(S_k; sum_{k'=1}^l A_{k'}right)right).$$



    In terms of combinatorial classes we have made use of the unlabeled
    class



    $$deftextsc#1{dosc#1csod}
    defdosc#1#2csod{{rm #1{small #2}}}
    textsc{MSET}_{=sigma_k}
    left(textsc{MSET}_{=k}
    left(sum_{k'=1}^l mathcal{A}_{k'}right)right).$$



    As an example for ${2,2choose 1,1,2} = 3$ we get



    $$textsc{MSET}_{=2}
    (textsc{MSET}_{=1}(mathcal{A_1}+mathcal{A}_2))
    times textsc{MSET}_{=1}
    (textsc{MSET}_{=2}(mathcal{A_1}+mathcal{A}_2)).$$



    As an additional example we find for ${2,2,4choose 1,1,3,3} = 16$



    $$textsc{MSET}_{=2}
    (textsc{MSET}_{=1}(mathcal{A_1}+mathcal{A}_2+mathcal{A}_3))
    times textsc{MSET}_{=2}
    (textsc{MSET}_{=3}(mathcal{A_1}+mathcal{A}_2+mathcal{A}_3)).$$



    Here we have used the cycle index of the symmetric group $Z(S_n)$,
    which is computed from the recurrence by Lovasz which says that



    $$Z(S_n) = frac{1}{n} sum_{l=1}^n a_l Z(S_{n-l})
    quadtext{where}quad
    Z(S_0) = 1.$$



    For this to be effective we need to compute the iterated cycle index
    when $Z(S_k)$ is substituted into $Z(S_{sigma_k}).$ This is
    accomplished with the substitution rule for substitution of the former
    into the latter:



    $$a_q = Z(S_k;; a_1=a_q, ; a_2=a_{2q}, ; a_3=a_{3q}, ; ldots).$$



    We have used the notation $Z(S_k; F)$ for substitution of a generating
    function and on the previous line, the notation for substitution into
    the variables of the cycle index. This is in fact all we need and we
    can start computing some of these multiset coefficients. For example
    we find for the example given by OP the cycle index



    $$Z(B_1^2 B_2) =
    1/4,{a_{{1}}}^{4}+1/2,{a_{{1}}}^{2}a_{{2}}+1/4,{a_{{2}}}^{2}.$$



    Continuing with the example we get



    $$Z(B_1^2 B_2; A_1+A_2) =
    1/4, left( A_{{1}}+A_{{2}} right) ^{4}
    +1/2, left( A_{{1}}+A_{{2}} right) ^{2}
    left( {A_{{1}}}^{2}+{A_{{2}}}^{2} right)
    \ +1/4, left( {A_{{1}}}^{2}+{A_{{2}}}^{2}
    right) ^{2} \ = {A_{{1}}}^{4}+2,{A_{{1}}}^{3}A_{{2}}
    +3,{A_{{1}}}^{2}{A_{{2}}}^{2}+2,A_{{1}}{A_{{2}}
    }^{3}+{A_{{2}}}^{4}$$



    and we confirm the value $3$ obtained by OP. This algorithm will make
    it possible to compute cycle indices not obtainable by enumeration. As
    an extra example we find the following excerpt from the cycle index
    for $[2,2,2,3,5,5]:$



    $$Z(B_2^3 B_3 B_5^2) = ldots
    +{frac {11,{a_{{1}}}^{8}a_{{2}}a_{{4}}a_{{5}}}{7200}}
    +{frac {49,{a_{{1}}}^{7}{a_{{2}}}^{2}a_{{3}}a_{{5}}}{14400}}
    \ +{frac {5,{a_{{1}}}^{7} a_{{2}}{a_{{3}}}^{2}a_{{4}}}{1152}}
    +{frac {1021,{a_{{1}}}^{6}{a_{{2}}}^{3}a_{{3}}a_{{4}}}{69120}}
    +{frac {43,{a_{{1}}}^{7}a_{{2}}a_{{4}}a_{{6}}}{17280}}+ldots$$



    Here are some additional values that may assist the reader who is
    investigating this problem to verify the results of their approach:



    $${1,3,3choose 3,4} = 7, ;
    {2,3,3choose 4,4} = 5, ;
    {2,3,3choose 2,2,4} = 16
    quadtext{and}quad
    {1,2,3,3choose 2,3,4} = 87.$$



    The Maple code for this problem was as follows.




    with(combinat);


    pet_cycleind_symm :=
    proc(n)
    option remember;

    if n=0 then return 1; fi;

    expand(1/n*
    add(a[l]*pet_cycleind_symm(n-l), l=1..n));
    end;

    pet_varinto_cind :=
    proc(poly, ind)
    local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
    pot := op(1, v);

    subs1 :=
    [seq(polyvars[k]=polyvars[k]^pot,
    k=1..nops(polyvars))];

    subs2 := [v=subs(subs1, poly)];

    res := subs(subs2, res);
    od;

    res;
    end;

    pet_cycleind_comp :=
    proc(idxtrg, idx)
    local varstrg, vars, vt, sbstrg, sbs, len;

    varstrg := indets(idxtrg);
    vars := indets(idx);

    sbstrg := ;

    for vt in varstrg do
    len := op(1, vt);

    sbs :=
    [seq(v = a[op(1, v)*len], v in vars)];

    sbstrg :=
    [op(sbstrg),
    a[len] = subs(sbs, idx)];
    od;

    expand(subs(sbstrg, idxtrg));
    end;

    pet_cycleind_mset :=
    proc(msetlst)
    option remember;
    local mset, res, ent, idxtrg, idx;

    mset := convert(msetlst, `multiset`);

    res := 1;

    for ent in mset do
    idx := pet_cycleind_symm(ent[1]);
    idxtrg := pet_cycleind_symm(ent[2]);

    res := res *
    pet_cycleind_comp(idxtrg, idx);
    od;

    expand(res);
    end;


    GENF :=
    proc(src, msetlst)
    local vars, srcp, res, gf, term;

    vars := add(A[q], q=1..nops(src));
    srcp := mul(A[q]^src[q], q=1..nops(src));

    gf := expand(pet_varinto_cind
    (vars, pet_cycleind_mset(msetlst)));

    if not type(gf, `+`) then
    gf := [gf];
    fi;

    res := 0;

    for term in gf do
    if type(srcp/term, `polynom`) then
    res := res + term;
    fi;
    od;

    res;
    end;


    The syntax to compute ${mathrm{A}choose mathrm{B}}$ is documented
    by the following examples:




    > GENF([1,2,3,3], [2,3,4]);

    2 3 3
    87 A[1] A[2] A[3] A[4]

    > GENF([1,2,3,3], [2,2,5]);

    2 3 3
    33 A[1] A[2] A[3] A[4]

    > GENF([1,1,1,1], [2,2]);

    3 A[1] A[2] A[3] A[4].


    The last one is $frac{1}{2} {4choose 2}.$



    Addendum. There is a slight improvement on this algorithm at the following MSE link.






    share|cite|improve this answer











    $endgroup$



    It would appear that these are multisets of multisets which may be
    enumerated using the Polya Enumeration Theorem (PET). Let the multiset
    that is being drawn have factorization



    $$prod_{k=1}^m B_k^{sigma_{k}}$$



    where $k$ is the value of a term and $sigma_k$ the number of times it
    ocurs and recall that we have $l$ types of items forming the source
    multiset



    $$prod_{k=1}^l A_k^{tau_{k}}.$$



    The answer is then given by



    $$left[prod_{k=1}^l A_k^{tau_{k}}right]
    prod_{k=1}^m
    Zleft(S_{sigma_k};
    Zleft(S_k; sum_{k'=1}^l A_{k'}right)right).$$



    In terms of combinatorial classes we have made use of the unlabeled
    class



    $$deftextsc#1{dosc#1csod}
    defdosc#1#2csod{{rm #1{small #2}}}
    textsc{MSET}_{=sigma_k}
    left(textsc{MSET}_{=k}
    left(sum_{k'=1}^l mathcal{A}_{k'}right)right).$$



    As an example for ${2,2choose 1,1,2} = 3$ we get



    $$textsc{MSET}_{=2}
    (textsc{MSET}_{=1}(mathcal{A_1}+mathcal{A}_2))
    times textsc{MSET}_{=1}
    (textsc{MSET}_{=2}(mathcal{A_1}+mathcal{A}_2)).$$



    As an additional example we find for ${2,2,4choose 1,1,3,3} = 16$



    $$textsc{MSET}_{=2}
    (textsc{MSET}_{=1}(mathcal{A_1}+mathcal{A}_2+mathcal{A}_3))
    times textsc{MSET}_{=2}
    (textsc{MSET}_{=3}(mathcal{A_1}+mathcal{A}_2+mathcal{A}_3)).$$



    Here we have used the cycle index of the symmetric group $Z(S_n)$,
    which is computed from the recurrence by Lovasz which says that



    $$Z(S_n) = frac{1}{n} sum_{l=1}^n a_l Z(S_{n-l})
    quadtext{where}quad
    Z(S_0) = 1.$$



    For this to be effective we need to compute the iterated cycle index
    when $Z(S_k)$ is substituted into $Z(S_{sigma_k}).$ This is
    accomplished with the substitution rule for substitution of the former
    into the latter:



    $$a_q = Z(S_k;; a_1=a_q, ; a_2=a_{2q}, ; a_3=a_{3q}, ; ldots).$$



    We have used the notation $Z(S_k; F)$ for substitution of a generating
    function and on the previous line, the notation for substitution into
    the variables of the cycle index. This is in fact all we need and we
    can start computing some of these multiset coefficients. For example
    we find for the example given by OP the cycle index



    $$Z(B_1^2 B_2) =
    1/4,{a_{{1}}}^{4}+1/2,{a_{{1}}}^{2}a_{{2}}+1/4,{a_{{2}}}^{2}.$$



    Continuing with the example we get



    $$Z(B_1^2 B_2; A_1+A_2) =
    1/4, left( A_{{1}}+A_{{2}} right) ^{4}
    +1/2, left( A_{{1}}+A_{{2}} right) ^{2}
    left( {A_{{1}}}^{2}+{A_{{2}}}^{2} right)
    \ +1/4, left( {A_{{1}}}^{2}+{A_{{2}}}^{2}
    right) ^{2} \ = {A_{{1}}}^{4}+2,{A_{{1}}}^{3}A_{{2}}
    +3,{A_{{1}}}^{2}{A_{{2}}}^{2}+2,A_{{1}}{A_{{2}}
    }^{3}+{A_{{2}}}^{4}$$



    and we confirm the value $3$ obtained by OP. This algorithm will make
    it possible to compute cycle indices not obtainable by enumeration. As
    an extra example we find the following excerpt from the cycle index
    for $[2,2,2,3,5,5]:$



    $$Z(B_2^3 B_3 B_5^2) = ldots
    +{frac {11,{a_{{1}}}^{8}a_{{2}}a_{{4}}a_{{5}}}{7200}}
    +{frac {49,{a_{{1}}}^{7}{a_{{2}}}^{2}a_{{3}}a_{{5}}}{14400}}
    \ +{frac {5,{a_{{1}}}^{7} a_{{2}}{a_{{3}}}^{2}a_{{4}}}{1152}}
    +{frac {1021,{a_{{1}}}^{6}{a_{{2}}}^{3}a_{{3}}a_{{4}}}{69120}}
    +{frac {43,{a_{{1}}}^{7}a_{{2}}a_{{4}}a_{{6}}}{17280}}+ldots$$



    Here are some additional values that may assist the reader who is
    investigating this problem to verify the results of their approach:



    $${1,3,3choose 3,4} = 7, ;
    {2,3,3choose 4,4} = 5, ;
    {2,3,3choose 2,2,4} = 16
    quadtext{and}quad
    {1,2,3,3choose 2,3,4} = 87.$$



    The Maple code for this problem was as follows.




    with(combinat);


    pet_cycleind_symm :=
    proc(n)
    option remember;

    if n=0 then return 1; fi;

    expand(1/n*
    add(a[l]*pet_cycleind_symm(n-l), l=1..n));
    end;

    pet_varinto_cind :=
    proc(poly, ind)
    local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
    pot := op(1, v);

    subs1 :=
    [seq(polyvars[k]=polyvars[k]^pot,
    k=1..nops(polyvars))];

    subs2 := [v=subs(subs1, poly)];

    res := subs(subs2, res);
    od;

    res;
    end;

    pet_cycleind_comp :=
    proc(idxtrg, idx)
    local varstrg, vars, vt, sbstrg, sbs, len;

    varstrg := indets(idxtrg);
    vars := indets(idx);

    sbstrg := ;

    for vt in varstrg do
    len := op(1, vt);

    sbs :=
    [seq(v = a[op(1, v)*len], v in vars)];

    sbstrg :=
    [op(sbstrg),
    a[len] = subs(sbs, idx)];
    od;

    expand(subs(sbstrg, idxtrg));
    end;

    pet_cycleind_mset :=
    proc(msetlst)
    option remember;
    local mset, res, ent, idxtrg, idx;

    mset := convert(msetlst, `multiset`);

    res := 1;

    for ent in mset do
    idx := pet_cycleind_symm(ent[1]);
    idxtrg := pet_cycleind_symm(ent[2]);

    res := res *
    pet_cycleind_comp(idxtrg, idx);
    od;

    expand(res);
    end;


    GENF :=
    proc(src, msetlst)
    local vars, srcp, res, gf, term;

    vars := add(A[q], q=1..nops(src));
    srcp := mul(A[q]^src[q], q=1..nops(src));

    gf := expand(pet_varinto_cind
    (vars, pet_cycleind_mset(msetlst)));

    if not type(gf, `+`) then
    gf := [gf];
    fi;

    res := 0;

    for term in gf do
    if type(srcp/term, `polynom`) then
    res := res + term;
    fi;
    od;

    res;
    end;


    The syntax to compute ${mathrm{A}choose mathrm{B}}$ is documented
    by the following examples:




    > GENF([1,2,3,3], [2,3,4]);

    2 3 3
    87 A[1] A[2] A[3] A[4]

    > GENF([1,2,3,3], [2,2,5]);

    2 3 3
    33 A[1] A[2] A[3] A[4]

    > GENF([1,1,1,1], [2,2]);

    3 A[1] A[2] A[3] A[4].


    The last one is $frac{1}{2} {4choose 2}.$



    Addendum. There is a slight improvement on this algorithm at the following MSE link.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Jan 25 at 22:56

























    answered Jul 25 '18 at 15:12









    Marko RiedelMarko Riedel

    40.6k339110




    40.6k339110












    • $begingroup$
      This is fantastic! I'm having some trouble understanding why this works, and specifically why this is a multiset of multisets, which I think is related to why we're itersting the cycle index of the symmetric group. What do you mean by a factorization of a multiset, and source multiset?
      $endgroup$
      – JJW5432
      Jul 26 '18 at 0:14










    • $begingroup$
      Thank you. The cycle index of the symmetric group implements the multiset operator in the symbolic method. Now your subsets are multisets and since we may choose them more than once we get multisets of multisets. The support of a multiset is a partition and in cycle indices these are usually written in factorized form, hence I chose to use this notation here as well.
      $endgroup$
      – Marko Riedel
      Jul 26 '18 at 9:22










    • $begingroup$
      For more information consult Wikipedia on the symbolic method.
      $endgroup$
      – Marko Riedel
      Jul 26 '18 at 9:31










    • $begingroup$
      I've read the first chapter of Flajolet and Sedgewick's "Analytic Combinatorics" on the symbolic method, so now I understand more about combinatorial classes and generator functions. Can you explain why the construction $$deftextsc#1{dosc#1csod} defdosc#1#2csod{{rm #1{small #2}}} textsc{MSET}_{=sigma_k} left(textsc{MSET}_{=k} left(sum_{k'=1}^l mathcal{A}_{k'}right)right)$$ is the correct one?
      $endgroup$
      – JJW5432
      Jul 28 '18 at 3:39










    • $begingroup$
      This part follows by inspection for the user of the symbolic method. I have added two examples to clarify the notation. The book by Harary and Palmer Graphical Enumeration is a useful reference for the nested cycle indices. I also checked my work using several enumeration routines for cycle indices and multisets.
      $endgroup$
      – Marko Riedel
      Jul 28 '18 at 12:50


















    • $begingroup$
      This is fantastic! I'm having some trouble understanding why this works, and specifically why this is a multiset of multisets, which I think is related to why we're itersting the cycle index of the symmetric group. What do you mean by a factorization of a multiset, and source multiset?
      $endgroup$
      – JJW5432
      Jul 26 '18 at 0:14










    • $begingroup$
      Thank you. The cycle index of the symmetric group implements the multiset operator in the symbolic method. Now your subsets are multisets and since we may choose them more than once we get multisets of multisets. The support of a multiset is a partition and in cycle indices these are usually written in factorized form, hence I chose to use this notation here as well.
      $endgroup$
      – Marko Riedel
      Jul 26 '18 at 9:22










    • $begingroup$
      For more information consult Wikipedia on the symbolic method.
      $endgroup$
      – Marko Riedel
      Jul 26 '18 at 9:31










    • $begingroup$
      I've read the first chapter of Flajolet and Sedgewick's "Analytic Combinatorics" on the symbolic method, so now I understand more about combinatorial classes and generator functions. Can you explain why the construction $$deftextsc#1{dosc#1csod} defdosc#1#2csod{{rm #1{small #2}}} textsc{MSET}_{=sigma_k} left(textsc{MSET}_{=k} left(sum_{k'=1}^l mathcal{A}_{k'}right)right)$$ is the correct one?
      $endgroup$
      – JJW5432
      Jul 28 '18 at 3:39










    • $begingroup$
      This part follows by inspection for the user of the symbolic method. I have added two examples to clarify the notation. The book by Harary and Palmer Graphical Enumeration is a useful reference for the nested cycle indices. I also checked my work using several enumeration routines for cycle indices and multisets.
      $endgroup$
      – Marko Riedel
      Jul 28 '18 at 12:50
















    $begingroup$
    This is fantastic! I'm having some trouble understanding why this works, and specifically why this is a multiset of multisets, which I think is related to why we're itersting the cycle index of the symmetric group. What do you mean by a factorization of a multiset, and source multiset?
    $endgroup$
    – JJW5432
    Jul 26 '18 at 0:14




    $begingroup$
    This is fantastic! I'm having some trouble understanding why this works, and specifically why this is a multiset of multisets, which I think is related to why we're itersting the cycle index of the symmetric group. What do you mean by a factorization of a multiset, and source multiset?
    $endgroup$
    – JJW5432
    Jul 26 '18 at 0:14












    $begingroup$
    Thank you. The cycle index of the symmetric group implements the multiset operator in the symbolic method. Now your subsets are multisets and since we may choose them more than once we get multisets of multisets. The support of a multiset is a partition and in cycle indices these are usually written in factorized form, hence I chose to use this notation here as well.
    $endgroup$
    – Marko Riedel
    Jul 26 '18 at 9:22




    $begingroup$
    Thank you. The cycle index of the symmetric group implements the multiset operator in the symbolic method. Now your subsets are multisets and since we may choose them more than once we get multisets of multisets. The support of a multiset is a partition and in cycle indices these are usually written in factorized form, hence I chose to use this notation here as well.
    $endgroup$
    – Marko Riedel
    Jul 26 '18 at 9:22












    $begingroup$
    For more information consult Wikipedia on the symbolic method.
    $endgroup$
    – Marko Riedel
    Jul 26 '18 at 9:31




    $begingroup$
    For more information consult Wikipedia on the symbolic method.
    $endgroup$
    – Marko Riedel
    Jul 26 '18 at 9:31












    $begingroup$
    I've read the first chapter of Flajolet and Sedgewick's "Analytic Combinatorics" on the symbolic method, so now I understand more about combinatorial classes and generator functions. Can you explain why the construction $$deftextsc#1{dosc#1csod} defdosc#1#2csod{{rm #1{small #2}}} textsc{MSET}_{=sigma_k} left(textsc{MSET}_{=k} left(sum_{k'=1}^l mathcal{A}_{k'}right)right)$$ is the correct one?
    $endgroup$
    – JJW5432
    Jul 28 '18 at 3:39




    $begingroup$
    I've read the first chapter of Flajolet and Sedgewick's "Analytic Combinatorics" on the symbolic method, so now I understand more about combinatorial classes and generator functions. Can you explain why the construction $$deftextsc#1{dosc#1csod} defdosc#1#2csod{{rm #1{small #2}}} textsc{MSET}_{=sigma_k} left(textsc{MSET}_{=k} left(sum_{k'=1}^l mathcal{A}_{k'}right)right)$$ is the correct one?
    $endgroup$
    – JJW5432
    Jul 28 '18 at 3:39












    $begingroup$
    This part follows by inspection for the user of the symbolic method. I have added two examples to clarify the notation. The book by Harary and Palmer Graphical Enumeration is a useful reference for the nested cycle indices. I also checked my work using several enumeration routines for cycle indices and multisets.
    $endgroup$
    – Marko Riedel
    Jul 28 '18 at 12:50




    $begingroup$
    This part follows by inspection for the user of the symbolic method. I have added two examples to clarify the notation. The book by Harary and Palmer Graphical Enumeration is a useful reference for the nested cycle indices. I also checked my work using several enumeration routines for cycle indices and multisets.
    $endgroup$
    – Marko Riedel
    Jul 28 '18 at 12:50











    0












    $begingroup$

    I'm posting an implementation of Marko Riedel's algorithm in Sage because Sage is open source and widely available. It works on all the examples he posted, but for larger examples like $binom{49, 49, 1, 1}{10, 10, 10, 10, 10, 10, 10, 10, 10, 10}$ it's hanging.





    #!/usr/bin/env sage

    import sys
    from sage.all import *

    Sym = SymmetricFunctions(QQ)
    p = Sym.powersum()

    def sub_cycle_index(Zout, Zin):
    """Substitutes Zin into Zout to produce Zout evaluated at Zin.

    This is accomplished by replacing p[i] in Zout with Zin, but with
    every p[j] in Zin replaced with p[i*j].
    """

    return p.sum(c * p.prod(Zin.frobenius(i) for i in mu) for mu, c in Zout)

    def multiset_cycle_index(ms):
    """The cycle index of the given multiset, given by the formula

    .. math:: prod_{{k}}left( Z(S_{sigma_k}; Z(S_k))right)

    where :math:`{k}` are the elements of the multiset and
    :math:`sigma_k` is the multiplicity of the element :math:`k`.
    """

    Z = lambda i: SymmetricGroup(i).cycle_index()
    return p.prod(sub_cycle_index(Z(sk), Z(k)) for k, sk in ms.items())

    def list_to_multiset(els):
    """Converts a list of elements representing a multiset to a dictionary
    where the keys are the elements of the multiset and the values are
    the multiplicities.
    """

    ms = {}
    for x in els:
    ms[x] = ms.get(x,0) + 1
    return ms

    def mset_choose(s, d):
    """Compute the "multiset coefficient" :math:`binom{s}{d}`."""

    A = PolynomialRing(QQ, len(s), 'A').gens()
    mono = prod(a^i for a, i in zip(A, s))
    Z = multiset_cycle_index(list_to_multiset(d))
    return Z.expand(len(A), A).coefficient(mono)

    if __name__ == '__main__':
    if len(sys.argv) != 3:
    print("Usage: %s 's_1, s_2, ..' 'd_1, s_2, ..'" % sys.argv[0])
    print("Outputs the number of ways the multiset s can be partitioned into multisets of sizes d_i.")
    sys.exit(1)

    s = map(int, sys.argv[1].split(' '))
    d = map(int, sys.argv[2].split(' '))

    if sum(s) != sum(d):
    print("The sum of the elements of s must equal the sum of the elements of d")
    sys.exit(1)

    print(mset_choose(s, d))





    share|cite|improve this answer









    $endgroup$


















      0












      $begingroup$

      I'm posting an implementation of Marko Riedel's algorithm in Sage because Sage is open source and widely available. It works on all the examples he posted, but for larger examples like $binom{49, 49, 1, 1}{10, 10, 10, 10, 10, 10, 10, 10, 10, 10}$ it's hanging.





      #!/usr/bin/env sage

      import sys
      from sage.all import *

      Sym = SymmetricFunctions(QQ)
      p = Sym.powersum()

      def sub_cycle_index(Zout, Zin):
      """Substitutes Zin into Zout to produce Zout evaluated at Zin.

      This is accomplished by replacing p[i] in Zout with Zin, but with
      every p[j] in Zin replaced with p[i*j].
      """

      return p.sum(c * p.prod(Zin.frobenius(i) for i in mu) for mu, c in Zout)

      def multiset_cycle_index(ms):
      """The cycle index of the given multiset, given by the formula

      .. math:: prod_{{k}}left( Z(S_{sigma_k}; Z(S_k))right)

      where :math:`{k}` are the elements of the multiset and
      :math:`sigma_k` is the multiplicity of the element :math:`k`.
      """

      Z = lambda i: SymmetricGroup(i).cycle_index()
      return p.prod(sub_cycle_index(Z(sk), Z(k)) for k, sk in ms.items())

      def list_to_multiset(els):
      """Converts a list of elements representing a multiset to a dictionary
      where the keys are the elements of the multiset and the values are
      the multiplicities.
      """

      ms = {}
      for x in els:
      ms[x] = ms.get(x,0) + 1
      return ms

      def mset_choose(s, d):
      """Compute the "multiset coefficient" :math:`binom{s}{d}`."""

      A = PolynomialRing(QQ, len(s), 'A').gens()
      mono = prod(a^i for a, i in zip(A, s))
      Z = multiset_cycle_index(list_to_multiset(d))
      return Z.expand(len(A), A).coefficient(mono)

      if __name__ == '__main__':
      if len(sys.argv) != 3:
      print("Usage: %s 's_1, s_2, ..' 'd_1, s_2, ..'" % sys.argv[0])
      print("Outputs the number of ways the multiset s can be partitioned into multisets of sizes d_i.")
      sys.exit(1)

      s = map(int, sys.argv[1].split(' '))
      d = map(int, sys.argv[2].split(' '))

      if sum(s) != sum(d):
      print("The sum of the elements of s must equal the sum of the elements of d")
      sys.exit(1)

      print(mset_choose(s, d))





      share|cite|improve this answer









      $endgroup$
















        0












        0








        0





        $begingroup$

        I'm posting an implementation of Marko Riedel's algorithm in Sage because Sage is open source and widely available. It works on all the examples he posted, but for larger examples like $binom{49, 49, 1, 1}{10, 10, 10, 10, 10, 10, 10, 10, 10, 10}$ it's hanging.





        #!/usr/bin/env sage

        import sys
        from sage.all import *

        Sym = SymmetricFunctions(QQ)
        p = Sym.powersum()

        def sub_cycle_index(Zout, Zin):
        """Substitutes Zin into Zout to produce Zout evaluated at Zin.

        This is accomplished by replacing p[i] in Zout with Zin, but with
        every p[j] in Zin replaced with p[i*j].
        """

        return p.sum(c * p.prod(Zin.frobenius(i) for i in mu) for mu, c in Zout)

        def multiset_cycle_index(ms):
        """The cycle index of the given multiset, given by the formula

        .. math:: prod_{{k}}left( Z(S_{sigma_k}; Z(S_k))right)

        where :math:`{k}` are the elements of the multiset and
        :math:`sigma_k` is the multiplicity of the element :math:`k`.
        """

        Z = lambda i: SymmetricGroup(i).cycle_index()
        return p.prod(sub_cycle_index(Z(sk), Z(k)) for k, sk in ms.items())

        def list_to_multiset(els):
        """Converts a list of elements representing a multiset to a dictionary
        where the keys are the elements of the multiset and the values are
        the multiplicities.
        """

        ms = {}
        for x in els:
        ms[x] = ms.get(x,0) + 1
        return ms

        def mset_choose(s, d):
        """Compute the "multiset coefficient" :math:`binom{s}{d}`."""

        A = PolynomialRing(QQ, len(s), 'A').gens()
        mono = prod(a^i for a, i in zip(A, s))
        Z = multiset_cycle_index(list_to_multiset(d))
        return Z.expand(len(A), A).coefficient(mono)

        if __name__ == '__main__':
        if len(sys.argv) != 3:
        print("Usage: %s 's_1, s_2, ..' 'd_1, s_2, ..'" % sys.argv[0])
        print("Outputs the number of ways the multiset s can be partitioned into multisets of sizes d_i.")
        sys.exit(1)

        s = map(int, sys.argv[1].split(' '))
        d = map(int, sys.argv[2].split(' '))

        if sum(s) != sum(d):
        print("The sum of the elements of s must equal the sum of the elements of d")
        sys.exit(1)

        print(mset_choose(s, d))





        share|cite|improve this answer









        $endgroup$



        I'm posting an implementation of Marko Riedel's algorithm in Sage because Sage is open source and widely available. It works on all the examples he posted, but for larger examples like $binom{49, 49, 1, 1}{10, 10, 10, 10, 10, 10, 10, 10, 10, 10}$ it's hanging.





        #!/usr/bin/env sage

        import sys
        from sage.all import *

        Sym = SymmetricFunctions(QQ)
        p = Sym.powersum()

        def sub_cycle_index(Zout, Zin):
        """Substitutes Zin into Zout to produce Zout evaluated at Zin.

        This is accomplished by replacing p[i] in Zout with Zin, but with
        every p[j] in Zin replaced with p[i*j].
        """

        return p.sum(c * p.prod(Zin.frobenius(i) for i in mu) for mu, c in Zout)

        def multiset_cycle_index(ms):
        """The cycle index of the given multiset, given by the formula

        .. math:: prod_{{k}}left( Z(S_{sigma_k}; Z(S_k))right)

        where :math:`{k}` are the elements of the multiset and
        :math:`sigma_k` is the multiplicity of the element :math:`k`.
        """

        Z = lambda i: SymmetricGroup(i).cycle_index()
        return p.prod(sub_cycle_index(Z(sk), Z(k)) for k, sk in ms.items())

        def list_to_multiset(els):
        """Converts a list of elements representing a multiset to a dictionary
        where the keys are the elements of the multiset and the values are
        the multiplicities.
        """

        ms = {}
        for x in els:
        ms[x] = ms.get(x,0) + 1
        return ms

        def mset_choose(s, d):
        """Compute the "multiset coefficient" :math:`binom{s}{d}`."""

        A = PolynomialRing(QQ, len(s), 'A').gens()
        mono = prod(a^i for a, i in zip(A, s))
        Z = multiset_cycle_index(list_to_multiset(d))
        return Z.expand(len(A), A).coefficient(mono)

        if __name__ == '__main__':
        if len(sys.argv) != 3:
        print("Usage: %s 's_1, s_2, ..' 'd_1, s_2, ..'" % sys.argv[0])
        print("Outputs the number of ways the multiset s can be partitioned into multisets of sizes d_i.")
        sys.exit(1)

        s = map(int, sys.argv[1].split(' '))
        d = map(int, sys.argv[2].split(' '))

        if sum(s) != sum(d):
        print("The sum of the elements of s must equal the sum of the elements of d")
        sys.exit(1)

        print(mset_choose(s, d))






        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Jan 6 at 7:14









        JJW5432JJW5432

        167111




        167111






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856255%2fpartitioning-a-multiset-into-multisets-of-fixed-sizes%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Ellipse (mathématiques)

            Quarter-circle Tiles

            Mont Emei