Prüfer Code, Cayley’s Formula, etc

Prufer Code is a way to represent a labeled tree as an array, which is related some tree counting problems

The Prüfer code is a way of encoding a labeled tree with $n$ vertices using a sequence of $n-2$ integers in the interval $[0, n−1]$

Conversion and Bijection between Tree and Prüfer code

We can construct Prüfer Code from a given tree by removing the smallest leaf and add the number of the only vertex adjacent to it to the list until there are only two vertices.

We can also constructing a tree from a given Prüfer Code by the following procedure.
for i from 1 to n – 2:
    Let the smallest leaf not in the current sequence and not used be u
    Let the first element in the sequence be v;
    Mark v as used;
    Connect u and v;
    Delete the first element in the sequence;
endfor
Connect the last two unused vertices;

From the construction, we know each Prüfer Code has a tree, and each tree has a Prüfer Code. Let $f: \text{Tree} \rightarrow \text{Prüfer Code}$ be the function we use to convert a tree to a Prüfer Code. We can further prove $f^{-1}(f(t)) = t$ for any tree $t$ by induction, which implies that there is a bijection between labeled trees with $n$ vertices and Prüfer Code with length $n – 2$. The direct result of the bijection is Cayley’s Formula as shown below.

Cayley’s Formula and Generalized Version

Theorem 1 (Cayley’s Formula): For any integer $n > 0$, the number of trees of $n$ labeled vertices is $n^{n-2}$.

Theorem 2 (Generalized Cayley’s Formula): Let $T_{n, k}$ be the number of labelled forests on $n$ vertices with $k$ connected components, such that vertices $1, 2, …, k$ all belong to different connected components. Then $T_{n, k} = k n^{n-k-1}$.

Property of Prüfer Code

1. The vertex with the highest number will not be in the Code
2. Each vertex $i$ appears $d_i – 1$ times in the Code, where $d_i$ is the degree of vertex $i$.

Lemma 3: Given the degree of each vertex in a tree of size $n$, $d_1, d_2, …, d_n$, the number of possible trees is $$\frac{(n – 2)!}{(d_1 – 1)! (d_2 – 1)! … (d_n – 1)!}$$

Related Problems

Prüfer-Code-like Bijection: CF156D
Problem in short: Given a graph, find the number of ways to connect the graph with minimum edges.
Idea: We can construct sequence $P$ and $Q$ that represent the final graph similar to Prüfer Code. Let $k$ be the current number of connected component. $P$ denotes the vertex $v$ that we connect to when we remove the smallest labeled leaf component $C$ one by one. $Q$ denotes the vertex in $C$ that we use to connect $v$. The bijection between the sequences can be proved in a similar manner. Since for each sequence $P$, we will have $\prod_i sz_i$ different $Q$s, where $sz_i$ is the size of the $i$th component, the answer will be $$n^{k-2} \cdot \prod_i sz_i $$.

Generalized Cayley’s Formula: CF1109D
Trivial Application

Leave a Reply

Your email address will not be published. Required fields are marked *