The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
1.1k views
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://http://gatecse.in/wiki/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.

answered by Boss (41k points)
edited by
0
Explain even permutations with an example
0
What is even permutation ???I'm not getting from above link ??
0

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
Answer:

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

Related questions

+4 votes
0 answers
6
asked Sep 12, 2014 in Non GATE by Kathleen Veteran (52k points) | 193 views
0 votes
0 answers
7
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
187,307 comments
71,027 users