Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.