6.3 Permutations and Combinations

Question 1

what are two strategies in solving counting problems?

Answer 1

1. finding the number of ways to arrange a specified number of distinct elements of a set of a particular size, where the order of the elements matters
2. 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

Question 2

In how many ways can we select three students from a group of five students to stand in line for
a picture?

Answer 2

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.

Question 3

In how many ways can we arrange all five of these students in a line for a picture?

Answer 3

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.

Question 4

permutation

Answer 4

An ordered arrangement of a set of objects

Question 5

r-permutation

Answer 5

An ordered arrangement of r elements of a set

Question 6

Let S = {1, 2, 3}. The ordered arrangement 3, 1, 2 is what?

Answer 6

a permutation of S

Question 7

Let S = {1, 2, 3}. The ordered arrangement 3, 2 is what?

Answer 7

a 2-permutation of S

Question 8

Let S = {a, b, c}. What are the 2-permutations of S?

Answer 8

The ordered arrangements a, b; a, c; b, a; b, c; c, a;
and c, b

Question 9

P(n, r)

Answer 9

If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are

P(n, r) = n(n − 1)(n − 2) ⋯ (n − r + 1)

r-permutations of a set with n distinct elements.

Question 10

Prove P(n, r) = n(n − 1)(n − 2) ⋯ (n − r + 1)

Answer 10

We will use the product rule to prove that this formula is correct.

The first element of the permutation can be chosen in n ways because there are n elements in the set.

There are n − 1 ways to choose the second element of the permutation, because there are n − 1 elements left in the set after using the element picked for the first position.

Similarly, there are n − 2 ways to choose the third element, and so on, until there are exactly n − (r − 1) = n − r + 1 ways to choose the rth element.

Consequently, by the product rule, there are n(n − 1)(n − 2) ⋯ (n − r + 1) r-permutations of the set.

Question 11

1 If n and r are integers with 0 ≤ r ≤ n, then P(n, r) = ?

Answer 11

Question 12

Prove

Answer 12

Question 13

How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize winner from 100 different people who have entered a contest?

Answer 13

Because it matters which person wins which prize, the number of ways to pick the three prize winners is the number of ordered selections of three elements from a set of 100 elements, that is, the number of 3 permutations of a set of 100 elements.

Consequently, the
answer is
P(100, 3) = 100 ⋅ 99 ⋅ 98 = 970,200.

Question 14

Suppose that there are eight runners in a race. The winner receives a gold medal, the second place finisher receives a silver medal, and the third-place finisher receives a bronze medal.

How many different ways are there to award these medals, if all possible outcomes of the race can occur and there are no ties?

Answer 14

The number of different ways to award the medals is the number of 3-permutations of a set with eight elements.

Hence, there are P(8, 3) = 8 ⋅ 7 ⋅ 6 = 336 possible ways to award the medals.

Question 15

Suppose that a saleswoman has to visit eight different cities. She must begin her trip in a specified city, but she can visit the other seven cities in any order she wishes.

How many possible orders can the saleswoman use when visiting these cities?

Answer 15

The number of possible paths between the cities is the number of permutations of seven elements, because the first city is determined, but the remaining seven can be ordered arbitrarily.

Consequently, there are 7! = 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 5040 ways for the saleswoman to choose her tour.

If, for instance, the saleswoman wishes to find the path between the cities with minimum distance, and she computes the total distance for each possible path, she must
consider a total of 5040 paths!

Question 16

How many permutations of the letters ABCDEFGH contain the string ABC ?

Answer 16

Because the letters ABC must occur as a block, we can find the answer by finding the number of permutations of six objects, namely, the block ABC and the individual letters D, E, F, G, and H.

Because these six objects can occur in any order, there are 6! = 720 permutations of the letters ABCDEFGH in which ABC occurs as a block

Question 17

How many different committees of three students can be formed from a group of four students?

Answer 17

To answer this question, we need only find the number of subsets with three elements from the set containing the four students.

We see that there are four such subsets, one for each of the four students, because choosing three students is the same as choosing one of the four students to leave out of the group.

This means that there are four ways to choose the three students for the committee, where the order in which these students are chosen does not
matter.

Question 18

r-combination

Answer 18

an unordered selection of r elements from the set

Question 19

Let S be the set {1, 2, 3, 4}. What is {1, 3, 4}?

Answer 19

A 3-combination from the set

Question 20

binomial coefficient

Answer 20

The number of r combinations of a set with n distinct elements, denoted C(n, r) or alternately,

Question 21

What is the number of r-combinations of a set with n elements?

Answer 21

When n is a nonnegative integer and r is an integer with 0 ≤ r ≤ n,

Question 22

Prove C(n, r)

method 1

Answer 22

The P(n, r) r-permutations of the set can be obtained by forming the C(n, r) r-combinations of the set, and then ordering the elements in each r-combination, which can be done in P(r, r) ways.

Consequently, by the product rule, P(n, r) = C(n, r) ⋅ P(r, r). You can plug and chug/solve for C(n, r) algebraically to yield the solution

Question 23

Prove C(n, r)

method 2

Answer 23

We can also use the division rule for counting to construct a proof of this theorem.

Because the order of elements in a combination does not matter and there are P(r, r) ways to order r elements in an r-combination of n elements, each of the C(n, r) r-combinations of a set with n elements corresponds to exactly P(r, r)r-permutations.

Question 24

How many poker hands of five cards can be dealt from a standard deck of 52 cards?

Answer 24

Because the order in which the five cards are dealt from a deck of 52 cards does not matter, there are
C(52, 5) different hands of 5 cards that can be dealt.

Question 25

How many ways are there to select 47 cards from a standard deck of 52 cards?

Answer 25

C(52, 47) = C(52, 52-5) = C(52, 5)

Question 26

what is a useful identity for combinations?

Answer 26

Let n and r be nonnegative integers with r ≤ n. Then C(n, r) = C(n, n − r)

Question 27

combinatorial proof

Answer 27

A proof that uses counting arguments to prove that both sides of the identity count the same objects but in different ways or a proof that is based on showing that there is a bijection between the sets of objects counted by the two sides of the identity. These two types of proofs are called double counting proofs and bijective proofs, respectively.

Question 28

use a bijective proof to show that C(n, r) = C(n, n − r) for all integers n and r with 0 ≤ r ≤ n.

Answer 28

n. Suppose that S is a set with n elements. The function that maps a subset A of S to Abar is a bijection between subsets of S with r elements and subsets with n − r elements (as the reader should verify). The identity C(n, r) = C(n, n − r) follows because when there is a bijection between two finite sets, the two sets must have the same number of elements.

Question 29

use a double counting proof to show that C(n, r) = C(n, n − r) for all integers n and r with 0 ≤ r ≤ n.

Answer 29

Alternatively, we can reformulate this argument as a double counting proof. By definition, the number of subsets of S with r elements equals C(n, r). But each subset A of S is also determined by specifying which elements are not in A, and so are in A. Because the complement of a subset of S with r elements has n − r elements, there are also C(n, n − r) subsets of S with r elements. It follows that C(n, r) = C(n, n − r).

Question 30

How many ways are there to select five players from a 10-member tennis team to make a trip to a match at another school?

Answer 30

The answer is given by the number of 5-combinations of a set with 10 elements. The number of such combinations is C(10, 5)

Question 31

A group of 30 people have been trained as astronauts to go on the first mission to Mars. How many ways are there to select a crew of six people to go on this mission (assuming that all crew members have the same job)?

Answer 31

The number of ways to select a crew of six from the pool of 30 people is the number of 6-combinations of a set with 30 elements, because the order in which these people are chosen does not matter. The number of such combinations is C(30, 6)

Question 32

How many bit strings of length n contain exactly r 1s?

Answer 32

The positions of r 1s in a bit string of length n form an r-combination of the set {1, 2, 3, … , n}. Hence, there are C(n, r) bit strings of length n that contain exactly r 1s.

Question 33

Suppose that there are 9 faculty members in the mathematics department and 11 in the computer science department. How many ways are there to select a committee to develop a discrete mathematics course at a school if the committee is to consist of three faculty members from the mathematics department and four from the computer science department?d

Answer 33

By the product rule, the answer is the product of the number of 3-combinations of a set with nine elements and the number of 4-combinations of a set with 11 elements. C(9, 3) ⋅ C(11, 4) = 27,720.