7
$\begingroup$

I'd like to prove the equation following:

$$x_1x_2x_3...x_n(x_1 + x_2 + ... x_n)^{n-2} = \sum_Tx_1^{d_{T(1)}}x_2^{d_{T(2)}}...x_n^{d_{T(n)}}\tag 1$$

where the sum is over all spanning trees $T$ in $K_n$ and $d_{T(i)}$ is the degree of $i$ in $T$


I heard this's called Cayley's generalized formula, which is the number of $trees$ in $n$ vertices:

$n^{n-2} \tag 2$

Only the morphological similarity between $(1)$ and $(2)$ is the power $n-2$.

I think in this case induction might work well, but honestly $induction$ itself is not a productive way of proving something to reveal one's mathematical identity to me including this case, proof of $(1)$.

Any hint to prove this equation in combinatoric and algebraic way?

$\endgroup$

2 Answers 2

3
$\begingroup$

Let's divide both sides of $(1)$ by $x_1\dots x_n$, then we have to prove $$ (x_1 + x_2 + \dots + x_n)^{n-2} = \sum_{T}x_1^{d_{T(1)}-1}x_2^{d_{T(2)}-1}\dots x_n^{d_{T(n)}-1}. $$ But now the argument is basically the same as Prüfer's proof. Note that each vertex $T(i)$ occurs $d_{T(i)}-1$ times (the number of steps in Prüfer's algorithm it takes for $T(i)$ to become a leaf) in the corresponding Prüfer's sequence, which has total length $n-2$. On the other hand, each term in the Prüfer's sequence can take any value from $1$ to $n$, so it corresponds to a factor of $x_1+\dots+x_n$. We have $n-2$ such factors, which yields the left-hand side. To derive $(2)$ from $(1)$, simply let $x_1=\dots=x_n=1$.

$\endgroup$
1
$\begingroup$

As you might have noticed, setting all the $x_i$ to $1$ recovers the fact that the number of trees on $n$ vertices, which is the same as the number of trees spanning $K_n$, is $n^{n-2}$.

To get a bijective proof of (1), let $x_1, \ldots, x_n$ be numbers labeling the vertices of $K_n$. Given a spanning tree $T$, note that $$\prod_{(i,j) \in T} x_ix_j = \prod_{i = 1}^n x_i^{d_i(T)}.$$ (The product on the left is over edges of $T$.)

Summing over all spanning trees $T$, we are reduced to showing that $$\sum_{T} \prod_{(i, j) \in T} x_ix_j = x_1x_2\ldots x_n(x_1 + x_2 + \ldots + x_n)^{n-2}.$$

Note that the right hand side is the sum over all monomials of degree $2n-2$ in which each variable has degree at least $1$. Now, given any set $S$ of $n-1$ edges $(u_i, v_i)$ in $K_n$, we can form the degree $2n-2$ monomial $$m(S) = \prod_{i=1}^{n-1} x_{u_i}x_{v_i}.$$ Moreover, if $S$ happens to be a spanning tree, each variable will appear at least once.

To complete the proof, it suffices to show that $m$ is a bijection between the set of spanning trees and monomials of degree $2n-2$ in which each $x_i$ occurs at least once. Can you take it from here?

$\endgroup$
1
  • $\begingroup$ could you give me a hint how to prove m constructs bijection between spanning trees and monomials? $\endgroup$
    – Beverlie
    Commented Dec 6, 2017 at 1:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .