Answer to Question #266774 in Discrete Mathematics for Nomas

Question

Consider all strings of length 12, consisting of all uppercase letters. Letters may be repeated. Please do not simplify your answers.

(a) How many such strings are there?

(b) How many such strings contain the word ”SCOOBY”?

(c) How many such strings contain neither the word ”SCOOBY” nor the word ”DAPHNE”?

Answer 1

(a)There are 26 letters from which we choose, order of characters in strings is important and we can repeat same characters in one string, so we have 26 variants for all of 12 characters of string, so exist 26¹² strings.

(b)At first consider number of strings, which begins with SCOOBY. Since remained length of string is 6 and we can place any combination of 6 letters after SCOOBY, there are 26⁶ strings which begins with SCOOBY. We start substring SCOOBY from any position from 1 to 7, so there are 7*26⁶ variants, but now we count string SCOOBYSCOOBY twice, first time we place substring in first position, second - in in seventh, so answer is 7*26⁶-1.

(c)If we need to now how many strings don't contain specific word, we can count how many string contain specific word and substract this number from number of all strings.

As we already counted, 7*26⁶-1 strings contain word SCOOBY. Since length word DAPHNE is same as length of world SCOOBY, number of strings, which contain word DAPHNE is also 7*26-1. But we cannot simply add this numbers, to obtain number of strings which contain word SCOOBY or DAPHNE, because some strings can contain both words and this strings will be counted twice. There are two strings which contain both words - SCOOBYDAPHNE and DAPHNESCOOBY, so number of strings which contains word SCOOBY or word DAPHNE is 14*26⁶-4. Knowing number of strings which contains at least one of words SCOOBY and DAPHNE we obtain number of strings which contain neither of them substracting their number from number of all strings, which gives us 26¹²-14*26⁶+4=26⁶(26⁶-14)+4