# Number of combinations of a multiset of objects

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.

-

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).$$

-

Hints.

1. If I have only one type of object ($k=1$), why is the answer $n_1+1$?

2. In the general case when we have $k$ types of objects, the answer $$\prod\limits_{i=1}^k (n_i+1)$$ suggests applying the product rule.

-