Quod Erat Demonstrandum

2010/06/01

Just a revision on counting

Filed under: Additional / Applied Mathematics,HKALE,Teaching — johnmayhk @ 4:03 下午
Tags:

Here is just an ordinary question:

“An elevator starts carrying five persons at the ground floor and then goes up. It can stop at any floor of the building (from the first floor to the third floor). Events that people leaving the elevator are assumed to be independent. Let X be the number of ‘stop’ of the elevator during a “going-up” journey. Find the value of E(X)."

We may use “balls and boxes" as tools of solving this problem.

Floor 1, 2, 3 can be represented by Box 1, 2, 3 respectively.

A person go out at the floor 1, 2 or 3 can be imagined as the case that a ball is placed in the box 1, 2 or 3 respectively.

Because people are different from each other, balls should also be different. May be labelled by different numbers (say).

Then,

P(X = 1)
= P(all people going out at exactly one floor)
= P(all balls are placed in exactly one box)

For placing 5 balls into 3 boxes, there are $3^5$ ways.
(i.e. 3 ways for the 1st ball, 3 ways for the 2nd, resulting $3^2$ ways already)

And there are 3 ways to put all balls into exactly one box (since there are 3 boxes), i.e. the number of favourable outcome is 3. Thus,

P(X = 1)
= $\frac{3}{3^5} = \frac{1}{81}$

Now,

P(X = 2)
= P(people going out at exactly two floors)
= P(balls are placed in exactly one boxes)

First, select 2 boxes out of 3 ($_3C_2$ ways).

Suppose we select box 1 and box 2 (say).

Then we place balls into there 2 boxes.

For placing 5 balls into 2 boxes, there are $2^5$ ways.
(i.e. 2 ways for the 1st ball, 2 ways for the 2nd, resulting $2^2$ ways already)

But, there are 2 ways resulting “exactly one box to be filled with balls", hence we should exclude these 2 ways.

Hence number of all favourable outcomes for the case “X = 2″ is $_3C_2(2^5 - 2)$, thus

P(X = 2)
= $\frac{_3C_2(2^5 - 2)}{3^5} = \frac{10}{27}$

And hence

P(X = 3)
= 1 – P(X = 1) – P(X = 2)
= 1 – $\frac{1}{81}$$\frac{10}{27}$
= $\frac{50}{81}$

Therefore,

E(X)
= $1 \times \frac{1}{81} + 2 \times \frac{10}{27} + 3 \times \frac{50}{81}$
= $\frac{211}{81}$

Done.

::::::::::

A student asked why his method of counting the case of “X = 3″ is invalid.

His suggestion is:

Select 2 people out of 5 ($_5C_2$ ways). Leave them behind.

The remaining 3 people occupy 3 different floors ($_3P_3$ ways).

Then the 2 firstly selected people can occupy any 2 floors out of 3 ($3^2$ ways).

Hence the number of favourable outcomes for the case “X = 2″ should be $_5C_2 \times _3P_3 \times 3^2 = 540$ (Instead of 150)

WOW! Too many cases.

What is the problem?

Obviously, there is double-counting.

We may imagine balls are labelled by 1,2,3,4,5.

Step 1, select 2 balls leaving behind.

Suppose ball #4 and ball #5 are selected.

Step 2, the remaining 3 balls occupy 3 different boxes.

Suppose ball #1, ball #2 and ball #3 occupy Box 1, Box 2 and Box 3 respectively.

Step 3, the firstly selected balls occupy any 2 boxes.

Suppose ball #4 and ball #5 are placed in Box 1, Box 2 respectively.

Then we have a case: “Box 1 contains balls #1, #4; Box 2 contains balls #2, #5; Box 3 contains ball #3″ … … … (*)

However, if

in step 1, we leave ball #1 and ball #2 behind; (One of the cases out of $_5C_2$ possible choices)

in step 2, we place ball #4, #5 and #3 into Boxes 1, 2 and 3 respectively; (One of the cases out of $_3P_3$ possible choices)

in step 3, we place ball #1 and #2 into Boxes 1, 2 respectively.

Then we have the case SAME as (*).

But, under student’s counting, they represent 2 cases and actually the 2 cases are the SAME. This is so-called a “double-counting". And that is the problem.

::::::::::

Can we obtain the number of cases for “X = 3″ directly?

Well, up to now, I just count it by the Principle of Inclusion and Exclusion（容斥原理）, as a result:

the number of ways of putting r distinct balls into n distinct boxes is

$\displaystyle \sum_{k = 0}^n (-1)^k C_k^n (n - k)^r$

In this question, we may put $r = 5, n = 3$, obtaining 150.

But, it seems that this is not so-called “direct" counting method in student’s mind (I guess).

Question: Can you explain the difference $540 - 150 = 390$? Can you count the 390 cases out?

How to count the number of ways of placing 5 indistinguishable balls into 3 different boxes without leaving a box empty? Just refer to my old writing at

http://www.hkms-nss.net/discuz/home/space.php?uid=423&do=blog&id=26

if you want to.