Question

no of different rooted labeled trees with n vertices ?

Answer 1

No of Labelled Trees => n^n-2 

https://en.wikipedia.org/wiki/Cayley's_formula

Then set each of tree node to be root, in each tree there are n ways to choose the root

Total No of rooted labeled trees => n^n-2 * n => n^n-1

Reference Graph Theory, Narsing Deo, Chapter on counting trees.

Comments

@Hemant Parihar

Why can't we use Catalan No??

---

Cayley's formula immediately gives the number of labelled rooted forests on n vertices, namely (n+1)^n-1. Each labelled rooted forest can be turned into a labelled tree with one extra vertex, by adding a vertex with label n+1 and connecting it to all roots of the trees in the forest.

acc to wiki https://en.wikipedia.org/wiki/Cayley%27s_formula

whts the difference?

---

someone please clarify my doubts.

1.What is the meaning of ROOTED?

2.Why can't we draw the answer like this:

²ⁿC_n / (n+1) , for the number unlabeled trees

(²ⁿC_n / (n+1) ) * (n!) , for labeled trees

3.please tell what's going wrong with this approach

---

Here the question is total no of tree, not the total no of binary tree

If we talk about total no of binary tree then it is  catalan no

Answer 2

It is n^n-2 which is Cayley's formula in graph theory.
https://en.wikipedia.org/wiki/Cayley%27s_formula