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.

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!

share|improve this question
    
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
add comment

2 Answers

up vote 1 down vote accepted

This does not answer your question, it just comments on the implicit introduction of multinomial coefficients.

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.

share|improve this answer
    
Awesome. Just the explanation I was looking for. Thank you! –  user1527227 Apr 19 '13 at 20:42
add comment

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.

share|improve this answer
    
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
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.