GATE CSE 1990 | Question: 3-iii

Question

The number of rooted binary trees with $n$ nodes is,

• A. Equal to the number of ways of multiplying $(n+1)$ matrices.
• B. Equal to the number of ways of arranging $n$ out of $2 n$ distinct elements.
• C. Equal to $\frac{1}{(n+1)}\binom{2n}{n}$.
• D. Equal to $n!$.

Answer 1

Number of rooted binary trees (unlabeled) with $n$ nodes is given by $n^{th}$ Catalan number which equals $\frac{{}^{2n}C_n}{n+1}.$

Here, both options $A$ and $C$ are true as option $A$ corresponds to $n$ multiply operations of $n+1$ matrices, the number of ways for this is again given by the $n^{th}$ Catalan number.

Ref: https://math.stackexchange.com/questions/1630457/how-many-ways-to-multiply-n-matrices

Comments

For Option (B) i got answer as (2n)! / (n!)

 

Is it correct sir?

---

im also getting the same thing

---

Please provide explanation of Option B.

Answer 2

Number of BTs with Unlabelled nodes is (2n C n )/(n+1)

Number of BTs with labelled nodes is (2n C n ) * (n!) /(n+1) .

 

So, answer is option C.

If question have asked about BTs with labelled nodes then answer is B i.e picking n out of 2n people i.e 2n C n then n can be arranged in n! ways

Comments

still (n+1) term would be missing in option B rt?

---

yes arjun sir i think he forgot to mention but still they given " Number of BTs with labelled nodes is (2n C n ) * (n!) /(n+1)"

---

To find the number of rooted binary trees with n internal nodes is same as to find the number of ways to parenthesize (n+1) matrices...and both are equal to the n^th Catalan Number C_n. So , I think both (A) and (C) are correct...