# Algorithm for calculating multiset permutations

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?

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.$$