Section 4.4 Permutations and Combinations
281
generate all possible ticket numbers. Or the county council (a group of 12 members) wants to form a subcommittee of 4 members but wants to pick the combination of council members it feels can best work together. The council could ask
someone to generate all C(12, 4) = 495 potential subcommittees and examine
the membership of each one. We see that in some situations, simply counting the
number of permutations or combinations is not enough; it is useful to be able to
list all the permutations or combinations.
example 59
Example 47 asked for the number of permutations of the three objects a, b, and c.
The answer is given by the formula P(3,3) = 3! = 6. However Example 47 went
on to list the six permutations:
abc, acb, bac, bca, cab, cba
This list presents the six permutations using lexicographical ordering, that is, the
order in which they would be found in a dictionary if they were legitimate words.
Thus abc precedes acb because although both words begin with the same first
character, for the second character, b precedes c. If we had three integers, say 4, 6,
and 7, instead of three alphabetical characters, the lexicographical ordering of all
six permutations would present values in increasing numerical order:
467, 476, 647, 674, 746, 764
PraCtiCe 36 Arrange the following list of permutations in lexicographical order:
scary, yarsc, scyra, cysar, scrya, yarcs
■
Words that are close in lexicographical order have the maximum number of
matching leftmost characters or, equivalently, differ in the fewest rightmost characters. We use this characteristic to develop a process to generate all permutations
of the integers {1, …, n} in lexicographical order.
example 60
Consider the set {1, 2, 3, 4, 5}. The smallest numerical value (the first permutation)
is given by the increasing order of all the integers, namely,
12345
To generate the next number in lexicographical order, we want to retain as many
of the leftmost digits as possible. Clearly we can’t keep the leftmost four digits because this also determines the fifth digit. To keep the leftmost three digits, 123 − −,
we must be able to rearrange the remaining two digits to represent a larger value
than they do now. Reading 12345 from right to left, we find in the last two digits
that 4 < 5, which means we can reverse the 4 and the 5 to get
12354
281
generate all possible ticket numbers. Or the county council (a group of 12 members) wants to form a subcommittee of 4 members but wants to pick the combination of council members it feels can best work together. The council could ask
someone to generate all C(12, 4) = 495 potential subcommittees and examine
the membership of each one. We see that in some situations, simply counting the
number of permutations or combinations is not enough; it is useful to be able to
list all the permutations or combinations.
example 59
Example 47 asked for the number of permutations of the three objects a, b, and c.
The answer is given by the formula P(3,3) = 3! = 6. However Example 47 went
on to list the six permutations:
abc, acb, bac, bca, cab, cba
This list presents the six permutations using lexicographical ordering, that is, the
order in which they would be found in a dictionary if they were legitimate words.
Thus abc precedes acb because although both words begin with the same first
character, for the second character, b precedes c. If we had three integers, say 4, 6,
and 7, instead of three alphabetical characters, the lexicographical ordering of all
six permutations would present values in increasing numerical order:
467, 476, 647, 674, 746, 764
PraCtiCe 36 Arrange the following list of permutations in lexicographical order:
scary, yarsc, scyra, cysar, scrya, yarcs
■
Words that are close in lexicographical order have the maximum number of
matching leftmost characters or, equivalently, differ in the fewest rightmost characters. We use this characteristic to develop a process to generate all permutations
of the integers {1, …, n} in lexicographical order.
example 60
Consider the set {1, 2, 3, 4, 5}. The smallest numerical value (the first permutation)
is given by the increasing order of all the integers, namely,
12345
To generate the next number in lexicographical order, we want to retain as many
of the leftmost digits as possible. Clearly we can’t keep the leftmost four digits because this also determines the fifth digit. To keep the leftmost three digits, 123 − −,
we must be able to rearrange the remaining two digits to represent a larger value
than they do now. Reading 12345 from right to left, we find in the last two digits
that 4 < 5, which means we can reverse the 4 and the 5 to get
12354