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!$.

Comments

For Option A - 

Suppose we have n+1 matrices: A1​,A2​,…,An+1​ and we want to multiply them while preserving their order.

The question is: how many different ways can we put parentheses?

For example, with 4 matrices: A1​A2​A3​A4​ possible parenthesizations include

((A1​A2​)A3​)A4,​ (A1​(A2​A3​))A4,​ (A1​A2​)(A3​A4​), A1​((A2​A3​)A4​)

Every way of parenthesizing their product corresponds to a rooted binary tree in which the (n+1) matrices are the leaves and each multiplication is an internal node. Since a full binary tree with (n+1) leaves has exactly (n) internal nodes, there is a one-to-one correspondence between parenthesizations of (n+1) matrices and rooted binary trees with (n) nodes. Therefore, both are counted by the Catalan Number.

---

NUMBER OF WAYS TO PUT PARETHESIS CAN BE FOUND OUT BY CN

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

Please provide explanation of Option B.

---

@This_is_Nimishka, we have to choose n distinct elements from 2n distinct elements so no. of ways of doing this  $2nCn$ , now there are n distinct elements so no. of ways to arrange them is n!.It's same as saying  $2nPn$.  

---

option c i know but learnt something new from option a

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...