Problem: Given an arbitrary finite sequence of letters (represented as a word), a subsequence is a sequence of one or more letters that appear in the same order as in the original sequence. For example, $N, C T, O T T$, and $C O N T E S T$ are subsequences of the word CONTEST, but NOT, ONSET, and TESS are not. Assuming the standard English alphabet $\{A, B, \ldots, Z\}$, compute the number of distinct four-letter "words" for which $E E$ is a subsequence. Solution: Notice that four-letter words containing at least two $Es are exactly those where $EE$ is a subsequence, so it suffices to count the number of four-letter words such that there are at least two $Es. We can case on the number of $Es: - Two $E$ 's: If the other two letters are identical: choose that letter ( 25 ways) and arrange $E E x x$ in $\frac{4!}{2!2!}=6$ ways, giving $25 \cdot 6=150$. If the other two letters are distinct: choose an unordered pair $\binom{25}{2}=300$ and arrange $E E x y$ in $\frac{4!}{2!}=12$ ways, giving $300 \cdot 12=3600$. - Three $E$ 's: Choose the last letter (25 ways) and arrange $E E E x$ in $\frac{4!}{3!}=4$ ways: $25 \cdot 4=100$. - Four $E$ 's: Exactly one word: $E E E E$. In total, we get $3600+150+100+1 = 3851$. Note that this method can be refined if we considered complementary counting first. The total number of four-letter words is $26^4$. Then, the number of four-letter words for which there are zero $Es is $24^4$ and the number of four-letter words for which there is exactly one $E$ is $4 \cdot 25^3$. The arithmetic result can be reduced using the binomial theorem (observing that $26 = 25+1$...).