Let f be a function from A → B. | A | = 4 , | B | = 3The number of surjective functions by applying the principle of inclusion exclusion is given by: 3 4 − ( 3 1 ) 2 4 + ( 3 2 ) 1 4 .The rationale is that we begin with the set of all possible functions, and subtract off the functions with one element in the codomain that is not in the range, and add back the functions with two elements in the codomain not in the range.However, I don't understand why we are adding back ( 3 2 ) 1 4 .If ( 3 1 ) 2 4 already include functions with two elements from the codomain not in the range, then wouldn't it be done already, as that's all the non-surjective functions?

Question

Let   f be a function from   A  →  B.      |    A      |    =  4  ,      |    B      |    =  3The number of surjective functions by applying the principle of inclusion exclusion is given by:       3          4        −                    (                    3      1                      )                  2          4        +                    (                    3      2                      )                  1          4      .The rationale is that we begin with the set of all possible functions, and subtract off the functions with one element in the codomain that is not in the range, and add back the functions with two elements in the codomain not in the range.However, I don&#039;t understand why we are adding back                     (                    3      2                      )                  1          4      .If                     (                    3      1                      )                  2          4       already include functions with two elements from the codomain not in the range, then wouldn&#039;t it be done already, as that&#039;s all the non-surjective functions?

recajossikpfmq · Accepted Answer

Let the elements of   B be   a,   b, and   c. For a set   S  ⊆  B, let       f    S   be the number of functions whose range is a subset of   S. The formula that you&#039;re suggesting can be expressed like this:      f    B    −      f          {      a      ,      b      }        −      f          {      a      ,      c      }        −      f          {      b      ,      c      }        .To see the problem with this equation, consider the function that sends everything to   a. That function is not surjective so we want it to make zero contribution to our counting. It is counted by the terms       f    B    ,      f          {      a      ,      b      }      , and       f          {      a      ,      c      }      , so its total contribution to this formula is   1  −  1  −  1  +  0  =  −  1. We counted this function twice when we were getting rid of bad functions, so we need to add it back once to cancel out the negative contribution. The same holds for the function that sends everything to   b and the function that sends everything to   с. Hence, the formula we want looks like      f    B    −      f          {      a      ,      b      }        −      f          {      a      ,      c      }        −      f          {      b      ,      c      }        +      f          {      a      }        +      f          {      b      }        +      f          {      c      }        .This is counted by the first formula you give, which is why it&#039;s correct.

Let f be a function from A → B . <mrow class="MJX-TeXAtom-O

Answered question

Answer & Explanation

New Questions in High school probability