1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Counting surjective functions

  1. Mar 8, 2016 #1


    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data

    Count the number of surjective functions from {1,2,...,n} to {a,b,c,d}. Use a formula derived from the following four-set venn diagram:

    2. Relevant equations

    None provided.

    3. The attempt at a solution

    First, I divided the Venn diagram into sets A,B,C,D and tried to express [itex]|A \cup B \cup C \cup D|[/itex] as: [tex]|A|+|B|+|C|+|D|-|A \cap B|-|A \cap C| - |A \cap D| - |B \cap C| - |B \cap D| - |C \cap D| + |A \cap B \cap C| + |A \cap B \cap D| +|B \cap C \cap D| + |A \cap C \cap D| - |A \cap B \cap C \cap D| = |A \cup B \cup C \cup D|[/tex]

    Then I consider the carnality of each set of functions that "misses" a particular value on the set {a,b,c,d}. This is four sets. It seems that the cardinality of each of these sets is picking one item from among three within {a,b,c,d} (to exclude one element from the range), and to perform this choice "n" times: n * C(3,1) or
    [itex]n \cdot \left( {\begin{array}{*{20}{c}}
    \end{array}} \right) = 3n[/itex].

    Consider that 3n value to be |A|,|B|,|C|, and |D| and then apply the fomulae above.
  2. jcsd
  3. Mar 8, 2016 #2


    User Avatar
    2017 Award

    Staff: Mentor

    If you have n independent choices of 3 options each, you have more than 3n options.

    Also, 3 options is not the only case you have to consider.
  4. Mar 8, 2016 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The calculation they seem to be trying to get you to do is a count of the non-surjective functions. Having found that count, we'd need to then deduct it from the count of all functions (a trivial calc) to get the number of surjective functions.

    If we define
    A as the set of functions that do not have ##a## in the range
    B as the set of functions that do not have ##b## in the range, etc

    then the formula will give you a count of the set of all non-surjective functions.

    A, B, C and D all have the same cardinality, but it is not ##3n##. How many ways are there of picking n elements, with replacement, from a set of 3 elements?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted