Question

Consider all length-13 strings of all uppercase letters. Letters may be repeated.

(a) How many such strings are there?
(b) How many such strings contain the word CHARITY?

(c) How many contain neither the word CHARITY nor the word HORSES?

For a, I got 26^13, since there are 13 possible spaces for the string and each space has 26 choices. For part b I just got 26^6, since I treated CHARITY as 1 block and then there was 6 other available spaces. For c, I did 26^13 - 26^6 - 26^7 since it wanted the amount without the two words. I wanted to check my thought process, since I am unsure if we need to multiply the answers by how many avaliable elements there are.

Answer 1

a. Your answer is correct, 26 choices for each of 13 positions, so $\boxed{26^{13}}$ total possible strings.

b. You have the right idea, but your method only counts one type of permutation, like

C H A R I T Y _ _ _ _ _ _

but doesn't account for other arrangements like

_ _ _ C H A R I T Y _ _ _

or

_ _ _ _ _ C H A R I T Y _

Treating CHARITY as one letter, we're then considering strings of length 7 (6 open slots plus this string), which we can arrange in 7! different ways. So the total number of such strings is $\boxed{7!26^6}$.

c. This one is a bit more involved. I would go about it by counting the number of strings containing CHARITY but not HORSES, HORSES but not CHARITY, and both CHARITY and HORSES.

• CHARITY but not HORSES

As we know from part (a), there are $7!26^6$ strings containing CHARITY, but the string HORSES can be found whenever there are 6 open slots to either side of CHARITY, i.e. in strings of either form

C H A R I T Y _ _ _ _ _ _

or

_ _ _ _ _ _ C H A R I T Y

Then there are 2 strings that we want to remove from the count, giving $7!26^6-2$ such strings.

• HORSES but not CHARITY

Reasoning as we did in part (b) suggests that there are $8!26^7$ possible strings containing HORSES, and reasoning as we did in the previous case suggests only 2 of these contain CHARITY, giving a total of $8!26^7-2$ such strings.

• CHARITY and HORSES

There are 2 such strings,

C H A R I T Y H O R S E S

H O R S E S C H A R I T Y

Then by the inclusion-exclusion principle, the number of strings containing either CHARITY or HORSES is $(7!26^6-2)+(8!26^7-2)-2=7!26^6209-6$.

Finally, the number of strings containing neither CHARITY nor HORSES is complementary to the number of strings containing either of them, so the total is $26^{13}-(7!26^6209-6)=\boxed{26^{13}-7!26^6209+6}$.