Permutations with Repetitions
Reference > Mathematics > Algebra > Counting PrinciplesIn the previous section we explored permutations - arrangements of objects, and we learned a formula for calculating the number of permutations of n objects taken r at a time. We finished by noting that the formula is incomplete if we have repetition of objects. Let's take an example and explore it.
Suppose I have two blue marbles, and one each of green, red, and yellow marbles. How many distinguishable permutations (arrangements) of the marbles are there?
Well, there are 5 marbles, and we're using all 5 of them, so that's 5P5.
5P5 =But in reality we have fewer permutations. Why? Since there are two blue marbles, and there are two ways to arrange these for each permutation, we've counted each permutation twice. (After all, BBGRY and BBGRY are exactly the same arrangement; I've put the blue marbles in a different order, but you can't tell, can you?)
So the total number of arrangements isLet's try another example. What if we've got three greens, a blue, and a red? How many ways can we arrange those?
The total arrangements hasn't changed (120) because we have the same number of marbles. But now we have 3 greens, and 3 greens can be arranged 6 ways (permutations of 3 things one at a time!). Thus, the actual total arrangements isIt turns out that for each repeated object, if it's repeated n times, we need to divide out total by n factorial.
So suppose we have 3 yellow, 2 green, and blue. Now how many permutations are there?
That probably seemed fairly simple, right? But Things can get a bit more complicated. Suppose you have two greens, a blue, a red, and a yellow, and we want permutations taken two at a time. Now we can't just take out total and divide by 2!, because not every permutation contains a green. So here is one way of approaching the problem.
First, since there are 5 marbles, we know there are 120 permutations, if we don't worry about repetitions.
Now let's figure out how many permutations don't have a green in them. If they don't have a green, then there are only three to choose from (B, R, and Y). There areNow we add together the permutations which do contain a green and the ones which do not: 57 + 6 = 63.