The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 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} & Q. & \binom{3n}{n} \text{ with an equal number of 0’s and 1’s}  \\ \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} & S. & \frac{1}{1+n}\binom{2n}{n} \text{ palindromes with 2n 0’s.}  \\ \hline \end{array}$
asked in Combinatory by Veteran (52k points)
edited ago by | 1.1k views

2 Answers

+26 votes
Best answer
  1. - S Catalan number http://
  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 -
  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.

answered by Boss (41k points)
edited by
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.

Source :

+2 votes

A - S
B - R
C - P
D - Q
answered by Boss (33.8k points)

Related questions

+4 votes
0 answers
asked Sep 12, 2014 in Non GATE by Kathleen Veteran (52k points) | 193 views
0 votes
0 answers
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,117 answers
71,027 users