9
$\begingroup$

In how many ways can a selection be done of $5$ letters out of $5 A's, 4B's, 3C's, 2D's $ and $1 E$.

$ a) 60 \\ b) 75 \\ \color{green}{c) 71} \\ d.) \text{none of these} $

Number of ways of selecting $5$ different letters = $\dbinom{5}{5} = 1$ way

Number of ways to select $2$ similar and $3$ different letter = $\dbinom{4}{1}\times \dbinom{4}{3}=16$.

Number of ways of selecting $2$ similar + $2$ more similar letter and $1$ different letter = $\dbinom{4}{2}\times \dbinom{3}{1}=18$.

Number of ways to select $3$ similar and $2$ different letter = $\dbinom{4}{2}\times \dbinom{3}{1}=18$.

Number of ways to select $3$ similar and another $2$ other similar = $\dbinom{3}{1}\times \dbinom{3}{1}=9$

Number of ways to select $4$ similar and $1$ different letter = $\dbinom{2}{1}\times \dbinom{4}{1}=8$

Ways of selecting

$5$ similar letters = $1$

Total ways = $1+16+18+18+9+8+1= 71$

Well I have the solution But I am not able to fully understand it.

Or if their could be an $\color{red}{\text{alternate way}}$ than it would be great.

I have studied maths up to $12$th grade.

$\endgroup$
  • $\begingroup$ What exactly is it that you don't understand ? It has been laid out pretty clearly case by case.... $\endgroup$ – true blue anil Sep 12 '15 at 9:16
  • $\begingroup$ For example just from the second line $\dbinom{4}{1}\times \dbinom{4}{3}$ till last one $\dbinom{2}{1}\times \dbinom{4}{1}=8$ $\endgroup$ – R K Sep 12 '15 at 9:19
  • $\begingroup$ Is this the book solution ? $\endgroup$ – true blue anil Sep 12 '15 at 9:33
  • $\begingroup$ @true: Yes from book $\endgroup$ – R K Sep 12 '15 at 9:34
  • $\begingroup$ Ok, I am explaining in answer, $\endgroup$ – true blue anil Sep 12 '15 at 9:35
12
+25
$\begingroup$

If Order is Unimportant

The number of ways to choose $5$ letters (if their order is unimportant) is the coefficient of $x^5$ in $$ \begin{align} &\small\overbrace{(1+x)\vphantom{x^2}}^{1\text{ E}} \overbrace{\left(1+x+x^2\right)}^{2\text{ D's}} \overbrace{\left(1+x+x^2+x^3\right)}^{3\text{ C's}} \overbrace{\left(1+x+x^2+x^3+x^4\right)}^{4\text{ B's}} \overbrace{\left(1+x+x^2+x^3+x^4+x^5\right)}^{5\text{ A's}}\\ &=\frac{1-x^2}{1-x}\frac{1-x^3}{1-x}\frac{1-x^4}{1-x}\frac{1-x^5}{1-x}\frac{1-x^6}{1-x}\\ &=\frac{1-x^2-x^3-x^4+O\left(x^7\right)}{(1-x)^5}\\[3pt] &=\small\left[1-x^2-x^3-x^4+O\!\left(x^7\right)\right]\!\left[1+5x+15x^2+35x^3+70x^4+126x^5+210x^6+O\!\left(x^7\right)\right]\\[9pt] &=1+5x+14x^2+29x^3+49x^4+71x^5+90x^6+O\!\left(x^7\right)\tag{1} \end{align} $$ where we used the Binomial Theorem for $(1-x)^{-5}$ above.

The coefficient of $x^5$ in $(1)$ is $71$.


If Order is Important

If the order of the letters is important, we can compute the exponential generating function with $$ \begin{align} &\small\overbrace{(1+x)\vphantom{\frac{x^2}{2!}}}^{1\text{ E}} \overbrace{\left(1{+}x{+}\frac{x^2}{2!}\right)}^{2\text{ D's}} \overbrace{\!\left(1{+}x{+}\frac{x^2}{2!}{+}\frac{x^3}{3!}\right)}^{3\text{ C's}} \overbrace{\!\left(1{+}x{+}\frac{x^2}{2!}{+}\frac{x^3}{3}{+}\frac{x^4}{4!}\right)}^{4\text{ B's}} \overbrace{\!\left(1{+}x{+}\frac{x^2}{2!}{+}\frac{x^3}{3!}{+}\frac{x^4}{4!}{+}\frac{x^5}{5!}\right)}^{5\text{ A's}}\\[3pt] &=\small1+5x+24\frac{x^2}{2!}+111\frac{x^3}{3!}+494\frac{x^4}{4!}+2111\frac{x^5}{5!}+8634\frac{x^6}{6!}+O\left(x^7\right)\tag{2} \end{align} $$

The coefficient of $\frac{x^5}{5!}$ in $(2)$ is $2111$.

$\endgroup$
3
$\begingroup$

Second line: You can get 2 of a type from A,B,C or D so $4\choose 1$. Then ${4\choose3}$ to select 3 different letters from the 4 types not yet selected, and finally, apply multiplication principle.

Second last line: 4 of a type only from A or B, so ${2\choose1}$, 1 more selection from the remaining 4 types, ${4\choose 1}$, and multiply.

You should be able to understand the remaining along similar lines.

$\endgroup$
3
$\begingroup$

Let $x_i$ be the number of letter $i$ chosen for $1\le i\le 5$, where we number the letters in alphabetical order.

We want to find the number of solutions in nonnegative integers to the equation $x_1+\cdots+x_5=5$

$\hspace{.5 in}$with the restrictions $x_1\le5,\; x_2\le4, \;x_3\le3,\; x_4\le2, \;x_5\le1$.

Let $S$ be the set of all solutions, and let $A_i$ be the set of solutions with $x_i\ge7-i$ for $i=2,\cdots,5$.

Using Inclusion-Exclusion, we have that

$\hspace{.15 in}\displaystyle\big|\overline{A_2}\cap\overline{A_3}\cap\overline{A_4}\cap\overline{A_5}\big|=|S|-\sum_{i}|A_i|+\sum_{i<j}|A_i\cap A_j|-\sum_{i<j<k}|A_i\cap A_j\cap A_k|+\cdots$

$\hspace{1.53 in}=|S|-|A_2|-|A_3|-|A_4|-|A_5|+|A_4\cap A_5|$

$\displaystyle\hspace{1.53 in}=\binom{9}{4}-\binom{4}{4}-\binom{5}{4}-\binom{6}{4}-\binom{7}{4}+\binom{4}{4}=\color{red}{71}$.

$\endgroup$
3
$\begingroup$

Ok so we are breaking this down by case:

Case 1: none of our letters are the same and we pick 5 distinct letters

Case 2a: exactly 2 of the letters are the same and the other 3 are distinct.

Case 2b: 2 of the letters are the same, 2 others are the same, and the fifth is distinct.

Case 3a: exactly 3 of the letters are the same and the other 2 are distinct.

Case 3b: exactly 3 of the letters are the same and the other 2 are also the same.

Case 4: exactly 4 of the letters are the same and the other 1 is distinct.

Case 5: all 5 letters are the same.

We see that any combination must be one of these $5$ cases, and there is no overlap in the $5$ cases. Thus we are going to sum up the number of total possibilities for each case.

Case 1: If we pick $5$ distinct letters, we pick one of each letter, so there is only $1$ way to do this.

Case 2a: First lets count the ways to pick the $2$ letters which are the same. It can't be E, so there are only $4$ ways to pick them. Second, we must pick $3$ more from the remaining $4$ letters (none of these can be the same letter as the first $2$ since that would be a different case). Thus we use $4$ choose $3$, which turns out to be $4$ options. We multiply these together to see that we have $4\times 4=16$ options for case 1.

Case 2b: We are now picking two pairs from four possible letters which have sufficient quantities. Thus the ways to pick the two pairs is $4$ choose $2$. The fifth letter is any of the remaining $3$ letters, so we have $6\times 3=18$ for this case.

Case 3a: Similarly, there are only $3$ ways to pick $3$ matching letters. Then we proceed to pick the other $2$ from $4$ choices, so we multiply $3$ by $4$ choose $2$ to get $3\times 6=18$ options for case 3.

Case 3b: There are $3$ ways to pick the triplet and the other pair only has $3$ options also, since it can't be the same letter as the triplet (that would be case 5). Thus there are $3\times 3=9$ possibilities.

Case 4: Hopefully you follow the pattern: there are only $2$ ways to pick $4$ of the same letter, and $4$ ways to pick the fifth letter, so we have $2\times 4=8$ for this case.

Case 5: Finally, there is only one way to pick $5$ of the same number.

Summing those together we get $1+16+18+18+9+8+1=71$ options. For me, this is the most straightforward approach once you understand it.

$\endgroup$
1
$\begingroup$

Well, you could just hammer through all of the possibilities. (You'll also appreciate why the shortcuts are there.)

Number of ways of selecting 5 different letters:
ABCDE (1)

Number of ways to select 2 similar and 3 different letter:
AABCD AABCE AABDE AACDE
BBCDE ABBCD ABBCE ABBDE
ACCDE ABCCD ABCCE BCCDE
ABCDD ABDDE ABCDD BCDDE (16)

Number of ways of selecting 2 similar + 2 more similar letter and 1 different letter:
AABBC AABBD AABBE
AACCD AACCE AABCC
AABDD AACDD AADDE
BBCCD BBCCE ABBCC
ABBDD BBCDD BBDDE
ACCDD BCCDD CCDDE (18)

Number of ways to select 3 similar and 2 different letters:
AAABC AAABD AAABE AAACD AAACE AAADE
ABBBC ABBBD ABBBE BBBCD BBBCE BBBDE
ABCCC ACCCD ACCCE BCCCD BCCCE CCCDE (18)

Number of ways to select 3 similar and another 2 other similar:
AAABB AAACC AAADD
AABBB BBBCC BBBDD
AACCC BBCCC CCCDD (9)

Number of ways to select 4 similar and 1 different letter:
AAAAB AAAAC AAAAD AAAAE
ABBBB BBBBC BBBBD BBBBE (8)

Number of ways to select 5 similar letters:
AAAAA (1)

Let's look at just one of these sets to see if we can get a feel for the nomenclature:

Number of ways to select 3 similar and 2 different:

$$\dbinom{4}{2}\times \dbinom{3}{1}=18$$

This is read "$4$ choose $2$ times $3$ choose $1$." This is shorthand for:

$$\frac{4!}{2!(4-2)!}\times\frac{3!}{1!(3-1)!}$$

which is shorthand for:

$$\frac{4\times 3\times 2 \times 1}{2 \times 2 \times 1} \times \frac{3\times 2 \times 1}{1 \times 2 \times 1} = 18$$

Okay, but why?

One of those "chooses" refers to the 2 similar, and the other to the 3 similar. Note that they are all laid out in 3 groups of 6.

Perhaps I will come back later to go over the theory in more detail....

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.