O'Reilly logo

The Manga Guide to Linear Algebra by Ltd. Trend-Pro Co., Iroha Inoue, Shin Takahashi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 Nemotos. 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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required