Divinding 8 teachers up among 4 schools.

Printable View

January 22nd 2014, 10:12 AM
bkbowser

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 $x_i$ is the number of teachers allocated to one of the four schools then $x_1+x_2+x_3+x_4=8$

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

So my first question is, since I need $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 $n=8$ and $r=4$ , I've got $\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?
January 22nd 2014, 10:25 AM
romsek

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 $x_i$ is the number of teachers allocated to one of the four schools then $x_1+x_2+x_3+x_4=8$

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

So my first question is, since I need $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 $n=8$ and $r=4$ , I've got $\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 $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 $4^8=65536$ .
January 22nd 2014, 10:27 AM
Plato

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 $m^n$ functions from a set of $n$ elements to a set of $m$ elements.

2) How many ways can we rearrange the string $AABBCCDD~?$
January 22nd 2014, 10:55 AM
bkbowser

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 $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 $4^8=65536$ .

With $n=1,r=2$ zero would have to be an option since we only care about integer solutions. $\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 $m^n$ functions from a set of $n$ elements to a set of $m$ elements.

2) How many ways can we rearrange the string $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? $\binom{n+r-1}{r-1}$ , which is the number of distinct nonnegative integer-valued vectors $(x_1, x_2, . . . , x_r)$ satisfying the equation $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.
January 22nd 2014, 11:08 AM
Plato

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? $\binom{n+r-1}{r-1}$ , which is the number of distinct nonnegative integer-valued vectors $(x_1, x_2, . . . , x_r)$ satisfying the equation $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 $4^8$ . The number of functions from eight teachers to four schools.

2) the answer is $\frac{8!}{(2)^4}$ .
Think of the schools as $\{A,B,C,D\}$ Make a list of the eight teachers.
Arrange the string $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.
January 22nd 2014, 11:28 AM
bkbowser

Re: Divinding 8 teachers up among 4 schools.

Quote:

Originally Posted by Plato

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

2) the answer is $\frac{8!}{(2)^4}$ .
Think of the schools as $\{A,B,C,D\}$ Make a list of the eight teachers.
Arrange the string $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 $r=4$ distinct subgroups is 2, which the proof in the text shows is equal to $\frac{n!}{n_1!n_2!n_3!n_4!}$ , and this is equal to $\frac{8!}{2!2!22!}=\frac{8!}{2^4}=2520$ .

Does this look good?
January 22nd 2014, 12:02 PM
Plato

Re: Divinding 8 teachers up among 4 schools.

Quote:

Originally Posted by bkbowser

and this is equal to $\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 $MISSISSIPPI~?$
Well $\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.
January 28th 2014, 11:51 AM
bkbowser

Re: Divinding 8 teachers up among 4 schools.

Quote:

Originally Posted by Plato

Do you understand how many ways you can rearrange the word $MISSISSIPPI~?$
Well $\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.
January 28th 2014, 12:08 PM
Plato

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: $MI_1S_1S_2I_2S_3S_3I_3P_1P_2I_4$ .
Now we have eleven different letters. We can rearrange that string in $11!$ ways.

Those subscripted I's can appear in $4!$ ways without changing relative places in the string.
Those subscripted S's can appear in $4!$ ways without changing relative places in the string.
Those subscripted P's can appear in $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.