Home
Generalized Permutations and Combinations Generating Permutations and Combinations

Computer Science 235 Project
Permutations & Combinations Patrick McAtee, Tom Rice, and Jesse Whidden 


Generalized Permuations and CombinationsRepetitions, Indistinguishable Objects, and Objects in Boxes
Permutations with RepetitionFor permutations with repetition, order still matters. In fact, the only difference between these types of permutations and the ones we looked at earlier in the tutorial are that you're allowed to choose an item more than once.
As an example, let's think about the car manufacturer again. We want to figure out how many different license plate combinations each car could have. To keep life simple, let's assume that only uppercase English alphabet letters can appear on a license plate. If a license plate has spots for 10 letters (and we can repeat those letters) how many different license plate combinations are there? Solution: The first spot of the license plate has 26 options, the second spot has 26 options, the third spot has 26 options,... and so on, until the tenth spot. We can write this as: Number of options = 26 * 26 * 26 * 26 * 26 * 26 * 26 * 26 * 26 * 26  or  Number of options = 26^{10}
This example also demonstrates the concept of sampling with replacement. 'Sampling with replacement' means that you get to choose from all n items each time. In our example, it would be as if we were drawing a letter out of a hat each time, and then putting it back in the hat so that we could choose it again. When using this formula for rpermutations with repetition in applications, replacement must be used.
Last updated 12/14/2001 