Number of possible functions satisfying the given conditions

Question

I Have to find the number of functions $f(x)$ from {1,2,3,4,5} to {1,2,3,4,5} that satisfy $ f(f(x)) = f(f(f(x)))$ for all $x$ in {1,2,3,4,5}.

However I am unable to understand from where to start. The number of cases I am trying to analyze is too much. I tried classifying it into functions which are onto, which are not unto wherein only 1 image appears twice and so on but I am realising that the list is becoming too huge. Can anyone help me with a simpler analysis of this question.

Answer 1

Hint: If $x=f^2(c)$ for some $c$, then you have $f(x) = x$. This means that every $x \in \text{Im}(f^2)$ is a fixed point of $f$. Do you think you can conclude?

---

We can build $f$ as follows.

$\quad\mathbf{(1)}$: $f$ must contain exactly $k$ fixed points in $\{1,2,\dots,5\}$ for some $k$ with $1\leqslant k\leqslant 5$.

$\quad\quad\mathbf{(1.1)}$: If $k=5$, then there is only one possibility: $f$ is the identity.

$\quad \mathbf{(2)}$: For $k<5$, consider the set $S$ of points that are not fixed and that are mapped to one of the $k$ fixed points. It is not empty, for otherwise we could iterate some non-fixed $x$ under $f$ and find a contradiction with $f^2 = f^3$. Let $j=|S|$, so that $1\leqslant j\leqslant 5-k$.

$\quad \mathbf{(3)}$: The remaining points, if any, must map to one of the $j$ points in $S$. Indeed, let $x$ be one such point, and consider $f(x)$. We have that $f(f(x)) = f^2(x)$ is a fixed point of $f$ $($because $f^2 = f^3)$, so either $f(x)\in S$ or $f(x)$ is itself a fixed point. The latter would in turn imply either $x\in S$ or else $x$ is itself a fixed point, but we've excluded these possiblities (the 'remaining' points).

We hence have

$$1 + \sum_{k=1}^4\left(\binom{5}{k}\cdot\sum_{j=1}^{5-k}\,\binom{5-k}{j}k^jj^{5-k-j}\right) = 756$$

possibilities. Let's explain the formula.

• The lone $1$ before the summation over $k$ is the identity $\mathbf{(1.1)}$.
• $\binom{5}{k}$ is the number of ways to choose $k$ of the points in $\{1,2,\dots,5\}$ to be fixed.
• $\binom{5-k}{j}$ is the number of ways to choose $j$ of the remaining $5-k$ points to be the points in $\mathbf{(2)}$, which map to fixed points.
• $k^j$ is the number of ways to choose, for each of the $j$ points above, to which of the $k$ fixed points it is mapped.
• $j^{5-k-j}$ is the number of ways to choose, for each of the remaining $5-k-j$ points, to which of the $j$ points in $\mathbf{(2)}$ it is mapped.

Notice that cancellations lead to the formula in Somos's answer, so here's a combinatorial interpretation for it.

---

It is easy to generalize this procedure for other values of $m$ with $f^m = f^{m+1}$, and this is basically a tiered approach. For some $x\in\text{Dom}(f)$, let $\text{ord}(x)$ be the smallest non-negative integer $n$ with $f^n(x) = f^{n+1}(x)$, where $f^0(x) = x$. Then it's easy to check that:

• $\text{ord}(x) = 0 \iff f(x) = x$
• $0 < \text{ord}(x) < \infty \implies \text{ord}(f(x)) = \text{ord}(x) - 1$
• $\text{ord} \leqslant m$

In this way, we can build $f$ from the ground up. Mimicking the bullet points above, we proceed as follows:

• We start with those $x$ with $\text{ord}(x) = 0$, ie, the fixed points.
• If we've defined $f$ on the set of points with $\text{ord} \leqslant k < m$, we may define $f$ on the set of points with $\text{ord} = k+1$ by mapping each of those points to some point with $\text{ord} = k$.
• This procedure must terminate, because $\text{ord} \leqslant m$.

Answer 2

The enumeration problem is solved by OEIS sequence A000949. The comment states "Equivalently, the number of mappings from a set of n elements into itself where f(f(x)) = f(f(f(x)))." The exponential generating function is $\, \exp(x \exp(x \exp(x))). \,$ A formula as a summation is $$\, a(n) = 1 + n! \sum_{m=1}^{n-1} \frac1{m!} \sum_{k=1}^{n-m} \frac{k^{n-m-k} m^k}{k! (n-m-k)!}. \,$$

Answer 3

This is a bad bad answer. No math at all. Just as a check on whatever solution you end up with, it seems the answer is 756.

Brute-force Python.

def funcs(N):
  "Construct a list of all N-tuples of elements of range(N):"
  res = [()]
  for j in range(N):
    res = [(a,) + f for a in range(N) for f in res]
  return res

def check(f,N):
  "Test whether f^2=f^3 for a given f"
  for j in range(N):
    if not(f[f[j]] == f[f[f[j]]]): return 0
  return 1

count =  0
for f in funcs(5):
  if check(f,5):
    count = count + 1

print count

Answer 4

Permit me to remark on the connection to Analytic Combinatorics. It is known that all endofunctions on $[n]$ are sets of cycles of labeled trees. This follows from the fact that when we iterate $f$ we obtain a path that terminates in a cycle and is documented in Random Mapping Statistics by P. Flajolet, where the asymptotics are then derived. The construction also appeared at this MSE link. The combinatorial class is then given by

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{F} = \textsc{SET}(\textsc{CYC}(\mathcal{T})) \quad\text{where}\quad \mathcal{T} = \mathcal{Z} \textsc{SET}(\mathcal{T}).$$

Now in the present case there can be no cycles of two or more elements because the values on those cycles would not fit the condition that $f(f(x)) = f(f(f(x))).$ This leaves sets of trees, with the root of the tree being a fixed point. Observe that any leaf with a path to the root including the root that contains more than three nodes also breaks the requirement that $f(f(x)) = f(f(f(x))).$ This restricts the class of trees to those where the path from every leaf to the root including the root contains at most three nodes. Now to characterize these trees they are first, a singleton node (fixed point) or second, a singleton node (also a fixed point) with a set of subtrees attached to it, which are in turn either leaves or have a set of leaves attached to them. With the combinatorial class $\mathcal{T}$ of these trees we thus obtain

$$\mathcal{T} = \mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1} (\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1}(\mathcal{Z})).$$

The desired combinatorial class $\mathcal{F}$ is a forest of these trees given by

$$\mathcal{F} = \textsc{SET}(\mathcal{T}) = \textsc{SET}(\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1} (\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1}(\mathcal{Z}))).$$

Observe that the distinction between nodes that have no subtrees attached to them and nodes with a set of subtrees as a feature which appears during the study of the problem givens is not essential here and we may use the convenient fact that

$$\mathcal{E} + \textsc{SET}_{\ge 1}(\mathcal{Q}) = \textsc{SET}(\mathcal{Q}).$$

We thus have for the class in question that it is

$$\mathcal{F} = \textsc{SET}(\mathcal{Z}\textsc{SET}(\mathcal{Z} \textsc{SET}(\mathcal{Z}))).$$

What is happening here is that for rooted trees of height at most $h$ we have $\mathcal{T}_{\le 0} = \mathcal{Z}$ and for $h\ge 1$

$$\mathcal{T}_{\le h} = \mathcal{Z} \textsc{SET}(\mathcal{T}_{\le h-1}).$$

We instantly obtain the EGF

$$F(z) = \exp(z\exp(z\exp(z))).$$

Extracting coeffficients here we find

$$n! [z^n] F(z) = n! [z^n] \sum_{q=0}^n \frac{1}{q!} z^q \exp(qz\exp(z)) \\ = n! \sum_{q=0}^n \frac{1}{q!} [z^{n-q}] \exp(qz\exp(z)) \\ = n! \sum_{q=0}^n \frac{1}{q!} [z^{n-q}] \sum_{p=0}^{n-q} \frac{1}{p!} q^p z^p \exp(pz) \\ = n! \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p [z^{n-q-p}] \exp(pz) \\ = n! \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p \frac{p^{n-q-p}}{(n-q-p)!}.$$

This is the formula that is presented at OEIS A000949. Apparently they chose to simplify by omitting the term for $q=0$ ($q^p=1$ only when $p=0$ but then $p^{n-q-p} = 0$) and extracting the term for $q=n$ (which simplifies to $1$) to get

$$1 + n! \sum_{q=1}^{n-1} \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p \frac{p^{n-q-p}}{(n-q-p)!}.$$