Divinding 8 teachers up among 4 schools.

28. If 8 new teachers are to be divided among 4 schools, how many divisions are possible? What if each school must receive 2 teachers?

OK, so it's pretty clear that if $\displaystyle x_i$ is the number of teachers allocated to one of the four schools then $\displaystyle x_1+x_2+x_3+x_4=8$

Comparing this too the chapter text leads me to the following, $\displaystyle \binom{n+r-1}{r-1}$, which is the number of distinct nonnegative integer-valued vectors $\displaystyle (x_1, x_2, . . . , x_r)$ satisfying the equation $\displaystyle x_1 + x_2 +...+ x_r=n$

So my first question is, since I need $\displaystyle x_i=0$, to be a valid entry does this formula cover that case? (I'm thinking it does because it mentions nonnegative integer-valued vectors.)

Secondly, taking $\displaystyle n=8$ and $\displaystyle r=4$, I've got $\displaystyle \binom{8+4-1}{4-1}=\frac{11!}{8!3!}=165$ as my current working solution. However, the text is talking about indistinguishable objects here and I hardly think teachers are indistinguishable. Also, the listed answer is 65,536. So I think I need to permute the teachers now somehow? Or is this all wrong?

Quote:

---

Originally Posted by bkbowser

28. If 8 new teachers are to be divided among 4 schools, how many divisions are possible? What if each school must receive 2 teachers?

OK, so it's pretty clear that if $\displaystyle x_i$ is the number of teachers allocated to one of the four schools then $\displaystyle x_1+x_2+x_3+x_4=8$

Comparing this too the chapter text leads me to the following, $\displaystyle \binom{n+r-1}{r-1}$, which is the number of distinct nonnegative integer-valued vectors $\displaystyle (x_1, x_2, . . . , x_r)$ satisfying the equation $\displaystyle x_1 + x_2 +...+ x_r=n$

So my first question is, since I need $\displaystyle x_i=0$, to be a valid entry does this formula cover that case? (I'm thinking it does because it mentions nonnegative integer-valued vectors.)

Secondly, taking $\displaystyle n=8$ and $\displaystyle r=4$, I've got $\displaystyle \binom{8+4-1}{4-1}=\frac{11!}{8!3!}=165$ as my current working solution. However, the text is talking about indistinguishable objects here and I hardly think teachers are indistinguishable. Also, the listed answer is 65,536. So I think I need to permute the teachers now somehow? Or is this all wrong?

---

for your first question the simple example of n=1, r=2 shows that the case of $\displaystyle x_i=0$ is covered by this formula.

for your second question, ignoring what you've posted, think about it this way. Each teacher can be assigned to 1 of 4 schools. Think of it as giving them a base 4 digit. there are 8 teachers so the total number of variations is $\displaystyle 4^8=65536$.

Quote:

---

Originally Posted by bkbowser

28. If 8 new teachers are to be divided among 4 schools, how many divisions are possible? What if each school must receive 2 teachers?
However, the text is talking about ndistinguishable objects here and I hardly think teachers are indistinguishable. Also, the listed answer is 65,536. So I think I need to permute the teachers now somehow? Or is this all wrong?

---

First I assume that there are two distinct questions here. 1) there are no restrictions. 2) each school gets two teachers.

1) There are $\displaystyle m^n$ functions from a set of $\displaystyle n$ elements to a set of $\displaystyle m$ elements.

2) How many ways can we rearrange the string $\displaystyle AABBCCDD~?$

Quote:

---

Originally Posted by romsek

for your first question the simple example of n=1, r=2 shows that the case of $\displaystyle x_i=0$ is covered by this formula.

for your second question, ignoring what you've posted, think about it this way. Each teacher can be assigned to 1 of 4 schools. Think of it as giving them a base 4 digit. there are 8 teachers so the total number of variations is $\displaystyle 4^8=65536$.

---

With $\displaystyle n=1,r=2$ zero would have to be an option since we only care about integer solutions. $\displaystyle \binom{1+2-1}{2-1}=\binom{2}{1}=2$. OK good.

Assigning each teacher a number out of a base 4 system seems to work well, but can I use the

Quote:

---

Originally Posted by Plato

First I assume that there are two distinct questions here. 1) there are no restrictions. 2) each school gets two teachers.

1) There are $\displaystyle m^n$ functions from a set of $\displaystyle n$ elements to a set of $\displaystyle m$ elements.

2) How many ways can we rearrange the string $\displaystyle AABBCCDD~?$

---

Sorry, yes there are two questions in the original, I didn't actually get around to trying to solve the second as I wasn't finished with the first.

1) looks very similar to romsek's suggestion. Is there no way to use this proposition from the text to solve part 1? $\displaystyle \binom{n+r-1}{r-1}$, which is the number of distinct nonnegative integer-valued vectors $\displaystyle (x_1, x_2, . . . , x_r)$ satisfying the equation $\displaystyle x_1 + x_2 +...+ x_r=n$.

For 2) there are essentially 8 slots and 8 options for the first slot. The options decrease by one with every slot so there are 8! ways? No this can't be right.

Quote:

---

Originally Posted by bkbowser

1) looks very similar to romsek's suggestion. Is there no way to use this proposition from the text to solve part 1? $\displaystyle \binom{n+r-1}{r-1}$, which is the number of distinct nonnegative integer-valued vectors $\displaystyle (x_1, x_2, . . . , x_r)$ satisfying the equation $\displaystyle x_1 + x_2 +...+ x_r=n$.

For 2) there are essentially 8 slots and 8 options for the first slot. The options decrease by one with every slot so there are 8! ways? No this can't be right.

---

NO! 1) is $\displaystyle 4^8$. The number of functions from eight teachers to four schools.

2) the answer is $\displaystyle \frac{8!}{(2)^4}$.
Think of the schools as $\displaystyle \{A,B,C,D\}$ Make a list of the eight teachers.
Arrange the string $\displaystyle AABBCCDD$, one next to each name.
Every rearrangement of that string is a possible way to assign eight teachers to four schools with two to each school.

Quote:

---

Originally Posted by Plato

NO! 1) is $\displaystyle 4^8$. The number of functions from eight teachers to four schools.

2) the answer is $\displaystyle \frac{8!}{(2)^4}$.
Think of the schools as $\displaystyle \{A,B,C,D\}$ Make a list of the eight teachers.
Arrange the string $\displaystyle AABBCCDD$, one next to each name.
Every rearrangement of that string is a possible way to assign eight teachers to four schools with two to each school.

---

I don't fully follow but I think I can make sense of it with the text as follows; So this is a Multinomial Coefficient problem where each of the $\displaystyle r=4$ distinct subgroups is 2, which the proof in the text shows is equal to $\displaystyle \frac{n!}{n_1!n_2!n_3!n_4!}$, and this is equal to $\displaystyle \frac{8!}{2!2!22!}=\frac{8!}{2^4}=2520$.

Does this look good?

Quote:

---

Originally Posted by bkbowser

and this is equal to $\displaystyle \frac{8!}{2!2!22!}=\frac{8!}{2^4}=2520$.
Does this look good?

---

Yes, that is correct.

But the other model is very useful.

Do you understand how many ways you can rearrange the word $\displaystyle MISSISSIPPI~?$
Well $\displaystyle \frac{11!}{(4!)^2(2!)}$.
That is also how many ways that a collection of eleven people can be divided into four different cells where two cells contain four people, another contains two and the fourth contains one.

Quote:

---

Originally Posted by Plato

Do you understand how many ways you can rearrange the word $\displaystyle MISSISSIPPI~?$
Well $\displaystyle \frac{11!}{(4!)^2(2!)}$.
That is also how many ways that a collection of eleven people can be divided into four different cells where two cells contain four people, another contains two and the fourth contains one.

---

I'm not sure I understand the model.

11! is the permutations of an 11 place word.

I know you have to take out the number of duplicates, which I presume is the denominator, I'm just not sure how.

Quote:

---

Originally Posted by bkbowser

I'm not sure I understand the model.
11! is the permutations of an 11 place word.
I know you have to take out the number of duplicates, which I presume is the denominator, I'm just not sure how.

---

Put subscripts on any repeated letters:$\displaystyle MI_1S_1S_2I_2S_3S_3I_3P_1P_2I_4$.
Now we have eleven different letters. We can rearrange that string in $\displaystyle 11!$ ways.

Those subscripted I's can appear in $\displaystyle 4!$ ways without changing relative places in the string.
Those subscripted S's can appear in $\displaystyle 4!$ ways without changing relative places in the string.
Those subscripted P's can appear in $\displaystyle 2!$ ways without changing relative places in the string.

So if we drop all the subscripts, we have to divide by those numbers to get the actual count.