Question

How many binary trees can be formed with 4 distinct nodes?

• A. 14
• B. 24
• C. 42
• D. 120

Hint:

The number of binary tree structures with \( n \) distinct nodes is given by the Catalan number \( C_n = \frac1n+1 \binom2nn \). Use factorial identities to evaluate the binomial term accurately.

Answer 1

The Correct Option is A

To find the number of binary trees that can be formed with \( n \) distinct nodes, we use the Catalan number.
The formula for the \( n^\text{th} \) Catalan number is:
\[ C_n = \frac{1}{n+1} \binom{2n}{n} \] 
Step 1: Substitute \( n = 4 \):
\[ C_4 = \frac{1}{4 + 1} \binom{2 \cdot 4}{4} = \frac{1}{5} \binom{8}{4} \] 
Step 2: Compute the binomial coefficient \( \binom{8}{4} \):
\[ \binom{8}{4} = \frac{8!}{4! \cdot 4!} = \frac{8 \cdot 7 \cdot 6 \cdot 5}{4 \cdot 3 \cdot 2 \cdot 1} = 70 \] 
Step 3: Calculate the Catalan number:
\[ C_4 = \frac{1}{5} \cdot 70 = 14 \] 
Therefore, the number of binary trees that can be formed with 4 distinct nodes is 14.