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.
Let A = {1, 2, 3, 4, 5} How many onto functions f : A → A are there so that f ◦ f (1) = 2? Explain
combinatoricsdiscrete mathematicsfunctions
Best Answer
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.