Abstract Algebra: counting onto functions

[hyperslime]

Given two sets, S and T, let S have 6 elements and T have 5 elements. How many onto functions are there from S to T? Explain.

 

[stapel]

I would think it would be ₆P₅.

Eliz.

__________________
Edit: ...but I can be wrong. Try the links below for further info regarding the following post.

explanation of number of surjections (PDF file)
Finite Calculus: A Tutorial for Solving Nasty Sums (PDF file)

 

[pka]

Given two sets, S and T, let S have 6 elements and T have 5 elements. How many onto functions are there from S to T? Explain.

This is not a trivial or elementary question.
On to functions are known as surjections.
The number of surjections from a set of N elements to a set of K elements, N≥K, is given by
\(\displaystyle \L
Surj(N,K) = \sum\limits_{j = 0}^K {\left( { - 1} \right)^j \left( \begin{array}{l}
K \\
j \\
\end{array} \right)} \left( {K - j} \right)^N\).

Thus, Surj(6,5)=1800. As for you request for an explanation, that is quite difficult.
That formula is derived by repeated applications of the inclusion/exclusion rule for counting. Remember that there are a total of 5<SUP>6</SUP>=15,625 functions from a set of 6 to a set of 5 and just 1800 of those are onto.