Its Principles and Techniques (2)

4. Subsets and Arrangements. Given a set 5 of 10 objects, how many 3-element subsets of S are there? If, further, the 3 elements chosen are to be arra...

0 downloads 53 Views 2MB Size
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 1989-90 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 3-element 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 4-element 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 r-element 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

1-element

4

2-element

{1, 2), {1, 3), {1, 4), {2, 3), {2, 4), {3, 4}

6

3-element

{1, 2, 3}, {1, 2, 4), {1, 3, 4), {2, 3, 4}

4

4-element

{1, 2, 3, 4}

1

Consider the

rth

3rd

t t choices

0 {1), {2), {3), {4}

0-element

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 r-permutation of INn, and denote by P~ the number

INn= {1, 2, .. In).

of r-permutations of INn. Thus, we have For

r=

0, 1, ... ,

n,

let ( ~) denote the number of r-element

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 2-element subsets of INs = {1, 2, 3, 4, 5}? By listing all the 2-element subsets of INs as shown below:

n! = n(n- 1) . . . 3-2-1. 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- r-1) ... 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 r-element 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 r-permutations and r-combinations of an n-element 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 r-permutation

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"r-1;

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"r-1 + P""r-1 + ... + P'r-1 )•

8 at her right.

We shall now return to the problem of determining the value

Solution.

of ( ~ ). The number P~ of r-permutations 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 r-permutation of JN", we may proceed in the following manner: first select an r-element 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 r-element 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 r-permutations

(respectively, r-element 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;

r-permutations (respectively, r-element subsets) of any n-element

(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 r-element subset of 5 is also called

(xii) G is between A and 8 (need not be adjacent).

an r-combination of 5. Thus, the quantity ( ~) is the number of r-combinations 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 7-member committee

(i) As shown in the diagram below, a has 3 choices (i.e., 2, 3, or 4), say

This is the number of 7-element 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 3-permutaion from the 9-element 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 6-digit 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 6-digit 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 2-permutation 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 japan-Singapore 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 7-member 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) 6-4 + 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