Tags: #theorem

Statement

The number of labellings of a tree on $n$ vertices is $n^{n-2}$

Proof 1: induction

We prove the more general result: define

Then, we shall prove the claim that

and then the statement follows by setting all $x_i=1$.

We shall show this via induction. One can manually verify that this is true for $n=1$. Define $G_n(x_1,\dots ,x_n)=F_n(x_1,\dots ,x_n)-(x_1+\cdots +x_n{)}^{n-2}$. It suffices to show that $G_n=0$ identically. By this lemma, it suffices to show that $G_n{|}_{x_i=0}=0$ for each $i$. WLOG let $i=n$ and consider

note that the only terms that survive in the summation are those where the degree of $n$ is exactly 1. In other words, when $n$ is a leaf. Then, we note that $T\setminus n$ is a tree with $n-1$ vertices, and so we may rewrite this as

where $T^{\prime }$ ranges over labelled trees on $n-1$ vertices and $j$ ranges over the vertices of these trees. In particular, $j$ symbolizes the vertex to which $n$ is connected to. Note that we have to add one more to the degree of $x_j$ since attaching $n$ will add one more to its degree.

But we note that

which yields the result as desired after applying the induction hypothesis.

As a corollary to this proof, number of labellings on a tree with given degrees

Proof 2: Prüfer's Coding

We build a bijection between trees with codes, which are sequences $(c_1,\dots ,c_{n-2})$ each elements of $\{1,\dots ,n\}$ as follows (it is clear that the number of such codes is $n^{n-2}$):

1. Find the minimal leaf $l$ of $T$ (ie. the leaf with the least number as its labelling)
2. Let $c$ such that $(l,c)$ is the edge incident to $l$
3. Record $c$ (the label thereof)
4. Erase $(l,c)$
5. Repeat the above steps $n-2$ times.

Note that for $i\in [n]$, the number of times that $i$ appears in the code is ${\mathrm{deg}}_T(i)-1$.
$i$ gets recorded whenever we erase an edge connected to it, and we have to remove all those other edges before we erase $i$ itself.

Decoding: given a sequence $C=(c_1,\dots ,c_{n-2})\in [n{]}^{n-2}$ and let $L=\{1,\dots ,n\}$

1. Find the minimum element $l\in L$ that is not in $C$
2. Let $c$ be the first element of $C$
3. Draw the edge $(l,c)$
4. Remove $l$ from $L$ and $c$ from $C$
5. Repeat the above $n-2$ times
6. Connect the remaining 2 elements of $L$ by an edge

By the observation above, these tow are inverse to each other.

As a corollary to this proof, number of labellings on a tree with given degrees

Example

Say we have this tree

We would record:

Proof 3 (Eğecioğlu-Remmel)

We shall build a bijection between labelled trees and maps $f:[n]\to [n]$ such that $f(1)=1$ and $f(n)=n$. The bijection will have a similar feel to that of records is Sterlingian.
Note that there are $n^{n-2}$ such functions since we have $n$ choices for each input that is not $1,n$.

Given a tree $T$ on $n$ vertices

• Draw the path from 1 to $n$ as a straight line on top, potentially with branches below
• On the top row, look for right to left minima and mark those
• Cut the tree after (to the right of) each of these marked vertices
• Draw arrows to the left on the top row
• On the leftmost of each section of the top row, draw an arrow back to the last of its connected component
• For the branches below, draw them with the path to their root on the top row
• By following arrows, this gives you a function $f:[n]\to [n]$.

Note that since the number to the left of $n$ and 1 are always right to left minimas, 1 and 15 will always have a self loop. There is always one arrow leaving each vertex and thus it's a well-defined function.

Given a function $f:[n]\to [n]$:

1. Draw a graph that corresponds to the function
   1. This will consist of periodic (cycles) and preperiodic points
2. You can place the periodic cycles in a line at the top with the preperiodic points below them
3. Arrange all cycles such that the smallest of them is on the right
4. Arrange each cycle such that they are decreasing
5. Erase the arrows and draw the appropriate edges to create the tree

Example

The tree:

and the resulting function: