Let $f:A\to B$ be an onto function where $A=\{1,2,3,4\}, B=\{x,y,z\}$. Also, $f(1)=x$. Find the total number of such functions.
My Attempt:
I listed all the cases separately and got only $12$ unique cases.
But with the following approach, I am getting $18$ cases.
If three input values are going to $x,y,z$ then the fourth value will go to either of $x,y,z$. i.e. for fourth value, we have $3$ mapping choices.
Also, this fourth input value can be either of $2,3,4$. So, $3$ choices.
Also, first input value is going to $x$. It's fixed. Fourth value I have discussed above. The remaining two input values have $2$ mapping choices.
So, $3*3*2=18$.
What's wrong here?
Edit:
Reattempting my second attempt here.
$f(1)=x$.
Let $f(2)=y$, $f(3)=z$
To map $f(4)$, I have $3$ choices.
Also, it output of $f(2)$ and $f(3)$ can also be permuted in $2!$ ways.
Also, when I chose $f(4)$, I could as well have chosen $f(2)$ or $f(3)$. So, $3$ choices.
So, $3*2*3=18$.
I must be counting something extra.
What's the proper way to count here without listing all the cases?
Best Answer
There are only $12$ such functions, as you found manually.
In your second approach, you are counting each map in which $y$ or $z$ is the image of two elements of the domain twice, once for each way you could designate one of the elements that maps to the element that is the image of two elements as the preimage of that element. For instance, you count the map $f(1) = x, f(2) = y, f(3) = y, f(4) = z$ twice, once when you designate $2$ as the preimage of $y$ with $3$ as the additional element that maps to $y$ and once when you designate $3$ as the preimage of $y$ with $2$ as the additional element that maps to $y$.
Method 1: I gather that the motivation behind your approach is that any surjective function $f: A \to B$ has the property that one value in the codomain is the image of exactly two values in the domain while each of the other values in the codomain is the image of one value in the domain.
Suppose that $x$ is the image of two values in the domain. Since $f(1) = x$, there are three choices for the other element in the domain that maps to $x$. That leaves two elements that could map to $y$ and one that maps to $z$. Hence, there are $3 \cdot 2 \cdot 1 = 6$ such functions.
Suppose that $x$ is the image of only one value in the domain, namely $1$. Then either $y$ or $z$ is the image of two values in the domain and the other element is the image of one value in the domain. Choose whether $y$ or $z$ is the image of two elements in the domain and choose which two of the three elements $2, 3, 4$ in the domain map to that element. The other element in the domain must map to the remaining element in the codomain. Hence, there are $\binom{2}{1}\binom{3}{2} = 6$ such functions.
In total, there are $12$ surjective functions $f: A \to B$ that have the property that $f(1) = x$.
Method 2: You can also solve this problem by using the Inclusion-Exclusion Principle.
If there were no restrictions other than $f(1) = x$, there would be three choices in the codomain for each of the elements in the subset $\{2, 3, 4\}$ of the domain. Hence, there would be $3^3$ functions $f: A \to B$ such that $f(1) = x$.
From these, we must subtract those functions that have the property that $y$ or $z$ is not in the range, as $x$ is guaranteed to be in the range.
There are two ways to select one element that is not in the range. There are $2^3$ ways to map the elements in the subset $\{2, 3, 4\}$ to the remaining elements of the codomain.
However, if we subtract this amount from the total, we will have subtracted the map that misses both $y$ and $z$ twice, once when we excluded functions that miss $y$ and once when we excluded functions that miss $z$. We only want to subtract this function once, so we must add the number of functions that map all elements to $x$ to the total. There is one such function.
Hence, the number of surjective functions $f: A \to B$ with the property that $f(1) = x$ is $$3^3 - \binom{2}{1}2^3 + \binom{2}{2}1^3 = 12$$ as we found above.