How many surjective functions are there from {1,2,...,n} to {a,b,c,d}?

[squelch]

Homework Statement

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:

Homework Equations

None provided.

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}}
3\\
1
\end{array}} \right) = 3n[/itex].

Consider that 3n value to be |A|,|B|,|C|, and |D| and then apply the fomulae above.

 

[mfb]

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.

 

[andrewkirk]

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?