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}$
in Combinatory by
edited by | 1.7k views
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.

4 Answers

+31 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.

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 :

then what will be the value of odd permutations?

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

+2 votes

A - S
B - R
C - P
D - Q
+2 votes

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

using the property of symmetry.

+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

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
52,345 questions
60,510 answers
95,354 users