Determine the total number of combinations (of any size) of a multiset of objects of $k$ different types with finite repetition numbers $n_1, n_2, \ldots, n_k$ respectively.
The answer is $(n_1+1)(n_2+1)….(n_k+1)$, but I don't see why.
[Math] Number of combinations of a multiset of objects
combinatoricsmultisets
Related Solutions
As Thomas Andrews said in the comments, the formula that you have in mind is actually $\binom{n+k-1}{k-1}$, but it doesn’t apply here. Here you simply have to find a way to divide up the $n$-combinations into chunks that can easily be counted and then add up the results.
First count the $n$-combinations that have $k$ of their members from the set $\{1,\dots,n+1\}$. There are $\binom{n+1}k$ ways to choose those $k$ members. The rest of the $n$-combination is completely determined by the number of $a$’s, which may be anything from $0$ through $n-k$; this is a total of $n-k+1$ possibilities, so there are $(n-k+1)\binom{n+1}k$ $n$-combinations with $k$ of their members in the set $\{1,\dots,n+1\}$. The final answer is the sum of these totals over the possible values of $k$,
$$\sum_{k=0}^n(n-k+1)\binom{n+1}k\;.$$
If you manipulate the term $(n+1-k)\binom{n+1}k$ properly, you can transform it to a term of the form $c\binom{d}k$, where $c$ and $d$ don’t depend on $k$, and then evaluate the sum quite easily. I’ve included a hint for the manipulation that you need, but I’ve left it spoiler-protected to give you a chance to work it out on your own. Mouse-over to make it visible.
The manipulation that you need is of the form $\displaystyle(m-k)\binom{m}k=m\binom{m-1}k$, which you can check by writing out the binomial coefficients in factorial form.
$T$ is a multiset that has $r+k-1$ members. These members are of two types: some of them are ones, and some of them are asterisks. Specifically, the multiset $T$ contains $r$ ones and $k-1$ asterisks.
To see how permutations of this multiset are related to solutions to $x_1+\ldots+x_k=r$ in non-negative integers $x_1,\ldots,x_k$, let’s look at a specific example, say $k=5$ and $r=10$. Here are three permutations of the multiset $T=\{10\cdot1,4\cdot*\}$:
$$\begin{align*} &111*11**1111*1\\ &1*11*111*1111*\\ &11*11*11*11*11 \end{align*}\tag{1}$$
The $4$ asterisks leave $5$ spaces for ones: one before the first asterisk, $3$ between consecutive asterisks, and one more after the last asterisk. These $5$ spaces correspond to the $5$ variables $x_1,x_2,x_3,x_4$, and $x_5$, and the number of ones in each space corresponds to the actual value of the variable. Thus, the three permutations of $T$ shown in $(1)$ correspond respectively to the solutions
$$\begin{align*} &3+2+0+4+1=10\\ &1+2+3+4+0=10\\ &2+2+2+2+2=10\;. \end{align*}\tag{2}$$
Going in the other direction, the solution $0+0+3+5+2=10$ corresponds to the permutation $**111*11111*11$ of $T$.
In general you will have $k-1$ asterisks; there is one space for ones before the first asterisk, one after the last asterisk, and $k-2$ between consecutive asterisks for a total of $k$ spaces, one for each variable. The number of ones in the first space corresponds to the value of $x_1$, the number in the second space to the value of $x_2$, and so on. Since we have $r$ ones, each permutation of $T$ will automatically yield a solution in non-negative integers to $x_1+\ldots+x_k=r$, since we distribute $r$ ones amongst $k$ spaces available to hold them. Conversely, each solution to the equation can be understood as describing a unique permutation of $T$ via this same correspondence.
Best Answer
You are all alone at an all-you can eat cafeteria line. First there are $n_1$ cherry tomatoes on a plate. You can take any number of the cherry tomatoes you want, $0$, or $1$, or $2$, and so on up to $n_1$, and put them on your tray.
Then comes a plate with $n_2$ radishes, and you can take any number of the radishes you want, including none. Then comes a plate with $n_3$ green olives, and you can take any number of the green olives you want. Then comes a plate of $n_4$ black olives. And so on. The $k$-th and final item in the cafeteria line is a plate of $n_k$ strawberries, and you can take any number of them you want, including $0$.
How many ways are there to choose lunch? There are $n_1+1$ choices for how many cherry tomatoes you take, namely $0$, $1$, and so on up to $n_1$. For each choice about the number of cherry tomatoes, there are $n_2+1$ choices for the number of radishes you take. Thus by the time you are past the radish plate, there are $(n_1+1)(n_2+1)$ possibilities for what is on your tray. For each of these possibilities, there are $n_3+1$ possible decisions for the number of green olives to take, for a total so far of $(n_1+1)(n_2+1)(n_3+1)$ possibilities. And so on. The total number of possible choices of lunch is therefore $$(n_1+1)(n_2+1)(n_3+1)\cdots (n_k+1).$$