# Enumeration problems

• Oct 11th 2009, 05:06 PM
melody
Enumeration problems
(a) How many strings of length 3 can be formed from the alphabet {'0' ,....., '9'} if each string must include '5' or '6'?

(b) We would like to use our standard English lower-case alphabet of 26 letters 'a', 'b',.....,'z' to form at least 300,000 words of equal length where no letter is repeated within a word.
What is the minimum length word that will suffice?

(c) In how many ways can a group of thirteen people be divided into two groups containing five people and a third group containing three people?

My english is weak, can someone explain to me how to do (a) and (b) please! thank you

for (c), it is very confused me, why there has a third group??
• Oct 12th 2009, 01:08 AM
Hello melody
Quote:

Originally Posted by melody
(a) How many strings of length 3 can be formed from the alphabet {'0' ,....., '9'} if each string must include '5' or '6'?

(b) We would like to use our standard English lower-case alphabet of 26 letters 'a', 'b',.....,'z' to form at least 300,000 words of equal length where no letter is repeated within a word.
What is the minimum length word that will suffice?

(c) In how many ways can a group of thirteen people be divided into two groups containing five people and a third group containing three people?

My english is weak, can someone explain to me how to do (a) and (b) please! thank you

for (c), it is very confused me, why there has a third group??

(a) The total number of strings of length 3 is $\displaystyle 10^3$, since there are 10 choices of character in each position (assuming that repetition is allowed).

If neither '5' nor '6' is allowed, there are $\displaystyle 8^3$ strings, since there are now only 8 choices for each position. So the total number that include a '5' or '6' (or both) is $\displaystyle 10^3 - 8^3 = 488$.

(b) If we choose $\displaystyle r$ items from $\displaystyle n$ different ones (where we're not allowed to choose the same item more than once) and then re-arrange them in order (this is called the number of permutations of $\displaystyle r$ items from $\displaystyle n$), the number of ways of doing this is $\displaystyle {^nP_r} = \frac{n!}{(n-r)!}$. We need to do this with the 26 letters, in such a way that the number of choices is at least 300,000. So we want the lowest value of $\displaystyle r$ for which $\displaystyle \frac{26!}{(26-r)!}\ge300000$.

Using a calculator (or other aid) the lowest value of $\displaystyle r$ is found by trial to be $\displaystyle r = 4$.

(c) The question is this: From a group of 13 people, a group of five is chosen. Then from the remaining 8 people a second group of five is chosen, with the remaining 3 then forming a third group. So the original group of 13 has been divided into two groups of five, plus a group of three.

Here we use $\displaystyle \binom{n}{r} ={^nC_r} = \frac{n!}{r!(n-r)!}$ to find the number of selections of $\displaystyle r$ items from $\displaystyle n$, where the order within the selection doesn't matter. The order in which we choose our groups of 5, 5 and 3 doesn't matter either, but there is a small problem to be overcome that arises because two of the groups are the same size.

Because of this problem, I think it's easier to understand if we choose the group of 3 first. This can be done in $\displaystyle {^{13}C_3} = 286$ ways.

We are left with a group of 10 that must be split into 2 groups of 5. The number of ways of choosing 5 from 10 is $\displaystyle {^{10}C_5} = 252$. But we need to realise that for every group of 5 that is chosen, another group of 5 is formed by those that are left over. So in the $\displaystyle 252$ ways, each group will be chosen twice. So we must divide by 2 to find the number of different ways of splitting the 10 into two groups of 5. This gives $\displaystyle 126$ ways.

So the total number of ways of forming groups of 5, 5 and 3 from the original $\displaystyle 13$ is $\displaystyle 286 \times 126 = 36036$.