# Inclusion/exclusion with identical sets that become distinct

This question is motivated by Blitzstein & Hwang Problem 1.49, but differs (I believe) in some crucial ways and so does not have the same answer. It is not (presently) an active problem on any homework assignment or exam.

Pre-Question 1. An athletic director has 7 identical athletic scholarships that he makes available to 4 varsity sports. The scholarships are available on a first-come-first service basis to the coaches for recruitment purposes, and all 7 scholarships will be used by the end of the recruitment period. Assume the probability that any one scholarship is assigned with probability (1/4, 1/4, 1/4, 1/4) to each of the sports, and assume the assignment events are independent of each other. For example, the results may look something like (3 football, 1 tennis, 2 basketball, 1 soccer), or any other combination that adds up to 7. Before the recruiting season begins, what is the probability that each of the four coaches will make use of at least one scholarship?

Pre-Question 2. Now consider that the scholarships have been awarded and the 7 scholar-athletes are known. They are introduced to the president of the university by name but not by sport. Let's assume that the athletes do not have any physical characteristics that make it obvious which sport they play. The athletic director asks the president, "What is the probability that these seven distinct athletes represent all four varsity sports?"

The questions I am asking: Are these different questions with different solutions? Or are they the same question with the same solution? Should we thinking of the unassigned, anonymous scholarships as placeholders for the distinct people, and should they be counted as distinct even when they don't seem to be?

• Pre-question (1) doesn't supply enough information to be answerable. Compare, for instance, your answers for the case where there are only seven athletes altogether and (a) they all play football and (b) collectively they include all four sports. In case (a) the answer is 0% and in case (b) is is 100%.
– whuber
Jan 25, 2019 at 14:10
• The first question addresses all possible distributions of 7 scholarships to 4 sports. As the scholarships are identical, the problem of counting the number of ways to do this boils down to stars-and-bars: $\binom{7+(4-1)}{4-1)}=\binom{10}{3}=120.$ The rest of the solution involves counting how many of these are missing at least one sport, which is a "standard" inclusion-exclusion problem. I get 100 ways of distributing the 7 scholarships so as to miss at least one sport, so the probability of at least one scholarship in each of the 4 sports is 20/120=1/6. Do you agree with my solution? Jan 25, 2019 at 16:10
• I disagree, because you haven't even supplied the information needed to determine whether this is just a counting problem. As my two examples show, you haven't even given enough information to solve it as a counting problem!
– whuber
Jan 25, 2019 at 20:07
• For part 1, if the assignments are made, then you are right. The answer is either 100% or 0%. As edited, it should now be clear that no assignments are made for part 1, and that the question involves calculating the probability that the as-yet-unassigned scholarships will be in all 4 sports, or in 3 or fewer sports. Jan 25, 2019 at 21:58
• Thank you for adding the probability information--that's exactly what was needed. (I presume the "1/3" is just a typo for "1/4".)
– whuber
Jan 25, 2019 at 21:59

My "paradox" falls into a class of subtly ill-posed problems. One famous member of this class is the Bertrand Paradox, which is a classic example of how the word "randomly" can be interpreted 3 ways to get 3 different answers.

To be sure, a simple random variale $$X$$ can be specified entirely by its pdf. The domain of the pdf is the support for $$X.$$ There are no ambiguities.

A random partitioning of a set is not a random number. There is no clear unique definition of support and so no unique relative frequency assigned to subsets. The random partition of a set requires a rule for the way in which it is partitioned. This is the way the Bertrand paradox is resolved.

For $$N$$ identical scholarships assigned randomly to $$M$$ sports, one way to randomly partition the scholarships is to select $$N$$ red playing cards and $$M-1$$ black ones, shuffle and deal. The number of red cards dealt before the first black card correspond scholarships assigned to the sport 1, then the number red cards dealt before the second black card are assigned to sport 2, etc. until the last black card is dealt, and then the remaining red are assigned to the $$M$$-th sport. In this case, the likelihood of at least one sport having no assigned scholarships is obtained by inclusion-exclusion on the set union of $$A_i$$ where $$A_i$$ is the event that sport $$i$$ is omitted from the scholarship list, and $$P(A_i)$$ is the probability that that happens.

$$P(every~sport~gets~a~scholarship) = 1-P(A_1 \cup A_2 \cdots \cup A_M).$$

In the problem the number of scholarships $$N=7$$ and the number of sports $$M=4,$$ so $$A_1, A_2, A_3, A_4$$ are the events that each sport is skipped. By symmetry, $$P(A_i)=P(A_j).$$ Also by symmetry, if two sports are omitted, it won't matter which two: $$P(A_i,A_j)=P(A_k,A_l)$$, and likewise for the 3-sport exclusion. We keep track of how many ways to choose $$k$$ sports to omit from the set of $$M$$ by using binomial coefficients $$\binom{M}{k}$$. Letting $$x, y, z$$ act as anonymous unique concrete instances of the indices:

$$P(A_1 \cup \cdots \cup A_4) = \binom{4}{1} P(A_x) - \binom{4}{2} P(A_x,A_y) + \binom{4}{3} P(A_x,A_y,A_z).$$

The probabilities are obtained using the stars-and-bars counting method for identical scholarships and distinct sports. We determine all of the ways to assign $$N=7$$ scholarships and $$M-1=3$$ dividers such that 1, 2, or 3 sports have no assignments. There are $$\binom{M+N-1}{M-1}=120$$ equally probably ways of dealing the 7 red and 3 black cards, or randomly assigning the 7 scholarships to 4 sports by the shuffling and dealing of cards.

\begin{align} P(A_1)&=\binom{7+2}{2}/120 = 36/120\\ P(A_1,A_2)&=\binom{7+1}{1}/120 = 8/120\\ P(A_1,A_2,A_3)&=\binom{7}{0}/120 = 1/120 \end{align}

so

$$P(A_1 \cup \cdots \cup A_4) = 4\frac{36}{120} - 6 \frac{8}{120} + 4 \frac{1}{120} = \frac{100}{120}$$

and finally $$P(every~sport~gets~a~scholarship)= 1 - 100/120=1/6$$.

On the other hand if the assignments are made on a first-come-first-serve basis and each sport has a 1/4 chance of claiming each scholarship, then the scholarships are not identical. The first scholarship is clearly distinct from the second, etc. And the solution is exactly the same as Blitzstein & Hwang 1.49, using the same method of inclusion-exclusion, but different probabilities of $$P(A_i), P(A_i, P_j)$$, etc. You can work it out yourself (!) but the probability of providing each sport with at least one scholarship rises to $$\sim 50\%$$.