# If 8 new teachers are to be divided among 4 schools, how many divisions are possible?

If 8 new teachers are to be divided among 4 schools, how many divisions are possible?

I understand that in this question you are just solving for the multinomial coefficients of the multinomial theorem. So x1=x2=x3=x4=1:

(1+1+1+1)^8 = 65,536.

But I thought about this question a different way and don't understand why this solution is not working:

Suppose I have 8 teachers: A B C D E F G H and the '^' symbol represents the dividing line for the school. Since I have 4 schools, I will have 3 dividers.

So an example division would be as such: AB^CD^EF^GH. In this case,
school1=AB,
school2=CD,
school3=EF,
school4=GH.

Another example would be ABC^D^EF^GH:
school1=ABC
school2=D
school3=EF
school4=GH

So how many different ways could I place the divisors? The answer is 8-1 and I have to choose 3. Also there are 8! permutations of the teachers. So I thought if I do: (7 choose 3) * 8! I would get the answer, but I don't. Can someone please explain what I am misunderstanding and what I just actually calculated? Thanks in advance!

-
I also found this question to be poorly worded. Another way you could have stated this to make it more clear is the following: Find the number of ways of placing 8 teachers in 4 schools with no restriction on the number assigned to each school. This is obviously 4^8. – user1527227 Apr 19 '13 at 20:43

Line up the teachers, say in order of age, or weight, or whatever. The first teacher can be assigned to a school in $4$ ways. For every such way, the second teacher can be assigned to a school in $4$ ways, and so on, for a total of $4^{8}$.

Remark: An approach of the Stars and Bars type runs into difficulties. Like not a few school boards, it starts off by treating new teachers as indistinguishable.

The count we get cannot be easily adjusted to take distinguishability into account. The magic multiplier depends on the structure of the decomposition. For example, the assignment of everybody to school A gives rise to only $1$ decomposition into parts when distinguishability is taken into account, while a distribution of type $2$-$2$-$2$-$2$ gives rise to many decompositions when we consider the teachers distinguishable. In our $8$ teacher $4$ school situation, the multiplier is never $8!$. One can find an expression for the average multiplier, but it is hard to imagine doing so in a way that bypasses the $4^8$ calculation.

-
Awesome. Just the explanation I was looking for. Thank you! – user1527227 Apr 19 '13 at 20:42

Your approach overcounts. That is, it counts distributions of teachers more than once. For instance, the distribution that puts all $8$ teachers in the first school is counted once for every permutation of the teachers, as XXXXXXXX^^^, so it’s counted $8!$ times. And every distribution is counted at least twice, since you can certainly get it by reversing the entire string of teachers and dividers.

-
How is that the case? When you multiply by 8! doesn't that give you ALL permutations of the object ABCDEFGH? – user1527227 Apr 19 '13 at 19:14
@user1527227: Sorry: I somehow missed the $8!$ at the end. You’re actually over-counting, because different permutations can give you the same distribution of teachers. I’ll fix my answer. – Brian M. Scott Apr 19 '13 at 19:16