Told by Professor that this is PIE, but don't see how it's PIE. Help understanding what constitutes the sets, or alternative ways to solve?

The magic words which indicate a usage of PIE are at least.

• If counting objects having at least a number of properties is simple, but counting objects having exactly a number of properties is difficult, than PIE comes into play.

In our example we have five jobs $\{J_1,\ldots,J_5\}$ which have to be assigned to four employees so that every employee is assigned at least one job.

Step 1: $4^5$

• We start with the easy things and observe there are $4$ ways to assign $J_1$ to one of the four employees. To each of these possibilities we have $4$ ways to assign $J_2$ to one of the four employees, giving a total of $4^2$ possibilities. Continuing this way we find there is a total of $$4^5$$ ways to assign five jobs to four employees.

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.

Step 2: $\binom{4}{1}3^5$

There are $\binom{4}{1}$ possibilities that one employee was not assigned a job. In each of these $\binom{4}{1}$ cases there are $3^5$ possibilities to assign the five jobs to the three remaining employees. Combined with step 1 we obtain a total of $$4^5-\binom{4}{1}3^5$$ ways.

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.

Step 3: $\binom{4}{2}2^5$

There are $\binom{4}{2}$ possibilities that two employees were not assigned a job. In each of these $\binom{4}{2}$ cases there are $2^5$ possibilities to assign the five jobs to the two remaining employees. Combined with step 1 and step 2 we obtain a total of $$4^5-\binom{4}{1}3^5+\binom{4}{2}2^5$$ ways.

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*}

As usual @MarkusScheuer gave an excellent answer. Here I "supplement" his answer by showing how all this maps to set theory, what the sets are, etc.

PIE goes like this:

$$|\bigcup_i A_i| = \sum_i |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i < j < k} |A_i \cap A_j \cap A_k| - ...$$

Here $\sum_{i<j}$ means you are summing over all pairs (size $2$ subsets). We write $i<j$ because then clearly $(4,7)$ and $(7,4)$ are not both included. (Whereas if we write $\sum_{i \neq j}$ then it can be a little ambiguous whether they are both included.)

Anyway, the LHS (left hand side), the thing you're trying to use PIE to count, is a union of sets. This is (almost?) always true of PIE: you are counting a union. So the first question is: for this problem, what union of what sets?

Now, "everybody gets at least $1$ job" sounds like an intersection (Peter gets a job AND Mary gets a job AND etc...), but then the complement would indeed be a union (Peter has no job OR Mary has no job OR etc...) So we are using PIE to count this complement.

In this problem, the individual sets are $A_i=$ assignments in which person $i$ gets no job. Then the "bad" assignments are: $Bad = A_1 \cup A_2 \cup A_3 \cup A_4 = \bigcup_i A_i=$ LHS, and your answer is all assignments minus the bad ones, i.e. $4^5 - |Bad|$. Now we can do the right hand side of PIE as follows:

• $\sum_i |A_i|$: There are ${4 \choose 1}$ terms in the summation, but luckily for you, all $|A_i|$ are equal! $A_i = $ person $i$ gets no jobs, and so the $5$ jobs are distributed to $3$ people; no. of ways $= 3^5$. The whole thing is ${4 \choose 1} 3^5$.

• $\sum_{i<j} |A_i \cap A_j|$: There are ${4 \choose 2}$ terms in the summation, but again luckily for you, every term is equal! Each term is $2^5$ and the total is ${4\choose 2} 2^5$.

• $\sum_{i<j<k} |A_i \cap A_j \cap A_k|$: There are ${4 \choose 3}$ terms in the summation, but again luckily for you, every term is equal! Each term is $1^5$ and the total is ${4\choose 3} 1^5$.

• $\sum_{i<j<k<l} |A_i \cap A_j \cap A_k \cap A_l|$: There is only $1$ term, $|A_1 \cap A_2 \cap A_3 \cap A_4|$, and it is zero since it is impossible for all $4$ to get no jobs.

Therefore: $|Bad| = {4 \choose 1} 3^5 - {4\choose 2} 2^5 + {4\choose 3} 1^5$ and your answer $=4^5 - |Bad|$.

P.S.: in this simple problem, in each summation all the terms are equal. For a more difficult problem this may not hold. While the PIE is still valid, the formula becomes more complicated to evaluate. See here for one of my other examples if you're interested.

Your father did overcount by exactly a factor of two. That method is very prone to overcounting, but we're lucky in this case to be able to quantify the overcounting exactly.

Suppose you have employees $\{A,B,C,D\}$ and jobs $\{P,Q,R,S,T\}.$ One of the ways you can assign one job to each of the four employees is $\{(A,P),(B,Q),(C,R),(D,S)\}.$ You have one job, $T,$ still to assign, so assign it to $D.$

Another way to assign one job to each of the four employees is $\{(A,P),(B,Q),(C,R),(D,T)\}.$ You have one job, $S,$ still to assign, so assign it to $D.$

But each of those two different ways of following your father's procedure gives you the same set of job assignments: $\{(A,P),(B,Q),(C,R),(D,S),(D,T)\}.$

Since it turns out all job assignments follow essentially the same pattern--two jobs to one employee, one job to each other employee--all the overcounting follows the same pattern as well. The employee with two jobs can get them in one of two ways: one of the jobs is assigned to that employee in the first step (choose either of the two jobs that eventually will be assigned to that employee), and the other must be assigned in the second step. Hence every set of assignments you wanted to count gets counted exactly twice.

If you had seven jobs for the four employees, things would have been much messier: the "extra" jobs could all go to one employee, or two to one employee and one to a different employee, or one each to three separate employees. In each of those cases the unwanted distinction between "job assigned in the first step" and "jobs assigned in the second step" results in each set of assignments being overcounted a different number of times, and inclusion-exclusion starts to become a lot easier in comparison.