0
$\begingroup$

For the problem of finding the number of strings of eight English letters that start and end with X that contain at least one vowel, if letters can be repeated, I tried to come up with a solution but it does not match the solution in the book. I am having a hard time wrapping my head around this.

What I tried: Since there are 8-2 positions (the 2 X's), for the 6 positions, there are 5 vowels and $21^5$ consonants. This would mean that there are $5*6*21^5 = 122523030$ strings.

The solution says the answer is $26^6 - 21^6 = 223,149,655 $. Wouldn't this solution just be the number of ways all letters can be positioned subtracted by number of ways all consonants can be positioned? I'm having a hard time understanding why this would be the solution.

$\endgroup$
1
  • $\begingroup$ You counted the words that have exactly on vowel and the rest of the conditions. They wanted and counted the words that have at least one vowel and the rest of the conditions. $\endgroup$
    – user545497
    Mar 27 '18 at 3:40
1
$\begingroup$

Trying to build by hand as you have is tough; for instance, you have not accounted for any such strings that have 2 vowels in them, or 3, etc.

Instead, lets try an old trick and count the number of ways we can fail, instead of succeed. What does a failure look like? It looks like a string with no vowels at all.

So, how many strings are there with no vowels? Just place consonants (21 of these) into the 6 positions (for a total of $21^6$ strings). Well how many strings were possible to begin with? There were 6 free positions, so out of $26^6$ possible strings, only $21^6$ were bad.

$\endgroup$
6
  • $\begingroup$ Oh I think I understand now. So it would be total # of strings with all letters = # of strings without vowels + # of string with at least one vowel. How would I be able to write this out with the multiplication rule without using the subtraction rule? In other words, how would I be able to fix 5∗6∗21^5 so it accounts for repeated 5's? $\endgroup$
    – Joe
    Mar 27 '18 at 3:48
  • $\begingroup$ @Joe To avoid using this "subtraction rule" you would have to use what is known as an inclusion exclusion argument, and I think you would find it tedious. You could write down an expression for all strings with at least one vowel, realize you have over-counted, then subtract off all strings with at least 2 vowels, realize you have under-counted, then add in all strings with at least 3 vowels, realize you have over-counted, etc. See this page: en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle $\endgroup$
    – Valborg
    Mar 27 '18 at 3:52
  • $\begingroup$ @Joe Or, you could try to write down expressions for all string with exactly one vowel, exactly 2 vowels, etc, and then add them all up. This would be easier here I think, but still tedious. $\endgroup$
    – Valborg
    Mar 27 '18 at 3:53
  • $\begingroup$ Thanks for the help! It really helped with the understanding. One last question and this one might be pretty dumb but since repetition of vowels are allowed, what error is made when we simply 5^6 * 6 * 21^5, just like we do for the consonants? What would I be counting here? $\endgroup$
    – Joe
    Mar 27 '18 at 4:00
  • $\begingroup$ @Joe I don't know what that counts... you have a factor of 6 from (presumably) choosing a location for a single vowel, but then you place the vowels freely in all 6 spaces (the 5^6), and then you place consonants in 5 other places? The moral here is probably don't re-use expressions during counting arguments, and instead re-derive every time. $\endgroup$
    – Valborg
    Mar 27 '18 at 4:02
0
$\begingroup$

There are only $6$ letters to make decision for. The book solution consider the number of length $6$ strings without restriction subtract away strings without any vowel (that is the complement of at least one vowel).

For your approach, you chose a single vowel, choose a position to place it and then fill the rest with consonants but remember it is possible to have more than one vowel.

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