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:
$m_i$ is a multiplicity of the $i$th elements
$M = \max\left({m_1, m_2, \ldots, m_n}\right)$
$c(i)$ is the number of numbers $m_p, p = 1,\ldots,n$, which are not smaller than $i$
$k = \sum{\lambda_ji_j}$ with $j ≤ s$
$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.$$