Combinations and Permutations 55

Combinations and Permutations

I thought the best way to explain combinations and permutations would be to give

a concrete example.

I’ll start by explaining the ? Problem, then I’ll establish a good * way of

thinking, and finally I’ll present a ! Solution.

? Problem

Reiji bought a CD with seven different songs on it a few days ago. Let’s call the

songs A, B, C, D, E, F, and G. The following day, while packing for a car trip he had

planned with his friend Nemoto, it struck him that it might be nice to take the

songs along to play during the drive. But he couldn’t take all of the songs, since

his taste in music wasn’t very compatible with Nemoto’s. After some deliberation,

he decided to make a new CD with only three songs on it from the original seven.

Questions:

1. In how many ways can Reiji select three songs from the original seven?

2. In how many ways can the three songs be arranged?

3. In how many ways can a CD be made, where three songs are chosen from a pool of

seven?

* Way of Thinking

It is possible to solve question 3 by dividing it into these two subproblems:

1. Choose three songs out of the seven possible ones.

2. Choose an order in which to play them.

As you may have realized, these are the first two questions. The solution to

question 3, then, is as follows:

In how many ways can

Reiji select three songs

from the original seven?

In how many ways can

the three songs be

arranged?

In how many ways can

a CD be made, where three

songs are chosen from a

pool of seven?

Solution to Question 1 · Solution to Question 2 = Solution to Question 3

56 Chapter 2 The Fundamentals

! Solution

1. In how many ways can Reiji select three songs from the original seven?

All 35 different ways to select the songs are in the table below. Feel free to

look them over.

Pattern 1 A and B and C

Pattern 2 A and B and D

Pattern 3 A and B and E

Pattern 4 A and B and F

Pattern 5 A and B and G

Pattern 6 A and C and D

Pattern 7 A and C and E

Pattern 8 A and C and F

Pattern 9 A and C and G

Pattern 10 A and D and E

Pattern 11 A and D and F

Pattern 12 A and D and G

Pattern 13 A and E and F

Pattern 14 A and E and G

Pattern 15 A and F and G

Pattern 16 B and C and D

Pattern 17 B and C and E

Pattern 18 B and C and F

Pattern 19 B and C and G

Pattern 20 B and D and E

Pattern 21 B and D and F

Pattern 22 B and D and G

Pattern 23 B and E and F

Pattern 24 B and E and G

Pattern 25 B and F and G

Pattern 26 C and D and E

Pattern 27 C and D and F

Pattern 28 C and D and G

Pattern 29 C and E and F

Pattern 30 C and E and G

Pattern 31 C and F and G

Pattern 32 D and E and G

Pattern 33 D and E and G

Pattern 34 D and F and G

Pattern 35 E and F and G

Choosing k among n items without considering the order in which they are

chosen is called a combination. The number of different ways this can be done

is written by using the binomial coefficient notation:

n

k

which is read “n choose k.”

In our case,

7

3

= 35

Start Free Trial

No credit card required