edited by
5,265 views
20 votes
20 votes

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

  1. Equal to the number of ways of multiplying $(n+1)$ matrices.
  2. Equal to the number of ways of arranging $n$ out of $2 n$ distinct elements.
  3. Equal to $\frac{1}{(n+1)}\binom{2n}{n}$.
  4. Equal to $n!$.
edited by

2 Answers

Best answer
20 votes
20 votes

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

0 votes
0 votes
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
Answer:

Related questions

52 votes
52 votes
2 answers
1
Kathleen asked Sep 12, 2014
6,337 views
Find the number of binary strings $w$ of length $2n$ with an equal number of $1's$ and $0's$ and the property that every prefix of $w$ has at least as many $0's$ as $1's....
12 votes
12 votes
2 answers
2
makhdoom ghaya asked Nov 22, 2016
3,074 views
The number of ways in which $5\; A's, 5\; B's$ and $5\; C's$ can be arranged in a row is:$15!/(5!)^{3}$$15!$$\left(\frac{15}{5}\right)$$15!(5!3!)$.
29 votes
29 votes
6 answers
4
makhdoom ghaya asked Nov 22, 2016
9,204 views
Indicate which of the following well-formed formulae are valid:$\left(P\Rightarrow Q\right) {\wedge} \left(Q \Rightarrow R\right) \Rightarrow \left(P \Rightarrow R\right)...