Quod Erat Demonstrandum


Just a revision on counting

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

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).


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}


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}


= 1 \times \frac{1}{81} + 2 \times \frac{10}{27} + 3 \times \frac{50}{81}
= \frac{211}{81}



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


if you want to.


發表迴響 »


RSS feed for comments on this post. TrackBack URI



WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )


您的留言將使用 Facebook 帳號。 登出 /  變更 )


連結到 %s


%d 位部落客按了讚: