Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 bein terms of P(n,r), C(n,r), powers, or combinations of these. The answers do not have to be calculated.

share|improve this question
6  
Hint: Imagine 200 students in a vertical line one above another, and you place ceilings between them to divide them into floors. How many ceilings do you have to place? How many ways can you place them? –  Rahul Nov 23 '10 at 6:18
add comment

3 Answers

up vote 16 down vote accepted

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$.

share|improve this answer
    
Good answer! I have posted a similar question here: math.stackexchange.com/questions/382115/… could you take a look? :) –  dynamic May 5 '13 at 13:57
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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