Let $A=\{1,2,3,4,5,6\}$ and $B=\{a,b,c,d,e\}$. How many functions $f: A$ to $B$ are there such that for every $x$ belonging to $A$, there exists one and only one $y$ in $A$ such that $x$ is not equal to $y$ and $f(x)=f(y)$?

What I understood is that we need to find all possible groups of 2 elements from $A$ such that they map out to the same element in $B$. I figured out that there'd be 15 such groups. Each group of 2 can be mapped into 5 such elements in $B$. This would give us 15*5 ways such that only one group in $A$ maps into the same element in $B$.

However, since $A$ has 6 elements, a total of 3 groups can be formed. The above calculation pertained to such functions when only one group mapped onto the same element in $B$.

How do we consider cases, i.e. such functions wherein, say, 2 or even all 3 groups satisfy the proerty stated in the question.

Please correct me if I'm wrong and help me with this question. Thanks.

Edit: I seemed to have overlooked the fact that we need ALL the elements in $A$ to have at least one $y$ in $A$ as well such that property holds. Thus, the no. of ways for 1st group to have a an element in the Range is 75. The no. of ways for the second group to have a similar image in Range is 6*4=24 and the no. of ways for the third group to have a similar image in Range is 1*3.

The total no. of ways would be 5400 (since we need the three groups to simultaneously validate the property stated in the question). I am not sure if this is correct.

Please try to elaborate the answer if possible. Thanks.

  • 1
    $\begingroup$ I get $\binom53\binom62\binom42\binom22=900$. $\endgroup$ – bof Jan 1 '19 at 8:03

For a function to satisfy the condition, it has to split A into three groups of two, which each group mapping to a unique value of B. So the first step is finding how many ways we can split A into three groups of two elements. Note that to make the groups we can simply rearrange A, and then take the first two, the next two, and the last two elements as our groups. This gives $6!$ ways, and then we divide out by $2^3$ because we double count the groups that just swap the pairs, and we divide out by $3!$ to account for the ways we can order the groups. So there are $\frac{6!}{2^3 3!} = 15$ ways to make these groups.

Now we need to map the three groups to a unique one of the five elements. So we have 5 choices for group 1, 4 for group 2, and 3 for group 3, giving 60 overall ways to do this.

Thus there are $15*60 = 900$ possible functions.

  • $\begingroup$ Understood. Thank you! $\endgroup$ – S.Rana Jan 1 '19 at 10:45
  • $\begingroup$ @ShinjiniRana Alternatively, you could first choose three elements from $B$ in $\binom52=10$ ways, then pick two elements of $A$ for one of them in $\binom62=15$ ways, then pick two elements of $A$ for the next one in $\binom42=6$ ways, then two elements of $A$ for the last one in $\binom22=1$ way, so the answer is $10\cdot15\cdot6\cdot1=900$. $\endgroup$ – bof Jan 1 '19 at 11:42

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.