Dgdrxrt

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$ - $binom41$$3^5$ + $binom42$$2^5$ - $binom43$$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:

$binom54$$cdot$4!$cdot$$binom41$ 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.

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: $binom413^5$

There are $binom41$ possibilities that one employee was not assigned a job. In each of these $binom41$ 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-binom413^5$$ ways.

But we have to be careful. What we really did when we subtracted $binom413^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: $binom422^5$

There are $binom42$ possibilities that two employees were not assigned a job. In each of these $binom42$ 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-binom413^5+binom422^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

beginalign*
colorblue4^5-binom413^5+binom422^5-binom431^5
endalign*

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.

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 $4choose 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 $4choose 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 - 4choose 2 2^5 + 4choose 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.