Question

The number of ways of selecting $n$ objects out of $3n$ objects, $n$ of which are alike and the rest different is\[\]
A.${{2}^{2n}}-\sum\limits_{0\le i < j\le n}{{{C}_{i}}{{C}_{j}}}$ \[\]
B.${{2}^{2n-1}}-\sum\limits_{0\le i < j\le n}{{{C}_{i}}{{C}_{j}}}$\[\]
C.$\sum\limits_{0\le i < j\le n}{{{C}_{i}}{{C}_{j}}}$\[\]
D. None of these \[\]

Answer 1

Hint: We recall that we can select $r$ objects from $n$ distinct objects in ${}^{n}{{C}_{r}}$ ways and we can select $r$ objects from $n$ identical or alike objects in 1 way. We find a number of ways for selecting 0 objects from $n$ alike objects and $n$ distinct objects from $2n$ distinct objects. We increase the number of alike objects by 1and continue the process. We find the number of ways we can select is ${}^{2n}{{C}_{0}}+{}^{2n}{{C}_{1}}+...+{}^{2n}{{C}_{n}}$. We use the sum of binomial coefficients and simplify.\[\]

Complete step-by-step answer:
We are given in the question that there are $3n$ objects out of which $n$ are alike. So the number of distinct objects is $3n-n=2n$. We are asked to select $n$ objects.

 We can select $n$ objects by selecting select 0 alike object from $n$ alike objects in 1 way and $n$ distinct objects from $2n$ distinct objects in ${}^{2n}{{C}_{n}}$ ways, so by rule of product $1\times {}^{2n}{{C}_{n}}={}^{2n}{{C}_{n}}$ ways.
Similarly we can select $n$ objects by selecting select 1 alike object from $n$ alike objects in 1 way and $n-1$distinct objects from $2n$ distinct objects in ${}^{2n}{{C}_{n-1}}$ ways, so by rule of product $1\times {}^{2n}{{C}_{n-1}}={}^{2n}{{C}_{n-1}}$ ways.\[\]
We can continue this process by increasing number alike objects by 1 up to $n$ alike objects. We can select $n$ objects by selecting select $n$ alike object from $n$ alike objects in 1 way and 0 distinct objects from $2n$ distinct objects in ${}^{2n}{{C}_{0}}$ ways, so by rule of product $1\times {}^{2n}{{C}_{0}}={}^{2n}{{C}_{0}}$ ways.
So total number of ways is
\[{}^{2n}{{C}_{n}}+{}^{2n}{{C}_{n-1}}+...+{}^{2n}{{C}_{0}}={}^{2n}{{C}_{0}}+{}^{2n}{{C}_{1}}+...+{}^{2n}{{C}_{n}}\]
We know that sum of binomial coefficients is given by
\[{}^{2n}{{C}_{0}}+{}^{2n}{{C}_{1}}+...+{}^{2n}{{C}_{n}}+{}^{2n}{{C}_{n+1}}+...+{}^{2n}{{C}_{2n}}={{2}^{2n}}........\left( 1 \right)\]
Let us denote
\[\begin{align}
  & S={}^{2n}{{C}_{0}}+{}^{2n}{{C}_{1}}+...+{}^{2n}{{C}_{n}} \\
 & {{S}^{'}}={}^{2n}{{C}_{n+1}}+...+{}^{2n}{{C}_{2n}} \\
\end{align}\]
We use relation between binomial coefficients ${}^{n}{{C}_{k}}={}^{n}{{C}_{n-k}}$ in the above step for ${{S}^{'}}$ and have;
\[\begin{align}
  & {{S}^{'}}={}^{2n}{{C}_{n+1}}+{}^{2n}{{C}_{n+2}}...+{}^{2n}{{C}_{2n}} \\
 & \Rightarrow {{S}^{'}}={}^{2n}{{C}_{2n-\left( n+1 \right)}}+{}^{2n}{{C}_{2n-\left( n+2 \right)}}+...+{}^{2n}{{C}_{2n-2n}} \\
 & \Rightarrow {{S}^{'}}={}^{2n}{{C}_{n-1}}+{}^{2n}{{C}_{n-2}}+...+{}^{2n}{{C}_{0}} \\
\end{align}\]
Let us add and subtract ${}^{2n}{{C}_{n}}$ in the right hand side of the above step to have;
\[\begin{align}
  & \Rightarrow {{S}^{'}}={}^{2n}{{C}_{n}}+{}^{2n}{{C}_{n-1}}+{}^{2n}{{C}_{n-2}}+...+{}^{2n}{{C}_{0}}-{}^{2n}{{C}_{n}} \\
 & \Rightarrow {{S}^{'}}={{2}^{2n}}-{}^{2n}{{C}_{n}} \\
\end{align}\]
We put $S,{{S}^{'}}$ in equation (1) t o have;
\[\begin{align}
  & S+S-{}^{2n}{{C}_{n}}={{2}^{2n}} \\
 & \Rightarrow 2S={{2}^{2n}}+{}^{2n}{{C}_{n}} \\
 & \Rightarrow S=\dfrac{{{2}^{2n}}}{2}+\dfrac{{}^{2n}{{C}_{n}}}{2} \\
 & \Rightarrow S={{2}^{2n-1}}+\dfrac{\left( 2n \right)!}{2{{\left( n! \right)}^{2}}} \\
\end{align}\]
So it is proved that the number of ways of selecting $n$ objects out of $3n$ objects, $n$ of which are alike and the rest different is
\[{}^{2n}{{C}_{0}}+{}^{2n}{{C}_{1}}+...+{}^{2n}{{C}_{n}}={{2}^{2n-1}}+\dfrac{\left( 2n \right)!}{2{{\left( n! \right)}^{2}}}\]
We know the result that $\sum\limits_{0\le i < j\le n}{{{C}_{i}}{{C}_{j}}}={{2}^{2n-1}}-\dfrac{\left( 2n \right)!}{2{{\left( n! \right)}^{2}}}$. Hence the correct option is D.\[\]

So, the correct answer is “Option D”.

Note: We note that the binomial expansion is expanded upon two terms say $x,y$ and integral exponents $n$ is given by ${{\left( x+y \right)}^{n}}={}^{n}{{C}_{0}}{{x}^{n}}{{y}^{0}}+{}^{n}{{C}_{1}}{{x}^{n-1}}{{y}^{1}}+...+{}^{n}{{C}_{n}}{{x}^{0}}{{y}^{n}}$. The coefficients appearing in the expansion are called binomial coefficients and their sum is 2 to the power the integral exponent that is ${}^{n}{{C}_{0}}+{}^{n}{{C}_{1}}+...+{}^{n}{{C}_{n}}={{2}^{n}}$. We can also express the obtained result as$\sum\limits_{0\le i\le j\le n}{{{C}_{i}}{{C}_{j}}}={{2}^{2n-1}}+\dfrac{\left( 2n \right)!}{2{{\left( n! \right)}^{2}}}$.