Fdtxjr

The problem goes like this (8.6 #17 Precalc with limits aga 5th edition):

Typically radio stations are identified by four "call letters." Radio stations east of the Mississippi River have call letters that start with the letter W and radio stations west of the Mississippi River have call letters that start withe the letter K.

(a) Find the number of different sets of radio station call letters that are possible in the United States.

(b) Find the number of different sets of radio station call letters that are possible if the call letters must include a Q.

Textbook's answers:

a) 35152

b) 3902

When I did the problem for (b), I got the answer by $2 cdot 3 cdot 26 cdot 26 = 4056$. This means that the first letter can either be a K or W (2), and the Q can be placed anywhere in the other three spots (3), and the other two spots can be filled with any letter of the alphabet ($26 cdot 2$). What am I doing wrong here that makes my answer not match up with the textbook answer (or the other way around)? Am I over counting?

edit: The textbook solution said that the answer came from subtracting the non-Qs from the total amount ((answer from (a)) $- (2 cdot 25^3)$).

The book's method of using complementary counting is the optimal way to solve the problem of counting sequences of radio station call letters that contain at least one Q.

As Daniel Mathias indicated in the comments, you counted sequences with more than one Q multiple times.

A direct count

Sequences of call letters with exactly one Q: Since the first position must be filled with a K or a W, there are two ways to fill it. There are three ways to choose the position of the only Q. Each of the remaining positions may be filled with one of the other $25$ letters. Hence, there are $2 cdot 3 cdot 25 cdot 25 = 3750$ such sequences.

Sequences of call letters with exactly two Qs: As above, there are two ways to fill the first position. There are $binom32$ ways to select two of the other three positions for the Qs. The remaining position can be filled with one of the other $25$ letters. Hence, there are $2 cdot binom32 cdot 25 = 150$ such sequences.

Sequences of call letters with exactly three Qs: There are two ways to fill the first position. The remaining three positions must be filled with Qs. Hence, there are $2$ such sequences, namely KQQQ and WQQQ.

Total: Since the three cases above are mutually exclusive and exhaustive, the number of permissible sequences of call letters is $3750 + 150 + 2 = 3902$.

Correcting your count

You chose the first letter, the position of a Q, and then filled the remaining two positions with any of the $26$ letters, which gave you a count of $2 cdot 3 cdot 26 cdot 26$ for sequences that contain a Q.

However, you have counted sequences with two Qs such as KQRQ twice, once for each way you could have designated one of those Qs as the Q in the sequence. Since we only want to count sequences with two Qs once, we must subtract them from the total.

We count sequences with two Qs. We still have two ways of choosing the first letter. We now have $binom32$ ways to select the positions of the two Qs. We also have $26$ ways to select the letter that goes in the remaining position. Hence, there are $2 cdot binom32 cdot 26$ sequences that contain two Qs.

Subtracting these from the total gives us a running count of $2 cdot 3 cdot 26 cdot 26 - 2 cdot binom32 cdot 26$.

However, we have subtracted too much. We only want to count sequences with three Qs once. However, we counted them three times in your original count, once for each way we could have designated one of those Qs as the Q that is contained in the sequence. We also subtracted three times, once for each of the $binom32$ ways we could have designated two of them as the two Qs in the sequence. Thus, we have not yet counted them at all. Therefore, we need to add them to the total.

As we saw above, there are two possible sequences of call letters with three Qs.

Thus, the number of permissible sequences of call letters is
$$2 cdot 3 cdot 26 cdot 26 - 2 cdot binom32 cdot 26 + 2 = 4056 - 156 + 2 = 3902$$

This method of counting uses the Inclusion-Exclusion Principle.