3
$\begingroup$

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.

$\endgroup$
15
  • 1
    $\begingroup$ Not sure this is clear. What does "$n$ together of $3n$ letters" mean? Also, what does "the rest unlike" mean? Do you mean that the rest are neither $a$ nor $b$ or do you mean that the rest are all distinct (presumably from $a,b$ and from each other)? Perhaps you could work the problem explicitly for, say, $n=2$ to illustrate what you have in mind. $\endgroup$
    – lulu
    Aug 19, 2018 at 11:35
  • $\begingroup$ I copied the question from a source using copy and paste option. What i understood that we have to select n letters from 3n letters which has n a n b and n different letters. $\endgroup$ Aug 19, 2018 at 11:37
  • $\begingroup$ I already framed the formula and then from that step forward I am not able to solve it $\endgroup$ Aug 19, 2018 at 11:39
  • $\begingroup$ Perhaps it is a translation issue....that phrasing doesn't sound like it was written by an English speaker. Nor do I understand your formula. As I say, it would help if you would write out the case of $n=2$ explicitly...to illustrate your view of the question, if nothing else. $\endgroup$
    – lulu
    Aug 19, 2018 at 11:40
  • $\begingroup$ @lulu Suppose n=2, We have a,a,b,b,c,d. Then what is the number of ways of selecting two letters $\endgroup$ Aug 19, 2018 at 11:41

1 Answer 1

2
$\begingroup$

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}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .