Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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