819 views

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}$
edited | 819 views

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 (42.8k points)
edited

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