Mastering Tricky Counting Problems: Step-by-Step Approach for Guaranteed Success

[Mogarrr]

I'm trying a few elementary counting problems, and a few are proving very difficult (for me). I have the answers and explanations, which I understand, so that's not the problem. I don't want to memorize answers. The problem is systematically analyzing these problems. My intuition is almost always wrong with counting, so I don't want to rely on any intutive explanations (adding to my frustration, most explanations use the intuitive approach). Here are some problems I found troubling:

My telephone rings 12 times each week, the calls being randomly distributed among the 7 days. What is the probability that I get at least one call each day?

If n balls are placed at random into n cells, find the probability that exactly one cell remains empty

A closet contains n pairs of shoes. If 2r shoes are chosen at random (2r<n), what is the probability that there will be no matching pair in the sample?

Given problems like these, how do you systematically work through the problem.

 

[jedishrfu]

You need to look more closely at the intuitive approach because the systematic scheme you're looking for is there.

Think of how we solve the problem of the number of 5 letters that can be made with 10 unique letters:

10 choices for the first letter
9 for the second
8 for the third
7 for the fourth
6 for the fifth

and then if any of the 10 letters are repeated then you have to take that into consideration:

the word upper with the repeated p would be counted twice for example

 

[Mogarrr]

Ok, say for the phone problem, I have some intuition about the nature of the question.

The problem asks for the probability that I get at least one call each day. Intuitively I would think the complement of this event would be receiving no phone calls on one of the days (not so sure about this).

Perhaps before starting there, I note the calls are received randomly, so the probability will be some form of: \frac {number of favorable outcomes}{total number of outcomes}, which is true.

Working on the total number of outcomes, I think of each day of the week as a slot, and then decide whether order matters, and whether replacement occurs. I picture (incorrectly) that phone calls are not repeated and order doesn't matter, so I use \binom {12}7.

Working on the denominator, I reason that there are 7 ways to choose a day of the week with no phone calls... and I'm going to stop my erroneous reasoning now.

Here's the answer:
A sample point specifies on which day (1 through 7) each of the 12 calls happen. Thus there are 7^{12} equally likely sample points. There are several different ways that the calls might be assigned so that there is at least one call each day. There might be 6 calls one day and I call each of the other days. Denote this by 6111111. The number of sample points with this pattern is 7\binom {12}66!. There are 7 ways to specify the day with 6 calls. There are \binom {12}6 to specify which of the remaining which of the 12 calls are on this day. And there are 6! ways of assigning the remaining 6 calls to the remaining 6 days...

And here's a list of the all the number patterns: 6111111, 5211111, 4221111, 4311111, 3321111, 3222111, 2222211. The answer is the sum of all those probabilities divided by 7^{12}. (Whether my calculator can handle this, I don't know).

As demonstrated, my intution is way off.

One author of a math text said that most probability problems can be viewed as placing balls into cells. What would say the ball is in this problem? and the cell?

Looking at the denominator, the total number of outcomes has replacement and ordered. In other problems I've seen the total number of outcomes as a binomial coefficient. How do you know which to choose?

Am I right or wrong about the complement of this event, and would that be a more efficient calculation than the one given?

I have a sneaky suspician, for a lot of these problems, there alluding to probability distributions in later chapters.

I'll have more questions, but let's just start with these. Please help.

 

[Ray Vickson]

I'm trying a few elementary counting problems, and a few are proving very difficult (for me). I have the answers and explanations, which I understand, so that's not the problem. I don't want to memorize answers. The problem is systematically analyzing these problems. My intuition is almost always wrong with counting, so I don't want to rely on any intutive explanations (adding to my frustration, most explanations use the intuitive approach). Here are some problems I found troubling:

My telephone rings 12 times each week, the calls being randomly distributed among the 7 days. What is the probability that I get at least one call each day?

If n balls are placed at random into n cells, find the probability that exactly one cell remains empty

A closet contains n pairs of shoes. If 2r shoes are chosen at random (2r<n), what is the probability that there will be no matching pair in the sample?

Given problems like these, how do you systematically work through the problem.

For the phone problem: as you say, the event D = {>=1 call each day} has complement E = {at least one day with 0 calls}, whose probability is (in this case) easier to determine.

Let $E_i =$ {0 calls on day i} for $i = 1,2, \ldots, 7$. Then
E = \bigcup_{i=1}^7 E_i,
whose probability can be obtained from the inclusion-exclusion principle; see http://en.wikipedia.org/wiki/Inclusion–exclusion_principle for the general idea and
http://en.wikipedia.org/wiki/Inclusion–exclusion_principle#In_probability for its specific application to probability.

I'll look at a simpler case of 3 days and 6 calls, with $E_i =$ {0 calls on day i}, $i=1,2,3$ and $E = E_1 \cup E_2 \cup E_3$. Inclusion-exclusion says that
P(E) = S_1 - S_2 + S_3, \\<br /> \text{where}\\<br /> S_1 = \sum_i P(E_i) = P(E_1) + P(E_2) + P(E_3),\\<br /> S_2 = \sum_{i &lt; j} P(E_i E_j) = P(E_1 E_2) + P(E_1 E_3) + P(E_2 E_3)\\<br /> S_3 = P(E_1 E_2 E_3).<br />
Here, I use the notation $AB$ instead of $A \cap B$ and $ABC$ instead of $A \cap B \cap C$.

Note that $P(E_1) = (2/3)^6$ because for each call there is a 2/3 chance it does not fall on Day 1, and this must happen for all 6 calls. We also have $P(E_2) = P(E_3) = (2/3)^6$ (essentially by symmetry of the days) so $S_1 = 3 P(E_1) = 3\,(2/3)^6$. Next, $P(E_1 E_2) = (1/3)^6$ because for each call there is a 1/3 chance it does not fall in Days 1 or 2, and that must happen for all 6 calls. By symmetry, all $P(E_i E_j)$ have the same value for any pairs $(i,j)$ of distinct days, so $S_2 = N_2 P(E_1 E_2)$, where $N_2$ is the number of distinct pairs:
N_2 = {3 \choose 2} = \frac{3\times 2}{2!} = 3.
Thus, $S_2 = 3\,(1/3)^6$.
Finally, $S_3 = P(E_1 E_2 E_3) = 0$ because the event that all three days receive 0 calls is impossible (i.e., non-existent).

Therefore, we have that
P(E) = 3\,(2/3)^6 - 3\, (1/3)^6 = 7/27
is the probability of at least one day with 0 calls.

Note: while I have used the inclusion-exclusion principle for probabilitities, it also applies to straight counting---that is, to determining cardinalities of event sets---so you can apply similar considerations to your problem if you insist on sticking with counting methods.

 

[PeroK]

My telephone rings 12 times each week, the calls being randomly distributed among the 7 days. What is the probability that I get at least one call each day?

Given problems like these, how do you systematically work through the problem.

First, this is not an easy problem. You are trying to count how many ways to distribute 12 calls across 7 days. You are NOT trying to choose 7 items from 12, which is where $\binom{12}{7}$ comes in.

Second, the solution given is not really "intuitive". It is more a systematic crunching of the problem.

If you are really stuck with these, I would try slightly simpler problems. Perhaps reduce the numbers and try distributing, say, 5 phone calls across 3 days. See if you can do that one.

Finally, the way to set this problem up so that there are no ambiguities is:

Let's label the calls C1, C2 ... C12 (imagine these are 12 people all going to call you once, randomly, during the week).

Each call is equally likely to be on any day. So, all 12 calls on Monday is equally likely as any other combination. A typical combination is:

M-Sa-Wed-Wed-...-Sun

So, that's why there are $7^{12}$ possibilities.

The next step (identifying all the patterns) is not easy. I can't see a better way.

Going for the complement was a good idea, but in this case it involves more work. That happens. There's nothing wrong with trying this but in this case it's not the easiest way.

These are not easy counting problems.

 

[verty]

For the phone problem, I think you need inclusion-exclusion. I was hoping it would be simpler but it seems not. Start with P(there is a day with no calls), apply inclusion-exclusion.

 

[Ray Vickson]

For the phone problem, I think you need inclusion-exclusion. I was hoping it would be simpler but it seems not. Start with P(there is a day with no calls), apply inclusion-exclusion.

Right: that is what I outlined above, and worked out a simpler example in detail (for the telephone problem). The exact answer to the full problem is not very difficult to write down, once one sees how to approach the issue.

For the second problem a similar method applies: if E_i = {cell i remains empty}, the OP wants P{exactly one of the events E_i occurs}. This can be worked out in detail using a generalization of inclusion/exclusion; my favorite source of material on all these matters is the classic book W. Feller, "Introduction to Probability Theory and its Applications", Vol. I, Wiley (1968), Chapter IV. Again, the exact formula is not so bad---once you "see" it.

The third problem is trickier; some conditions on r must apply besides the given r < n, because for large enough r there is no way to avoid having at least one good pair among the 2r shoes.

I agree that these problems are NOT trivial; their solution involves concepts/tools that go beyond the material in Probability 101, although as Feller makes clear, the methods can be viewed as "elementary" in that no calculus or similar tools are needed. Good luck to the OP on these questions!

 

[Jonathan Yang]

The first two problems are actually quite simple.
1. Assume that the calls are indistinguishable.

We know that there has to be at least one phone call each day. This means that we can distribute 1 call to each day.

The problem now reduces to arranging 5 calls amongst the 7 days. We can use a method called stars and bars. There are 6 bars (representing the days) and 5 stars (representing the phone calls). So, the numerator, or the number of successful outcomes is 11C6, the number of ways to order the phone calls.

Now, we can apply the same method for the number of total outcomes. There are 6 bars still, but now 12 starts, The total number of outcomes is then 18C6.
The answer is 11C6/18C6 = 11/442.

2. Again, we can use the same approach. We need to choose one cell to be empty, which has n possibilities. If one cell remain empty, there are now (n-2) bars. After assigning (n-1) balls to (n-1) cells, there is one ball left. So, the number of ways to order (n-2) bars and 1 star is n-1. There are n*(n-1) total outcomes that work.

Now we need to find the total number of possibilities. There are (n-1) bars and n stars. So, the number of ways to order this is (2n-1)C(n-1).

So, the total is (n*(n-1))/(2n-1)C(n-1), which can be simplified, but turns out to be pretty ugly.

3. I believe there might be a mistake in the problem if r is a integer. I believe the problem should state that the person chooses r shoes instead of 2r shoes.