1
$\begingroup$

According to Cayley's formula, we have number of spanning trees on a complete graph as n^n-2 and number of labelled trees with n vertices as n^n-2

If the tree is rooted then in each tree we can choose a root in n ways so total number of rooted labelled trees is n^n-1.

Here when computing the total number for rooted labelled tree, why don't we consider the ordering of elements ?

For example if we have a regular graph with 3 vertices then one of the spanning tree is 1->2->3. Here each element can be root and we can have remaining elements at right or left. So why don't we consider the ordering (right or left) in the formula?

|cite|improve this question
$\endgroup$
  • $\begingroup$ What research have you done? There are many different expositions that explain how to get that result. Which one are you looking at? What specifically does it say? Incidentally, that's Cayley's formula, which is different from Cayley's theorem. $\endgroup$ – D.W.♦ Aug 21 '17 at 18:51
  • 1
    $\begingroup$ We don't consider the order since the vertices are labelled. You are more than welcome to count some other quantity if you so wish. $\endgroup$ – Yuval Filmus Aug 21 '17 at 19:24
  • $\begingroup$ If the vertices are labelled then a tree with root 3 ,left child 2 and right child 1 and a tree with root 3,right child 2 and left child 1 are different right? $\endgroup$ – Zephyr Aug 21 '17 at 19:34
  • $\begingroup$ You can consider them as different, and then the problem itself becomes different. There are many different variants of the enumeration problem, and every specific formula can be true for only one of them. $\endgroup$ – Yuval Filmus Aug 21 '17 at 21:11
  • $\begingroup$ In combinatorics, these are often called "plane labeled trees", and counting them is also interesting; see oeis.org/A006963/a006963_1.pdf, for instance. $\endgroup$ – jschnei Aug 21 '17 at 22:56
1
$\begingroup$

We don't consider the order of elements since what we are counting is the number of graphs on the vertex set $\{1,\ldots,n\}$ which are trees, that is, connected and having no cycles.

This is the usual graph-theoretic notion of tree. In computer science we often think of trees as rooted objects with ordered children, which is a similar but different concept.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Sir, nowhere it is mentioned that if we take ordering of trees into consideration then we have a different formula. So I got confused. $\endgroup$ – Zephyr Aug 22 '17 at 4:42
  • $\begingroup$ There's no need to mention it. They count one thing. If you count another thing, you get a different result. $\endgroup$ – Yuval Filmus Aug 22 '17 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.