Let f be a function. We say that f is two-to-one provided for each $b \in\operatorname{im} f$ there are exactly two elements $a_1, a_2 \in\operatorname{dom} f$ s.t. $f(a_1) = f(a_2) = b$.
For a positive integer $n$, let $A$ be a $2n$-element set and $B$ be an $n$-element set. How many functions $f: A\to B$ are two-to-one?
I'm just starting to learn functions but I'm confused about two-to-one functions. I don't even know where to begin. I need a clear explanation. Thanks.
Best Answer
HINT: Since $|A|=2n$ and $|B|=n$, a two-to-one function $f$ from $A$ to $B$ must map $A$ onto $B$. In effect you’re just dividing $A$ into $n$ pairs of elements and then letting $f$ send each pair to a different element of $B$. For example, if $n=3$, $A=\{0,1,2,3,4,5\}$, and $B=\{0,1,2\}$, one possible two-to-one function $f$ is the one defined by
$$\left\{\begin{align*} &f(0)=f(1)=0\\ &f(2)=f(3)=1\\ &f(4)=f(5)=2\;. \end{align*}\right.$$
To count these function, let $B=\{b_1,\dots,b_n\}$. There are $\binom{2n}2$ ways to choose the two elements of $A$ that are to be sent to $b_1$. Once that’s been done, there are $2(n-1)$ elements of $A$ left, so there are $\binom{2(n-1)}2$ ways to choose a pair to be sent to $b_2$. Can you finish it from there? You should get a product of binomial coefficients, which you should write out as quotients of factorials: you’ll find that you can do a lot of canceling to simplify the result.