[Math] Counting total and onto functions

Question

The question is :

How many total and onto functions there are from
$X = \{1,2,3,4,5,6,7,8\}$ to $Y = \{a,b,c,d\}$.

I'm pretty sure you need to use the Inclusion – Exclusion method here but not really sure how.

Thanks in advance !

Answer 1

A total function maps each element of $X$ to an element of $Y$. Since there are four elements in $Y$, there are four ways we can map each of the eight elements in $X$. Thus, there are $4^8$ total functions from $X$ to $Y$.

We do need to use the Inclusion-Exclusion Principle for the second question since we must exclude those functions that map to fewer than four elements of $Y$. There are $4^8$ functions from $X$ to $Y$. The number of functions that map to three elements of $Y$ is $$\binom{4}{3}3^8$$ since there are $\binom{4}{3}$ ways of selecting which of the three elements of $Y$ are in the range and three ways we can map each of the eight elements in $X$. By similar reasoning, there are $$\binom{4}{2}2^8$$ functions whose range is two of the four elements in $Y$ and $$\binom{4}{1}1^8$$ functions whose range is one of the four elements in $Y$. Thus, by the Inclusion-Exclusion Principle, the number of surjective (onto) functions from $X$ to $Y$ is $$4^8 - \binom{4}{3}3^8 + \binom{4}{2}2^8 - \binom{4}{1}1^8$$