This is a generalized version of the IMO problem:
Prove that the function $f \colon \mathbb{N} \to \mathbb{N}$ such that $f(f(x)) = x+k$ is nonexistent if $k$ is odd.
Now here is my problem:
For natural numbers $a,b$, let $$\mathcal{F} = \{f \colon \mathbb{N} \to \mathbb{N}\mid \forall x \in \mathbb{N},\: f^a(x) = x+b \}$$ (a) Find a neccesary and sufficient for $\mathcal{F} \neq \varnothing$.
(b) Find $|\mathcal{F}|$. (in terms of $a$ and $b$)
I was able to give proof for (a), by mimicking the solution of the above IMO problem. I think that $\mathcal{F}$ is nonempty iff $a\mid b$.
Let $S_i = f^{i}(\mathbb{N}) \setminus f^{i+1}(\mathbb{N})$, where $S_0 = \mathbb{N} \setminus f(\mathbb{N})$.
Proposition 1. $f^{j}(\mathbb{N}) \subseteq f^{i}(\mathbb{N})$ if $i \leq j$.
Proof. Since $f^{j}(\mathbb{N}) = f^{i}(f^{j-i}(\mathbb{N}))$ and $f^{j-i}(\mathbb{N}) \subseteq \mathbb{N}$, it is pretty clear.
Proposition 2. $S_i \cap S_j = \varnothing$ if $i \neq j$.
Proof. WLOG $i<j$. Since $S_{i} = f^{i}(\mathbb{N}) \setminus f^{i+1}(\mathbb{N})$, so $S_i$ does not contain the elements of $f^{i+1}(\mathbb{N})$. However, $S_j = f^{j}(\mathbb{N})\setminus f^{j+1}(\mathbb{N})$, so $S_j$ is a subset of $f^{j}(\mathbb{N})$, and thus a subset of $f^{i+1}(\mathbb{N})$, by proposition 1. So they are disjoint.
Proposition 3. $|S_i| = |S_j|$ for all $i,j$.
Proof. It suffices to show that $|S_i| = |S_{i+1}|$. I claim that $f$ is actually a bijection between them. (upon restriction of domain to $S_i$) We know that $f$ is an injection since $f^a$ is an injection. So surjectivity is a problem. Let $x \in f^{i+1}(\mathbb{N}) \setminus f^{i+2}(\mathbb{N})$, then there exists $y \in f^{i}(\mathbb{N})$ such that $f(y) = x$, by definition. But if $y \in f^{i+1}(\mathbb{N})$, then $f(y) = x \in f^{i+2}(\mathbb{N})$, contradiction. Therefore $y \in f^{i}(\mathbb{N}) \setminus f^{i+1}(\mathbb{N}) = S_i$, proving surjectivity. Let's say $|S_i| = n$ for all $i$.
Proposition 4. $\mathcal{F}$ is nonempty iff $a|b$.
Proof. If part is obvious(give $f(x) = x + b/a$). So let's go for only if part. Consider the set $$ \bigcup_{i = 0}^{a-1} S_i = [\mathbb{N} \setminus f(\mathbb{N})] \cup \cdots \cup [f^{a-1}(\mathbb{N}) \setminus f^{a}(\mathbb{N})] = \mathbb{N} \setminus f^{a}(\mathbb{N})$$ And note that $\mathbb{N} \setminus f^{a}(\mathbb{N}) = \{1,2,\cdots, b\}$ by the condition of problem. However since $S_i$'s are all disjoint, so $\left| \bigcup_{i = 0}^{a-1} S_i \right| = an = b $. Thus $\mathcal{F} = \varnothing $ if $a \nmid b$, completing the proof.
However, I have no idea about (b). Hint for this problem suggests finding a bijection from $\mathcal{F}$ to some easy set, such as a subset of $S_b$ (symmetric group). But what is the set? How can I evaluate the size of $|\mathcal{F}|$?
Thank you for any help, hint, or solution.
