# Two-to-one functions

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.

-
Hello, user65422! I noticed you've asked a handful of questions and received a few answers, but haven't accepted any. We encourage users to accept an answer when they find it helpful (you can accept only one answer per question by clicking on the $\checkmark$ to the left of the answer you'd like to accept). You can also upvote answers, and can upvote as many as you'd like. –  amWhy Apr 10 '13 at 20:22

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.
I suggest you to write out a set $A$ of $2n$ elements, a set $B$ of $n$ elements, and try to count the maps yourself first. Then you can prove this via induction very quickly. Induction is certainly not the best way to solve this problem, but I think it helps a learner at your level in this case. Then you can try to think it through and see what better ways are available before posting on this site.