calculating number of onto functions

**jmedsy** · December 17th 2009, 12:59 AM

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 $3^8=6561$ functions total.

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

3. There are $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:

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

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

**Plato** · December 17th 2009, 03:50 AM

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

So 5796 is correct.

**Also sprach Zarathustra** · December 17th 2009, 02:00 PM

Originally Posted by Plato

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

So 5796 is correct.

Can you please prove it?

**Plato** · December 17th 2009, 02:08 PM

Originally Posted by Also sprach Zarathustra

Can you please prove it?

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.

Thread: calculating number of onto functions

LinkBack

Thread Tools

Display

calculating number of onto functions

Similar Math Help Forum Discussions

[SOLVED] Calculating the number of moles

Calculating the closest number power of 2 to a given number

Calculating the number of possible outcomes

[SOLVED] Calculating number of possible combinations

Calculating the Number of Combinations?

Search Tags