Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$

share|improve this question
2  
First question: What is a subword? –  Phira May 22 '11 at 7:34
    
2nd question, contains only once or are repetitions allowed? –  Arjang May 22 '11 at 7:39
    
And could you in the future choose a title that is useful to other people? –  Phira May 22 '11 at 7:40
1  
@Arvin: If you have a problem that you are not familiar and at ease with, it is always a good idea to look at a simpler case: How many 3-letter-words contain the word TO ? How many 5-letter-words contain the word TO? –  Phira May 22 '11 at 8:23
1  
@Arvin: I assumed, since you hadn't defined what a subword was and since you said "Choose the 4 positions to put FRED in: c(11,4)", that any 4 positions would do, not necessarily 4 consecutive positions. In any case, your answer of "c(11,4) * p(26,7)" is wrong under any interpretation. –  ShreevatsaR May 22 '11 at 8:29

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

The answer that you suggest is not right, unfortunately in more than one way. Here is a concrete analysis of the problem, lengthy but I hope fairly straightforward. Your mistake was to try to use a simple formula, before carrying out an analysis of what is really going on.

How many $11$ letter words have FRED as a subword, with the letters FRED, in that order, occupying the first $4$ positions in the word? The remaining letters can be filled in $26^7$ ways, so the answer is $26^7$.

How many words have FRED as a subword, with the letters FRED, in that order, occupying positions $2$ to $5$ in the word? The remaining letters can be filled in $26^7$ ways, so the answer is $26^7$.

The same is true for the words that have FRED occupying positions $3$ to $6$, $4$ to $7$, $5$ to $8$, and so on up to $8$ to $11$.

Now it is tempting to add up, getting a total of $(8)(26^7)$. However, this will double count, for example, the words that start with FRED, then some useless letter, then FRED again, with $2$ letters added at the end. There are several other types of words that have two FRED's in them that will be double-counted.

Luckily, we don't have to worry about words that have $3$ or more occurrences of FRED. (If we were dealing with $47$-letter words, things could get very unpleasant.)

Let us find out how many double-counted words there are. We will do it slowly, and then in a slicker way.

How many "two FRED" words have the first one at the beginning? The second one can then start in any of positions $5$ to $8$, so $4$ positions in all. For each of thse choices, the remaining "useless" letters can be placed in $26^3$ ways, for a total of $(4)(26^3)$.

How many "two FRED" words have the first FRED starting at position $2$? The same reasoning as in the paragraph above shows that there are $(3)(26^3)$ such words.

How many have the first FRED starting at position $3$? Clearly $(2)(26^3)$. How many with the first FRED starting at position $4$? Clearly $(1)(26^3)$. And that's all.

So in total the number of "two FRED" words is $(10)(26^3)$.

Recall that with some double-counting, we got a total of $(8)(26^7)$. Get rid of the double counting by subtracting $(10)(26^3)$ and we get $$(8)(26^7) -(10)(26^3)$$

A slicker way: We describe another way of counting the "two FRED" words. Take some Scrabble tiles, and glue them together to form two copies of the word "FRED." Think of these as two special mega letters. To make a "two FRED" word, we take our $2$ mega letters, and $3$ ordinary letter, and put them in a row. So we are making a weird $5$-letter word. The positions of the two mega letters can be chosen in $\binom{5}{2}$ ways. For each such choice, the other letters can be filled in $26^3$ ways, for a total of $\binom{5}{2}(26^3)$. This is exactly the count of $(10)(26^3)$ that we got in a slower way earlier.

Cute, but maybe more than a little dangerous. The more plodding approach probably lets us retain greater control over what is going on.

Comment: It is all too easy to count in a plausible way that turns out to be incorrect. As a partial check, one might try to use the same reasoning on say $5$-letter words, and MO instead of FRED. Use the kind of "general" reasoning mentioned above, and compare with a detailed hand-count.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.