Why do I get two different answers for this counting problem?

Suppose that we consider English alphabets so we have 26 letters which 5 of them are vowels. I want to find all three letters sequences that contain at least one vowel.

My first approach is $$26^3-21^3=8315$$ which is the number of all three lettres sequences minus the number of three letter sequences which do not contain vowels.

Second approach: at least one vowel means one vowel or two vowels or three vowels so the answer is $$(5\cdot21^2)+(5^2\cdot21)+5^3=2855$$.

Why are these two answers different?

• Nearly right, you're only missing factors of C(3,1) and C(3,2) on the terms respectively. So that you handle the possibilities CCV, CVC, VCC and CVV, VCV, VVC. – smci Apr 4 at 20:36
• Also, you could have intuited those terms by considering the binomial expansion $(21 + 5)^3$ – smci Apr 4 at 20:37

Take the number of all three letter words, $$26^3$$, and subtract from it the number that have only consonants, $$21^3$$.

Your second method does not address all possible sequences of vowels, such as vowel-consonant-vowel or vowel-vowel-consonant or consonant-vowel-vowel...

• I get it. Thanks so much – user660730 Apr 4 at 4:52
• It's only missing factors of C(3,1) and C(3,2) on the terms respectively. – smci Apr 4 at 20:35

It is worth noting that to count properly with the second approach, you would have to write $$3 \cdot 5 \cdot 21^2 + 3 \cdot 5^2 \cdot 21 + 5^3 = 8315.$$ The first term counts all cases where there is exactly one vowel, and there are three positions for the location of this vowel. The second term counts all cases where there are exactly two vowels, and there are three positions for the location of the sole consonant. The third term counts all cases where there are exactly three vowels, but we do not multiply by three because all three letters are of the same type. You only have to consider the ordering of the types of letters (vowel vs. consonant) when there is more than one type of letter used.

When wondering why (or if) something is wrong, a general approach is to make the numbers as small as you can while still maintaining the error but so that you can brute-force the answer. So let's try an alphabet with one vowel A and one consonant B. (Note that this way you can never prove that something is correct, but it's a valuable tool for finding some errors.)

You get 1 word with no vowels (BBB), 3 words with one vowel (ABB, BAB, BBA), 3 words with two vowels (AAB, ABA, BAA), and 1 word with three vowels (AAA). Your first approach finds the correct number, $$2^3-1^3=7$$.

However, the second approach claims for example that there is only $$1 \cdot 1^2 = 1$$ word with exactly one vowel. From here, you can try to see why it gives the wrong answer work (which has already been answered by the other answers).

Refer to Binomial Expansion

$$(21+5)^3=21^3+\tbinom 31\cdotp 21^2\cdotp5+\tbinom 32\cdotp21\cdotp 5^2+5^3$$

so$$26^3-21^3= (3\cdot21^2\cdotp 5)+(3\cdot21\cdotp 5^2)+5^3$$

The binomial coefficients count the ways to select elements from a set.

In your case, that is positions to place the vowels in the word.

There are $$3\cdot21^2\cdotp 5$$ ways to select 1 vowels and two consonants where the vowel is in the first, second, or third place. And so on.

From a generating function perspective, if $$V$$ is the number of vowels, $$C$$ is the number of consonants, and $$L$$ is the total number of letters, then we have that the number of ways to have one vowel followed by two consonants is $$VCC$$, or $$5*21*21$$. We also have $$CVC$$ and $$CCV$$. Since multiplication is communative, we have that $$VCC+CVC+CCV=3VCC$$, so adding those together gives $$3VCC$$, or $$3*5*21*21$$. Similarly, for two vowels we have $$3VVC=3*5*5*21$$. For $$VVV$$, there's no other way to arrange the order, so it's just $$1*5*5*5$$.

So your error was in calculating only $$VCC$$. That is, you calculated the number of ways of getting a particular order, and didn't take into account the different orders possible.

We can also look at what happens when we take the total number of sequences, $$L^3$$. This is equal to $$(C+V)^3$$. That gives eight terms, $$CCC, CCV, CVC, CVV, VCC, VCV, VVC, \text{and } VVV$$. Collecting terms that are equivalent up to commutation gives us the binomial formula results: $$C^3+3C^2V+3CV^2+V^3$$. Subtracting off $$C^3$$ gives $$3C^2V+3CV^2+V^3$$.

In your second case $$(5\cdot21^2)+(5^2\cdot21)+5^3=2855$$, the first term represents selecting 1 vowel and any two constants. But this represents ABB, BAB, and BBA as one entity, so multiply it by 3 since the vowel could be in any position. Likewise the second term represents one constant and any combinations of vowels, but the constant can be in any of the three positions, so multiply that by 3 as well.

$$3(5\cdot21^2)+3(5^2\cdot21)+5^3=2855 = 8315$$

For the first term, you can represent vowel, constant, constant as $$5\cdot21\cdot21$$, constant, vowel, constant as $$21\cdot5\cdot21$$, and constant, constant, vowel as $$21\cdot21\cdot5$$, adding those together gives you $$3(5\cdot21^2)$$