The Gateway to Computer Science Excellence

+27 votes

Match the pairs in the following questions by writing the corresponding letters only.

$\begin{array}{|cl|cl|} \hline A. & \text{The number of distinct binary tree with n nodes.} & P. & \frac{n!}{2} \\ \hline B. & \text{The number of binary strings of the length of 2n with an equal number of 0’s and 1’s} & Q. & \binom{3n}{n} \ \\ \hline C. & \text{The number of even permutation of n objects.} & R. & \binom{2n}{n} \\ \hline D. & \text {The number of binary strings of length 6n which are palindromes with 2n 0’s.} & S. & \frac{1}{1+n}\binom{2n}{n} \\ \hline \end{array}$

$\begin{array}{|cl|cl|} \hline A. & \text{The number of distinct binary tree with n nodes.} & P. & \frac{n!}{2} \\ \hline B. & \text{The number of binary strings of the length of 2n with an equal number of 0’s and 1’s} & Q. & \binom{3n}{n} \ \\ \hline C. & \text{The number of even permutation of n objects.} & R. & \binom{2n}{n} \\ \hline D. & \text {The number of binary strings of length 6n which are palindromes with 2n 0’s.} & S. & \frac{1}{1+n}\binom{2n}{n} \\ \hline \end{array}$

+31 votes

Best answer

- - S Catalan number http://http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_nodes
- - R Choosing $n$ locations for $0$'s out of $2n$ locations. The remaining $n$ locations are filled with $1$'s (no selection required).
- - P An even permutation is a permutation obtainable from an even number of two-element swaps, For a set of $n$ elements and $n>2$, there are $n!/2$ even permutations.

Ref - http://mathworld.wolfram.com/EvenPermutation.html - - Q

Length $= 6n$, as it is palindrome, we need to select only the first half part of the string.

Total length to consider is $3n$ (Remaining $3n$ will be revese of this $3n$)

Now, choose $n \ 0's$ out of $3n$. So **Q** is correct for **D**.

+1

The option for the number of binary trees is incorrect.

Number of BSTs (Binary Search Trees) = nth Catalan Number, whereas number of Binary Tress = (n!) * nth Catalan number.

Source : https://www.geeksforgeeks.org/total-number-of-possible-binary-search-trees-with-n-keys/

+2 votes

An even permutation is a permutation obtainable from an even number of two-element swaps, For initial set 1,2,3,4, the twelve even permutations are those with zero swaps: (1,2,3,4); and those with two swaps: (1,3,4,2, 1,4,2,3, 2,1,4,3, 2,3,1,4, 2,4,3,1, 3,1,2,4, 3,2,4,1, 3,4,1,2, 4,1,3,2, 4,2,1,3, 4,3,2,1). etc.

For a set of **n **elements and **n>2**, there are **n! /**** 2 **even permutations, which is the same as the number of odd permutations

52,345 questions

60,510 answers

201,930 comments

95,354 users