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 Combinations

Repetitions, Indistinguishable Objects, and Objects in Boxes

Permutations with Repetition

For 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¹⁰

Theorem

To generalize for an r-permutation with repetition, when you have n things to choose from and there are r places to put these items:
Number of r-permutations = n^r

see more examples...

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 r-permutations with repetition in applications, replacement must be used.

Previous: Introduction Next: Combinations with Repetition

Last updated 12/14/2001