edited by
4,895 views
43 votes
43 votes
Match the pairs in the following questions by writing the corresponding letters only.
$$\begin{array}{|c|l|c|l|} \hline A. & \text{The number of distinct binary tree} & P. & \frac{n!}{2} \\& \text{ with n nodes.}\\ \hline B. &  \text{The number of binary strings of the length } & Q. & \binom{3n}{n} \\& \text{of 2n with an equal number of 0’s and 1’s}  \\ \hline C. & \text{The number of even permutation of n } & R. & \binom{2n}{n} \\& \text{ objects.}\\ \hline D. & \text {The number of binary strings of length 6n } & S. & \frac{1}{1+n}\binom{2n}{n} \\& \text{which are palindromes with 2n 0’s.} \\ \hline \end{array}$$
edited by

4 Answers

Best answer
43 votes
43 votes
  1. $- S$  Catalan number https://gatecse.in/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.

edited by
3 votes
3 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

Related questions

24 votes
24 votes
1 answer
1
Kathleen asked Sep 12, 2014
5,737 views
Match the pairs in the following questions by writing the corresponding letters only.$$\begin{array}{|ll|ll|}\hline \text{(a)} & \text{Buddy system} & \text{(p)} & \tex...
1 votes
1 votes
2 answers
2
0 votes
0 votes
3 answers
3
Kathleen asked Sep 12, 2014
1,913 views
Using the 8087 arithmetic coprocessor with the 8086 CPU requires that the 8086 CPU is operated ............
52 votes
52 votes
2 answers
4
Kathleen asked Sep 12, 2014
6,337 views
Find the number of binary strings $w$ of length $2n$ with an equal number of $1's$ and $0's$ and the property that every prefix of $w$ has at least as many $0's$ as $1's....