We study functions $f: V \rightarrow V$ and their properties by thinking of them as a graph with vertex set $V$ and directed edges $(v, f(v))$. This gives us insight into permutations, rooted trees, and a bunch of counting principles. Such a structure is called as functional digraph

§ Principle 1: Structure theory

every functional digraph uniquely decomposes into disjont rooted trees which feed into one or more disjoint cycles. We think of nodes as pointing from the leaves towards the root. The root of the tree lies in a cycle.

§ Existence of tree implies not bijection

If we have a tree, we can keep walking backwards using edges from the root towards the leaves. Now this leaf does not have an incoming edge. This means that this leaf is not in the image of $f$. Hence $f$ cannot be surjective.

§ Rooted Trees: a single cycle

in a rooted tree, only the root node $r$ is such that $f(r) = r$. All other nodes point to other nodes without cycles.

§ Permutations: no rooted tree, only cycle

In a permutation, all we have are cycles. There are no trees that hang from the cycles.

§ Counting number of rooted trees: $n^{n-2}$: (TODO)

Say we have a function $f: V \rightarrow V$ where $|V| = n$ and $f(1) = 1$, $f(n) = n$.

§ References

• USACO: functional graphs