Anagrams

Let's say you were given 1 Plum, 2 Oranges, and 1 Lime to put on a string. How many ways could you arrange them?

You could represent the fruit as P, O, O and L and create a table to show all the possibilities:

There are 12 possible arrangements, or permutations.

Q: You can't repeat any number of fruit/characters in your arrangement, but according to the node permutations without repetition, 4 characters should be able to be arranged in 4! = 24 possible ways, not 12.

Question: How could you solve this problem in general?
Try to figure out the solution before looking ahead, perhaps by seeing how permutations could be created by "POOOL".

Solution

Here are 2 possible approaches you can take to this problem:

Convert to recent problem

In the arranging beads problem, permuting black and white beads was really just a problem of choosing which beads should be black. You can do the same thing with 3 and more types. In this example, you can choose which spots will be 'O' 'P' and 'L':

O - 5 Choose 3 = 10. You will then have 2 remaining spots to choose from, so:
P - 2 choose 1 = 2. Finally, there's 1 choice left:
L - 1 choose 1 = 1.

Since you will need to choose where to put the P's for each possible 'O' choice, you multiply the different choices together to get the total:
10 * 2 * 1 = 20 possible permutations of POOOL.

Direct Approach

In the word POOOL, if you use the regular formula (5!), you will get duplicates from the triple O's. How many duplicates? The 3 O's could have been arranged in 3! different ways (if they had been different), so for each word with 3 O's there will be 3! 'false' ways to arrange the O's. The same technique is used to convert a permutation to a combination.

So 5! / 3 != 20 possible permutations of POOOL.

General Formula

If a group G contains n elements, and r of the elements are identical, then the number of unique permutations of G equals:

If there are additional duplicated characters, which are duplicated r₁, r₂... times, then the formula will be:

  n!  
r₁!, r₂!, etc...