Cayley's Formula

Let be a Ring and let .
Let be the complete Directed Graph on
with weights

For any Weighted Graph define its weight as

Consider spanning trees of with edges directed away from some root.
The sum of weights of all such trees is:

Proof

Note that is a symmetric, homogeneous polynomial of degree .
The weight of trees with leaf node is
Counting another way, we find

Proceed by induction.
For we can check (there are only 2 trees).
Now assume that

We conclude that

Consider .
This is a symmetric, homogeneous polynomial of degree at most .
Also , so is divisible by .
By symmetry, it is divisible by all of ,
but this can only happen if so we conclude:

Corollary

Consider all undirected trees spanning .
Then the following holds:

Equivalently, if we define undirected weights ,
then the sum of weights of all spanning trees of is:

Proof

Take an undirected spanning tree .
By rooting it at node , obtain the directed spanning tree .
Note that

Now the LHS is all the directed spanning trees so we conclude

For the second part, note that the weight of an undirected spanning tree is:

from where the result follows.

Corollary

Fix some numbers
The number of spanning trees of that satisfy
is the Multinomial Coefficient:

Proof

Follows immediately from Multinomial Theorem, and previous corollary.