The combinations of a finite multiset [closed]

Question

Suppose there is a basket $S$ containing $3\ \color{blue}{blue}$, $2\ \color{green}{green}$ and $1\ \color{red}{red}$ balls. A subject can extract any $k$ number of balls (including $0$) at random from the basket. How many combinations $C$ there are for each extraction of $k$ balls? I can't conjure an efficacious function to cope with this type of enumeration. There is the following attributed to one Percy Alexander MacMahon (1854-1929):

$C$, combination(s)

$k$, grouping

$e_i$, $i$th element

$m_i$ $i$th multiplicity

$S = \{e_1m_1,e_{2}m_{2},..., e_{n}m_n\}$, multiset

$n=|S|$, multiset cardinality

$$C(k;m_1,m_2,\ldots,m_n)\\ =\sum_{j=0}^n (-1)^j\sum_{1\le i_1\lt i_2\lt \cdots \lt i_j\le n } \binom{n+k-m_{i_1}-m_{i_2}-\cdots-m_{i_j}-j-1}{n-1}$$

With summation taken over all terms where $n+k-m_{i_1}-m_{i_2}-\cdots-m_{i_j}-j>0$.

Are there any other algorithms to solve this problem?

Meanwhile, my cumbersome procedure follows...

$$ \begin{array}{rllllll} i & e & m & & & & \text{Possibilities}\\ \hline 1 & \color{blue}{blue} & \color{blue}{\bullet\bullet\bullet} & \color{blue}{\bullet\bullet} & \color{blue}{\bullet} & \color{blue}{\circ} & 4\\ 2 & \color{green}{green} & \color{green}{\bullet\bullet} & \color{green}{\bullet} & \color{green}{\circ} & & 3\\ 3 & \color{red}{red} & \color{red}{\bullet} & \color{red}{\circ} & & & 2 & \end{array} $$

The table illustrates how one can only extract $3$, $2$, $1$ or $0$ $\color{blue}{blue}$ balls, $2$, $1$ or $0$ $\color{green}{green}$ balls, and $1$ or $0$ $\color{red}{red}$ balls from the basket. This makes all the possible combinations $C = (3+1)(2+1)(1+1) = 24$. And thus the generalized formula for all possible combinations of a finite multiset is expressed:

$$\prod_{i=1}^{n}m_i+1 $$

The $k$-combinations of $S$ can be found by cross adding all the extraction possibilities shown in the table. This becomes more manageable once those possibilities are tabulated in the shape of matrices. Each respective element $e_i$ is assigned its own set of matrices like so...

The matrix of $\color{blue}{blue}$:

$$ \color{blue}{ \begin{pmatrix} 3 & 2 & 1 & 0\\ 3 & 2 & 1 & 0\\ 3 & 2 & 1 & 0\\ \end{pmatrix}} $$

The matrix of $\color{green}{green}$:

$$ \color{green}{ \begin{pmatrix} 2 & 2 & 2 & 2\\ 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 0\\ \end{pmatrix}} $$

The matrices of $\color{red}{red}$:

$$ \color{red}{ \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ \end{pmatrix}} $$

$$ \color{red}{ \begin{pmatrix} 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ \end{pmatrix}} $$ These matrices are then added... $$ \color{blue}{ \begin{pmatrix} 3 & 2 & 1 & 0\\ 3 & 2 & 1 & 0\\ 3 & 2 & 1 & 0\\ \end{pmatrix}} + \color{green}{ \begin{pmatrix} 2 & 2 & 2 & 2\\ 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 0\\ \end{pmatrix}} + \color{red}{ \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ \end{pmatrix}} = \begin{pmatrix} 6 & 5 & 4 & 3\\ 5 & 4 & 3 & 2\\ 4 & 3 & 2 & 1\\ \end{pmatrix}\\ \color{blue}{ \begin{pmatrix} 3 & 2 & 1 & 0\\ 3 & 2 & 1 & 0\\ 3 & 2 & 1 & 0\\ \end{pmatrix}} + \color{green}{ \begin{pmatrix} 2 & 2 & 2 & 2\\ 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 0\\ \end{pmatrix}} + \color{red}{ \begin{pmatrix} 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ \end{pmatrix}} = \begin{pmatrix} 5 & 4 & 3 & 2\\ 4 & 3 & 2 & 1\\ 3 & 2 & 1 & 0\\ \end{pmatrix} $$

The sum of these matrices concatenated form the set of solutions for $C(k;3,2,1)$:$\{6,5,5,5,4,4,4,4,4,3,3,3,3,3,3,2,2,2,2,2,1,1,1,0\}$.

$$ \begin{array}{ll} k & C \\ \hline 6 & 1 \\ 5 & 3 \\ 4 & 5 \\ 3 & 6 \\ 2 & 5 \\ 1 & 3 \\ 0 & 1 \\ \end{array} $$

Thus, for example, there are only $3$ ways of extracting $5$ balls from the basket:

$C(5;3,2,1) = \{\color{blue}{\bullet}\color{blue}{\bullet}\color{blue}{\bullet}\color{green}{\bullet}\color{green}{\bullet}, \color{blue}{\bullet}\color{blue}{\bullet}\color{blue}{\bullet}\color{green}{\bullet}\color{red}{\bullet}, \color{blue}{\bullet}\color{blue}{\bullet}\color{green}{\bullet}\color{green}{\bullet}\color{red}{\bullet}\}$

The procedure becomes unfeasible as the elements of $S$ increase in quantity and size.

Answer 1

It can be easily seen that $C(k;m_1,\dots,m_n)$ equals the coefficient of $x^k$ in $$\prod_{i=1}^n (1+x+\dots+x^{m_i}) = \prod_{i=1}^n \frac{1-x^{m_i+1}}{1-x} = (1-x)^{-n} \prod_{i=1}^n (1-x^{m_i+1}).$$ MacMahon's formula can be now obtained by going over all subset of indices $\{ i_1, \dots, i_j\}\subseteq \{1,2,\dots,n\}$ (i.e., $1\leq i_1<\dots<i_j\leq n$), and assuming that we take the power of $x$ term from the corresponding parentheses in the last product, while from the other parentheses we take the term 1. Then from $(1-x)^{-n}$ we extract the power of $x$ that gives the total power equal $k$, i.e. we extract $x^{k-(m_{i_1}+1)-\dots-(m_{i_j}+1)}=x^{k-m_{i_1}-\dots-m_{i_j}-j}$, whose coefficient equals $$(-1)^{k-m_1-\dots-m_{i_j}-j}\binom{-n}{k-m_{i_1}-\dots-m_{i_j}-j}=\binom{n+k-m_{i_1}-\dots-m_{i_j}-j-1}{n-1}.$$ It follows that \begin{split} &C(k;m_1,m_2,\ldots,m_n)\\ &=\sum_{j=0}^n \sum_{1\le i_1 < i_2< \cdots <i_j\le n }^n (-1)^{k-m_{i_1}-\dots-m_{i_j}}\binom{-n}{k-m_{i_1}-\dots-m_{i_j}-j}\\ &=\sum_{j=0}^n (-1)^j \sum_{1\le i_1 < i_2< \cdots <i_j\le n }^n \binom{n+k-m_{i_1}-m_{i_2}-\cdots-m_{i_j}-j-1}{n-1}\\ &=\sum_{S\subseteq \{1,2,\dots,n\}} (-1)^{|S|} \binom{n+k-|S|-1-\sum_{s\in S} m_s}{n-1}. \end{split}