Counting permutations with repetition

The permutations of n things can be thought of as arrangements of those n things. The Fundamental Counting Principle informs us that there are (n)(n – 1) . . . (2)(1) = n! of these permutations.

To solve some kinds of problems, it's helpful to group permutations in particular ways and then to count the numbers of groups:

Circular permutations

If the ends of an arrangement are considered as being next to each other, then shifts of the elements around the circle may be considered as the same arrangement. If you imagine grouping together the permutations that give any of these shifts, the number of distinct arrangements will be the number of those groups of permutations. For each arrangement, there are n shifts that are the same, so the number of circular permutations is ^nPn / _n = ^n! / _n = (n – 1)!.

Indistinguishable elements

For example, the number of permutations of six letters is six factorial (6!). But some of the six letters may be the same letter. If the set of letters contains, say, three occurrences of one letter (and just one occurrence of the other letters), then the permutations that interchange those three occurrences of one letter can be grouped. There are 3! such permutations, so the number of groups—and the number of distinct arrangements—is 6! divided by 3!. If two of the other letters were also identical, the number of distinct permutations would be ^6!/_3!2!.

Combinations

When you're working in a set and trying to count the number of its subsets that have a particular size, you can group permutations that interchange the elements of any subset of that size; the number of subsets of that size is then the number of those groups of permutations. Subsets counted this way are called combinations.

Copyright © 1999-2000 SciMathMN