Counting the number of functions restricted by cardinality Let $n\geq4$ be a positive integer and let $S=\{1,2,\ldots,n\}$. Find the number of functions $f:S\to S$ whose image has cardinality at most $n-3$.

I'm trying to do this using inclusion-exclusion. Immediately we know that the total # of functions is $n^n$. So then I want to subtract off the number of functions whose image has cardinality $n,n-1$, and $n-2$. The # of functions whose image has cardinality $n$ is akin to counting bijections based on the domain and codomain, so it's $n!$. The # of functions whose image has cardinality $n-1$ is a bit more complicated. I have $n$ choices for which element does not get hit in the codomain, and since functions are everywhere defined I have $n$ choices for which 1 element in my domain is "doubling up" via that particular map. So for this "block" I think it's $n^2$. Finally for the $n-2$ case, I have $\binom{n}{2}$ options for which 2 elements are missed, and I think I have again $\binom{n}{2}$ options for which elements get paired up.... So the answer is $n^n-n!-n^2-\binom{n}{2}^2$?

I'm betting what's wrong is I'm not imposing enough structure on what the maps do. I need to ensure, and only count the functions that surject onto $n-1$ and $n-2$. I'm stuck. If I'm correct about what I'm missing, then the answer will use Stirling numbers. So I think the answer is $n^n−n!−S(n,n−1)∗(n−1)!−S(n,n−2)∗(n−2)!$.
 A: *

*Number of functions whose image has cardinality $n-1$: there are $n$ ways to choose the number that is not in the image, and $n-1$ ways to choose which number is "mapped to twice" in the image. Finally there are $n!/2$ ways to assign these image elements as the targets of each domain element. So we have $n(n-1) n!/2$.

*Number of functions whose image has cardinality $n-2$: there are $\binom{n}{2}$ ways to choose the two numbers not in the image. Then one of two things can happen.


*

*Two of the $n-2$ remaining numbers are "mapped to twice": there are $\binom{n-2}{2}$ ways to choose these two numbers. Finally there are $n!/4$ ways to assign these image elements as the targets of each domain element. So we have $\binom{n}{2} \binom{n-2}{2} n!/4$.

*One of the $n-2$ remaining numbers is "mapped to three times": there are $n-2$ ways to choose this number. Then there are $n!/6$ ways to assign these image elements as the targets of each domain element. So we have $\binom{n}{2}(n-2) n!/6$.


A: Quite interestingly, the solution that angryavian provided matches (numerically, for small $n$'s tested) my answer with a slight tweak:
I failed to account for the number of options for which elements to disregard when looking at the Stirling numbers of the second kind. So, using Stirling numbers, the answer should be
$$n^n-n!-n!S(n,n-1)-\binom{n}{2}S(n,n-2)(n-2)!$$
