- Intro to Combinations and Permutations
- Permutations with Repetition
- Permutations without Repetition
- Permutations Formula
- Android Lock Screen
- Tigers and Bears - Oh My
Combination without Repetition
- Combination Formula
- Combining Combinations
The String of Beads
- Combinations with Repetition I
- Combinations with Repetition II
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".
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.
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.
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 r1, r2... times, then the formula will be:
r1!, r2!, etc...