So, basically, my professor has taught us the principle of inclusion and exclusion. We were given the basic formulation of the problem using set theory (A$\cup$B$\cup$C), and then launched into examples. I failed to see in any of the examples how it related to set theory, and he seemed to want us to learn through pattern matching (which has left me very confused).
An example of this: How many ways are there to assign five different jobs to four different employees if every employee is assigned at least one job?
$4^5$ – $\binom{4}{1}$$3^5$ + $\binom{4}{2}$$2^5$ – $\binom{4}{3}$$1^5$ He talked us through this somewhat, but I couldn't understand how or why it worked. It seemed very much intuition based, as though it changed with every circumstance, rather than following a rule that was unchanging through the various circumstances.
Calculating this, the answer is 240. I'm not good at pattern matching, and I don't really understand how the Professor chose the values that he did for the binomial coefficients, and I don't really understand what the sets constitute in this case (what does set A represent versus set B versus set C). My main question in this case is what do the sets represent, and what do the intersections being added and subtracted represent? I need more than a pattern in order to understand what's going on in this problem.
My Dad was helping me with this problem and he didn't understand what the professor was doing either. He attempted to solve the problem this way:
$\binom{5}{4}$$\cdot$4!$\cdot$$\binom{4}{1}$ The idea was to distribute one job to each of the four employees, determine the possible number of combinations, and then choose one employee for the remaining job.
The answer was twice that of the Professor's answer. Either my Dad over-counted somehow, or it just plain isn't the correct way to solve the problem. Which is unfortunate because at least with that method I could see what was going on. My second question is whether or not there is any amendment that could be made to my Dad's method in order to get the correct answer with these problems, or if there is some second method of solving PIE problems that do not involve pure pattern matching?
Thank you for taking the time to read this. I was trying to be as specific as possible, which was noted in the guidelines (vague questions get vague answers). I'm a first time poster, and so I would appreciate any additional feedback if there is something I can do to improve any future posts.
Best Answer
The magic words which indicate a usage of PIE are at least.
Here we did some overcounting, since we also count possibilities where one (or more) of the employees were not assigned a job. We are now going to compensate for this. We subtract the possibilities one employee was not assigned a job.
But we have to be careful. What we really did when we subtracted $\binom{4}{1}3^5$ was to subtract the possibilities that at least one employee was not assigned a job. The $3^5$ ways which we have identified do also include cases where less than three employees were assigned the five jobs. So, we did some overcounting in the other direction and we have again to compensate for this.
Again, we observe that $2^5$ possibilities to assign the five jobs to two remaining employees also include the (two) possibilities that one employee was assigned all five jobs. We have to compensate this also and obtain finally
\begin{align*} \color{blue}{4^5-\binom{4}{1}3^5+\binom{4}{2}2^5-\binom{4}{3}1^5} \end{align*}