1
$\begingroup$

I have this algorithm to calculate multiset combinations:

$$\mathcal P(k; m_1, m_2, \ldots, m_n) = \Sigma \binom{c(i_1)}{\lambda_1}\ \binom{c(i_2)-\lambda_1}{\lambda_2} \cdots \binom{c(i_s)-\lambda_1-\lambda_2-\ldots-\lambda_{s-1}}{\lambda_s}$$

, which I got from this document

It specifies:

  1. $m_i$ is a multiplicity of the $i$th elements

  2. $M = \max\left({m_1, m_2, \ldots, m_n}\right)$

  3. $c(i)$ is the number of numbers $m_p, p = 1,\ldots,n$, which are not smaller than $i$

  4. $k = \sum{\lambda_ji_j}$ with $j ≤ s$

  5. $M ≥ i_1 > i_2 > \ldots > i_s ≥ 1$

I can't say I understand it completely, as I am mainly a computer scientist, no mathematician.

I try to use this algorith with an example:

I have this set: ${ A A A B B C C }$ and I draw $k = 3$ balls, which means there are the following combinations $AAA, AAB, ABB, AAC, ACC, ABC, BBC, BCC$, which are eight in total.

Now I try to use this algorith, I come up with this:

$$\binom{3}{3}\binom{2-3}{0}\binom{2-3}{0} + \binom{3}{1}\binom{2-1}{1}\binom{2-2}{0} + \binom{3}{1}\binom{2-1}{0}\binom{2-1}{1} = 1 + 3 +3 = 7$$

What am I doing wrong? How can I calculate multiset combinations with this algorithm?

$\endgroup$
1
$\begingroup$

It looks like you needed to tweak a couple of things. First, it looks like your calculations of $c(i)$ aren't correct. Second, the strictly decreasing nature of the terms in the representations of $k$ don't allow for any zeroes.

If we take $i=1,2,3$ to correspond to $A,B,C$ then $m_1 = 3, m_2 = m_3 = 2$.

Then, $c(1) = 3, c(2) = 3, c(3) = 1.$ The value of $c(1)$ is $3$ because each of $2, 2, 3$ is not less than $1$. The value of $c(2)$ is also $3$ because each of $2, 2, 3$ is not less than $2$. Finally, $c(3) = 1$ because only $3$ is not less than $3$.

Next we have the representations of $k$, for which I think there are three:

$$\lambda_1 = 1, i_1 = 3$$ $$\lambda_1 = 3, i_1 = 1$$ $$\lambda_1 = 1, i_1 = 2, \lambda_2 = 1, i_2 = 1$$

Respectively, these represent (a) one element appearing three times; (b) three elements appearing once; (c) one element appearing twice, one element appearing once.

Summing over these three we get

$$P(3,3,2,2) = {c(3) \choose 1} + {c(1) \choose 3} + {c(2) \choose 1}{c(1) - 1 \choose 1} = {1 \choose 1} + {3 \choose 3} + {3 \choose 1}{3 - 1 \choose 1} = 8.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.