Its Principles and Techniques ( 4)

Its Principles and Techniques ( 4) ... the form : 111 0 0 111 0000 000 11 00 1111 0 To have three 00 and four 11 in such a sequence, we must (i) put...

0 downloads 56 Views 2MB Size
COUNTING Its Principles and Techniques (4) by K. M. Koh and B. P. Tan

•••••••••••••••••••••••••••••• Professor Koh Khee Meng obtained his first degree from Nanyang University in 1968 and PhD from Manitoba, Canada , in 1971. He then returned to teach at Nanyang University and he has been with •

Mr Tan Ban Pin is a PhD student in Mathematics at

the Department of Mathematics of NUS

NUS. His area of research is graph theory. He

since 1980. He was the Chairman of the

obtained his BSc with Honours in Mathematics in

Singapore Mathematical Olympiad

J992from NUS. Mr Tan was the

Training Committee from 1991 to 1993

Treasurer and the Academic

and he was awarded the Faculty of

Chairman of the NUS Mathematics

Science Mathematics Teaching Award in

Society in the 1989-90 academics

1994, 1995 and 1996.

year. He is the author of several articles in the NUS Mathematics Society annual publications.

9. Distribution of Identical Objects into Distinct Boxes In Section 7 of [3], we have discussed the problem of distributing identical objects into distinct boxes. Let us consider

Suppose that there are

(I)

this problem again.

r identical

objects to be distributed

n distinct boxes.

into

If each box can hold at most one object, (thus

r :s; n), the number of ways of distribution is given

Figure 9.1 shows 7 distinct boxes into which 5 identical objects

by (~).

are to be distributed.

(II) If each box can hold any number of objects, the 1 number of ways of distribution is given by ( r + ~- ). (Ill) If each box must hold at least one object (thus r:? n), the number of ways of distribution is given by

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(

(r - n)

+ n - 1) .

r - n

' 1.e.,

(r - 1) r- n

·

Figure 9.1

Example 9.1 Eight letters are to be selected from the five English vowels

Question 1

a,

e, i, o, u with repetition allowed. In how many ways can this

Suppose that each box can hold at most one object. In how

be done if

many ways can this be done ?

(i) there are no other restrictions ?

As shown in Figure 9 .2, we first select 5 boxes from the

(ii) each vowel must be selected at least once?

seven, and then put an object in each of the 5 selected boxes. There are (

(i) Some examples of ways of selection are give below :

~)

ways for the first step, and 1 way for the

second. Thus the answer is

(~).

•I

•I

(1)

I• (2)

(3)

(4)

a, a, u, u, u, u, u, u; e, i, i, o, o, o, u, u; (3) a, e, i, i, o, o, u, u. (1) (2)

As shown in Figure 9.3, these selections can be treated as

•1•1 (5)

(6)

ways of distributing 8 identical objects into 5 distinct boxes.

(7)

Fig 9.2

(1)

<------4

Question 2

(2)

<------4

Suppose that each box can hold any number of objects. In

(3)

<------4

••• ••

••• • •• •• ••

0

u

••

how many ways can this be done?



••





••

a

e

Questions of this sort were studied in Section 7. Applying the

Figure

9.3

method of counting certain binary sequences and bijection principle

(BP), we obtain the answer to question 2 which is

Thus, by (BP) and result (II) above, the number of ways of

. by g1ven

(5+7-1). , 1.e. (11) .

. se Iect1on

5

5

Question 3

.IS g1ven . by (8 + 5 - 1) , .1.e, ( 12) . 4 8

(ii) As shown in the last box of Figure 9.3 , a way of selection

Suppose now that there are 11 identical objects (instead of 5) to be put into 7 distinct boxes. In how many ways can this be done if each box must hold at least one object?

which includes each vowel can be treated as a way of distribution such that no box is empty. Thus, by (BP) and result (Ill) above, the number of ways of selection is given by

To fulfil the requirement that no box is empty, we first put one

(

(8 - 5) + 5 -

8 - 5

1) .

' I.e,

( 7)

3 .

object in each box. We are now left with 4 objects, but are free to put them in any box. Again, by what we learned in

. 7, t he answer .IS g1ven . by Sect1on

(4 + 7-1) , .1.e., (10) . 4

Example 9.2

4

Consider the following two 13-digit binary sequences : Let us summarize what we discussed above by stating the

1 1 1 0 1 0 1 1 1 0 0 0 0,

following general results 1 0 0 0 1 1 0 0 1 1 1 1 0.

athematical

MEU~EY

11!'1'!11

llii:l

For binary sequences, any block of 2 adjacent digits is of the form : 00, 01 , 10, 11. In each of th e above sequences, there are three 00, two 01 , three 10 and four 11 . Find the number of 13-digit binary sequences which have exactly three 00,

Find the number of ways of distributing 10 identical tables into 5 distinct rooms in each of the following cases. (i) Room 1 holds at most 2 tables.

two 01 , three 10 and four 11. To have exactly three 10 and two 01 in a sequence, such a sequence must begin with ' 1', end with '0', and have the changeovers of ' 1' and '0' as shown below, where each of the boxes (1), (3) and (5) [resp. , (2), (4) and (6)] holds only '1' (resp. , '0') and at least one ' 1' (resp ., '0').

0

Problem 9.3

(ii) Each of room 1 and room 2 holds at most 1 table.

Problem 9.4 Show that the number of ways of distributing

r identical objects

into n distinct boxes such that box 1 can hold at most one object is given by

0

0

(1) [1 0] (2) [01] (3) [10] (4) [01] (5) [1 0] (6)

10. Distribution of Distinct Objects into Distinct Boxes For instance, the two sequences given in the problem are of the form :

As can be seen from the various examples given in Sections

7 and 9, the distribution problem, which deals with the counting of ways of distributing objects into boxes, is a basic

111

0

0

111

0000

model for many counting problems. In distribution problem, objects can be identical or distinct, and boxes too can be

11

000

00

1111

0

identical or distinct. Thus there are four cases to be considered; namely

To have three 00 and four 11 in such a sequence, we must

Objects

Boxes

(i) put three more '0' in boxes (2), (4) or (6) arbitrarily and

(1)

identical

distinct

(ii) put four more '1 ' in boxes (1), (3) or (5) arbitrarily. (Check

(2)

distinct

distinct

(3)

distinct

identical

(4)

identical

identical

that there are 13 digits altogether.) The number of ways to do (i)

.IS (3 + 3 -1) , 1.e., . 3

i.e.,

(~)-

is(;)(~) ,

(5) 2

w h"l1 e t hat o f (""11 ) .IS

(4

+

3- 1) ,

4

Thus, by (MP), the number of such sequences i.e., 150.

We have considered case (1) in Sections 7 and 9. Cases (3) and (4) will be discussed in due course. In this section, we shall consider Case(2). Before we proceed, we would like to

The following problem is taken from the American Invitational Mathematics Examination Paper (1986) :

point out that the ordering of the distinct objects in each box is not taken into consideration in the discussion in this section. Suppose that 5 distinct balls are to be put into 7 distinct

Problem 9.1

boxes.

In a sequence of coin tosses one can keep a record of the

Question 1 In how many ways can this be done if each box

number of instances when a tail is immediately followed by

can hold at most one ball?

a head, a head is immediately followed by a head , etc.. We denote these by TH, HH, etc.. For example, in the sequence

Question 2 In how many ways can this be done if each box can hold any number of balls?

HHTTHHHHTHHTTTT of 15 coin tosses we observe that there are five HH, three HT, two TH and four TT subsequences.

We first consider Question 1. As shown in Figure 10.1, let a,

How many different sequences of 15 coin tosses will contain

b, c, d and e denote the 5 distinct balls. First, we put 'a' (say)

exactly two HH, three HT, four TH and five TT subsequences?

Problem 9.2

a, b, c, d, e

/

Consider the following two 15-digit ternary sequences (formed by 0, 1 and 2) : 0 0 0 1 1 1 2 2 0 0 1 1 2 2 2 0 1 2 2 2 0 0 0 0 1 1 1 1 2 2 Observe that each of the sequences contains exactly three 00, three 11 , three 22, two 01 , two 12 and one 20. Find the number of such ternary sequences . . . , . Mathematical ~~iii~:.

EOLEY

September lSSE

(1)

(2)

(3)

(4)

(5)

Figure 10.1

(6)

(7)

into one of the boxes. There are 7 choices. Next, we consider

'b' (say). As each box can hold at most one ball, and one of the boxes is occupied by 'a', there are now 6 choices for 'b'. Likewise, there are, respectively, 5, 4 and 3 choices for 'c', 'd' and 'e'. Thus, by (MP), the number of ways of distribution is given by 7 · 6 · 5 · 4 · 3.

Let A be the set of ways of distributing 3 distinct objects into 4 distinct boxes 1, 2, 3 and 4 with no restriction, and let 8 be the set of 3-digit numbers using 1, 2, 3, 4 as digits with repetition allowed (e.g., 222, 441 , 431 , ... ). Establish a 1-1 correspondence between A and B.

Note that the above answer can be expressed as

P~ , which

as defined in Section 4 of [2], is the number of ways of arranging any 5 objects from the 7 distinct objects. The fact that the above answer is

Problem 10.2

P~ does not surprise us as there is a

Problem 10.3 Suppose that

m distinct objects are to be distributed into n

1-1 correspondence between the distributions of 5 distinct

distinct boxes so that each box contains at least one object

balls into 7 distinct boxes and the arrangements of 5 distinct

(thus m :2: n). In how many ways can this be done if

objects from 7 distinct objects as shown in Figure 10.2. (Find

(i) m = n?

(ii )

m = n + 1?

(iii) m = n

+ 2?

out the rule of the correspondence!)

{a, b, c, d, el

11, 2, 3, 4, 5, 6,

n

Problem 10.4 Find the number of ways of distributing 8 distinct objects into

(1)

(2)

(3)

(4)

(5)

(6)

.._..

41275

.._..

74321

(7)

3 distinct boxes if each box must hold at least 2 objects .

11. Other Variations Two cases of distribution problem were discussed in the preceding sections. In this section, we shall study some of

Figure 10.2

their variations. When

In general, we have : The number of ways of distributing

r distinct objects

.into n distinct boxes such that each box can hold at most one object (and thus

p;

identical objects are put in distinct boxes, whether the ordered or not makes no difference.

objects in each box are

r :5:

The situation is no longer the same if the objects are distinct as shown in Figure 11.1

n) is given by

(= _n!_). (n - r)!

de

ab c

(1)

(2)

in the boxes. As each box can hold any number of balls, there

e.

Thus, by (MP), the answer is 7

5

cb a

(1)

(2)

(3)

Figure 11.1

We now consider Question 2. There are 7 ways of putting 'a' are also 7 choices for each of the remaining balls b, c, d, and

(3)

ed

In Section 10, we did not consider the ordering of objects in each box. In our next example, we shall take it into account.



In general, we have :

Example 11.1 Suppose that 5 distinct objects

The number of ways of distributing r distinct objects into n distinct boxes such that each box can hold any number of objects is given by n'.

a, b, c, d, e are distributed into

3 distinct boxes, and that the ordering of objects in each box counts. In how many ways can this be done ? First, consider 'a' (say), clearly, there are 3 choices of a box for 'a' to be put in (say, 'a' is put in box 2). Next, consider

Problem 10.1 Find the number of ways for a teacher to distribute 6 different books to 9 students if

'b'. 'b' can be put in one of the 3 boxes. The situation is different if 'b' is put in box 2 due to the existence of 'a' in that box. As the ordering of objects in each box counts, if 'b' is put in box 2, then there are two choices for 'b', namely,

(i) there is no restriction; (ii) no student gets more than one book.

athematical

MED~EY

II!'CI llim

/

I

(1)

A - B - -- -

® 1\~ a

2

- } -H-D - -

3

- J - C- - -

4

-E-C - F- -

I

(3)

(2) Figure 11.2

Problem 11.2

left of 'a' or right of 'a' as indicated in Figure 11.2. Thus,

Solve Problem 10.3 under an additional condition that the

altogether, there are 4 choices for 'b', (say, 'b' is put in box 3).

ordering of objects in each box counts.

0

In our previous discussion on distribution problem, objects

~j\ I

(1)

a

I

are either

all identical or all distinct. We now consider a case

that is a mixture of these two.

b

Example 11.2

(3)

(2)

'a',

Four identical objects

Figure 11.3

three identical objects 'b' and two

identical objects 'c' are to be distributed into 9 distinct boxes

Now, consider 'c'. As shown in Figure 11.3, 'c' has 5 choices.

so that each box contains one object. In how many ways can

Continuing in this manner, we see that 'd' and 'e' have,

this be done?

respectively, 6 and 7 choices. Thus the answer is given by 3·4·5·6·7. Let us try a different approach to solve the above problem. First, we pretend that the objects

a, b,

c,

d and e are all

identical. The number of ways of distributing 5 identical objects into 3 distinct boxes is, by result (II) in Section 9, (

(~).

i.e.,

First, consider 4 a's (say). Among the 9 boxes, we choose 4 of them, and put one 'a' in each box chosen. Next, consider

5

+ ~-

1

3 b's (say). Among the 5 boxes that remain, we choose 3, and put one 'b' in each box chosen (see Figure11.4). Finally, we put a 'c' in each of the 2 remaining boxes.

),

Next, take such a way of distribution,

00

say

0 0 0

(1)

(2)

(3) (1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

Since the 5 objects are actually distinct and the ordering of Figure 11 .4

identical objects corresponds to 5! different distributions for distinct objects in each box counts, such a distribution for

objects. Thus, by (MP), the answer is given by

{i) ·5!, which

agrees with the first answer 3 · 4 · 5 · 6 · 7.

There are ( ~) ways for step 1, ( ~) ways for step 2 and ( ~) (= 1) way for step 3. Thus, by (MP), the answer is given by

In general, we have:

(~) ( ~) ·1 = _2l__ . __2_ = _ 9!_ The number of ways of distributing into

4!5!

r distinct objects

n distinct boxes such that the ordering of objects

3!2!

4!3!2!

Remark

in each box counts is given by (

r 1) . r.1

r + n -

In the above, 'a' is considered first, followed by considered first, followed by 'c' and

which is equal to

n (n + 1)(n + 2) ... ( n + r - 1).

'b' and 'c'.

The answer is independent of the order. For instance, if 'b' is

argument, we arrive at

'a', by applying a similar

C)(~)(:),

which is again

_1L_

4! 3! 2!.

There is a 1-1 correspondence between the distributions

Problem 11.1 Ten students are to line up in a 4-line queue as shown below. In how many ways can this be done?

..r..MathemaHcal ~

EDLEY

September 1996

considered in Example 11.2 and the arrangements of 4a's,

3b's and 2c's in a row as shown in Figure 11 .5.

Let A = {1 , 2, ... , m) and B = {1 , 2, ... , n), where m, n ~ 1. A

mapping f from A to B, denoted by f: A --7 B, is a rule which a of A a unique element f (a) of B.

assigns to each element lclblalalblalalblcl

~cbaabaabc

For instance, given A = {1 , 2, 3) and B = {1 , 2, 3, 4), the

g , h defined, respectively, by

following rules Figure 11.5

g (1) = 2

Thus, by the result of Example 11.2, the number of

B

A

B

g (2) = 4

3b's and 2c's in a row is given by

arrangements of 4 a's,

A

{ g (3) = 2

9! 4! 3! 2! .

h(1 ) =

In general, we have:

n1 identical objects of type 1, n2 identical objects of type 2, ... , nk identical objects of type k. Let n = n1 + n2 + ... + nk. Then the number of arrangements of these n objects in a row is given

{

Suppose that there are

h (2)

3

=4

h(3) = 1

are mappings from A to B. A mapping f: A --7 B is (i.e., 1-1 ) if f(i )

by

mapping

h

* f(j ) in

B whenever i

*j

injective

in A. Thus the

defined above is 1-1 while g is not (why?).

f : A --7 B can actually be regarded as a way of distributing m distinct objects 1, 2, .. . m into n distinct boxes 1, 2, ... , n (ordering of objects in each box does not count) A mapping

which is equal to

n!

in the following manner : f(i ) = j means that object ' i ' is put in box 'j '. Thus, the mappings g and

h defined above can be

treated as the ways of distribution shown below :

Problem 11.3

CD CD 1

Show that

g: (1)

(2)

(3)

(4)

n!

CD

h: (1)

(2)

(3)

(4)

Let us re-consider Example 11 .1 . We observe that there is a 1-1 correspondence between the distributions considered in Example 11 .1 and the arrangements of

a, b, c, d, e and ·2 1's

as shown in Figure 11.6. By the above result, the number of

Problem 11.5 Let A = (1, 2, .... , m) and

B = {1 ,2, ... ., n) , where m, n

~ 1.

Find

be

a

cde

de

<---->

be I a I de

ba

<---->

cde I I ba

(i)

the number of mappings from A to B;

(ii)

the number of 1-1 mappings from A to B (here, m ~ n);

(iii) the number of mappings (1)

(2)

(iv) the number of mappings Figure 11.6 arrangements of

a, b,

c,

2!

there exists

surjective (i.e., onto) if for each b E B, a E A such that f (a) = b. The mappings g and h

from {1, 2, 3) to (1 , 2, 3, 4) defined above are not surjective. Indeed, iff: {1 , 2, ... , m) --7 {1 , 2, ... , n) is an onto mapping, then

Problem 11.4 Find the number of arrangements of 3

f: A --7 B such that f (1) = 1.

A mapping f : A --7 B is

d, e and 2 1's is given by Zl, which

agrees also with the first two answers.

f : A --7 B such that f (i) < f(j ) in

B whenever i < j in A (here, m :o; n);

(3)

m ~ n (why?). Consider the following two h from {1 , 2, 3, 4) to {1 , 2, 3) :

mappings g and

x's, 4 y's and 5 z's in

g

a row if (i) there is no restriction;

y's are adjacent; (iii) any two x's are separated by at least 2 other letters. (ii) no two

It can be checked that g is onto while

h is not so. 'them,tical

MEDcEY

~ ~

Problem 11.6 Let A= {1 1 21

•••

1

m) and 8 = {1 1 21

•••

1

n}. Find the number

Problem 11.4

of onto mappings from A to 8 in each of the following cases:

m = n; (ii) m = n + 1; (iii) m = n + 2. (i)

(Compare this problem with Problem 10.3 .)

M'

Answers

(i)

12! 3!4!5!

(ii)

(~)

(iii) ( ~)

(i)

560

(ii)

64

(iii)

CD + CD + en

(ii) (1n + 2(1n +

(i) 9

(1~)

n!

nm - l

same as Problem 10.3

References

6

[1] K. M. Koh and B. P. Tan, Counting -Its Principles and Techniques (1 ), Mathematical Medley Vol 22 March (1995) 8-13.

(ii) 2l

[2] K. M. Koh and B. P Tan, Counting - Its Principles and Techniques (2), Mathematical Medley Vol 22 September (1995) 47-51.

3! Problem 10.2

[3] K. M. Koh and B. P Tan, Counting - Its Principles and Techniques (3), Mathematical Medley Vol 23 March (1996) 9-14 1

The i'h digit is j when and only when object i is put in box 1

ljl. Problem 10.3 (i) n!

(n; 1 )-n!

(iii)( n ; 2 )(; ) · n! + ( n ; 2). n!

Problem 10.4

[(~)(i)

+

(~)(~)]-3!

Problem 11.1

13!

3! Problem 11.2

n!

(n; 1 ) -n! -2! (iii) (n; 2 )(; )-n!-2!-2! + (n; 2 )-n! -3! (ii)

n:11 Mathematical EDLEY

nm

Problem 11.6

Problem 10.1

~

(~)(~)

(iii) ( ; )

Problem 9.3

(i)

_2_L

4!5!

(n- m)!

Problem 9.2

(ii)

(~)(~)

Problem 11.5

Problem 9.1

(i)

8! 3!5!

Septemberl996

1 1