How many functions $f^m(n) = n$ over $\mathbb{N}$?

Question

I got a task that i have problem with. I have to find how many functions are there that satisfies $$f^m(n) = n$$ for some $m > 0$. So, i came up with an idea. How many functions there are for $m=2$? So, we can make function that is bijection and contains only cycles of size 2. This is, first function will be $f(1) = 2, f(2) = 1$ next $f(3) = 4, f(4) = 3$ and so on... Next function will be $f(1) = 3, f(3) = 1$ and $f(2) = 4, f(4) = 2$ and so on... So function will be of form $$f(x) = x + i, f(x + i) = x$$ for every $i=1,2,3\dots$ and this will give us $\aleph_0$ functions. For functions $f^3(n) = n$ should be bijections and contains only cycles of size 3. etc etc... so i think, processing it for every $n$ we will end up with $\aleph_0^{\aleph_0}$ functions, but i'm not sure of this. Is it equal to continuum? I will really appreciate some help with this. :-) Thanks in advance!

Answer 1

More generally a function $f:\mathbb{N}\to \mathbb{N}$ satisfying $f^m(n)=n$ amounts to a permutation consisting of disjoint cycles of lengths dividing $m$.

These disjoint cycles (including singletons, if any) partition all of $\mathbb{N}$.

There are a continuum number of these if $m \gt 1$ (only one if $m=1$, as janmarqz pointed out in a Comment).

To show this we construct $f$ through a countable sequence of steps, with a countable number of choices at each step. Choose the orbit of the least element not yet used, starting with 1. The orbit is a subset of size $r$ dividing $m$, so there are a countable number of ways to pick the orbit (including placing that least unused element in a singleton orbit). Make a choice of the order of the orbit, so that it becomes a disjoint cycle in $(r-1)!$ ways.

The cumulative number of possibilities is $\aleph_0^{\aleph_0}$, so the cardinality is exactly the continuum, $2^{\aleph_0}$.

Answer 2

No, if there are no more solutions that the ones you mention (and I don't believe it to be the case) then you would have a countable union of countable sets, which is still countable.

But there are a lot more solutions to $f^2(n)=n$ than the ones you mention. Indeed, any such solution can be thought of as a partition of $\mathbb{N}$ into sets of cardinality 2, with $f$ sending each element of those set to the other or to itself (with that choice to be made for every pair). It is not hard to see that there are uncountably many such functions. In fact, for any such partition, you have to make one choice, so you already have $2^{\aleph_0}$ solutions for one partition.