4
$\begingroup$

Maps $g$ maps $\left\{1,2,3,4,5\right\}$ onto $\left\{11,12,13,14\right\}$ and $g(1)\neq g(2)$. How many g are there.

My answer: I transformed the question to a easy-understand way and find out the solution. Consider there are five children and four seats. Two of them are willing sitting together but only two of them never seat together.

$\left(\begin{pmatrix} 5 \\ 2 \end{pmatrix}-1\right)*4!=456$

However the answer is 216. I don't know what's wrong.

Could you please help me find out what's wrong or give a right way to solve the problem?

Thanks!

2 Answers 2

5

Suppose that $g$ is a function from $\{1,2,3,4,5\}$ onto $\{11,12,13,14\}$. Then exactly one of the numbers in the set $\{11,12,13,14\}$ is $g(k)$ for two different values of $k$. In terms of the children and the seats, exactly one seat has to contain two children. There are $4$ ways to choose this seat. There are $\binom52-1=9$ ways to choose which pair of children will occupy the seat. The remaining $3$ children must each take one of the other $3$ seats, and they can do this in $3!$ ways. The final result is therefore $4\cdot\left(\binom52-1\right)\cdot3!=4\cdot9\cdot6=216\;.$

In other words, the only thing wrong with your answer is the arithmetic:

$\left(\binom52-1\right)\cdot4!=216\;,$

not $456$.

(I like your translation into a problem about children and seats.)

  • 0
    Nice solution Brian M. Scott..2013-11-15
4

EDIT: Oh, ”onto” means it's surjective. In that case Brian M. Scott has the right answer, tough you can still solve it my way.

Old answser: Here's a tip for how I would solve it: How many functions are there from the first set to the second without restrictions? How many are there for $g(1)=g(2)$?

  • 0
    @PENGTENG Right you are, I am not used to that terminology. :)2012-10-29