Skip to main content

​
Permutations with Repetition

Counting permutations when repetition of elements is allowed can easily be done using the product rule.

​
Example

How many strings of length r can be formed from the uppercase letters of the English alphabet?Solution:
By the product rule, because there are 26 uppercase English letters, and because each letter can be used repeatedly, we see that there are 26r26^r strings of uppercase English letters of length rr.
The number of rr-permutations of a set with nn elements when repetition is allowed is given in Theorem 1.

​
Theorem

The number of rr-permutations of a set of nn objects with repetition allowed is nrn^r. Proof:
  • There are nn ways to select an element of the set for each of the rr positions in the rr-permutation when repetition is allowed, because for each choice all n objects are available.
  • Hence, by the product rule there are nrrn^r r-permutations when repetition is allowed.

​
Combinations with Repetition

​
Example 1

How many ways are there to select four pieces of fruit from a bowl containing apples, oranges, and pears if the order in which the pieces are selected does not matter, only the type of fruit and not the individual piece matters, and there are at least four pieces of each type of fruit in the bowl?Solution:
To solve this problem we list all the ways possible to select the fruit. There are 15 ways:
4 apples4 oranges4 pears
3 apples, 1 orange3 apples, 1 pear3 oranges, 1 apple
3 oranges, 1 pear3 pears, 1 apple3 pears, 1 orange
2 apples, 2 oranges2 apples, 2 pears2 oranges, 2 pears
2 apples, 1 orange, 1 pear2 oranges, 1 apple, 1 pear2 pears, 1 apple, 1 orange

The solution is the number of 4-combinations with repetition allowed from a three-element set, {apple,orange,pear}\{apple, orange, pear\}.

​
Theorem

There are C(n+r−1,r)=C(n+r−1,n−1)rC(n + r - 1, r) = C(n + r - 1, n - 1) r-combinations from a set with nn elements when repetition of elements is allowed.

​
Example 2

Suppose that a cookie shop has four different kinds of cookies. How many different ways can six cookies be chosen? Assume that only the type of cookie, and not the individual cookies or the order in which they are chosen, matters.Solution:
The number of ways to choose six cookies is the number of 66-combinations of a set with four elements.
This equals
C(9,6)=C(9,3)=9×8×71×2×3=84C(9, 6) = C(9, 3) = \dfrac{9 \times 8 \times 7}{1 \times 2 \times 3} = 84 ways to choose 6 cookies.

​
Combinations and Permutations with and Without Repetition Table.

TypeRepetition Allowed?Formula
rr-permutationsNon!(n−r)!\dfrac{n!}{(n-r)!}
rr-permutationsNon!r!(n−r)!\dfrac{n!}{r!(n-r)!}
rr-permutationsYesnrn^r
rr-combinationsYes(n+r−1)!r!(n−1)!\dfrac{(n+r-1)!}{r!(n-1)!}