I've come across an exercise like this in my discrete maths textbook (Grimaldi), and I'm thoroughly stumped.
Suppose $A = \left\{1, 2,...,n\right\}$ and $B = \left\{1, 2,...,m\right\}$ where $n \gt m$.
How do you count the number of functions $f: A \rightarrow B$ satisfying $|f(A)| = x$ for some fixed non-negative integer $x \lt m$.
My confusion stems from $|f(A)| = x$. What exactly is the cardinality of a function applied to a set? For that matter, what would $|f(1)|$ be?
Hint: Let's consider the case where $x=m=5$. Once you understand this case, the rest will (hopefully) follow.
There are $5^m$ functions $f:A\rightarrow B$, but not all of these are surjective, so we have over-counted.
Each non-surjective function is missing at least one element of $B$. Let $B_1\subseteq B$ such that $|B_1|=4$. There are $4^n$ functions to $B_1$. Since there are $5$ elements of $B$ that could be removed, so this accounts for $5\cdot 4^n$ functions. However, we've over-counted again because functions which are not surjections onto $B_1$ are also counted twice.
Let $B_2$ be a subset of $B$ of cardinality $3$. We must add these functions back. Since there are $\begin{pmatrix}5\\2\end{pmatrix}$ such subsets, we must add back $\begin{pmatrix}5\\2\end{pmatrix}3^n$ functions. This is adding back too many functions again!
For subsets of cardinality $2$, there are $\begin{pmatrix}5\\3\end{pmatrix}2^n$ functions to sets of cardinality $2$. This is subtracting too many functions.
We are left with the functions to sets of cardinality $1$, but these are just the constant functions, so there's only $5$ of these.
Summarizing, the number of functions is $$ 5^n-\begin{pmatrix}5\\4\end{pmatrix}4^n+\begin{pmatrix}5\\3\end{pmatrix}3^n-\begin{pmatrix}5\\2\end{pmatrix}2^n+\begin{pmatrix}5\\1\end{pmatrix} $$
Now, generalize, generalize, generalize!