10
$\begingroup$

How many sequences are there of five lowercase letters that includes at least one vowel (a, e, i, o, u)?

What is erroneous about the following solution?

There are five choices for the certain vowel and $26$ choices for each of the remaining four letters. The certain vowel can appear in any of the five spaces. Therefore, the number is $5\times26^4\times5=11{,}424{,}400$.

This number differs from the solution $26^5-21^5=7{,}797{,}275$.

$\endgroup$
23
$\begingroup$

"There are five choices for the vowel and $26$ choices for each of the remaining four letters. The certain vowel can be in appear in any of the five spaces."

If the "certain" vowel is in the first position, then your sequence could be "aeghp", and if the "certain" vowel is in the second position, then your sequence could be "aeghp". So you're counting that same sequence twice, and similarly with lots of others.

However, you you subtract the number of sequences with no vowels from the total number of sequences, that does it: the problem described above does not happen. Thus $26^5 - 21^5$.

$\endgroup$
  • 1
    $\begingroup$ While some of the other answers were very helpful, this solution most clearly demonstrates how the overcounting happens with the erroneous solution. $\endgroup$ – Joel Christophel Nov 21 '14 at 4:00
9
$\begingroup$

Hint: Make the numbers smaller and you can see for yourself what's wrong with your erroneous solution.

How many sequences are there of two letters from the alphabet $\{a,b,e\}$ that contain at least one vowel?

Correct solution: There are $3^2=9$ two-letter words, there is $1^3=1$ word with no vowels, so $9-1=8$ words with at least one vowel.

Erroneous solution: There are $2$ choices for the vowel and $3$ choices for the other letter. The vowel can appear in either of the two spaces. Therefore, the number is
$2\times3\times2=12$.

Why, you ask, does doing it with smaller numbers make it any easier to find the mistake? Well, you can actually list the $12$ sequences that you counted with the second method, and then you can see which ones were double-counted.

$\endgroup$
  • 1
    $\begingroup$ +1 for the suggestion to test the idea in a smaller case. $\endgroup$ – Jyrki Lahtonen Nov 21 '14 at 15:39
  • 1
    $\begingroup$ An even smaller case of the alphabet $\{e\}$ would also suffice to show the error (though wouldn't be as enlightening). $\endgroup$ – Milo Brandt Nov 21 '14 at 18:14
6
$\begingroup$

The problem is that it overcounts cases in which the remaining $4$ letters have vowels among them.

You could fix this by doing casework on the number of vowels. You'd have five terms corresponding to the five possibilities ($1$ vowel, $2$ vowels, etc.), where the number $21$ would show up a bunch because the non-vowels would have $21$ possibilities. But there's a much easier way.


We can count the number of sequences with no vowels, and subtract this from the total number of sequences. There are $21$ non-vowels and $26$ letters, so we get

$$26^5-21^5 =\boxed{7797275}$$

$\endgroup$
  • 1
    $\begingroup$ it's just nice to complete it :) $\endgroup$ – Zubin Mukerjee Nov 21 '14 at 3:50
3
$\begingroup$

You are counting the number of ways to create a word with exactly 1 vowel. What you want to do is count the number of total words on five letters: $26^5$, and subtract the number of words with only consonants: $(26-5)^5 = 21^5$.

$\endgroup$
  • 1
    $\begingroup$ Actually, the number of words with exactly one vowel would be $5 \cdot 21^4 \cdot 5$. He's just overcounting the number of words with at least $1$ vowel. $\endgroup$ – Zubin Mukerjee Nov 21 '14 at 3:49
  • $\begingroup$ @ZubinMukerjee You're correct :) I clearly didn't read the question properly. $\endgroup$ – Johanna Nov 21 '14 at 3:51
  • 1
    $\begingroup$ no worries, not sure why someone downvoted you, since your explanation of the proper answer is still correct. +1 $\endgroup$ – Zubin Mukerjee Nov 21 '14 at 3:55
  • $\begingroup$ My rationale behind the downvote was that the part of this response aimed at answering my question was incorrect. I already knew the correct method, which I cited in my question. $\endgroup$ – Joel Christophel Nov 21 '14 at 3:58

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.