Solving Counting Problems with Groupings

Solving Counting Problems with Groupings

We have just looked at Techniques for Solving Counting Problems, however, we will want to look at one more type of counting problem that may pop up.

Let $A = \{ a, b, c, ..., x, y, z \}$ be the set of all $26$ letters in the alphabet. Suppose that we want to determine how many $5$ letter words can be constructed using the letters from $A$. By "words" we don't mean real words but instead any combination of letters from $A$. For example, we will consider $qzkrx$ a word.

The problem at hand is no different than the problems we have already seen. We set up $5$ placeholder $*$s, say $* \: * \: * \: * \: *$ and fill each with the number of options of elements from $A$ that can be placed there. There are no restrictions in this problem and each position can hold one of the $26$ letters of the alphabet. Hence we have $26 \: 26 \: 26 \: 26 \: 26 \:$, i.e., there are $26^5$ different words that we can create from the letters in $A$.

Now suppose instead that we want to determine how many $5$ letter words can be constructed using the letters from $A$ and such that if either $s$ or $t$ is in the word then they both appear once and appear together side by side, i.e., $st$ or $ts$.

Case 1.

First let's consider the case where neither $s$ or $t$ appear in the word. Then we have $24$ letters to choose from in each of the $5$ positions so there are $24^5$ words in this manner.

Case 2.

Now let's consider the case where $s$ and $t$ appear exactly once. Then we must group $s$ and $t$ together in these words. To ensure $s$ and $t$ are always together, we will treat them as a single entity. We set up four placeholder $*$s to get:

(1)
\begin{align} * \: * \: * \: * \end{align}

We must have one of these $*$s be either $st$ or $ts$. Note that this still ensures we obtain a $5$ letter word. For any arbitrary position we have $25$ choices to choose from. Either we choose one of the $24$ remaining letters OR we choose a grouping of $s$ and $t$. For the remaining $3$ positions we must choose one of the $24$ remaining letters for this case. Therefore we get:

(2)
\begin{align} 25 \: 24 \: 24 \: 24 \end{align}

So there are $25 \cdot 24^3$ words that can be formed from this second case… or are there?. We have missed a very important detail. We must also account for the fact that a grouping of $s$ and $t$ can switch around as a grouping of $t$ and then $s$. There are $2!$ ways this swap can be done. Therefore there are actually $2! \cdot 25 \cdot 24^3$ words that can be formed for this case.

We have covered all cases and the total number of $5$ letter words that satisfy our conditions are:

(3)
\begin{align} \quad 24^5 + 2! \cdot 25 \cdot 24^3 = 7962624 + 691200 = 8653824 \end{align}