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: