0
$\begingroup$

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).

$\endgroup$
3
$\begingroup$

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\}$.

$\endgroup$
0
$\begingroup$

You can find the mistake yourself if you follow these instructions. First, find minimal values of $n,k$ for which your formula gives the wrong answer. I bet they will be very small indeed, so the next step won't be too arduous. Next, implement your argument explicitly for this $n$ and $k$: list all the $k$-element subsets of $A$, list all the bijections from each of those sets to $B$, etc. Make an explicit list of ${n\choose k}\ k!\ k^{n-k}$ surjections from $A$ to $B$. Find the repetitions in your list. Now think about how they got there.

O.K., let me help. Your formula says that there are $2$ bijections from $[2]$ to $[1]$. Of course there is only one, so your method is counting the same bijection twice. Now do you see what you did wrong?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.