The problem (taken from Harvard Stat 110) is as follows:

For a group of 7 people, find the probability that all 4 seasons (winter, spring, summer, fall) occur at least once each among their birthdays, assuming that all seasons are equally likely.

The authors propose a solution using Inclusion-Exlusion method, which is clear for me, so I decided to try a different method, using naive definition of probability. Here's my solution:

1. Denominator, as there are $4^7$ ways to assign seasons to these people, will look as follows: $|\Omega|=4^7$
2. To compute the numerator, we have to pick 4 people, and assign seasons to them ($\binom{7}{4}\times4!$ ways). Then we assign seasons to the rest ($4^3$ ways). So, numerator: $\binom{7}{4}\times4!\times4^3$.

This solution looks reasonable for me, however it's incorrect. Please, explain, why I'm wrong?

  • 4
    $\begingroup$ This method badly over counts. There's no difference between A. initially assigning $P_1$ to Winter and then assigning $P_2$ to Winter later on and B. initially assigning $P_2$ to Winter and then assigning $P_1$ to Winter later on . $\endgroup$
    – lulu
    Aug 15 '19 at 13:45

Others have already commented on why the solution you pose overcounts. Instead, I offer an alternate methodology that does not use Inclusion/Exclusion, but instead focuses on the addition and multiplication principles. First, I separate the problem into disjoint cases, then I count the number of elements in each disjoint case:

Let there be $x_1$ winter birthdays, $x_2$ spring birthdays, $x_3$ summer birthdays, and $x_4$ fall birthdays. We have:

$$x_1+x_2+x_3+x_4 = 7, \forall i, 1\le x_i$$

Each solution to this equation corresponds to a solution to the equation:

$$y_1+y_2+y_3+y_4 = 3, \forall i, 0\le y_i$$

(The bijection between solutions is $y_i = x_i-1$).

For each solution to this equation, consider a multiset:

$$\{\text{Winter}\cdot (1+y_1), \text{Spring}\cdot (1+y_2), \text{Summer}\cdot (1+y_3), \text{Fall}\cdot (1+y_4)\}$$

Each permutation of one of these multisets corresponds to a distinct possible outcome of birthdays where all four seasons are represented. It is not difficult to show that as you span all possible solutions to the Diophantine equation and all possible multiset permutations, you find all possible ways to assign the birthdays. So, the next step would be counting them all.

You can have: 3,0,0,0 (in some order) 2,1,0,0 (in some order) 1,1,1,0 (in some order)

This gives three cases: 3,0,0,0, choose one season to have 4 birthdays while every other one has 1, then permute the multiset: $$\dbinom{4}{1}\dfrac{7!}{4!1!1!1!}$$

Case 2: 2,1,0,0 Permute the multiplicities, then permute the multiset: $$\dfrac{4!}{2!1!1!}\cdot \dfrac{7!}{3!2!1!1!}$$

Case 3: 1,1,1,0 $$\dbinom{4}{3}\dfrac{7!}{2!2!2!1!}$$

Add all of these up and divide by $4^7$ and you should get the same answer as the book.

$$\dfrac{8,400}{16,384} = \dfrac{525}{1,024} \approx 51.27\%$$


Consider the case: (S for Spring, SS for Summer, F for Fall, and W for Winter)


In your method, you count this case by choosing the first four people and count it again by choosing the last four people.

Basically, at the second time when you pick 4 people, you have to eliminate the cases that appeared in the first time, which is too complicated.


Let us say that the seven people are A through G. So your plan of choosing four of them and assigning different seasons to them then randomly assigning seasons to the rest would include this case among the 53,760 total cases:

B is spring, E is summer, F is fall, C is winter - A is winter, D is spring, G is winter

Awesome! Here's another one:

D is spring, E is summer, F is fall, G is winter - A is winter, B is spring, C is winter

Do you see what happened there? Your strategy is counting those as two different assignments, but in fact they are identical. That's the over-counting that Lulu is talking about. To get around that, you need the Inclusion-Exclusion Principle.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.