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.

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!

share|improve this question
    
It’s hard to know what to say in general. Why don’t you edit your question to include one or two specific problems of the type that you have in mind. –  Brian M. Scott Oct 29 '12 at 1:47
    
Ok, I will do that. –  user1038665 Oct 29 '12 at 1:48
add comment

1 Answer 1

up vote 1 down vote accepted

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.

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.