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.

::::::::::

One more thing to add.

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?

Also read:

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.

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: