Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.6—Generating Permutations and Combinations
p.383, icon at Example 2
#1. Place the following permutations of 1, 2, 3, 4, 5, 6 in lexicographic order: 461325, 326145, 516243, 324165, 461235, 324615, 462135.
Solution:
Proceeding from smallest to largest we have:
Extra Examples
Section 5.6—Generating Permutations and Combinations
p.383, icon at Example 2
#1. Place the following permutations of 1, 2, 3, 4, 5, 6 in lexicographic order: 461325, 326145, 516243, 324165, 461235, 324615, 462135.
Solution:
Proceeding from smallest to largest we have:
324165, 324615, 326145, 461235, 461325, 462135, 516243.
p.383, icon at Example 2
#2. Find the permutation of 1, 2, 3, 4, 5, 6 immediately after 263541 in lexicographic order.
Solution:
The digits 5, 4, 1 are in descending order, so we need to increase the digit in the third position, 3. Replacing this digit 3 by 4 and then putting the remaining digits in increasing order, we have 264135.
#2. Find the permutation of 1, 2, 3, 4, 5, 6 immediately after 263541 in lexicographic order.
Solution:
The digits 5, 4, 1 are in descending order, so we need to increase the digit in the third position, 3. Replacing this digit 3 by 4 and then putting the remaining digits in increasing order, we have 264135.
p.383, icon at Example 2
#3. Find the permutation of 1, 2, 3, 4, 5, 6 immediately before 261345 in lexicographic order.
Solution:
The final four digits, 1345, are in increasing order. Therefore the permutation that comes immediately before this must have a 5 in the second position and the four digits to the right of the 5 in decreasing order. Thus, the predecessor of 261345 is 256431.
p.383, icon at Example 2
#4. If the permutations of 1, 2, 3, 4, 5, 6 are put in lexicographic order, with 123456 in position 1, 123465 in position 2, etc., find the permutation in position 362.
Solution:
There are 6! = 720 permutations of 1, 2, 3, 4, 5, 6. The first 120 (i.e., the permutations in positions 1 through 120) begin with 1, the second 120 (in positions 121 through 240) begin with 2, etc. Hence the first permutation beginning with 4, 412356, is in position 361. Therefore, the next permutation, 412365, will be in position 362.
#3. Find the permutation of 1, 2, 3, 4, 5, 6 immediately before 261345 in lexicographic order.
Solution:
The final four digits, 1345, are in increasing order. Therefore the permutation that comes immediately before this must have a 5 in the second position and the four digits to the right of the 5 in decreasing order. Thus, the predecessor of 261345 is 256431.
p.383, icon at Example 2
#4. If the permutations of 1, 2, 3, 4, 5, 6 are put in lexicographic order, with 123456 in position 1, 123465 in position 2, etc., find the permutation in position 362.
Solution:
There are 6! = 720 permutations of 1, 2, 3, 4, 5, 6. The first 120 (i.e., the permutations in positions 1 through 120) begin with 1, the second 120 (in positions 121 through 240) begin with 2, etc. Hence the first permutation beginning with 4, 412356, is in position 361. Therefore, the next permutation, 412365, will be in position 362.
p.383, icon at Example 2
#5. If the permutations of 1, 2, 3, 4, 5 are put in lexicographic order, in what position is the permutation 41253?
Solution:
There are 4! = 24 permutations of 1, 2, 3, 4, 5 that begin with 1; these permutations are in positions 1 through 24. Similarly, the permutations in positions 25 through 48 begin with 2 and the permutations in positions 49 through 72 begin with 3. Thus, the first permutation beginning with 4, 41235, is in position 73. Therefore 41253 is in position 74.
#5. If the permutations of 1, 2, 3, 4, 5 are put in lexicographic order, in what position is the permutation 41253?
Solution:
There are 4! = 24 permutations of 1, 2, 3, 4, 5 that begin with 1; these permutations are in positions 1 through 24. Similarly, the permutations in positions 25 through 48 begin with 2 and the permutations in positions 49 through 72 begin with 3. Thus, the first permutation beginning with 4, 41235, is in position 73. Therefore 41253 is in position 74.
No comments:
Post a Comment