Harvard Stat 110 Strategic Practice 2, Fall 2011 - Inclusion Exclusion - Problem 1.1

Harvard Stat 110 Strategic Practice 2, Fall 2011 - Inclusion Exclusion - Problem 1.1

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.

I tried to solve it using another method (which came into my mind at that moment) but I must be doing a mistake. Maybe someone could help me finding the error and also explaining WHY I make the error, so I can avoid it in the future.

I tried to apply the naive definition. So, I have $$7$$ people and $$4$$ seasons to choose.

1st person can have $$4$$ picks, the 2nd $$4$$ picks, etc etc. All are independent, so I have a total of $$4^7$$ possibilities.

The number of favourable outcomes are when from the $$7$$ people, $$4$$ have each Spring, Summer, Fall, Winter and the other $$3$$ might get any choice.

From $$7$$ people, I chose $$4$$ to fill Spring, Summer, Fall, Winter and the other $$3$$ can have whatever choice.

So, result should be $$\binom{7}{4} \cdot \frac{4^3}{4^7}$$ which yields $$0.546$$ which is clearly different from the practice answer of $$0.513$$.

Could somebody, please, point out what I am doing wrong?

Thank you!

The error in your reasoning is that you are counting desired outcomes multiple times. To see why, suppose we represent the seasons as $$W, S, U, F$$ for winter, spring, summer, and fall, and the seven people are ordered so that their birthdays are denoted as a $$7$$-tuple. Then one desired outcome could be $$(W, S, U, F, S, F, W).$$ But there are at least two distinct ways you could count this: first, by selecting the first four people to have distinct seasons $$(W, S, U, F)$$, but we could also select the third, fifth, sixth, and seventh people $$(U, S, F, W)$$ as the ones to have distinct seasons.

To count correctly, what you need to do instead is use the recommended inclusion-exclusion principle. First, count all the outcomes in which there are strictly fewer than four seasons represented: $$\binom{4}{3} 3^7$$ where there are $$\binom{4}{3}$$ ways to select three distinct seasons out of the four, and $$3^7$$ represents the number of ordered outcomes using those three seasons. However, this also multiple-counts outcomes in the same way your original approach does, but here we are double-counting outcomes where at most two seasons are represented. So we subtract out $$\binom{4}{2} 2^7$$ of these, but now we have to add back in those outcomes where exactly one season is represented, of which there are $$\binom{4}{1} 1^7.$$ So the total number of desired outcomes is $$4^7 - \binom{4}{3} 3^7 + \binom{4}{2} 2^7 - \binom{4}{1} 1^7 = 8400$$ and the resultant probability is $$\frac{8400}{4^7} = \frac{525}{1024} \approx 0.512695.$$

To verify this, we can run Mathematica with the following inputs:

Select[Tuples[Range[4], 7], Length[Union[#]] == 4 &]


which outputs $$8400$$, and for simulation, we can input

Length@Select[ParallelTable[RandomInteger[{1, 4}, 7], 10^6], Length[Union[#]] == 4 &]/10^6


which outputs for me $$0.513070$$ for $$10^6$$ simulations.

• Another combinatorial triumph. (+1) – BruceET May 31 at 17:52

There are multiple mistakes here. First, once you choose the four people, you neglected to designate how the four different seasons are assigned to them, since in the denominator you are counting all possible sequences of seven season assignments. It should be $$7 \cdot 6 \cdot 5 \cdot 4$$ rather than $$\binom{7}{4}$$. However, this leads to a nonsensical probability larger than $$1$$, which I explain below.

You are counting some outcomes multiple times. For example, if the seven people are ordered and their picks are

Fall, Spring, Summer, Summer, Winter, Summer, Summer

in that order, then this is counted four times too many in your computation, because there are four different ways this could have arisen from choosing the set of "four different seasons" people first, before letting the rest be summer. Specifically, it could have been the 1st, 2nd, 3rd, and 5th people that were chosen first, or it could have been the 1st, 2nd, 4th, and 5th people that were chosen first.

The difficulty is that there isn't a uniform way to correct for this overcounting (like just dividing by 4 or something). For instance, for

Fall, Spring, Summer, Summer, Winter, Winter, Winter

this would be counted six multiple times due to the different ways this could have arisen from a selection of "four different seasons" people first.

If you want to handle this case by case, you have to go through all possible frequencies of exactly how many occurrences of each season there are, which is a bit difficult to compute. Admittedly, the standard approach (inclusion-exclusion) also doesn't have a simple expression either, but is slightly easier to write down.

The complement event is "at least one season does not appear." Letting $$A_1, A_2, A_3, A_4$$ be the events that "season $$i$$ does not appear" respectively, we want $$1-P(A_1 \cup A_2 \cup A_3 \cup A_4)$$. Using inclusion-exclusion, this is $$1-\left(4 (3/4)^7 - \binom{4}{2} (2/4)^7 + \binom{4}{3} (1/4)^7\right) \approx 0.5126953125$$ which matches BruceET's simulation.

Lets think people as distict balls and the seasons as distinct boxes. So , our question turned out to be how many ways are there to distribute $$7$$ distinct balls into $$4$$ distict boxes so that each box has at least one ball.

Now , think firstly the boxes are the $$\color{red}{same}$$ of each other , so if we find $$S(7,4)$$ where $$S$$ is the $$\color{blue}{stirling}$$ number of $$\color{purple}{second}$$ kind, we can find the number of dispersing $$7$$ different balls into $$4$$ pieces (identical boxes) where each piece (box) has at least one element.

However, the boxes were different so we should multiply by $$4!$$ to make them different again.(because we want to disperse the pieces into different boxes)

So , $$S(7,4) \times 4! = 350 \times 24 = 8400$$

Moreover , the number of ways distributing $$7$$ different balls into $$4$$ distinct boxes without restriction is $$4^7=16384$$

So ; $$8400/16384=0,5126..$$

Comment: Based in simulation of a million performances of this experiment, which should give 2 or 3 place accuracy, I'm betting on the answer $$0.513.$$ The simulated result is $$0.5135 \pm 0.001.$$

set.seed(536)
nr.s = replicate(10^6,
length(unique(sample(1:4,7,rep=T))))
mean(nr.s == 4)
[1] 0.513456       # aprx P(All seasons)
2*sd(nr.s == 4)/1000
[1] 0.0009996383   # aprx 95% margin of sim error


Note: Your method in clever and comes close, but it's approximate.

By designating four of the people as the ones who satisfy the condition that at least one person must be born in each season, you are counting each outcome multiple times because there is more than one way to designate a person as the person born in a particular season for each season in which more than one person was born. Since there are seven people and four seasons, there must be more than one person born in some season by the Pigeonhole Principle. However, you also made another error. You did not assign people to seasons, which had the effect of lowering your count, so your errors partially canceled each other.

We will solve the problem in two ways. In what follows, imagine you are a novelist creating seven characters and assigning birthdays to them.

Method 1: We count directly.

If there are no restrictions, there would be four possible seasons in which the birthdays of each of the seven people could occur. Hence, there are $$4^7$$ possible distributions of birthdays to seasons.

The number $$7$$ can be partitioned into four parts in three ways: \begin{align*} 7 & = 4 + 1 + 1 + 1\\ & = 3 + 2 + 1 + 1\\ & = 2 + 2 + 2 + 1 \end{align*}

Four people are born in one season, with one person each born in the other three seasons: There are four ways to select in which of the four seasons four people are born, $$\binom{7}{4}$$ ways to select which four of the seven people were born in that season, and $$3!$$ ways to assign seasons to the birthdays of the remaining three people so that one person each is born in the other three seasons. Thus, there are $$\binom{4}{1}\binom{7}{4}3!$$ ways to assign birthdays to your seven characters so that four people are born in one season and one person each is born in the other three seasons.

Three people are born in one season, two people are born in another season, and one person each is born in each of the remaining two seasons: There are four ways to select the season in which three people are born, $$\binom{7}{3}$$ ways to select the three people born in that season, three ways to select in which of the remaining two people are born, $$\binom{4}{2}$$ ways to select two of the remaining characters to be born during that season, and $$2!$$ ways to assign seasons to the birthdays of the remaining two people so that each person is born in one of the remaining two seasons. Hence, there are $$\binom{4}{1}\binom{7}{3}\binom{3}{1}\binom{4}{2}2!$$ ways to assign birthdays to your seven characters so that three people are born in one season, two people are born in another season, and one person each is born in each of the remaining two seasons.

Two people each are born in three of the seasons, and one person is born in the remaining season: There are four ways to select the season in which only person is born, seven ways to select the person born in that season, $$\binom{6}{2}$$ ways to select which two people will be born in the first unused season of the year, and $$\binom{4}{2}$$ ways to select which two people will be born in the next unused season of the year. The remaining two people must be born in the remaining season. Hence, there are $$\binom{4}{1}\binom{7}{1}\binom{6}{2}\binom{4}{2}$$ ways to assign birthdays to your characters so that two people each are born in three of the seasons, and one person is born in the remaining season.

Thus, the probability that each character is born in a different season is $$\frac{1}{4^7}\left[\binom{4}{1}\binom{7}{4}3! + \binom{4}{1}\binom{7}{3}\binom{3}{1}\binom{4}{2}2+ \binom{4}{1}\binom{7}{1}\binom{6}{2}\binom{4}{2}\right] \approx 0.5126953125$$

Method 2: We use the Inclusion-Exclusion Principle.

There are four ways to assign a season to each character's birthday. Hence, there are $$4^7$$ ways to assign birthdays without restriction. From these, we must subtract those assignments in which one or more seasons is excluded.

We can exclude $$k$$ of the four seasons from consideration in $$\binom{4}{k}$$ ways, leaving $$(4 - k)^7$$ ways to assign seasons to the birthdays of the characters. Hence, by the Inclusion-Exclusion Principle, the number of ways to assign birthdays to seasons so that each season is represented among the characters birthdays is $$\sum_{k = 0}^{4} (-1)^k\binom{4}{k}(4 - k)^7 = 4^7 - \binom{4}{1}3^7 + \binom{4}{2}2^7 + \binom{4}{3}1^7 - \binom{4}{4}0^7$$ Hence, the probability that each season is represented among the birthdays of the seven people is $$\frac{1}{4^7}\left[4^7 - \binom{4}{1}3^7 + \binom{4}{2}2^7 + \binom{4}{3}1^7\right] \approx 0.5126953125$$