§ Structure theory of finite endo-functions
We study functions f:V→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: nn−2: (TODO)
Say we have a function f:V→V where ∣V∣=n and f(1)=1, f(n)=n.
§ References