When learning about permutations and combinations, I've come across certain problems that allow things to be repeated, but I'm not particularly sure what it means nor how it changes the problem. Can someone please explain how I can make this distinction?
For example, let's say we have the following problem:
How many ways are there to select four pieces of fruit from a bowl containing apples, oranges, and pears if the order in which the pieces are selected does not matter, only the type of fruit and not the individual piece matters, and there are at least four pieces of each type of fruit in the bowl?
What combinations are involved in this problem?
Thank you!
Best Answer
Let $n_a,n_o$, and $n_p$ be the numbers of apples, oranges, and pears, respectively, in a selection of four pieces of fruit. We’re told to consider all pieces of one kind of fruit equivalent, and we’re told that only the number of pieces of each kind matters, not the order in which they are chosen. Thus, the three numbers $n_a,n_o$, and $n_p$ completely describe a selection of fruit. The question then amounts to asking how many solutions there are to the equation $n_a+n_o+n_p=4$ if the numbers $n_a,n_o$, and $n_p$ must be non-negative integers. (We’re told that at least $4$ pieces of each type of fruit are available, so every solution corresponds to a possible selection of fruit.)
This is a classic stars-and-bars problem; the answer, which is explained reasonably well in the Wikipedia article to which I linked, is that there are
$$\binom{4+3-1}{3-1}=\binom62=15$$
solutions in non-negative integers and hence $15$ possible selections of fruit.
Quite a few combinatorial problems can be reduced to this form or to something similar; it’s well worth learning to spot them. Here is an answer to another problem of this type that goes into more detail; in this answer I listed several of the guises in which this kind of problem can appear.
If repetition were not allowed, we couldn’t select more than three pieces of fruit, one of each kind. If the order of selections mattered, we’d have to argue very differently: the first piece could be any one of $3$ types, as could the second, third, and fourth, so there would be $3^4=81$ different ordered selections.