For, let u be a fixed vertex of the complete graph
. Compute the number
of spanning trees of
where
is the base number for the natural logarithm.
Let's denote bythe number of labeled ( label set
) trees - with n vertices- such that the degree of vertex
is
.
Then we have the generating function: = \sum f_n(d_1,..,d_n)\cdot x_1^{d_1}\cdot x_2^{d_2}...x_n^{d_n} = x_1\cdot ...x_n\cdot (x_1+...+x_n)^{n-2})
Now ifwhat we want is the sum of the entries where the corresponding exponent of
is 1.
But of course if we require the exponent ofsince we may never choose
we had in
.
Thus the number of trees such that vertex u is a leaf is:
And the total number of labelled trees is.
For further details on this read here.
  |
LinkBack URL
About LinkBacks