Find the number of combination of 'n' together of '3n' letters

1.1k Views Asked by At

Find the number of ways of selecting n letters from 3n letters which contains 'n' a s , 'n' b s and the rest n letters are distinct from each other.

From the language of the problem I can easily understood that we need to select n letters.

I will categorize it into three category using $C(n,r) = \frac{n!}{(n-r)!r!}$

I will use $C(n,\ r_1)*C(n,\ r_2)*C(n,\ r_3)$,

$\ r_1$ =a group, $\ r_2$ =b group & $\ r_3$ =unlike group

Where $\ r_1+\ r_2 +\ r_3 =n$ I presume that i am on the right approach but I am not able to proceed hence forth.

1

There are 1 best solutions below

0
On BEST ANSWER

You've already provided the answer in a comment: $(n+2)2^{n-1}$.

Here's an algebraic proof: There are $k+1$ ways to select $k$ a's and b's, and then there are $\binom nk$ ways to choose the distinct letters you don't select. Thus the desired count is

\begin{eqnarray*} \sum_{k=0}^n(k+1)\binom nk &=& \left[\frac\partial{\partial q}\sum_{k=0}^n\binom nkq^{k+1}\right]_{q=1} \\ &=& \left[\frac\partial{\partial q}\left(q(1+q)^n\right)\right]_{q=1} \\ &=& 2^n+n2^{n-1}\;. \end{eqnarray*}

Here's a combinatorial proof: The selections without b's correspond to the $2^n$ subsets of the $n$ distinct letters. (Add the right number of a's to such a subset, and you get a unique selection without b's.) Now consider the selections with at least one b. Each contains a proper subset $S$ of the $n$ distinct letters, and the number of elements not contained in $S$ is the number of choices for the non-zero number of b's to add. Thus, the choice of the non-zero number of b's corresponds to distinguishing one of the distinct letters not contained in $S$. Thus, the selections with at least one b are in bijection with the ways to distinguish one of the distinct letters ($n$ choices) and to choose a subset of the remaining distinct letters ($2^{n-1}$ choices). Hence the total number of selections is $2^n+n2^{n-1}$.