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$ , set cardinality

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

However, I do not fully understand the meaning of the expression. **Will someone expand it utilizing the scenario just described as an example?**

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}} $ $ This matrices are then cross 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;m_1,m_2,..,m_n)$ :$ \{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.