How many ways are there to assign each of five professors in a math department to two courses in the Fall semester (that is 10 different math courses in all) and then assign each professor two courses in the spring semester such that no professor gets to teach the same two courses both semesters? i know how to solve it using other form, but i don`t know how to solve it using inclusive and exclusive principle.
Asked
Active
Viewed 43 times
-1
-
1Are we assuming that the same $10$ courses are taught in the fall and in the spring? Are we eliminating combinations only when one professor teaches the same set of two courses in both semesters, or are we also eliminating combinations where a professor has one course in common between the two semesters? Please edit your question both to clarify these points and also to show us how you've attempted to apply the principle of inclusion and exclusion, so we can focus on where you're stuck. – Robert Shore May 11 '21 at 22:48
1 Answers
0
SKETCH: Label the professors $P_1,\ldots,P_5$ and the courses $C_1,\ldots,C_{10}$ so that $P_k$ is assigned the courses $C_{2k-1}$ and $C_{2k}$ in the fall. For $k=1,\ldots,5$ let $A_k$ be the set of all course assignments such that $P_k$ gets the pair $\{C_{2k-1},C_{2k}\}$; then $A_1\cup\ldots\cup A_5$ is the set of spring assignments in which at least one professor does get to teach the same pair of courses as in the fall. Thus, if $A$ is the set of all possible spring course assignments, we want
$$|A|-\left|\bigcup_{k=1}^5A_k\right|\,.$$
- How many ways are there to partition $10$ courses into $5$ pairs of courses? If you get stuck, see this question.
- Once the courses have been partitioned into $5$ pairs of courses, how many ways are there to assign these pairs to the $5$ professors?
- Suitably combine these answers to find $|A|$.
The inclusion-exclusion principle says that
$$\left|\bigcup_{k=1}^5A_k\right|=\sum_{\varnothing\ne I\subseteq\{1,\ldots,5\}}(-1)^{|I|+1}\left|\bigcap_{k\in I}A_k\right|\,,\tag{1}$$
so the next step is to work out $\left|\bigcap_{k\in I}A_k\right|$ for a non-empty subset $I$ of $\{1,\ldots,5\}$. Finding $|A_k|$ would be a good start.
- Once we assign the pair $\{C_{2k-1},C_{2k}\}$ to $P_k$, how many ways are there to partition the remaining $8$ courses into $4$ pairs and assign them to the remaining $4$ professors? If you successfully calculated $|A|$, you should have no trouble with this: it’s another problem of exactly the same kind.
More generally, suppose that $I=\{k_1,\ldots,k_\ell\}$.
- Once we assign the pair $\{C_{2k_i-1},C_{2k_i}\}$ to $P_{k_i}$ for $i=1,\ldots,\ell$, how many ways are there partition the remaining $10-2\ell$ courses into $5-\ell$ pairs and assign them to the remaining $5-\ell$ professors? This is yet another problem of the same kind.
- If $1\le\ell\le 5$, how many $\ell$-element subsets $I$ of $\{1,\ldots,5\}$ are there?
If $a_\ell$ denotes the answer to the first of these two questions and $s_\ell$ the answer to the second, we can rewrite $(1)$ as
$$\left|\bigcup_{k=1}^5A_k\right|=\sum_{\ell=1}^5(-1)^{\ell+1}s_\ell a_\ell\,,$$
and the answer now is just a matter of a bit of arithmetic.
Brian M. Scott
- 616,228