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?When adding zero really counts …Probability of a 3 digits occurence from a sequence of 64 random hexadecimal symbols?SAT Probability of 4…Assignment problem with serval 'rounds' and additional constraintsCounting problem combinatorics with employees of a faculty.n boys, n dads and n momsWhy is my solution to this counting problem incorrect?Basic combinatorics question - christmas presentsEmployees can be assigned three tasks if and only if $|N(A)| geq 3|A|$ for all $A subseteq E$How many ways are there to assign six different jobs to five different employees if every employee is assigned at least one job?Random Gift Giving at a Party - Combinatorics ProblemOptimal Assignment With A Dissimilar Earnings Between Actors

How can we prove that any integral in the set of non-elementary integrals cannot be expressed in the form of elementary functions?

How to safely derail a train during transit?

Is HostGator storing my password in plaintext?

Is a stroke of luck acceptable after a series of unfavorable events?

Crossing the line between justified force and brutality

Is `x >> pure y` equivalent to `liftM (const y) x`

What does "I’d sit this one out, Cap," imply or mean in the context?

Do sorcerers' Subtle Spells require a skill check to be unseen?

Implement the Thanos sorting algorithm

What can we do to stop prior company from asking us questions?

Method to test if a number is a perfect power?

Risk of infection at the gym?

Would a high gravity rocky planet be guaranteed to have an atmosphere?

How can I kill an app using Terminal?

Lay out the Carpet

Is this apparent Class Action settlement a spam message?

Opposite of a diet

Is the destination of a commercial flight important for the pilot?

What is the intuitive meaning of having a linear relationship between the logs of two variables?

Why Were Madagascar and New Zealand Discovered So Late?

Increase performance creating Mandelbrot set in python

You cannot touch me, but I can touch you, who am I?

Applicability of Single Responsibility Principle

Did Dumbledore lie to Harry about how long he had James Potter's invisibility cloak when he was examining it? If so, why?



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?


When adding zero really counts …Probability of a 3 digits occurence from a sequence of 64 random hexadecimal symbols?SAT Probability of 4…Assignment problem with serval 'rounds' and additional constraintsCounting problem combinatorics with employees of a faculty.n boys, n dads and n momsWhy is my solution to this counting problem incorrect?Basic combinatorics question - christmas presentsEmployees can be assigned three tasks if and only if $|N(A)| geq 3|A|$ for all $A subseteq E$How many ways are there to assign six different jobs to five different employees if every employee is assigned at least one job?Random Gift Giving at a Party - Combinatorics ProblemOptimal Assignment With A Dissimilar Earnings Between Actors













4












$begingroup$


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.










share|cite|improve this question









New contributor




Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$











  • $begingroup$
    Welcome to MSE and nice first post! I am going to bed soon so I will let someone else (in another time zone) tackle the PIE formula. Re: your dad, he double-counted. Suppose employee Pat got two jobs $A$ and $B$. Your dad counted once for the case when $A$ is the $5$th job (the one *not* chosen in the $5 choose 4$), and once more for the case when $B$ is the $5$th job. This is true for every single case, luckily, so you just need to divide by 2.
    $endgroup$
    – antkam
    22 hours ago







  • 1




    $begingroup$
    One "dad style" way that is correct would be: Pick an unlucky employee to have $2$ jobs ($4$ ways), then arrange the other $3$ by height (they're distinguishable) and give the tallest person a job ($5$ ways), the next tallest a job ($4$ ways), the shortest a job ($3$ ways). The unlucky employee by necessity gets the last $2$ jobs. Total no. $=4 times 5 times 4 times 3 = 240$.
    $endgroup$
    – antkam
    22 hours ago










  • $begingroup$
    This example is not the greatest for demonstrating the power of PIE, since it's so easy by multiplication principle (which in turn is due to only one pattern 5=2+1+1+1 occurring). To see why PIE is useful, do the same problem with, say, 8 jobs assigned to 4 people with everyone getting at least one job.
    $endgroup$
    – Ned
    14 hours ago















4












$begingroup$


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.










share|cite|improve this question









New contributor




Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$











  • $begingroup$
    Welcome to MSE and nice first post! I am going to bed soon so I will let someone else (in another time zone) tackle the PIE formula. Re: your dad, he double-counted. Suppose employee Pat got two jobs $A$ and $B$. Your dad counted once for the case when $A$ is the $5$th job (the one *not* chosen in the $5 choose 4$), and once more for the case when $B$ is the $5$th job. This is true for every single case, luckily, so you just need to divide by 2.
    $endgroup$
    – antkam
    22 hours ago







  • 1




    $begingroup$
    One "dad style" way that is correct would be: Pick an unlucky employee to have $2$ jobs ($4$ ways), then arrange the other $3$ by height (they're distinguishable) and give the tallest person a job ($5$ ways), the next tallest a job ($4$ ways), the shortest a job ($3$ ways). The unlucky employee by necessity gets the last $2$ jobs. Total no. $=4 times 5 times 4 times 3 = 240$.
    $endgroup$
    – antkam
    22 hours ago










  • $begingroup$
    This example is not the greatest for demonstrating the power of PIE, since it's so easy by multiplication principle (which in turn is due to only one pattern 5=2+1+1+1 occurring). To see why PIE is useful, do the same problem with, say, 8 jobs assigned to 4 people with everyone getting at least one job.
    $endgroup$
    – Ned
    14 hours ago













4












4








4


0



$begingroup$


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.










share|cite|improve this question









New contributor




Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




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.







combinatorics inclusion-exclusion






share|cite|improve this question









New contributor




Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited 17 hours ago









N. F. Taussig

44.8k103358




44.8k103358






New contributor




Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 23 hours ago









DanielDaniel

233




233




New contributor




Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











  • $begingroup$
    Welcome to MSE and nice first post! I am going to bed soon so I will let someone else (in another time zone) tackle the PIE formula. Re: your dad, he double-counted. Suppose employee Pat got two jobs $A$ and $B$. Your dad counted once for the case when $A$ is the $5$th job (the one *not* chosen in the $5 choose 4$), and once more for the case when $B$ is the $5$th job. This is true for every single case, luckily, so you just need to divide by 2.
    $endgroup$
    – antkam
    22 hours ago







  • 1




    $begingroup$
    One "dad style" way that is correct would be: Pick an unlucky employee to have $2$ jobs ($4$ ways), then arrange the other $3$ by height (they're distinguishable) and give the tallest person a job ($5$ ways), the next tallest a job ($4$ ways), the shortest a job ($3$ ways). The unlucky employee by necessity gets the last $2$ jobs. Total no. $=4 times 5 times 4 times 3 = 240$.
    $endgroup$
    – antkam
    22 hours ago










  • $begingroup$
    This example is not the greatest for demonstrating the power of PIE, since it's so easy by multiplication principle (which in turn is due to only one pattern 5=2+1+1+1 occurring). To see why PIE is useful, do the same problem with, say, 8 jobs assigned to 4 people with everyone getting at least one job.
    $endgroup$
    – Ned
    14 hours ago
















  • $begingroup$
    Welcome to MSE and nice first post! I am going to bed soon so I will let someone else (in another time zone) tackle the PIE formula. Re: your dad, he double-counted. Suppose employee Pat got two jobs $A$ and $B$. Your dad counted once for the case when $A$ is the $5$th job (the one *not* chosen in the $5 choose 4$), and once more for the case when $B$ is the $5$th job. This is true for every single case, luckily, so you just need to divide by 2.
    $endgroup$
    – antkam
    22 hours ago







  • 1




    $begingroup$
    One "dad style" way that is correct would be: Pick an unlucky employee to have $2$ jobs ($4$ ways), then arrange the other $3$ by height (they're distinguishable) and give the tallest person a job ($5$ ways), the next tallest a job ($4$ ways), the shortest a job ($3$ ways). The unlucky employee by necessity gets the last $2$ jobs. Total no. $=4 times 5 times 4 times 3 = 240$.
    $endgroup$
    – antkam
    22 hours ago










  • $begingroup$
    This example is not the greatest for demonstrating the power of PIE, since it's so easy by multiplication principle (which in turn is due to only one pattern 5=2+1+1+1 occurring). To see why PIE is useful, do the same problem with, say, 8 jobs assigned to 4 people with everyone getting at least one job.
    $endgroup$
    – Ned
    14 hours ago















$begingroup$
Welcome to MSE and nice first post! I am going to bed soon so I will let someone else (in another time zone) tackle the PIE formula. Re: your dad, he double-counted. Suppose employee Pat got two jobs $A$ and $B$. Your dad counted once for the case when $A$ is the $5$th job (the one *not* chosen in the $5 choose 4$), and once more for the case when $B$ is the $5$th job. This is true for every single case, luckily, so you just need to divide by 2.
$endgroup$
– antkam
22 hours ago





$begingroup$
Welcome to MSE and nice first post! I am going to bed soon so I will let someone else (in another time zone) tackle the PIE formula. Re: your dad, he double-counted. Suppose employee Pat got two jobs $A$ and $B$. Your dad counted once for the case when $A$ is the $5$th job (the one *not* chosen in the $5 choose 4$), and once more for the case when $B$ is the $5$th job. This is true for every single case, luckily, so you just need to divide by 2.
$endgroup$
– antkam
22 hours ago





1




1




$begingroup$
One "dad style" way that is correct would be: Pick an unlucky employee to have $2$ jobs ($4$ ways), then arrange the other $3$ by height (they're distinguishable) and give the tallest person a job ($5$ ways), the next tallest a job ($4$ ways), the shortest a job ($3$ ways). The unlucky employee by necessity gets the last $2$ jobs. Total no. $=4 times 5 times 4 times 3 = 240$.
$endgroup$
– antkam
22 hours ago




$begingroup$
One "dad style" way that is correct would be: Pick an unlucky employee to have $2$ jobs ($4$ ways), then arrange the other $3$ by height (they're distinguishable) and give the tallest person a job ($5$ ways), the next tallest a job ($4$ ways), the shortest a job ($3$ ways). The unlucky employee by necessity gets the last $2$ jobs. Total no. $=4 times 5 times 4 times 3 = 240$.
$endgroup$
– antkam
22 hours ago












$begingroup$
This example is not the greatest for demonstrating the power of PIE, since it's so easy by multiplication principle (which in turn is due to only one pattern 5=2+1+1+1 occurring). To see why PIE is useful, do the same problem with, say, 8 jobs assigned to 4 people with everyone getting at least one job.
$endgroup$
– Ned
14 hours ago




$begingroup$
This example is not the greatest for demonstrating the power of PIE, since it's so easy by multiplication principle (which in turn is due to only one pattern 5=2+1+1+1 occurring). To see why PIE is useful, do the same problem with, say, 8 jobs assigned to 4 people with everyone getting at least one job.
$endgroup$
– Ned
14 hours ago










3 Answers
3






active

oldest

votes


















6












$begingroup$

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*






share|cite|improve this answer











$endgroup$












  • $begingroup$
    Thank you for the answer. I'm going to attempt to internalize the method so that I can apply the principle to not only this particular problem, but PIE problems in general.
    $endgroup$
    – Daniel
    10 hours ago










  • $begingroup$
    @Daniel: You're welcome. I appreciate your approach. The PIE method belongs to the so-called sieve methods. Maybe not yet but soon you might want to have a look at section 4.2 of H.S. Wilf's Generatingfunctionology which provides helpful information.
    $endgroup$
    – Markus Scheuer
    10 hours ago


















2












$begingroup$

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.






share|cite|improve this answer









$endgroup$




















    2












    $begingroup$

    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.






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      Nice and instructive answer. (+1). Your ref inspired me to also give an answer there. It is in fact also based upon PIE as indicated in this post. :-)
      $endgroup$
      – Markus Scheuer
      8 hours ago










    Your Answer





    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "69"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );






    Daniel is a new contributor. Be nice, and check out our Code of Conduct.









    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3164044%2ftold-by-professor-that-this-is-pie-but-dont-see-how-its-pie-help-understandi%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    6












    $begingroup$

    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*






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      Thank you for the answer. I'm going to attempt to internalize the method so that I can apply the principle to not only this particular problem, but PIE problems in general.
      $endgroup$
      – Daniel
      10 hours ago










    • $begingroup$
      @Daniel: You're welcome. I appreciate your approach. The PIE method belongs to the so-called sieve methods. Maybe not yet but soon you might want to have a look at section 4.2 of H.S. Wilf's Generatingfunctionology which provides helpful information.
      $endgroup$
      – Markus Scheuer
      10 hours ago















    6












    $begingroup$

    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*






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      Thank you for the answer. I'm going to attempt to internalize the method so that I can apply the principle to not only this particular problem, but PIE problems in general.
      $endgroup$
      – Daniel
      10 hours ago










    • $begingroup$
      @Daniel: You're welcome. I appreciate your approach. The PIE method belongs to the so-called sieve methods. Maybe not yet but soon you might want to have a look at section 4.2 of H.S. Wilf's Generatingfunctionology which provides helpful information.
      $endgroup$
      – Markus Scheuer
      10 hours ago













    6












    6








    6





    $begingroup$

    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*






    share|cite|improve this answer











    $endgroup$



    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*







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited 17 hours ago

























    answered 17 hours ago









    Markus ScheuerMarkus Scheuer

    63.2k460150




    63.2k460150











    • $begingroup$
      Thank you for the answer. I'm going to attempt to internalize the method so that I can apply the principle to not only this particular problem, but PIE problems in general.
      $endgroup$
      – Daniel
      10 hours ago










    • $begingroup$
      @Daniel: You're welcome. I appreciate your approach. The PIE method belongs to the so-called sieve methods. Maybe not yet but soon you might want to have a look at section 4.2 of H.S. Wilf's Generatingfunctionology which provides helpful information.
      $endgroup$
      – Markus Scheuer
      10 hours ago
















    • $begingroup$
      Thank you for the answer. I'm going to attempt to internalize the method so that I can apply the principle to not only this particular problem, but PIE problems in general.
      $endgroup$
      – Daniel
      10 hours ago










    • $begingroup$
      @Daniel: You're welcome. I appreciate your approach. The PIE method belongs to the so-called sieve methods. Maybe not yet but soon you might want to have a look at section 4.2 of H.S. Wilf's Generatingfunctionology which provides helpful information.
      $endgroup$
      – Markus Scheuer
      10 hours ago















    $begingroup$
    Thank you for the answer. I'm going to attempt to internalize the method so that I can apply the principle to not only this particular problem, but PIE problems in general.
    $endgroup$
    – Daniel
    10 hours ago




    $begingroup$
    Thank you for the answer. I'm going to attempt to internalize the method so that I can apply the principle to not only this particular problem, but PIE problems in general.
    $endgroup$
    – Daniel
    10 hours ago












    $begingroup$
    @Daniel: You're welcome. I appreciate your approach. The PIE method belongs to the so-called sieve methods. Maybe not yet but soon you might want to have a look at section 4.2 of H.S. Wilf's Generatingfunctionology which provides helpful information.
    $endgroup$
    – Markus Scheuer
    10 hours ago




    $begingroup$
    @Daniel: You're welcome. I appreciate your approach. The PIE method belongs to the so-called sieve methods. Maybe not yet but soon you might want to have a look at section 4.2 of H.S. Wilf's Generatingfunctionology which provides helpful information.
    $endgroup$
    – Markus Scheuer
    10 hours ago











    2












    $begingroup$

    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.






    share|cite|improve this answer









    $endgroup$

















      2












      $begingroup$

      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.






      share|cite|improve this answer









      $endgroup$















        2












        2








        2





        $begingroup$

        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.






        share|cite|improve this answer









        $endgroup$



        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.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 15 hours ago









        David KDavid K

        55.4k344120




        55.4k344120





















            2












            $begingroup$

            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.






            share|cite|improve this answer











            $endgroup$












            • $begingroup$
              Nice and instructive answer. (+1). Your ref inspired me to also give an answer there. It is in fact also based upon PIE as indicated in this post. :-)
              $endgroup$
              – Markus Scheuer
              8 hours ago















            2












            $begingroup$

            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.






            share|cite|improve this answer











            $endgroup$












            • $begingroup$
              Nice and instructive answer. (+1). Your ref inspired me to also give an answer there. It is in fact also based upon PIE as indicated in this post. :-)
              $endgroup$
              – Markus Scheuer
              8 hours ago













            2












            2








            2





            $begingroup$

            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.






            share|cite|improve this answer











            $endgroup$



            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.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited 11 hours ago

























            answered 11 hours ago









            antkamantkam

            2,427312




            2,427312











            • $begingroup$
              Nice and instructive answer. (+1). Your ref inspired me to also give an answer there. It is in fact also based upon PIE as indicated in this post. :-)
              $endgroup$
              – Markus Scheuer
              8 hours ago
















            • $begingroup$
              Nice and instructive answer. (+1). Your ref inspired me to also give an answer there. It is in fact also based upon PIE as indicated in this post. :-)
              $endgroup$
              – Markus Scheuer
              8 hours ago















            $begingroup$
            Nice and instructive answer. (+1). Your ref inspired me to also give an answer there. It is in fact also based upon PIE as indicated in this post. :-)
            $endgroup$
            – Markus Scheuer
            8 hours ago




            $begingroup$
            Nice and instructive answer. (+1). Your ref inspired me to also give an answer there. It is in fact also based upon PIE as indicated in this post. :-)
            $endgroup$
            – Markus Scheuer
            8 hours ago










            Daniel is a new contributor. Be nice, and check out our Code of Conduct.









            draft saved

            draft discarded


















            Daniel is a new contributor. Be nice, and check out our Code of Conduct.












            Daniel is a new contributor. Be nice, and check out our Code of Conduct.











            Daniel is a new contributor. Be nice, and check out our Code of Conduct.














            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3164044%2ftold-by-professor-that-this-is-pie-but-dont-see-how-its-pie-help-understandi%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            រឿង រ៉ូមេអូ និង ហ្ស៊ុយលីយេ សង្ខេបរឿង តួអង្គ បញ្ជីណែនាំ

            Crop image to path created in TikZ? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Crop an inserted image?TikZ pictures does not appear in posterImage behind and beyond crop marks?Tikz picture as large as possible on A4 PageTransparency vs image compression dilemmaHow to crop background from image automatically?Image does not cropTikzexternal capturing crop marks when externalizing pgfplots?How to include image path that contains a dollar signCrop image with left size given

            Romeo and Juliet ContentsCharactersSynopsisSourcesDate and textThemes and motifsCriticism and interpretationLegacyScene by sceneSee alsoNotes and referencesSourcesExternal linksNavigation menu"Consumer Price Index (estimate) 1800–"10.2307/28710160037-3222287101610.1093/res/II.5.31910.2307/45967845967810.2307/2869925286992510.1525/jams.1982.35.3.03a00050"Dada Masilo: South African dancer who breaks the rules"10.1093/res/os-XV.57.1610.2307/28680942868094"Sweet Sorrow: Mann-Korman's Romeo and Juliet Closes Sept. 5 at MN's Ordway"the original10.2307/45957745957710.1017/CCOL0521570476.009"Ram Leela box office collections hit massive Rs 100 crore, pulverises prediction"Archived"Broadway Revival of Romeo and Juliet, Starring Orlando Bloom and Condola Rashad, Will Close Dec. 8"Archived10.1075/jhp.7.1.04hon"Wherefore art thou, Romeo? To make us laugh at Navy Pier"the original10.1093/gmo/9781561592630.article.O006772"Ram-leela Review Roundup: Critics Hail Film as Best Adaptation of Romeo and Juliet"Archived10.2307/31946310047-77293194631"Romeo and Juliet get Twitter treatment""Juliet's Nurse by Lois Leveen""Romeo and Juliet: Orlando Bloom's Broadway Debut Released in Theaters for Valentine's Day"Archived"Romeo and Juliet Has No Balcony"10.1093/gmo/9781561592630.article.O00778110.2307/2867423286742310.1076/enst.82.2.115.959510.1080/00138380601042675"A plague o' both your houses: error in GCSE exam paper forces apology""Juliet of the Five O'Clock Shadow, and Other Wonders"10.2307/33912430027-4321339124310.2307/28487440038-7134284874410.2307/29123140149-661129123144728341M"Weekender Guide: Shakespeare on The Drive""balcony"UK public library membership"romeo"UK public library membership10.1017/CCOL9780521844291"Post-Zionist Critique on Israel and the Palestinians Part III: Popular Culture"10.2307/25379071533-86140377-919X2537907"Capulets and Montagues: UK exam board admit mixing names up in Romeo and Juliet paper"Istoria Novellamente Ritrovata di Due Nobili Amanti2027/mdp.390150822329610820-750X"GCSE exam error: Board accidentally rewrites Shakespeare"10.2307/29176390149-66112917639"Exam board apologises after error in English GCSE paper which confused characters in Shakespeare's Romeo and Juliet""From Mariotto and Ganozza to Romeo and Guilietta: Metamorphoses of a Renaissance Tale"10.2307/37323537323510.2307/2867455286745510.2307/28678912867891"10 Questions for Taylor Swift"10.2307/28680922868092"Haymarket Theatre""The Zeffirelli Way: Revealing Talk by Florentine Director""Michael Smuin: 1938-2007 / Prolific dance director had showy career"The Life and Art of Edwin BoothRomeo and JulietRomeo and JulietRomeo and JulietRomeo and JulietEasy Read Romeo and JulietRomeo and Julieteeecb12003684p(data)4099369-3n8211610759dbe00d-a9e2-41a3-b2c1-977dd692899302814385X313670221313670221