Consider: A. The number of labelled binary trees possible with n nodes is (2n)!/(n + 1)!. B. The number of binary search trees possible with n nodes is (2n)!/((n + 1)! n!). C. The number of unlabelled binary trees possible with n nodes is C(2n, n)/(n + 1)!. D. The number of simple, undirected, labelled graphs possible with n vertices is 2^(n(n−1)/2).

1. A(A, B) and (C) are only correct
2. B(A, B) and (D) are only correct
3. C(B, C) and (D) are only correct
4. D(A, C) and (D) are only correct

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. (A, B) and (D) are only correct

Explanation

Unlabelled binary trees (and BSTs) number the Catalan number C(2n,n)/(n + 1) = (2n)!/((n + 1)! n!), so B is true and C (dividing by (n + 1)!) is false. Labelled trees multiply the Catalan number by n!: (2n)!/(n + 1)! (A true). Each of the C(n,2) possible edges is present or not: 2^(n(n−1)/2) (D true).