Page 428 - Discrete Mathematics and Its Applications

6.3 Permutations and Combinations 407

2
∗ 45. Let x be an irrational number. Show that for some positive a) Assume that i k ≤ n for k = 1, 2,...,n + 1. Use the
integer j not exceeding the positive integer n, the absolute generalized pigeonhole principle to show that there
value of the difference between jx and the nearest integer are n + 1 terms a k 1 ,a k 2 ,...,a k n+1 with i k 1 = i k 2 =
to jx is less than 1/n. ··· = i k n+1 , where 1 ≤ k 1 <k 2 < ··· <k n+1 .
46. Let n 1 ,n 2 ,...,n t be positive integers. Show that if
n 1 + n 2 + ··· + n t − t + 1 objects are placed into b) Show that a k j >a k j+1 for j = 1, 2,...,n.[Hint:As-
t boxes, then for some i, i = 1, 2,...,t, the ith box con- sume that a k j <a k j+1 , and show that this implies that
tains at least n i objects. i k j >i k j+1 , which is a contradiction.]
∗ 47. An alternative proof of Theorem 3 based on the general-
ized pigeonhole principle is outlined in this exercise. The c) Use parts (a) and (b) to show that if there is no increas-
notation used is the same as that used in the proof in the ing subsequence of length n + 1, then there must be
text. a decreasing subsequence of this length.

6.3 Permutations and Combinations

Introduction

Many counting problems can be solved by finding the number of ways to arrange a specified
number of distinct elements of a set of a particular size, where the order of these elements
matters. Many other counting problems can be solved by finding the number of ways to select
a particular number of elements from a set of a particular size, where the order of the elements
selected does not matter. For example, in how many ways can we select three students from a
group of five students to stand in line for a picture? How many different committees of three
students can be formed from a group of four students? In this section we will develop methods
to answer questions such as these.

Permutations

We begin by solving the first question posed in the introduction to this section, as well as related
questions.

EXAMPLE 1 In how many ways can we select three students from a group of five students to stand in line for
a picture? In how many ways can we arrange all five of these students in a line for a picture?
Solution: First, note that the order in which we select the students matters. There are five ways
to select the first student to stand at the start of the line. Once this student has been selected,
there are four ways to select the second student in the line. After the first and second students
have been selected, there are three ways to select the third student in the line. By the product
rule, there are 5 · 4 · 3 = 60 ways to select three students from a group of five students to stand
in line for a picture.
To arrange all five students in a line for a picture, we select the first student in five ways,
the second in four ways, the third in three ways, the fourth in two ways, and the fifth in one
way. Consequently, there are 5 · 4 · 3 · 2 · 1 = 120 ways to arrange all five students in a line for
a picture. ▲

Example 1 illustrates how ordered arrangements of distinct objects can be counted. This leads
to some terminology.
A permutation of a set of distinct objects is an ordered arrangement of these objects.
We also are interested in ordered arrangements of some of the elements of a set. An ordered
arrangement of r elements of a set is called an r-permutation.