3,052 views
Match the pairs in the following questions by writing the corresponding letters only.
$$\begin{array}{|c|l|c|l|} \hline A. & \text{The number of distinct binary tree} & P. & \frac{n!}{2} \\& \text{ with n nodes.}\\ \hline B. & \text{The number of binary strings of the length } & Q. & \binom{3n}{n} \\& \text{of 2n with an equal number of 0’s and 1’s} \\ \hline C. & \text{The number of even permutation of n } & R. & \binom{2n}{n} \\& \text{ objects.}\\ \hline D. & \text {The number of binary strings of length 6n } & S. & \frac{1}{1+n}\binom{2n}{n} \\& \text{which are palindromes with 2n 0’s.} \\ \hline \end{array}$$

The editing of this question has gone haywire. Some part of B and D is showing up in Q and S section. Same is the case in GO hardcopy.
true

Hey Folks,

Quick FYI, This question is not correctly formatted in the Gate overflow PDF.

Lakshman Patel RJIT

Thank you for fixing this question

### Subscribe to GO Classes for GATE CSE 2022

1. $- S$  Catalan number https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/
2. $- R$  Choosing $n$ locations for $0$'s out of $2n$ locations. The remaining $n$ locations are filled with $1$'s (no selection required).
3. $- 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
4.  $- 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.

Explain even permutations with an example
What is even permutation ???I'm not getting from above link ??

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.

then what will be the value of odd permutations?

same as even permutations, $\frac{n!}{2}$

Number of Binary trees possible with n nodes:

https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/

A - S
B - R
C - P
D - Q

It will be $\frac {n!}{2}$

using the property of symmetry.

http://mathworld.wolfram.com/EvenPermutation.html

by

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

by