Math Combination Help: Finding Possible Divisions for New Teachers Among Schools

[yitriana]

Homework Statement

a) 8 new teachers are to be divided among 4 schools, and each teacher can teach at maximum 3 schools. There is a staff limit such that 3 of the schools only allow 4 new teachers. How many divisions are possible?

The Attempt at a Solution

Without staff limit
a) So if all teachers can teach at max one school, # divisions is 4^8.

If a teacher must teach at exactly two schools, this includes the possibility of all 8 teachers teaching at one school and another and no teachers at the remaining 2 schools, as well as the possibility of an evenly distributed 4 teachers for each of the four schools. A teacher has 4*3 possibilities for their two schools, so combinations is 12^8

Event of all teachers teaching at max one school and event of all teachers teaching at exactly two schools are mutually exclusive events. Teachers teaching at exactly 3 schools is (4*3*2)^8 = 24^8.
Thus, answer for part a) is 4^8 + 12^8 + 24^8

Adding staff limit
Adding staff limit for the case of teacher teaching at exactly one school, find number of division amongst all schools for case of teacher teaching at one school.

<br /> \sum_{0 \leq m\leq 8}\sum_{\substack{i+j+k=m\\ i\leq4, j\leq4, k\leq4}}\frac{m!}{i!j!k!} \sum_{0\leq n\leq8-m} \binom{8-m}{n}<br />

This is because a 0 to 8 teachers can be divided among 3 schools with staff limit (i, j and k), and depending on the number of teachers left after dividing, 8-m, consider all division of teachers from choosing 0 to 8 teachers for the 4th school with no staff limit.

Now, the hard part for me is to figure out how to apply this reasoning for the whole problem which is that teachers can teach at most three schools.

Does anyone have any suggestions?

 

[Tedjn]

Let's start with the without staff limit section. First, you must clarify the question. Does every teacher need to teach at a school, or can a teacher choose not to teach at all?

If every teacher must teach at one school, the number of possibilities is 4⁸. If every teacher teaches at exactly two schools, then every teacher gets to choose 2 of the 4 schools. Does order matter? I don't agree that each teacher has 12 choices. Likewise for the case of all teachers teaching at 3 schools.

Here is an illuminating way to think about this. A teacher who teaches at one school has 4 choices for the school at which he or she teaches. A teacher who teaches at three schools has 4 choices for the school at which he or she does not teach.

Furthermore, it is true that all teachers teaching at one school, all teachers teaching at two schools, and all teachers teaching at three schools are pairwise mutually exclusive. However, they do not account for all the possibilities. What if some teachers decide to teach at one school, but others decide to teach at two schools?

How can you account for this possibility? One way is to work off the following observation: for a single teacher, teaching at one school, two schools, or three schools are pairwise mutually exclusive possibilities. More importantly, they are all the possibilities (if the answer to the first question in my post is that every teacher needs to choose at least one school).