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.

In how many ways can ten teachers be divided among five schools?

One answer is that each teacher can go to any of the five schools so there are $10^5$ possibilities. However, if you treat each school as a partition the answer is different. The answer is $\binom{9}{4}$. Why is there a difference between both answers?

share|improve this question
add comment

2 Answers

up vote 13 down vote accepted

The numbers are counting different things. When you count the number of ways in which $n$ things may be distributed amongst $k$ ‘containers’, the answer depends on whether or not the things are distinguishable from one another, and it depends on whether or not the ‘containers’ are distinguishable from one another. It also depends on whether you require each ‘container’ to receive at least one of the objects.

The number of ways to distribute $10$ distinguishable teachers amongst $5$ distinguishable schools is $5^{10}$, not $10^5$. Teachers and schools are not usually considered to be indistinguishable, so this is the most reasonable answer. In the unlikely event that the teachers (but not the schools) are indistinguishable, there are $\binom{14}{4} = 1001$ ways to distribute them, not $\binom94 = 126$; $\binom94$ is the number of ways to distribute $10$ indistinguishable teachers amongst $5$ schools if each school is required to get at least one teacher. Thus, even assuming that $10^5$ is a careless error for $5^{10}$, the two answers offered in the question correspond to markedly different questions.

If we impose the boldface requirement on the version in which the teachers are distinguishable, the calculation is a bit more complicated. A standard inclusion-exclusion argument yields $$\begin{align*} \sum\limits_{k=0}^5 (-1)^k \binom{5}{k}(5-k)^{10} &= 5^{10} - \binom51 4^{10} + \binom52 3^{10} - \binom53 2^{10} + \binom54 1^{10}\\ &= 5^{10} - 5\cdot 4^{10} + 10\cdot 3^{10} - 10\cdot 2^{10} + 5\\ &=5,103,000, \end{align*}$$ significantly fewer than $5^{10} = 9,765,625$.

All of these calculations assume that the schools are distinguishable. If the teachers are distinguishable and the schools are not, and each school is required to get at least one teacher, the answer is $\left\{\begin{matrix}10\\5\end{matrix} \right\} = 42,525$, a Stirling number of the second kind. If one or more of the schools may receive no teacher, the answer is $$\sum\limits_{k=1}^5 \left\{\begin{matrix}10\\k\end{matrix}\right\} = 1+511+9330+34,105+42,525 = 86,472.$$

Finally, if neither teachers nor schools are distinguishable, we’re simply counting the number of partitions of $10$ into exactly $5$ or at most $5$ parts, depending on whether or not each school is to receive at least one teacher. These numbers are small enough to be calculated by direct enumeration. There is one partition of $10$ into one part. There are $5$ partitions of $10$ into $2$ parts: $$\begin{matrix}1+9; & 2+8; & 3+7; & 4+6; &5+5\end{matrix}$$. There are $8$ partitions of $10$ into $3$ parts: $$\begin{matrix}1+1+8; & 1+2+7; & 1+3+6; & 1+4+5\\ 2+2+6; & 2+3+5; & 2+4+4; & 3+3+4\end{matrix}$$ There are $9$ partitions of $10$ into $4$ parts: $$\begin{matrix}1+1+1+7; & 1+1+2+6; & 1+1+3+5\\ 1+1+4+4; & 1+2+2+5; & 1+2+3+4\\ 1+3+3+3; & 2+2+2+4; & 2+2+3+3\end{matrix}$$ And there are $4$ partitions of $10$ into $5$ parts: $$\begin{matrix}1+1+1+1+6; & 1+1+1+2+5\\ 1+1+1+3+4; & 2+2+2+2+2\end{matrix}$$

Thus, if neither schools nor teachers are indistinguishable, there are $27$ or $4$ ways to distribute the teachers, depending on whether or not every school must get at least one.

share|improve this answer
    
+1 and yet another nice answer badge. It might be good to remark that $$n!\left\{\begin{matrix}m\\n\end{matrix} \right\}= \sum\limits_{k=0}^n (-1)^k \binom{n}{k}(n-k)^{m} $$ And that dividing through $n!$ accounts for distinguishable and non-distinguishable things. A good reference is when counting subsets versus functions. Functions are are distinguishable, and thus the $n!$ factor kicks in ($n!$ times Stirling counts surjective functions which partition the domain into the fibers) while subsets do not care about order, whence $n!$ must be used to kill repetitions. –  Pedro Tamaroff Aug 7 '13 at 20:36
add comment

why $10^5$ ?

Dividing $10$ distinct teachers into $5$ distinct schools (with some schools may be empty) is $5^{10}$

Dividing $10$ identical teachers (this is absurd) into $5$ distinct schools (with no schools being empty) is $\binom{9}{4}$.This could be easily proved using stars and bars concept.

However,given the question in this form "how many ways can $10$ teachers be divided among $5$ schools" I would have go for $5^{10}$ option!

share|improve this answer
2  
I guess they could all be clones... –  mixedmath Aug 27 '11 at 18:51
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.