# Is there a Graph theory way to solve this iteration problem

This thought came when i was trying 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\}$$. What i did was took cases when only one , two...etc values of x such that all those are identity functions from that i got the answer as 756 which is correct. But i was thinking if there was some kind of GT use can be done here which can solve it more easily than case bash?

• You can make a directed graph, with an edge $x\to f(x)$ for each $x$. If you ignore any edges of the form $x\to x$, you can this graph is a rooted forest where every tree has depth at most $2$. I am not sure this makes it much easier to count, though Mar 15, 2021 at 13:49
• Can caseys theorem help here to get the required number of forests by removing the unwanted trees? Mar 15, 2021 at 14:06
• I am not sure. Cayley's formula implies the number of rooted forests is $6^4=1296$. You would then need to subtract out all rooted forests with a depth of three or more, of which there are apparently $540$. But counting those seems like just as much of a bash. Mar 15, 2021 at 14:41
• Hmm yeah seems like Sir Mar 15, 2021 at 16:59

I'll give a strategy that generalizes using generating functions. As Mike Earnest points out, we want to count rooted labelled forests of size $$5$$ with depth at most $$2$$. Let's find the EGF of such forests of size $$n$$.

A tree is a root with a set of trees attached. Let $$\mathcal T^{(2)}$$ be the class of trees of depth at most $$2$$, and let $$\mathcal Z$$ denote a node. Then using the symbolic method we have $$\mathcal T^{(2)} = \mathcal Z\star SET(\mathcal Z\star SET(\mathcal Z))$$ (Each use of $$SET$$ correspond to a possible layer). A forest is just a set of trees, so we get the following EGF $$\mathcal F^{(2)} = SET(\mathcal T^{(2)}) \implies F^{(2)}(z) = \exp(z\exp(z\exp(z)))$$ The number of these forests that have $$n$$ nodes is then given by $$F_n^{(2)} = n![z^n]F^{(2)}(z)$$, where $$[z^n]$$ means the coefficient at $$z^n$$ in the series expansion of the EGF. We find $$\begin{split} F^{(2)}(z) &= \exp(z\exp(z\exp(z))) \\ &= \sum_{m\ge0}\frac{z^me^{mze^z}}{m!}\\ &= \sum_{m\ge0}\frac{z^m}{m!} \sum_{k\ge0}\frac{m^kz^ke^{kz}}{k!}\\ &= \sum_{m\ge0}\frac{z^m}{m!} \sum_{k\ge0}\frac{m^kz^k}{k!} \sum_{j\ge0}\frac{k^jz^j}{j!}\\ &= \sum_{m,k,j\ge0}\frac{m^kk^j}{m!k!j!}z^{m+k+j}\\ &= \sum_{n\ge0} \left(\sum_{m=0}^n \sum_{k=0}^{n-m} \frac{m^kk^{n-m-k}}{m!k!(n-m-k)!}\right)z^n \end{split}$$ So our final answer is $$F_n^{(2)} = n! \sum_{m=0}^n \sum_{k=0}^{n-m} \frac{m^kk^{n-m-k}}{m!k!(n-m-k)!}$$ and we can verify that $$F_5^{(2)}$$ is indeed $$756$$ using this formula. You can find the sequence at A949 on OEIS. I don't know if we can do much more than this, other than cleaning up the edge cases and perhaps rewriting with a trinomial coefficient: $$F_n^{(2)} = 1 + \sum_{m=1}^{n-1} \sum_{k=1}^{n-m}\binom{n}{m,k,n-m-k} m^kk^{n-m-k}$$

The best I can give is a generating function solution, which gives a way to count such graphs automatically with a computer.

If you make a directed graph with an edge $$x\to f(x)$$ for each $$x\in \{1,\dots,5\}$$, and ignore any self loops $$x\to x$$, what remains is a rooted forest where each tree has depth at most $$2$$. If we let $$F_{h,n}$$ be the number of rooted forests on $$n$$ vertices with a depth of at most $$h$$, and $$F_h(x)=\sum_{n\ge 0}F_{h,n}x^n$$ be the exponential generating function, then $$F_h(x)=\exp(x F_{h-1}(x))$$ This is because a rooted forest is given by partitioning the underlying set ($$\exp$$), choosing a root for each set $$(x)$$, and then putting a rooted forest structure with depth $$h-1$$ on the remaining elements of each set $$F_{h-1}(x)$$. In your case, we get $$F_2(x)=\exp(xF_1(x))=\exp(x\exp(xF_0(x)))=\exp(x\exp (x\exp(x)))$$ Therefore, it follows that $$F_{2,n}=n![x^n]\exp(x\exp (x\exp(x)))$$ where $$[x^n]f(x)$$ is the coefficient of $$x^n$$ in the power series $$f(x)$$. For example, the Mathematica code

5! * SeriesCoefficent[ Exp[x Exp[x Exp[x]]], {x, 0, 5}]


verifies your count of $$756$$, as shown on Wolfram Alpha.

• Oops, you beat me to it. Mar 15, 2021 at 15:22
• @Milten I prefer the exposition in your answer, and the summation formula you derived gives a pretty doable way to evaluate the number by hand. Mar 15, 2021 at 15:25
• From both of your methods i got a method which is not lengthy and bashy respected Milten Sir and Mike Earnest Sir , should i post it as a answer to my own query ? Mar 15, 2021 at 16:53
• @WizardMath I would be very interested in seeing it! Mar 15, 2021 at 16:59
• I shared , pls comment if its all gud or something is missing :) Mar 15, 2021 at 17:07

From @Mike Earnest and @Milten approaches, now I am considering a graph on $$\{1,2,3,4,5\}$$ made by placing an arrow from $$i$$ to $$j$$ if $$f(i)=j$$, and removing all self-loops. Absolutely we can have no cycles, so this graph is in fact a forest. Adding a vertex $$r$$ to the graph and having all roots of trees in this graph (that is, $$i$$ with $$f(i)=i$$) point to $$r$$. Then what we want to count is trees on $$\{1,2,3,4,5,r\}$$ with every vertex a distance of at most $$3$$ from $$r$$ (this is equivalent by directing all edges towards $$r$$). Ignoring the distance condition, Cayley's formula gives that there are $$6^4=1296$$ trees. We now must subtract the trees with at least one vertex of distance $$4$$ from $$r$$. Such trees will have a "backbone" of $$5$$ consecutive vertices ending at $$r$$ (say $$v_4,v_3,v_2,v_1,r$$) and then the 6th vertex will have one of these as its parent. If the parent is $$r,v_1,v_2,v_4$$ there are $$5!$$ trees each, and if the parent is $$v_3$$ there will be $$\frac{5!}{2}$$ because the 6th vertex and $$v_4$$ can be swapped. Hence required answer is $$1296-120\cdot 4-60 = 756$$.

• That all checks out, nicely done :^) Mar 15, 2021 at 17:09
• Ty Sir:) , now i am just thinking whose answer i should tick mark it as only one answer can be choosen according to the system here in MSE Mar 15, 2021 at 17:23
• Nice :) You are free to accept your own answer if you feel it matches the question best. Of course with just a few more vertices you would get more and more cases to consider again. Mar 15, 2021 at 17:24
• Hmm well said Sir 👍 Mar 15, 2021 at 17:31