# Thread: calculating number of onto functions

1. ## calculating number of onto functions

Please confirm I'm doing this correctly:

How many onto functions are there from a set with eight elements to a set with 3 elements?

Steps

1. There are $\displaystyle 3^8=6561$ functions total.

2. There are 3 functions with 1 element in range.

3. There are $\displaystyle 2^8-2$ functions with 2 elements in the range for each pair of elements in the codomain.

4. There are "3 choose 2"=3 ways to choose 2 elements from a set of 3.

5. Considering steps 1. through 4., the number of onto functions is:

$\displaystyle 3^8-(3*(2^8-2)+3)=5796$ onto functions

I'm almost positive this is correct. Could somebody please confirm?

2. The number of surjections (onto functions) from a set of N elements to a set of M is given by:
$\displaystyle Surj(N,M) = \sum\limits_{k = 0}^M {\left( { - 1} \right)^k \binom{M}{k}\left( {M - k} \right)^N }$ of course $\displaystyle N\ge M$.

So 5796 is correct.

3. Originally Posted by Plato
The number of surjections (onto functions) from a set of N elements to a set of M is given by:
$\displaystyle Surj(N,M) = \sum\limits_{k = 0}^M {\left( { - 1} \right)^k \binom{M}{k}\left( {M - k} \right)^N }$ of course $\displaystyle N\ge M$.

So 5796 is correct.

4. Originally Posted by Also sprach Zarathustra
The proof is simply repeated use of the inclusion/exclusion principle.
Count the number of functions which fail to have certain terms in the range: taken one at a time; taken two at a time; taken three at a time; etc.

,

,

,

,

,

,

,

,

,

,

,

,

,

,

# all formulas to calculate number of onto funtions

Click on a term to search for related topics.