[Math] Counting 11 letter words with subword “FRED” – check the answer

combinatorics

I'm preparing for an exam and just want to make sure I am getting things correctly.

How many 11-letter 'words' constructed from the 26 letters of the english alphabet contain the subword "FRED" Where 'words' are just any string of 11 letter words (does not have to be a word in the dictionary)

a subword is a word inside another word. So an 11 letter word must have the word "FRED" in it, so FREDAABBCDEF is allowed, or XYZFREDABBC

My answer:
FRED contains 4 letters, so:

Choose the 4 positions to put FRED in: $c(11,4)$
Choose the remaining 7 letters (can be any repeatable letters): $p(26,7)$

So we have $c(11,4) * p(26,7)$

Best Answer

You double-count words. This is a very frequent error in this sort of problems, where you fix some positions to have a specific value, and choose freely the values for the other positions. The problem is that those other positions may also have the specific value, and so you'll double count the solution.

Here is a simple example: Count all binary words that contain at least one occurrence of 1. There are 3 of them, of course: 11,01,10 (but not 00). However, your method yields 4: You choose a place in which to place "1" (2 choices: either first or last letter) and then you choose the value of the other position (2 choices: 0 or 1). It is easy to see that you count "11" twice.

Usually such problems are solved using the Inclusion-Exclusion principle.

Related Question