Past exam of the Probability, statistics and options II course of the University of Oxford / 2011 / R / R2 / d

Root the tree at any vertex and order vertices so every parent precedes its children. The root has $k$ colour choices. Each of the other $n-1$ vertices has exactly one earlier adjacent vertex, its parent, and therefore exactly $k-1$ choices. There are no other restrictions because a tree has no cycles and no extra edges between those branches. Multiplication yieldsThe formula also includes the one-vertex tree.

In the complete graph every pair of vertices is adjacent, so all $n$ colours assigned to vertices must be distinct. Choose colours successively, leaving one fewer choice at each step. ThusFor nonnegative integer $k<n$ the product is zero, as required.