# Combinatorics question involving having a fixed subword

Words of $20$ letters are constructed from the English Alphabet. How many such words contain the subword DISCRETE?

Can someone give a detailed explanation for this?
This is what I did: Fix a subword 'DISCRETE' and treat this as one letter.
Then,we require 12 other letters. This can be chosen in $26^{12}$ ways. Then, once picking these letters, we can arrange the entire $20$-letter word in $13!$ ways.
So total is $13! \times 26^{12}$.

• I'm afraid you double counted those situations where DISCRETE occured twice. – Zhuoran He Oct 15 '17 at 7:04
• @ZhuoranHe I just realise I over-counted more than that right? Because I should multiply by $13$ (this is double counting) instead of $13!$ – Natash1 Oct 15 '17 at 7:10
• Yes. I assumed you did your part correctly. The double counting is not easy to see. – Zhuoran He Oct 15 '17 at 7:11
• Hint: split up in 2 cases. DISCRETE one, or two times. – drhab Oct 15 '17 at 7:12
• Also DISCRETE is an easy word with no common prefix and postfix. If your word is AHA, then how many times it appeared in AHAHA becomes not well-defined. This has to do with KMP matching. – Zhuoran He Oct 15 '17 at 7:14

Let: $$W:=\{\langle L_1,\dots,L_{20}\rangle\mid L_i\in\{A,B,\dots,Z\}\}$$for $k=1,\dots13$ let: $$S_k:=\{\langle L_1,\dots,L_{20}\rangle\in W\mid \langle L_k,\dots,L_{k+7}\rangle=\langle D,I,S,C,R,E,T,E\rangle\}$$and finally let:$$S=\bigcup_{k=1}^{13}S_k$$

Then you are looking for $|S|$, and with inclusion/exclusion we find:$$|S|=\sum_{k=1}^{13}|S_k|-\sum_{1\leq i<j\leq13}|S_i\cap S_j|$$

Here $\sum_{1\leq i<j\leq13}|S_i\cap S_j|$ can be recognized as then number of 20-letter words that contain subword DISCRETE twice. In order to find it we use stars and bars.

There are $\binom{4+2}{2}=\binom{6}{2}=15$ sums $l+m+r=4$ where $l$ and $r$ are nonnegative integers. Here $l$ stands for the number of letters at the utmost left of the first DISCRETE, $m$ for the number of letters in between and $r$ for the number of letters at the utmost right of the second DISCRETE. This makes clear that $$\sum_{1\leq i<j\leq13}|S_i\cap S_j|=15\cdot26^4$$

Further it is clear that $|S_k|=26^{12}$ so our final outcome is:$$|S|=13\cdot26^{12}-15\cdot26^4$$

You cannot do permutations in the end since letters may repeat, and you overlooked that other letters may form word descrete on their own. There you must subtract all the cases with two descretes

So you can put descrete on 1st,2nd,...,13th position, it is $13\cdot26^{12}$. And double discrete you can put on 1st&2nd, 1st&3rd, ..., 5th&6th. Total of 5+4+...+1=15

$13\cdot26^{12}-15\cdot26^{4}$ is the result