The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 votes

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

A. The number distinct binary trees with $n$ nodes. P. $\frac{n!}{2}$

B. The number of binary strings of length of $2n$ with
an equal number of $0’s$ and $1’s$.

Q. $ \binom{3n}{n}$
C. The number of even permutation of $n$ objects. R. $\binom{2n}{n}$
D. The number of binary strings of length $6n$ which are
palindromes with $2n$  $0’s$.
S. $\frac{1}{1+n}\binom{2n}{n}$
asked in Combinatory by Veteran (59.9k points)
edited by | 1k views

2 Answers

+24 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 (43.5k 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 (34.1k points)

Related questions

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
47,903 questions
52,285 answers
67,713 users