# The combinations of a finite multiset [closed]

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.

## closed as off-topic by Neil Strickland, Gabriel C. Drummond-Cole, Jan-Christoph Schlage-Puchta, Ira Gessel, Max AlekseyevFeb 15 '18 at 18:54

This question appears to be off-topic. The users who voted to close gave these specific reasons:

• "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Neil Strickland, Gabriel C. Drummond-Cole, Max Alekseyev
• "This question does not appear to be about research level mathematics within the scope defined in the help center." – Jan-Christoph Schlage-Puchta, Ira Gessel
If this question can be reworded to fit the rules in the help center, please edit the question.

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}
• In your example, for each value of $j\in\{0,1,2,3\}$, you need simply to iterate over the subsets of $\{1,2,3\}$ of size $j$. Then $i_1,i_2,\dots,i_j$ are simply the elements (in increasing order) of each such subset. E.g., for $j=2$ and subset $\{0,2\}$, you have $i_1=0$ and $i_2=2$. – Max Alekseyev Feb 15 '18 at 12:17
• What exactly is not clear in my explanation? Can you list all subsets of $\{1,2,3\}$? Can you count the number of elements in each subset? (This is $j$.) Can you then label the elements of the subset in increasing order with $i_1,\dots,i_j$ to obtain their values? – Max Alekseyev Feb 15 '18 at 12:31
• @RichardSantiago: I've just added a new expression for $C(k;m_1,\dots,m_n)$ where the sum is indexed by the subsets of $\{1,2,\dots,n\}$ (there total $2^n$ subsets, and thus there are $2^n$ summands). I hope it'd cause less confusion. – Max Alekseyev Feb 15 '18 at 17:15