If there are $200$ students in the library, how many ways are there for them to be split among the floors of the library if there are $6$ floors?

Need help studying for an exam.

Practice Question: If there are $200$ students in the library, how many ways are there for them to be split among the floors of the library if there are $6$ floors?

Hint: The students can not be told apart (they are indistinguishable).

The answer must be in terms of $P(n,r), C(n,r)$, powers, or combinations of these. The answers do not have to be calculated.

Solution 1:

Note that if they are distinguishable then the number of ways is given by $6^{200}$ since each of the 200 students have $6$ choices of floors.

However, we are given that the students are indistinguishable.

Hence, we are essentially interested in solving $a_1 + a_2 + a_3 + a_4 + a_5 + a_6 = 200$, where $a_i$ denotes the number of students in the $i^{th}$ floor.

The constraints are $0 \leq a_i \leq 200$, $\forall i \in \{1,2,3,4,5,6\}$.

We will in fact look at a general version of this problem.

We want to find the total number of natural number solutions for the following equation:

$\displaystyle \sum_{i=1}^{n} a_i = N$, where $a_i \in \mathbb{N}$

The method is as follows:

Consider $N$ sticks.

$| | | | | | | | ... | | |$

We want to do partition these $N$ sticks into $n$ parts.

This can be done if we draw $n-1$ long vertical lines in between these $N$ sticks.

The number of gaps between these $N$ sticks is $N-1$.

So the total number of ways of drawing these $n-1$ long vertical lines in between these $N$ sticks is $C(N-1,n-1)$.

So the number of natural number solutions for $\displaystyle \sum_{i=1}^{n} a_i = N$ is $C(N-1,n-1)$.

If we are interested in the number of non-negative integer solutions, all we need to do is replace $a_i = b_i - 1$ and count the number of natural number solutions for the resulting equation in $b_i$'s.

i.e. $\displaystyle \sum_{i=1}^{n} (b_i - 1) = N$ i.e. $\displaystyle \sum_{i=1}^{n} b_i = N + n$.

So the number of non-negative integer solutions to $\displaystyle \sum_{i=1}^{n} a_i = N$ is given by $C(N+n-1,n-1)$.

So, for the current problem assuming that some of the floors can be empty, the answer is $C(200+5,5) = C(205,5) = 2872408791$.

Solution 2:

Since the students are indistinguishable, we can number them from $1$ to $200$, and can assume that students $a_i$ to $a_{i+1}-1$ get assigned to floor $i$, where $a_1 = 1$ and $a_7 = 201$. Since $a_1,a_7$ are fixed, we have to choose $a_2,\ldots,a_6$. Note that $1 \leq a_2 \leq \cdots \leq a_6 \leq 200$, and this is the only restriction on them.

Solution 3:

I'm too new here to comment on @Sivaram's answer, but I believe it to be correct and well explained. For further reference see Stanley's "Twelvefold Way" in Combinatorics at either [1] or the Wikipedia page.

[1] http://mathsci.kaist.ac.kr/~drake/pdf/twelvefold-way.pdf