Consider the following statements:
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 (distinct) keys 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)
Choose the correct answer from the options given below:
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) are counted by the Catalan number C(2n,n)/(n+1) = (2n)!/((n+1)!n!). Labelled trees multiply this by n!, giving (2n)!/(n+1)!. Labelled graphs: each of the C(n,2) edges is present or absent. C is wrong, since it divides by (n+1)! instead of (n+1).More Discrete Structures and Optimization questions
- The relation R = {(1, 3), (1, 1), (3, 1), (1, 2), (3, 3), (4, 4)} defined on {1, 2, 3, 4} is ____
- Let G be a simple undirected graph with n (n > 10) vertices and k connected components. What is the minimum possible number of edges of G?
- The negation of "Some students like hockey" is:
- A relation R is defined on ordered pairs of integers as (x, y) R (u, v) if x < u and y > v. Then R is
- Suppose you are married and you and your partner attend a party with three other married couples. Several handshakes took place. No one sho…
- Consider the following graph with vertices A, B, C, D and edges: A – B, B – C, A – D, B – D, C – D (A, B, C lie in a row; D is below and jo…