Functional Graphs
Lesson · Advanced
Combinatorics
A functional graph represents a function
by drawing a directed edge
from every element x ∈ X.
Since f assigns exactly one value to each element, every vertex has exactly one outgoing edge.
Every component of a finite functional graph consists of one directed cycle together with directed trees feeding into that cycle.
For example, assume X = {1, 2, 3, ..., 14} and
Let X be a finite set and f : X → X be a one-to-one function. Then the functional graph of f is a disjoint union of directed cycles.
Consider any a ∈ X and the sequence
Since X is finite, eventually an element must repeat. Consider the first time this happens.
If the first repeated element is a, then
Otherwise, suppose
Since f is one-to-one,
But this means that an element had already repeated before fⁱ(a), contradicting our choice of fⁱ(a) as the first repeated element.
Therefore, the first repeated element must be a, so a lies on a directed cycle.
Since this is true for every a ∈ X, the functional graph of f is a disjoint union of directed cycles.
A particularly important special case occurs when f is a permutation of
A permutation is bijective, so every vertex has:
• exactly one outgoing edge
• exactly one incoming edge
Therefore, there can be no trees attached to the cycles.
Hence:
The functional graph of a permutation is a disjoint union of directed cycles.
Suppose x lies on a cycle of length k. Then
and more generally
Let f be a permutation with cycle lengths
Then
if and only if
Equivalently,
The smallest positive m for which
is therefore
Suppose f is a permutation and
Then
Let
By Bézout's Identity, there exist integers r, s such that
Since f is a permutation, f⁻¹ exists. Therefore,
Since
we also have
and since
applying f⁻ᵇ to both sides gives
so
Hence,
Therefore,
A permutation f of {1, 2, ..., 10} satisfies
for every x. What cycle lengths are possible?
If x belongs to a cycle of length k, then
Therefore
So the permutation consists entirely of cycles of lengths 1, 2, and 4.
A permutation of 12 elements consists of cycles of lengths 3, 4, and 5. Find the smallest positive integer m such that applying the permutation m times returns every element to its original position.
We need
Therefore
How many permutations of
have a functional graph consisting of exactly one cycle?
The cycle must contain all n elements.
Fix 1 as the first element. The remaining n − 1 elements can be arranged around the cycle in
ways.
Therefore the number is
How many permutations of 8 elements consist of two cycles of length 4?
We could first choose 4 elements for one cycle:
and arrange each group into a cycle:
But this counts the two cycles twice, because exchanging the two cycles does not produce a new permutation.
Therefore
A permutation f of 15 elements consists of exactly three cycles. The smallest positive integer m satisfying
is 30.
Find the greatest possible length of the largest cycle.
Let the three cycle lengths be
Then
and
Each cycle length must therefore divide 30.
The possible cycle lengths at most 15 are
To get an LCM of 30, we need factors 2, 3, 5.
Try to make the largest cycle as large as possible.
A 15-cycle already supplies 3 · 5, so we need an even cycle. But the remaining two cycle lengths sum to 0, impossible since
Try 10. It supplies 2 · 5, so we need a factor 3. We can take
and
Thus the greatest possible largest cycle is
A permutation f of 20 elements satisfies
and has no fixed points. What is the minimum possible number of elements satisfying
Every cycle length must divide 12. Since there are no fixed points, possible cycle lengths are
An element satisfies f⁴(x) = x exactly when its cycle length divides 4.
So 2- and 4-cycles contribute, while 3-, 6-, and 12-cycles do not.
We want to cover as many of the 20 elements as possible using
Since
cannot be written as a sum of 3's, 6's, and 12's, some elements must belong to 2- or 4-cycles.
We can write
so only 2 elements need to belong to a cycle whose length divides 4.
Therefore the minimum is
Suppose a permutation of n elements has
where
Then the number of such permutations is