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

In summary, the conversation discusses finding the number of surjective functions from a given set to another set using a formula derived from a Venn diagram. The formula is then applied to consider the cardinality of sets of functions that do not include certain elements in the range. It is noted that there are more than 3n options for these sets and that there are other cases to consider. Finally, the concept of using sets to calculate the number of non-surjective functions is mentioned.
  • #1
squelch
Gold Member
57
1

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:
548px-Edwards-Venn-four.svg.png


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.
 
Physics news on Phys.org
  • #2
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.
 
  • #3
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?
 

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

What is a surjective function?

A surjective function is a type of mathematical function in which every element in the output range is mapped to by at least one element in the input domain. In other words, every possible output value has at least one corresponding input value.

What is the difference between surjective and injective functions?

A surjective function is a type of function where each output value has at least one corresponding input value. An injective function, on the other hand, is a type of function where each input value has at most one corresponding output value. In simpler terms, surjective functions are "onto" while injective functions are "one-to-one."

How do you count the number of surjective functions?

The number of surjective functions from a set with m elements to a set with n elements can be calculated using the formula n!/(n-m)!. This is because each element in the output set can be mapped to by any of the m elements in the input set, so there are n^m possible functions. However, not all of these functions will be surjective, so we must divide by the number of ways to choose m elements from n elements, which is given by the formula (n!/(n-m)!).

What is the importance of counting surjective functions?

Counting surjective functions is important in many areas of mathematics, such as combinatorics and graph theory. It allows us to determine the number of ways in which a set of elements can be mapped onto another set, which has various applications in fields such as computer science, economics, and physics.

Can a function be both surjective and injective?

Yes, a function can be both surjective and injective. This type of function is called a bijective function, which means that each input value has exactly one corresponding output value, and each output value has exactly one corresponding input value. Bijective functions are often referred to as "one-to-one and onto" functions.

Back
Top