[Math] How many ways can 10 teachers be divided among 5 schools

combinatorics

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?

Best Answer

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.

Related Question