COUNTING Its Principles and Techniques (2) by K M Koh and B P Tan
•••••••••••••••••••••••••••••• Associate Professor Koh Khee Meng obtained his first degree from Nal'!yang University in 1968 and PhD from Manitoba, Canada, in 1971. He then returned to teach at Nanyang University Mr Tan Ban Pin is a PhD student in Mathematics at
and he has been with the Department of
NUS. His area of research is graph theory. He
mathematics of NUS since 1980. He was
obtained his BSc with Honours in Mathematics in
the Chairman of the Singapore
1992from NUS. Mr Tan was the
Mathematical Olympiad Training
Treasurer and the Academic
Committee from 1991 to 1993 and he was
Chairman of the NUS Mathematics
awarded the Faculty of Science
Society in the 198990 academics
Mathematics Teaching Award in 1994.
year. He is the author of several articles in the NUS Mathematics Society annual publications. athemaNcal~
M EDLEY
lijM
Before answering this question, let us consider a different but
4. Subsets and Arrangements. Given a set 5 of 10 objects, how many 3element subsets of S are there? If, further, the 3 elements chosen are to be arranged in a row, where the ordering counts, how many ways can this
related problem. How many ways are there to arrange any two elements of IN4 = {1, 2, 3, 4} in a row? All such arrangements are shown below: 12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43.
be done? In this article, our attention will be focused on the aboved two basic counting problems. We shall see how the Multiplication Principle (MP) that we learned in Part (1) of the article can be used to solve the above problems, and how (MP) can be incorporated with the Addition Principle (AP) to
Thus there are '12' ways to do so. Indeed, we can get the answer easily without listing all such arrangements. We observe that there are '4' ways (choosing 1, 2, 3 or 4) to fill the 1st position, and '3' ways to fill the 2nd position. Thus, by (MP),
enable us to solve more complicated problems.
the desired number of ways is 4 ·3 = 12, which agrees with Consider the 4element set IN4 =
!1,
2, 3, 4}. How many
subsets of IN4 are there? This question can be answered readily by listing all the subsets of IN4 • Table 1 displays all the relement subsets of IN4 , where element subsets (0
r = 0, 1, r 4) are
2, 3, 4. The numbers of
r
what we have obtained. In general, how many ways are there to arrange any of INn, where 0
recorded on the right hand
1st
column of the table.
Subsets of N4
I
number
2nd
I
n
1element
4
2element
{1, 2), {1, 3), {1, 4), {2, 3), {2, 4), {3, 4}
6
3element
{1, 2, 3}, {1, 2, 4), {1, 3, 4), {2, 3, 4}
4
4element
{1, 2, 3, 4}
1
Consider the
rth
3rd
t t choices
0 {1), {2), {3), {4}
0element
r elements
n, in a row?
r
I
I
I
n (r 1)
n 1 choices
r spaces
t choices
shown in the above diagram. We wish
r elements from {1, 2, ... , n} to fill the r spaces, where the orderings of elements count. There are n choices for the 1st space. After fixing one in the 1st space, there are n  1
to choose
choices for the 2nd space. After fixing one in the 2nd space,
Table 1.
there are n  2 choices for the 3rd space, and so on. After Numbers of this kind (i.e., 1, 4, 6, 4, 1) are so useful and important that mathematicians had introduced special symbols
fixing one in (r 1)th space, there are n  (r 1) choices for the rth space. Thus, by (MP), the number of ways to arrange any
to denote them.
r elements from INn in a row is given by n(n 1)(n 2) ... (n (r 1)).
Given a positive integer n, let
For convenience, let us call an arrangement of any r elements from INn an rpermutation of INn, and denote by P~ the number
INn= {1, 2, .. In).
of rpermutations of INn. Thus, we have For
r=
0, 1, ... ,
n,
let ( ~) denote the number of relement
P~ = n(n 1)(n 2) ... (n r + 1)
subsets of INn. Thus, Table 1 tells us that
(~)
= 1,
(~)
= 4,
(~)
For simplicity, given a positive integer n, define n! to be the = 6, (;) = 4 and(:)= 1.
The symbol ( ~) is read 'n choose r'. Some other symbols for
product of the n consecutive integers n, n 1, ... , 3, 2, 1; that is,
this quantity include enr and nc.r What is the value of ( ~ ), the number of 2element subsets of INs = {1, 2, 3, 4, 5}? By listing all the 2element subsets of INs as shown below:
n! = n(n 1) . . . 321. Thus 4! = 4·3·2·1 = 24. The symbol 'n!' is read 'n factorial'. By convention, we define 0! = 1. Using the 'factorial' notation, we now have
P~ = n (n  1) ... (n  r + 1) n(n 1) ... (n r+ 1)(n r)(n r1) ... 2·1 (n  r)(n  r  1)... 2 ·1
{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}, we see that there are '10' in number. Thus, by definition,
(~)
=
(1)
n! (n  r)!
10. That is,
When n is large, it would be tedious to list all the relement subsets of INn just to determine what the value of ( ~) is. Is there a more economical way to find (~)?
.r.ll Mathematical
....
EDLEY
September 199S
pn = ~n_!~ r (n  r)!
(2)
(ii) (~) = (~_;) +
= 4 and r = 2, we obtain p4 = _ 4_!=_±!_= 4.3.2.1 = 4·3 = 12
When n
l
(4 2)!
2!
2.1
I
(n ~ 1), where 1
r
n 1.
5. Applications.
which agrees with what we found before.
Having introduced the concepts of rpermutations and rcombinations of an nelement set, and deriving the formulae
Consider two extreme cases when r = 0 and r When r
= 0,
= n respectively.
by (2), n!
n
Po= (n
for
P;
and ( ~ ), we shall now give some examples to illustrate
how these can be applied. n!
0)!
=nr=
1.
Example 5.1.
r = n,
an rpermutation
There are 4 girls and 5 boys in a class, which include two
of JN" is simply called a permutation of JN". Thus, by (2) and
(How could this be explained?) When
particular boys A and 8, and one particular girl G. Find the
that 0! = 1, the number of permutations of JN" is given by
P"= _ n_!  =~ = nl n (n  n)! 0! ·
(3)
( "I)
(ii) A and 8 are adjacent;
p"r + r p"r1;
pn+1 _ r
(i) There are no restrictions;
n,
Problem 4.1. Show that for 1 
1 ( .1.1) p"+r 
r.I
number of ways to arrange them in a row in each of the following cases:
(iii) G is at the centre, A at her left (need not be adjacent) and
1 + r (P"r1 + P""r1 + ... + P'r1 )•
8 at her right.
We shall now return to the problem of determining the value
Solution.
of ( ~ ). The number P~ of rpermutations of JN" is given by (2).
(i) This is the number of permutations of the 9 children.
Let us count this number in a different way. To obtain an rpermutation of JN", we may proceed in the following manner: first select an relement subset of JN"' and then arrange the
The answer is 9!. (ii) Treat !A, 8} as a single entity. The number of ways to arrange the remaining 7 children together with this entity is
r elements of the subset in a row. The number of ways for the
(7
first step is, by definition, ( ~ ), while that for the second step is, by (3), r!. Thus, by (MP),
p;
+ 1)!. But A and 8 can permute themselves in '2' ways.
Thus the desired number of ways is, by (MP), 2·8!. (iii)
= (~)(r!).
®
Hence, by (2),
(4)
As shown above, A has '4' choices and 8 also has '4' choices. The remaining 6 children can be placed in 6! ways. By (MP), the desired number of ways is 4·4·6!.
When n = 5 and r = 2, we have, by (4),
(5) 2
5! = 2!(5  2)!
5!
~=
10
Problem 5.1. (Continuation of Example 5.1)
'
which agrees with what we obtained before. Note that, in particular, we have(;) = 1 and (~) = 1. By (4), we can now compute the value of(~) without listing all the relement subsets
(iv) (v) (vi)
A and 8 are at the two ends; G is at the centre and adjacent to A and 8; A, 8, and G form a single block (i.e., there is no other child between any two of them);
of JN""
(vii) All girls form a single block; We define
P; (respectively,(~)) as the number of rpermutations
(respectively, relement subsets) of JN" =
P;
!1, 2,
(viii) All girls form a single block and all boys form a single
... , n}. Actually,
block;
(respectively, ( ~ )) can be defined as the number of
(ix)
No two of A, 8 and G are adjacent;
rpermutations (respectively, relement subsets) of any nelement
(x)
All boys form a single block and G is adjacent to A;
set 5, since it is the number but not the nature of the elements
(xi)
Boys and girls alternate;
in the set that counts. Any relement subset of 5 is also called
(xii) G is between A and 8 (need not be adjacent).
an rcombination of 5. Thus, the quantity ( ~) is the number of rcombinations of 5.
Example 5.2. Find the number of integers between 2000 and 5000 in which
Problem 4.2. Show that (i)
(~) = (n ~ r), where 0
no digit is repeated in each of the following cases:
r
n· I
athemancal 11!'1':1
MEDLEY
~
(i) There are no additional restrictions;
Solution.
(ii) The integers are even.
(i)
set. By definition, the desired number is (
Solution. Let abed be a required integer.
1 ;).
(ii) This is the number of ways to form a 7member committee
(i) As shown in the diagram below, a has 3 choices (i.e., 2, 3, or 4), say
This is the number of 7element subsets of a 17 element
from the 9 japanese. Thus the desired number is (
a = 2.
~).
(iii) We first select a member from the 8 Singaporeans and then select the remaining 6 from the 9 japanese. By (MP), the desired number is ( ~)(
'bed' corresponds
to a 3permutaion from the 9element set (0, 1, 3, 4, ... , 9}. Thus the required number of integers is
3·Pi. (ii) Again,
8( ~).
=
(iv) Obviously, the desired number is ( ~)
{2, 3, 4} Since no digit is repeated, a way of forming
~)
(v) There are 4 cases; namely,
= 8.
r Singaporeans, where r = 0, 1,
2, 3. Thus, by (AP), the desired number is
C)
+
(~)(~)
+
(~)(~)
+
(~)(!)·
Example 5.4.
a = 2, 3, or 4. We divide the problem into two
cases.
As shown in Example 2.1 (Part (1 )), the number of 6digit binary sequences is 2
6
•
How many of them contain exactly
two O's (e.g., 001111, 101101, ... )?
Case (1) Solution
a = 3 (odd)
Forming a 6digit binary sequence with two O's is the same as
d = 4.
choosing two spaces from the following 6 spaces into which
Then a way of forming 'be' is a 2permutation from the 8
the two O's are put (the rest are then occupied by 1's) as
element set (0, 1, 2, 5, 6, 7, 8, 9}. Thus the required number
shown below
In this case, d has '5' choices (i.e., 0, 2, 4, 6 or 8), say
of integers is
5.P~.
(1)
(2)
(3)
a = 2 or 4 (even) In this case,
d has '4' choices (Why?), and the number of ways
to form 'be' is
(5)
(6)
0
0
Case (2)
(4)
t
t
0
0
Thus the number of such binary sequences is (
~ ).
P~. The required number of integers is 2.4.P~. Example 5.5.
By (AP), the desired number of integers is
Figure 5.1 shows 10 distinct points on the circumference of a circle. (i) How many chords of the circle are there formed by these
Problem 5.2. (Continuation of Example 5.2) (iii) The integers are odd;
points? (ii) If no 3 of the chords are concurrent within the circle, how
(iv) The integers are divisible by 5;
many points of intersection of these chords are there within
(v) The integers are greater than 2345.
the circle? 1 10
Example 5.3.
9
2
8
At a japanSingapore conference held in Singapore, there are
3
17 participants from the two countries. Among them, 9 are 4
japanese.
7
6
In how many ways can a 7member committee be formed 5
from these participants in each of the following cases:
Figure 5.1
(i)
there are no restrictions?
(ii) there is no Singaporean in the committee?
Solution
(iii) there is exactly one Singaporean in the committee?
(i) Every chord joins two of the ten points, and every two of
(iv) the committee consists of Singaporeans?
the ten points determine a unique chord. Thus the required
(v) there are at most three Singaporeans in the committee?
number of chords is
r,r.'ll M•thematicat . . _ ED~EY
September 1995
C~).
In how many ways can 11 be written as a sum of 5 natural
(ii)
numbers, taking order into account?
Problem 5.7. Four people A, B, C and 0 can be paired off in the following three different ways:
(1) {!A, B), (C, O}}, Every point of intersection of two chords corresponds to four
(2) {!A, C), (B, 0}},
of the ten points, and every four of the ten points determine
(3) {(A, o}, (B, cl}.
a point of intersection. Thus the required number of points of
.mtersect1on . .IS (10) . 4
In how many ways can 10 people be paired off?
Answers
Problem 5.3. In how many ways can a committee of 5 be formed from a group of 11 people consisting of 4 teachers and 7 students if (i)
M'
the committee must include exactly 2 teachers?
(ii) the committee must include at least 2 teachers? (iii) a particular teacher and a particular student are both in the committee?
Problem 5.1. (iv) 2.7!
(v) 2.6!
(ix) 6!7.6.5
(x) 2.4!4! (xi) 4!5!
(vi) 3!7!
(vii) 4!6!
(viii) 4!5!2!
(xii) 2.4.5.6.7.8.9
Problem 5.2.
2.5P~ + 4.P~ = 14.P~
(iii)
8
8
(iv) 2.3.P 2 = 6.P 2
Problem 5.4. How many rectangles are there in the following 5 x 8 rectangular grid?
9
8
7
9
8
2.P 3 + 6.P 2 + 5.P 1 + 4 or 3.P 3  2.P 2
(v)
7

2.P 1  3
Problem 5.3. (i)
(~)(i)
(ii)
(~)(i) + (~)(;) + (:)( ~)
(iii)
G)
Problem 5.4. Problem 5.5.
(~)(~)
The following figure shows 15 distinct points chosen on the
Problem 5.5.
sides of
ABC. (i)
(i)
6·4·5 + (
How many triangles can be formed from these points?
(ii) How many line segments are there joining any 2 points on different sides?
within
(iii) (
ABC. c,
+
(~)11
+
(Dw
(ii) 64 + 4·5 + 5·6
~)(~) + (~)(D + (~)( ~)
(iii) If no 3 of these line segments are concurrent, find the number of points of intersection of these line segments
~)9
+ (
~)4·5
+
(~)·5·6
+
(~)·6·4
Problem 5.6.
A
C2)
b, b]
b2 b,
Problem 5.7
8~~~~~~' C
9.7.5.3.1 or
C2°)(~)(~)(~)(~) 5!
Problem 5.6. The number 5 can be expressed as a sum of 3 natural numbers, taking order into account, in 6 ways;
5=1+1+3 =3+1+1 =2 + 1 +2
1+3 + 1
1+ 2 + 2 2+2+1. atllemaNcalm
MED LEY