Loading [MathJax]/extensions/TeX/mathchoice.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

4.2: Overcounting

( \newcommand{\kernel}{\mathrm{null}\,}\)

In this section, we will explore a common fallacy that occurs while counting. Allow us to consider (and critique!) the following solution:

Critique This Solution4.2.1

Poker dice is played by simultaneously rolling 5 fair six-sided dice. Find the probability that we obtain one pair.

Note: By one pair, we mean that the dice have denominations a,a,b,c,d where a,b,c and d are all distinct. For instance, the following are examples of one pair: (2,1,2,3,5) and (6,2,1,5,5). Meanwhile, the outcomes (2,1,2,3,2) and (2,2,1,1,1) do not meet the conditions of being one pair.

Solution

As usual, we apply our counting framework. Let A={we obtain one pair} and let S be the set of all outcomes where an outcome is an ordered 5-tuple. That is, an outcome looks like (__,__,__,__,__). Notice there is no reason to believe that a certain ordered 5-tuple is more likely that another ordered 5-tuple and so S is indeed a simple sample space. Clearly, |S|=65. All that remains is to compute |E|. To do this, we proceed in steps:

  1. We first choose a value of a. That is, we must select the denomination to be repeated. There are \binom{6}{1} ways to do so.
  2. We now must select a value of b that is different from a. There are \binom{5}{1} ways to do so.
  3. We now must select a value of c that is different from a and b. There are \binom{4}{1} ways to do so.
  4. We now must select a value of d that is different from a, b and c. There are \binom{3}{1} ways to do so.
  5. Finally, we must impose an ordering on a, a, b, c, d . There are \frac{5!}{2! ~ 1! ~ 1~ 1!} ways to do so.

Hence |A| = \binom{6}{1} \times \binom{5}{1} \times \binom{4}{1} \times \binom{3}{1} \times \frac{5!}{2! ~ 1! ~ 1!~ 1!} .

Putting everything together, we obtain

P(A) = \frac{|A|}{|S|} = \frac{ \binom{6}{1} \times \binom{5}{1} \times \binom{4}{1} \times \binom{3}{1} \times \frac{5!}{2! ~ 1! ~ 1!~ 1!} }{6^5} \nonumber

Does the above solution seem correct? If not, then can you explain what is wrong?

Answer

It turns out the answer above is incorrect! How do we know this? Observe that P(A) = \frac{|A|}{|S|} = \frac{ \binom{6}{1} \times \binom{5}{1} \times \binom{4}{1} \times \binom{3}{1} \times \frac{5!}{2! ~ 1! ~ 1!~ 1!} }{6^5} \approx 2.78 \nonumber and so clearly something is wrong since for any event A of sample space S, we proved that P(A) \leq 1 .

We will now explore what is wrong in our solution and why.

Definition: Overcount

An overcount is when any distinct outcome has been incorrectly counted as multiple distinct outcomes.

The above example and definition raises two questions:

  1. How can we recognize if an overcount has occurred?
  2. If an overcount has occurred, then is there anything we can do to fix our answer?

We first answer question 1 by providing a recipe to check for overcounting.

Recipe to Check for an Overcount
  1. After writing down the steps for computing the cardinality of some event, go through your steps and fix an actual outcome which we will denote by s_1.
  2. Now go through the steps again and change your choice on at least one step. Call the resulting outcome s_2.
  3. If for some change in choice, s_1 = s_2 , then you have overcounted. If for all possible changes in your selection for s_2, s_1 \neq s_2 , then we have not overcounted.

Allow us to apply the recipe to our poker dice question discussed above. We do so by creating a chart:

Steps s_1 s_2
1) We first choose a value of a. That is, we must select the denomination to be repeated. There are \binom{6}{1} ways to do so.    
2) We now must select a value of b that is different from a. There are \binom{5}{1} ways to do so.    
3) We now must select a value of c that is different from a and b. There are \binom{4}{1} ways to do so.    
4) We now must select a value of d that is different from a, b and c. There are \binom{3}{1} ways to do so.    
5) Finally, we must impose an ordering on a, a, b, c, d . There are \frac{5!}{2! ~ 1! ~ 1!~ 1!} ways to do so.    

We will now go through our steps and fix an outcome for s_1. Let us suppose we come up with the following choices:

Steps s_1 s_2
1) We first choose a value of a. That is, we must select the denomination to be repeated. There are \binom{6}{1} ways to do so. 4, 4  
2) We now must select a value of b that is different from a. There are \binom{5}{1} ways to do so. 3  
3) We now must select a value of c that is different from a and b. There are \binom{4}{1} ways to do so. 1  
4) We now must select a value of d that is different from a, b and c. There are \binom{3}{1} ways to do so. 2  
5) Finally, we must impose an ordering on a, a, b, c, d . There are \frac{5!}{2! ~ 1! ~ 1!~ 1!} ways to do so. (4, 2, 1, 4, 3)  

Here, s_1 = (4, 2, 1, 4, 3) . To complete our recipe, we check if there is a way to change our choice on at least one step that will result in generating s_1 again. If there is a way to do so, then we have overcounted. Let us change our choice on steps 2, 3, and 4.

Steps s_1 s_2
1) We first choose a value of a. That is, we must select the denomination to be repeated. There are \binom{6}{1} ways to do so. 4, 4 4,4
2) We now must select a value of b that is different from a. There are \binom{5}{1} ways to do so. 3 1
3) We now must select a value of c that is different from a and b. There are \binom{4}{1} ways to do so. 1 2
4) We now must select a value of d that is different from a, b and c. There are \binom{3}{1} ways to do so. 2 3
5) Finally, we must impose an ordering on a, a, b, c, d . There are \frac{5!}{2! ~ 1! ~ 1!~ 1!} ways to do so. (4, 2, 1, 4, 3) (4, 2, 1, 4, 3)

Here s_2 = (4, 2, 1, 4, 3) . Since s_1 = s_2 , then we have overcounted. This leads to our second question. How do we fix an overcount?

Method 1 to Fixing an Overcount

To fix an overcount, you may simply divide by the number of ways you have overcounted.

To use Method 1, we have to understand how did we overcount? Looking back at our steps, we see that the order in which we select b, c and d does not matter since their arrangement can yield the same outcome. How many ways can we arrangeb, c and d? There are 3! ways to do so. Hence, all we have to do is divide |A| by 3! to obtain the correct answer.

P(A) = \frac{|A|}{|S|} = \frac{ \Bigg[ \binom{6}{1} \binom{5}{1} \binom{4}{1} \binom{3}{1} \frac{5!}{2! ~ 1! ~ 1~ 1!} \Bigg] / 3! }{6^5} \approx 0.4630 \nonumber

Method 2 to Fixing an Overcount

To fix an overcount, redo the counting process and condense the steps so that the overcount no longer occurs in the first place.

Consider the follow revision in our counting process:

Old Steps New Steps
1) We first choose a value of a. That is, we must select the denomination to be repeated. There are \binom{6}{1} ways to do so. 1) We first choose a value of a. That is, we must select the denomination to be repeated. There are \binom{6}{1} ways to do so.
2) We now must select a value of b that is different from a. There are \binom{5}{1} ways to do so. 2) We now select the values of b, c and d. There are \binom{5}{3} ways to do so.
3) We now must select a value of c that is different from a and b. There are \binom{4}{1} ways to do so.
4) We now must select a value of d that is different from a, b and c. There are \binom{3}{1} ways to do so.
5) Finally, we must impose an ordering on a, a, b, c, d . There are \frac{5!}{2! ~ 1! ~ 1!~ 1!} ways to do so. 3) Finally, we must impose an ordering on a, a, b, c, d . There are \frac{5!}{2! ~ 1! ~ 1!~ 1!} ways to do so.

P(A) = \frac{|A|}{|S|} = \frac{ \binom{6}{1} \binom{5}{3} \frac{5!}{2! ~ 1! ~ 1!~ 1!} }{6^5} \approx 0.4630 \nonumber

Notice how steps 2, 3 and 4 under the old method have now been collapsed into one step in the new method.


4.2: Overcounting is shared under a CC BY license and was authored, remixed, and/or curated by LibreTexts.

  • Was this article helpful?

Support Center

How can we help?