4
$\begingroup$

This is a practice i was doing preparing for my quiz and i thought the answer would be 18 but the answer key states 1x4x3x2x1 or 24. I tried to understand why it would be 24 but i don't get it? I began by choosing a value for f(1) and i know because it is onto then 1 cannot be 1 or 2 because if f(1) =1 then f(f(1) cannot be 2 and similarily if f(1)=2 then f(f(1))=f(2)=2 and since it is a finite set in order for it to be onto it must also be one to one thus if f(1)=2 then two elements of the domain point to 2 which would be fine if for instance there were 6 elements in the domain. Is my logic flawed or am i missing something please let me know. Continuing to the other numbers i just would remove an options so f(2) cannot be 2 for the same reason above or the number picked for f(1), so 3 options there , and then down to 2 then 1 and 1. If anyone could explain this please, the answer key did not explain and it seems simple enough don't know why i'm stuck.

$\endgroup$
2
4
$\begingroup$

Counting in a completely different way...

It's a permutation. $1$ and $2$ must belong to the same cycle, and that cycle has length at least $3$ (or $f(f(1))$ would be $1$ instead of $2$).
If that's a $3$-cycle, it goes $(1,x,2)$ for some $x$. There are three ways to choose that $x$, and then two ways to choose how the two remaining elements are permuted, for $6$ options in this case.
If that's a $4$-cycle, it goes $(1,x,2,y)$ for some $x,y$. There are $3$ ways to choose $x$, $2$ ways to choose $y$, and the lone element outside the cycle goes to itself. $6$ options here.
If that's a $5$-cycle, it goes $(1,x,2,y,z)$. Three choices for $x$, two for $y$, one for $z$. $6$ options here.

Your answer of $18$ is confirmed. The answer key is wrong.

$\endgroup$

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.