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?
Re: Divinding 8 teachers up among 4 schools.
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$.
Re: Divinding 8 teachers up among 4 schools.
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~?$
Re: Divinding 8 teachers up among 4 schools.
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.
Re: Divinding 8 teachers up among 4 schools.
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.
Re: Divinding 8 teachers up among 4 schools.
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?
Re: Divinding 8 teachers up among 4 schools.
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.
Re: Divinding 8 teachers up among 4 schools.
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.
Re: Divinding 8 teachers up among 4 schools.
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.