Techniques for Solving Counting Problems

# Techniques for Solving Counting Problems

The study of Combinatorics is essentially about counting various things. Many of the problems that we will see later on involving counting, so we will develop some techniques to solving simple counting problems that will also be useful and applicable later on.

## Example 1

Suppose that $A = \{a, b, c \}$ and $B = \{y, z \}$. How many ways are there to create a list of length $3$ where the first and second value in the list come from $A$ and the third value in the list comes from $B$?

One way to solve this counting problem is by assigning three placeholders, say $*$, and replacing each $*$ with the number of options/choices we have for each of those $3$ positions. For the problem posed above, we first write:

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

In the first position we must choose one element in $A$. There are $3$ elements in $A$ to choose from. Therefore we write a $3$ in the place of the first $*$.

(2)
\begin{align} \quad 3 \: * \: * \end{align}

In the second position we must choose one element in $A$ again to which there are still $3$ to choose from. We write a $3$ in the place of the second $*$.

(3)
\begin{align} \quad 3 \: 3 \: * \end{align}

In the third position we must choose one element in $B$ to which there are $2$ to choose from. We write a $2$ in the place of the third $*$.

(4)
\begin{align} \quad 3 \: 3 \: 2 \end{align}

The total number of length $3$ ordered lists is therefore $3 \cdot 3 \cdot 2 = 18$.

## Example 2

Suppose that for the sets $A = \{a, b, c \}$ and $B = \{x, y \}$ above, we want to count the number of lists of length $3$ where: the first two elements come from $A$, the third element comes from $B$, and where no two elements in the list are the same.

Example 2 is a counting problem that has a restriction placed on it in that no two elements in this list are the same. For counting problems like this - we generally want to write the number of options for the placeholder $*$ with the most amount of restrictions as the restrictions become relevant in positioning.

For the position we must choose one element from $A$ to which there are no restrictions.

(5)
\begin{align} \quad 3 \: * \: * \end{align}

We now have incurred a restriction on the second element so we should deal with it next. We must choose an element from $A$ that is NOT the same element we chose for the first position. There are $2$ elements from $A$ to choose from regardless of the choice of element in the first position. Therefore:

(6)
\begin{align} \quad 3 \: 2 \: * \end{align}

Lastly for the third position we must choose an element from $B$ to which there are $2$.

(7)
\begin{align} \quad 3 \: 2 \: 2 \end{align}

There are thus $3 \cdot 2 \cdot 2 = 12$ lists of length $3$ for this problem.

## Example 3

Determine how many $7$-digit numbers have alternating odd-even digits and no digit repeated.

The problem posed above has multiple restrictions that we need to deal with. For simplicity's sake, we will break this problem up into two cases. We first start with the case where we start with an odd number.

Case 1: Odd Numbers.

(8)
\begin{align} \quad * \: * \: * \: * \: * \: * \: * \end{align}

The first digit can be one of $5$ of the odd digits ($1$, $3$, $5$, $7$ or $9$). The third digit can be one of the remaining $4$ odd digits. The fifth digit can be one of the remaining $3$ odd digits. The seventh number can be one of the remaining $2$ odd digits. So:

(9)
\begin{align} \quad 5 \: * \: 4 \: * \: 3 \: * \: 2 \end{align}

Now the second digit can be one of the $5$ even digits ($0$, $2$, $4$, $6$, or $8$). The fourth digit can be one of the remaining $4$ even digits. Lastly, the sixth digit can be one of the remaining $3$ even digits.

(10)
\begin{align} \quad 5 \: 5 \: 4 \: 4 \: 3 \: 3 \: 2 \end{align}

So there are $7200$ many $7$-digit even numbers whose digits alternate from odd to even and none of whose digits are repeated.

Let's now look at the second case - when the first number is even.

Case 2: Even Numbers.

We set up placeholders once again.

(11)
\begin{align} \quad * \: * \: * \: * \: * \: * \: * \end{align}

The first position can be one of $4$ even digits ($2$, $4$, $6$, or $8$) since the first digit cannot be $0$. The third digit can then be one of $0$ or the remaining $3$ even digits which is $4$ total. The fifth digit has $3$ options to choose from, and the seventh digit has $2$ options to choose from.

(12)
\begin{align} \quad 4 \: * \: 4 \: * \: 3 \: * \: 2 \end{align}

For the odd digits we get the the second position has $5$ options, the fourth position has $4$ options, and the third position has $3$ options.

(13)
\begin{align} \quad 4 \: 5 \: 4 \: 4 \: 3 \: 3 \: 2 \end{align}

So there are $5760$ many $7$-digit odd numbers whose digits alternate from even to odd and none of whose digits are repeated. Combining the odd case from earlier and we get that there are $12960$ total $7$-digit numbers that satisfy the requirements to our problem.