Suppose there are two sets $A\ \&\ B$ between which to define a surjective map $f: A\to B$. Here let's say $A$ is $[n]\ \&\ B$ is $[k]$, where $[i]$ is $\{1,2,3,\ldots ,i\}$. I need to find the number of such $f$s. I know there are more than $1$ way of doing it.
However I've come up with a different way, which of course is not giving the usual answer. Nevertheless I'm unable to find the flaw in it.
By definition of surjection we know that, for any map $f:A\to B$, in
order for it to be surjective (onto), there must be at least one element $\ x\in
A$ such that $f(x) = y,\ \forall y\in B$.Since all those $k$ elements in $B$ must have at least one pre-image
in $A$, we can choose a subset $S_k$ of $k$ elements from $A$ each
element of which maps to exactly one element in $B$. This subset
selection can be done in $n\choose k$ different ways. And for each of
these subsets $S_k$ we have $k!$ bijections from $S_k\to B$. That is for
each such $S_k\subseteq A$ we can make $k!$ maps such that each $y\in B$ has exactly one pre-image in $S_k\ \&$ in $A$ as well. Something of this sort:Now lets consider the rest of the $n-k$ elements in $A$, each of which can
map to any one of the $k$ elements in $B$. In total $k^{n-k}$
distributions are possible for these rest $n-k$ elements.So, for each choice of $S_k$ we've $(k!\times k^{n-k})$ distributions,
for which the mapping $\ f$ is onto. So, in total there are ${n\choose k}\ k!\ k^{n-k}$ surjections from $A\to B$.
Clearly this is not the correct result. Can anyone help me find out where I'm making the mistake (i.e over-counting/under-counting).
Best Answer
It seems like you're overcounting a lot. Just think of $n=2, k=1$ for instance. There is just one function, while your formula produces two surjective functions. Why is this?
You're counting the one function you have twice: you start by picking any $1$-element subset of $[2]$ and send it to $[1]$ to ensure surjectivity and then you send the other element of $[2]$ to any element. Both choices from $[2]$ to ensure surjectivity however yield the same result.
More generally, the problem is that if you have a map $[n]\to[k]$ that is surjective, it may very well have several $k$-element subsets that ensure surjectivity yet. With your method, you're counting these as if they're different surjective functions, where they aren't.
In case it's not entirely clear yet, just think how often you count the following $f:[n]\to[k]$, given by $$i\mapsto \left\{\begin{array}{rl}i&\text{if }i<k,\\ k& \text{otherwise.}\end{array}\right.$$ First you count it by the choice of subset $\{1,\ldots,k\}\subset[n]$, but then it occurs again when choosing $\{1,\ldots,k-1,k+1\}$, up to $\{1,\ldots,k-1,n\}$.