Section 4.4 Permutations and Combinations
279
PraCtiCe 34 How many distinct permutations are there of the characters in the word MONGOOSES? ■
Permutations and Combinations with Repetitions
Our formulas for P(n, r) and C(n, r) assume that we arrange or select r objects out
of the n available using each object only once. Therefore r ≤ n. Suppose, however,
that the n objects are available for reuse as many times as desired. For example, we
construct words using the 26 letters of the alphabet; the words may be as long as
desired with letters used repeatedly. Or we may draw cards from a deck, replacing
a card after each draw; we may draw as many cards as we like with cards used
repeatedly. We can still talk about permutations or combinations of r objects out
of n, but with repetitions allowed, r might be greater than n.
Counting the number of permutations of r objects out of n distinct objects
with repetition is easy. We have n choices for the first object and, because we can
repeat that object, n choices for the second object, n choices for the third, and so
on. Hence, the number of permutations of r objects out of n distinct objects with
repetition allowed is n
r
.
To determine the number of combinations of r objects out of n distinct objects
with repetition allowed, we use a rather clever idea.
example 58
A jeweler designing a pin has decided to use five stones chosen from a supply of
diamonds, rubies, and emeralds. How many sets of stones are possible?
Because we are not interested in any ordered arrangement of the stones, this is
a combinations problem rather than a permutations problem. We want the number
of combinations of five objects out of three objects with repetition allowed. The
pin might consist of 1 diamond, 3 rubies, and 1 emerald, for instance, or 5 diamonds. We can represent these possibilities by representing the stones chosen by
5 asterisks and placing markers between the asterisks to represent the distribution
among the three types of gem, diamonds, rubies, and emeralds. For example, we
could represent the choice of 1 diamond, 3 rubies, and 1 emerald by
* 0 *** 0 *
while the choice of 5 diamonds, 0 rubies, and 0 emeralds would be represented by
***** 0 0
Although we wrote the asterisks and markers in a row, there is no ordering implied.
We are just looking at seven slots holding the five gems and the two markers, and
the different choices are represented by which of the seven slots are occupied by
asterisks. We therefore count the number of ways to choose five items out of seven,
which is C(7, 5) or
7!
5!2!
279
PraCtiCe 34 How many distinct permutations are there of the characters in the word MONGOOSES? ■
Permutations and Combinations with Repetitions
Our formulas for P(n, r) and C(n, r) assume that we arrange or select r objects out
of the n available using each object only once. Therefore r ≤ n. Suppose, however,
that the n objects are available for reuse as many times as desired. For example, we
construct words using the 26 letters of the alphabet; the words may be as long as
desired with letters used repeatedly. Or we may draw cards from a deck, replacing
a card after each draw; we may draw as many cards as we like with cards used
repeatedly. We can still talk about permutations or combinations of r objects out
of n, but with repetitions allowed, r might be greater than n.
Counting the number of permutations of r objects out of n distinct objects
with repetition is easy. We have n choices for the first object and, because we can
repeat that object, n choices for the second object, n choices for the third, and so
on. Hence, the number of permutations of r objects out of n distinct objects with
repetition allowed is n
r
.
To determine the number of combinations of r objects out of n distinct objects
with repetition allowed, we use a rather clever idea.
example 58
A jeweler designing a pin has decided to use five stones chosen from a supply of
diamonds, rubies, and emeralds. How many sets of stones are possible?
Because we are not interested in any ordered arrangement of the stones, this is
a combinations problem rather than a permutations problem. We want the number
of combinations of five objects out of three objects with repetition allowed. The
pin might consist of 1 diamond, 3 rubies, and 1 emerald, for instance, or 5 diamonds. We can represent these possibilities by representing the stones chosen by
5 asterisks and placing markers between the asterisks to represent the distribution
among the three types of gem, diamonds, rubies, and emeralds. For example, we
could represent the choice of 1 diamond, 3 rubies, and 1 emerald by
* 0 *** 0 *
while the choice of 5 diamonds, 0 rubies, and 0 emeralds would be represented by
***** 0 0
Although we wrote the asterisks and markers in a row, there is no ordering implied.
We are just looking at seven slots holding the five gems and the two markers, and
the different choices are represented by which of the seven slots are occupied by
asterisks. We therefore count the number of ways to choose five items out of seven,
which is C(7, 5) or
7!
5!2!