How many number of functions are there?

73 Views Asked by At

$A=\{1,2,\dots,10\}$

Define $f:A \rightarrow A$

then $f^{30}(x) = x$ ($30$ times composite of $f(x) = x$ and the number $30$ is the least number for $f$ to become an identity function)

How many $f:A \rightarrow A$ are there ?

P.S : I don't know what category is right.

1

There are 1 best solutions below

8
On

As coffeemath has remarked in a comment, the function must be a bijection and thus a permutation in the symmetric group $S_{10}$. We can decompose it into cycles, and its order $30$ is the least common multiple of its cycle lengths. Thus its cycle lengths are among the divisors of $30$ not greater than $10$: $1$, $2$, $3$, $5$, $6$ and $10$. If there's a cycle of length $10$, there are no other cycles, and then the least common multiple isn't $30$, so we can exclude that case. Then there must be a cycle of length $5$ to get the factor $5$ in $30$, and that doesn't leave any space for a cycle of length $6$. Then we need a cycle of length $3$ and one of length $2$ to get the remaining factors in $30$.

So there must be one $5$-cycle, one $3$-cycle and one $2$-cycle. There are $\binom{10}{5,3,2}$ ways to select elements for them, and $4!\cdot2!$ ways to order them, for a total of $\binom{10}{5,3,2}\cdot4!\cdot2!=2520\cdot24\cdot2=120960$ permutations.