5
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ 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 $\endgroup$ Mar 15 at 13:49
  • $\begingroup$ Can caseys theorem help here to get the required number of forests by removing the unwanted trees? $\endgroup$
    – WizardMath
    Mar 15 at 14:06
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 15 at 14:41
  • $\begingroup$ Hmm yeah seems like Sir $\endgroup$
    – WizardMath
    Mar 15 at 16:59
5
$\begingroup$

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} $$

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Oops, you beat me to it. $\endgroup$
    – Milten
    Mar 15 at 15:22
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 15 at 15:25
  • $\begingroup$ 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 ? $\endgroup$
    – WizardMath
    Mar 15 at 16:53
  • $\begingroup$ @WizardMath I would be very interested in seeing it! $\endgroup$ Mar 15 at 16:59
  • $\begingroup$ I shared , pls comment if its all gud or something is missing :) $\endgroup$
    – WizardMath
    Mar 15 at 17:07
2
$\begingroup$

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$.

$\endgroup$
4
  • 1
    $\begingroup$ That all checks out, nicely done :^) $\endgroup$ Mar 15 at 17:09
  • $\begingroup$ 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 $\endgroup$
    – WizardMath
    Mar 15 at 17:23
  • 2
    $\begingroup$ 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. $\endgroup$
    – Milten
    Mar 15 at 17:24
  • $\begingroup$ Hmm well said Sir 👍 $\endgroup$
    – WizardMath
    Mar 15 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.