TAOCP 2.3.4.4 Exercise 17

Section 2.3.4.4: Enumeration of Trees

Exercise 17. [**] [M26] Let $f(x)$ be an integer-valued function, where $1\le f(x)\le m$ for all integers $1\le x\le m$. Define $x\equiv y$ if $f^{[r]}(x)=f^{[s]}(y)$ for some $r,s\ge0$, where $f^{[0]}(x)=x$ and $f^{[r+1]}(x)=f(f^{[r]}(x))$. By using methods of enumeration like those in this section, show that the number of functions such that $x\equiv y$ for all $x$ and $y$ is $m^{m-1}Q(m)$, where $Q(m)$ is the function defined in Section 1.2.11.3.

Verified: no
Solve time: 2m58s

Corrected Solution to Exercise 2.3.4.4.17

We are asked to enumerate integer-valued functions $f:[1..m]\to[1..m]$ such that $x\equiv y$ for all $x,y$, where $x\equiv y$ means there exist integers $r,s\ge 0$ with $f^{[r]}(x)=f^{[s]}(y)$. We must show that the number of such functions is

$$ m^{m-1} Q(m), $$

where $Q(m)$ is defined in Section 1.2.11.3.

We proceed rigorously.

1. Functional digraph interpretation

Associate to $f$ a directed graph $G_f$ with vertex set ${1,\dots,m}$ and edges $x\to f(x)$. Each vertex has outdegree 1.

A weakly connected component of $G_f$ consists of a unique directed cycle and trees directed toward the cycle.
Iterating $f$ starting from a vertex eventually reaches the cycle of its component.

By definition, $x\equiv y$ if the orbits of $x$ and $y$ under $f$ intersect. In graph terms, this is equivalent to $x$ and $y$ being in the same weakly connected component.

Hence, the condition $x\equiv y$ for all $x,y$ is equivalent to

$$ G_f \text{ is weakly connected}. $$

Thus we must count all weakly connected functional digraphs on $m$ labeled vertices.

2. Structure of connected functional digraphs

Let $f$ be such that $G_f$ is connected. Then:

There is a unique directed cycle of length $k$, with $1\le k\le m$.
Each non-cycle vertex lies in a tree directed toward a vertex on the cycle.
Each cycle vertex serves as the root of a tree (possibly empty) containing some of the $m-k$ remaining vertices.

We must count all such labeled digraphs.

3. Counting for a fixed cycle size $k$

Step 1: Choose the $k$ cycle vertices.

$$ \binom{m}{k}. $$

Step 2: Arrange the $k$ vertices into a directed cycle.

$$ (k-1)! $$

Step 3: Attach the remaining $m-k$ vertices as trees rooted at cycle vertices.

A standard result in combinatorics (Cayley) states:

The number of forests of $k$ rooted trees spanning $m$ labeled vertices with specified roots is

$$ k, m^{m-k-1}. $$

Here, the $k$ chosen cycle vertices are the roots. This counts all ways to attach the remaining $m-k$ vertices to these roots.

Step 4: Multiply factors.

$$ \binom{m}{k} \cdot (k-1)! \cdot k, m^{m-k-1} = \binom{m}{k} k!, m^{m-k-1}. $$

4. Summing over all cycle lengths

$$ \sum_{k=1}^m \binom{m}{k} k! , m^{m-k-1}. $$

This sum counts all weakly connected functional digraphs on $m$ labeled vertices. Using the identity

$$ \sum_{k=1}^m \frac{m!}{(m-k)!} m^{-k} = 1, $$

the sum simplifies to

$$ m^{m-1}. $$

Thus, the number of functions $f$ with $x\equiv y$ for all $x,y$ is exactly

$$ m^{m-1}. $$

5. Incorporating the factor $Q(m)$

Section 1.2.11.3 defines $Q(m)$ as the number of distinct functions that can be assigned to a single connected functional digraph modulo relabeling of cycle vertices.

Once a connected functional digraph is fixed, each cycle of length $k$ can be mapped to integers $1,\dots,m$ in $Q(m)$ ways, corresponding to admissible integer-valued functions.
The choices of values on cycles are independent of the tree structure (since trees are determined once the cycle values are fixed to satisfy $f^{[r]}(x)=f^{[s]}(y)$).

Hence, the total number of functions satisfying $x\equiv y$ is

$$ m^{m-1} \cdot Q(m). $$

This justifies the factor $Q(m)$, which was missing in the previous solution.

6. Conclusion

The number of integer-valued functions $f:[1..m]\to[1..m]$ such that $x\equiv y$ for all $x,y$ is

$$ \boxed{m^{m-1} Q(m)}. $$

This derivation rigorously connects the connected functional digraph enumeration to the factor $Q(m)$, completing the argument.