[Math] Consider the lists of length six made with the symbols $P, R, O, F, S$ where repetition is allowed.

combinatorics

Consider the lists of length six made with the symbols $P, R, O, F, S$ where
repetition is allowed. (For example, the following is such a list: $(P,R,O,O,F,S)$.)
How many such lists can be made if the list must end in an $S$ and the symbol
$O$ is used more than once?

Here's my attempt at counting the lists:
$S$ must be the last entry of the list, so there is $1$ possible value. $O$ must occur more than once, so I arranged $1$'s in the other five entries to represent possible combinations of $O$ in the list.

$\begin{align}1\cdot1\cdot5\cdot5\cdot5\cdot1 + 1\cdot5\cdot 1 \cdot5\cdot5\cdot1 + 1 \cdot 5 \cdot 5 \cdot 1 \cdot 5 \cdot 1+ 1 \cdot 5 \cdot 5 \cdot 5 \cdot 1 \cdot 1 + 5\cdot1\cdot1\cdot5\cdot5\cdot 1 + 5 \cdot 1 \cdot 5\cdot1\cdot5\cdot1 + 5\cdot1\cdot5\cdot5\cdot1\cdot1+ \cdots + 5 \cdot 5 \cdot 5 \cdot1\cdot1\cdot1 \end{align}$

Also: Is there an easier way to count this?

Best Answer

We want to count $5$ letter words with at least $2$ O letters.

  1. The number of arbitrary $5$ letter words is $5^5$.
  2. The number of $5$ letter words with exactly one "O" is $5 \cdot 4^4$ (fix the location of the O, and the rest can consist of the four remaining letters).
  3. The number of $5$ letter words without the letter O is $4^5$.

Since (2) and (3) are disjoint, the number of $5$ letter words with at least $2$ O letters is $$5^5 - 5 \cdot 4^4 - 4^5 = 821$$

Related Question