Chapter 5

Permutations and Combinations

5.3     Combinations

Definition. A combination is a selection, in which the order does not matter, of objects from a collection. The number of combinations of n distinct objects taken r at a time is denoted by nCr.

The number of permutations of objects is related to the number of corresponding combinations. For example, the combinations of 4 objects A, B, C and D taken 3 at a time and the corresponding permutations are listed in the following table.
Combinations Permutations {A, B, C} {A, B, D} {A, C, D} {B, C, D} ABC ABD ACD BCD ACB ADB ADC BDC BAC BAD CAD CBD BCA BDA CDA CDB CAB DAB DAC DBC CBA DBA DCA DCB
We can see from the table that each combination gives rise to 3!(= 6) permutations. Since there are 4C3 combinations, the number of permutations must be 4C3 ⋅ 3!. Thus, we have
4C3 × 3! = 4P3
Generally, for integers n and r with 0 ≤ rn,
nCr × r! = nPr

If n and r are integers with 0 ≤ rn, then
nCr = nPr r! = n! r! (n - r)!
= n(n - 1) (n - 2) ... (n - r + 1) r (r - 1) (r - 2) ... 1.


Example 14.
In how many ways can a committee of 4 people be selected from a group of 10 people?
Solution
The number of ways is
10C4 = 10 ⋅ 9 ⋅ 8 ⋅ 7 4 ⋅ 3 ⋅ 2 ⋅ 1 = 210.

Example 15.
Evaluate   21C1 ,   21C21 , ⋅ 21C19 and 21C2 .
Solution
21C1 = 21
21C21 = 21! 21! (21 - 21)!
= 21! 21! 0!
= 21! 21! ⋅ 1
= 1

21P19 = 21! 19 (21 - 19)!
= 21! 19! 2!
= 21 ⋅ 20 ⋅ 19!19! ⋅ 2 ⋅ 1
= 210

21P2 = 21! 2! (21 - 2)!
= 21! 2! 19!
= 21 ⋅ 20 ⋅ 19!2 ⋅ 1 ⋅ 19!
= 210
We notice that 21C1 = 21, 21C21 = 1 and 21C19 = 21C2 = 21C21-19.

Generally, the integers n and r with 0 ≤ rn,
nC1 = n,     nCn = 1   and nCr = nCn-r

Example 16.
A music class consists of 5 piano players, 7 guitarists and 4 violinists. A band of 1 piano player, 3 guitarists and 2 violinists must be chosen to play at a school concert. In how many ways can the band be chosen?
Solution
From the music class,
1 piano player can be chosen in 5C1 ways,
3 guitarists can be chosen in 7C3 ways, and
2 violinists can be chosen in 4C2 ways.
So, the number of ways to choose a band is
5C17C34C2 = 5 ⋅ 7 ⋅ 6 ⋅ 5 3 ⋅ 2 ⋅ 1 4 ⋅ 32 ⋅ 1
= 1050

Example 17.
Suppose there are 4 black cars and 7 white cars. If all the cars are distinguishable, in how many ways can 3 cars of the same color be chosen?
Solution
To get the same color, the 3 cars must be all black or all white.
Out of 4 black cars, three can be chosen in 4C3 ways.
Out of 7 white cars, three can be chosen in 7C3 ways.
So, the required number of ways is
4C37C3 = 4 ⋅ 3 ⋅ 2 3 ⋅ 2 ⋅ 1 7 ⋅ 6 ⋅ 53 ⋅ 2 ⋅ 1
= 4 + 35
= 39 .

Example 18.
There are 6 different books. In how many ways can the books be given to 3 children, if the youngest wants to receive 3 books, the elder 1 and the eldest 2 respectively.
Solution
For the youngest child, the books can be chosen in 6C3 = 6 ⋅ 5 ⋅ 43 ⋅ 2 ⋅ 1 = 20 ways.
For the elder child, the books can be chosen in 3C1 = 3 ways.
For the eldest child, the books can be chosen in 2C2 = 1 ways.
So, the required number of ways is 20 ⋅ 3 ⋅ 1 = 60.

Example 19.
In how many ways can 4 fruits be selected out of 9 fruits, so as always to:
(a) include the largest fruit?   (Assume that such a largest fruit exists.)
(b) exclude the smallest fruit?   (Assume that such a smallest fruit exists.)
Solution
(a) The largest one is included in every selection. The number of ways only depends on the choice of the other three from the remaining 8 fruits, and hence it is
8C3 = 8 ⋅ 7 ⋅ 6&rasl; 3 ⋅ 2 ⋅ 1 = 56.
(b) Since the smallest one is excluded in every selection, we have to select 4 fruits from the remaining 8 fruits. So the required number ways is
8C4 = 8 ⋅ 7 ⋅ 6 ⋅ 5 4 ⋅ 3 ⋅ 2 ⋅ 1 = 70 .

fig 5.2

Exercise 5.3

1 Show that 12C57C4 = 12C48C5 .
Solution
nCr = n! r! (n - r)!
12C57C4 = 12×11×10×9×8×7×6×5!5! (12 - 5)! 7×6×5×4!4! (7 - 4)!
= 12×11×10×9×8×7×67×6×5×4×3×2×1 7×6×53×2×1
= 792 ⋅ 35
= 27720
12C48C5 = 12C12-48C5       (∵ nCr = nCn-r)
= 12C88C5
= 12×11×10×9× 8!8! (12 - 8)! 8×7×6×5!5! (8 - 5)!
= 12×11×10×91×2×3×4 8×7×63×2×1
= 495 × 56
= 27720
12C57C4 = 12C48C5 .

2. There are 10 candle holders, which are fixed in different locations along a line and each can hold only one candle. In how many ways can 7 identical candles be put in these holders?
Solution
Number of candle holders = 10
Number of identical candles = 7
Ways to be put in these holders = 10C7
= 10×9×8×7!7! (10 - 7)!
= 10×9×83×2×1
= 120

3. There are three parts in a test. Each of the first two parts contains 5 questions, but the last part only 4. If a student must answer all from the first part, 4 and 3 questions from the second and the last part respectively, in how many ways can this be done?
Solution
A student must answer 5 out of 5 questions from the first part = 5C5 = 1
A student must answer 4 out of 5 questions from the second part = 5C4
= 5×4!4! (5 - 4)!
= 5
A student must answer 3 out of 4 questions from the last part = 4C3
= 4×3!3! (4 - 3)!
= 4
Ways the test can be done = 1 × 5 × 4 = 20.

4. How many games can be played in a 9-team sport league if each team plays all other teams once?
Solution
Kind of sport league = 9-team
Number of teams that can be played in a game = 2
Number of games can be played = 9C2
= 9!2! (9 - 2)!
=9!2! 7!
= 9×8×7!1⋅2 ⋅ 7!
=9×41
= 36

5. How many lines are determined by 8 points, if no 3 such points are collinear?
How many triangles are determined by the points?
Solution
Number of points = 8
Number of points for each line = 2
Number of lines determined = 8C2
= 8C8-2       (∵ nCr = nCn-r)
= 8C6
= 8×7×6!6! (8 - 6)!
=8×71×2
= 28

6. In how many ways can 4 fruits be selected out of 9 fruits, having different size, so as always to include the largest fruit and exclude the smallest fruit?
Solution
The largest one is included in every selection and the smallest one is excluded.
The number of ways only depends on the choice of the other three from the remaining 7 fruits, and hence
it is 7C3
= 7×6×5×4×3!3! (7 - 3)!
= 7×6×5×41×2×3×4
= 35