How many surjective functions are there from 1 , 2 , 3 , 4 , 5} to 1 , 2 , 3

Question

How many surjective functions are there from   1  ,  2  ,  3  ,  4  ,  5} to   1  ,  2  ,  3

Shyanne Meyers · Accepted Answer

First one is with your current approach and using inclusion-exclusion, so you need to count the number of functions that miss at least 1 element, lets call it

1, 2, 3, 4, 5

which is equal to

(\binom{3}{1}) 2^{5} = 96

. However, notice that this expression overcounts in the case of missing 2 elements. Everytime we count missing 1 and 3 for example, we also count missing 3 and 1 which are the same function. The number of functions that miss 2 elements, call it

S_{2}

is

(\binom{3}{2}) 1^{5} = 3

. Now, the total number of surjective functions is

3^{5} - 96 + 3 = 150

The reason I showed you these two ways, is that you can use them to prove the "explicit" formula for the stirling numbers of the second kind, which is

k! S (n, k) = \sum_{j = 0}^{k} (- 1)^{k - j} (\binom{k}{j}) j^{n}

How many surjective functions are there from A={1,2,3,4,5} to B={1,2,3}?

Answered question

Answer & Explanation

New Questions in Algebra I