0
$\begingroup$

A course is divided into $n$ classes. There are exactly $r$ students enrolled in the course. Assume that each student chooses a class at random and that the capacity of each of the classes is unlimited.

(a) Assume that there is only one class on Friday. What is the probability that there will be exactly k students in this Friday class ?

(b) What is the probability that there will be at least one student in each of the classes?

For a, it's a binomial distribution so the answer is $\binom{ r }{ k }$ ${(1- {1 \over n})}^{r-k}{({1 \over n})}^{k} $

For b, the answer is $$\sum_{k=0}^{n-1} (-1)^{k} \binom{ n }{ k } {({ n-k \over n})}^{r} $$ (for r $\ge$ n)

Shouldn't it be something like ${1 - \binom{ r }{ 0 } {(1- {1 \over n})}^{r-0}} {({1 \over n})}^{0}$ = ${1 - {(1- {1 \over n})}^{r}}$ for the probability that there will be at least 1 student in each of the classes = 1 - the probability of there will be no students in each of the classes? Can someone help me explain the answer for b?

$\endgroup$
3
  • $\begingroup$ For (a) the stated answer is correct. For (b) the stated answer involving the summation is correct and the expression following "shouldn't it be something like..." is not. The probability you wrote is the probability that there is at least one student in the friday class specifically, but it does not care about whether any of the tuesday classes have any students. $\endgroup$
    – JMoravitz
    Oct 22, 2019 at 12:31
  • $\begingroup$ To correctly approach (b), apply the principle of inclusion-exclusion over the events "There are no students in class $i$." The union of those events is the opposite event to the one we are interested in. Alternatively, a more advanced direct approach can be done using Stirling Numbers of the Second Kind. It is worth knowing about them for the future, but the first approach is the one you are expected to be able to come up with. $\endgroup$
    – JMoravitz
    Oct 22, 2019 at 12:34
  • $\begingroup$ @JMoravitz can you explain a little bit more, I can't still figure it out the the principle inclusion-exclusion :( $\endgroup$
    – amV
    Oct 22, 2019 at 21:02

1 Answer 1

1
$\begingroup$

Let $A_i$ be the event that class $i$ has no students.

We are interested in finding the probability of $Pr(A_1^c\cap A_2^c\cap \dots \cap A_n^c) = 1 - Pr(A_1\cup A_2\cup \dots \cup A_n)$

This expands via inclusion-exclusion as:

$=1 - Pr(A_1)-Pr(A_2)-\dots-Pr(A_n)+Pr(A_1\cap A_2)+Pr(A_1\cap A_3)+\dots+Pr(A_{n-1}\cap A_n)-Pr(A_1\cap A_2\cap A_3)-\dots \pm \dots \pm Pr(A_1\cap \dots\cap A_n)$

Now... notice that $Pr(A_1)$ is the probability that no student was in class $1$ which can be found via binomial distribution as above or directly as $\left(\dfrac{n-1}{n}\right)^r$. Meanwhile $Pr(A_1\cap A_2)$ is the probability no student was in either of the first two classes, leaving $n-2$ available classes out of the $n$ for each and occurs with probability $\left(\dfrac{n-2}{n}\right)^r$.

In a similar fashion, you find that $Pr(A_1\cap A_2\cap \dots \cap A_k)$, the probability that no student is in any of the first $k$ classes will be $\left(\dfrac{n-k}{n}\right)^r$

Finally, recognize that by symmetry, all probabilities involving the intersection of $k$ of these events will result in the same probability and so we may group them together, there being precisely $\binom{n}{k}$ different intersections involving exactly $k$ of the events.

Correctly accounting for the plus or minus that arises from inclusion exclusion, we arrive at a final probability of:

$$1-\sum\limits_{k=1}^n(-1)^{k+1}\binom{n}{k}\left(\dfrac{n-k}{n}\right)$$

The only differences here to the formula given above is that I opted to write it so that we are subtracting the sum, hence the different exponent on the $-1$, and they stopped their summation at $n-1$ which doesn't affect anything since $Pr(A_1\cap A_2\cap \dots \cap A_n)=0$ since obviously it is impossible for every class to be empty.

$\endgroup$

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.