ISRO2014-73

Question

How many different trees are there with four nodes $\text{A, B, C}$ and $\text{D}?$

• A. $30$
• B. $60$
• C. $90$
• D. $120$

Comments

@rude sir what can you say about this question ?

---

@Manojk sir.. If we are creating Binary tree only then also its give around 336 tree ($\binom{2n}{n} * \frac{1}{n+1}$). I am really not getting sir. What should i say about this. .

---

(2n C n)*1/n+1=8C4/5=8!/5!4!=8x7x6/4x3x2=14 not 336

Answer 1

Please look at below link:
http://www-math.mit.edu/~djk/18.310/18.310F04/counting_trees.html

$F(n)=n^{n-2}$

Comments

This is the formula to calculate the number of spanning trees

---

1. We can consider this questn as a complete graph of 4 vetices.

2. then any spanning tree , will respresent one element in the set of ans.
i.e n^(n-2)

i.e --->   (n^(n-2) ) * 4! , becoz the nodes are labelled, unfortunately none matches

Answer 2

Answer (D)

Below trees are possible if the tree has four nodes

These trees are for unlabeled nodes. Since we have a trees with labels, so each tree in the above diagram, can

be permuted with labels. Since there are four labels (A, B, C, D), so tree can be permuted 4! times.

So there are total of 5 trees possible and each of it can be permuted 4! times.

Therefore total trees possible would be

5 x 4! = 5! = 120

Comments

Gurdeep Saini  THIS QUESTION SAYS   TREE SO THIS WILL INCLUDE BINARY TREE SO ATLEAST  336 TREES WILL BE THERE  ? 

---

@eyeamgj 

1) see the diagram in my  comment which contain  the binary tree also (not rooted binary tree) 

2)  here we do not have to make the rooted tree (catalan no is used in case of rooted binary tree , nad mutliply by n factorial if label ) and you are making rooted tree 

3) example   

try to make the tree with 3 different node  you will get 3 answer  (remember we have to make  nonrooted tree) 

4) after this try to make the binary tree with 4 node  which you are thinking (forgot the formula which you are using i.e. catalan no because these is used to make the binary tree .  but tree may be tarnary and so on...... )

---

Gurdeep Saini OK THANK I SO MUCH FOR HELP

Answer 3

I think all options are wrong !

In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer n, the number of trees on n labeled vertices is .

So here 4^(4-2) i.e. 16.

Reference :-

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

Comments

This is the formula to calculate the number of spanning trees

Answer 4

1.No of different rooted unlabeled binary tree with n nodes =catalan no=C(2n,n)/n+1 

2.No of different rooted labeled binary tree with n nodes =(C(2n,n)/n+1) *n!

3.No of spanning tree of complete graph with n nodes=No of unrooted labeled tree with n nodes=caley formula=n^n-2

4.No of rooted tree with n nodes=n*(no of unrooted labeled tree with n nodes)=n^n-1

So, answers to the above question will depend upon whether we need a rooted or unrooted labeled tree with n nodes

1.rooted=4^2=16

2.unrooted=4^3=64

both are not in option.

References

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

https://gateoverflow.in/25231/no-of-different-rooted-labeled-trees-with-n-vertices

http://gatecse.in/number-of-binary-trees-possible-with-n-nodes/