## [Soln] Counting 7-digit Numbers

How many seven digit numbers have AT LEAST one 3 AND AT LEAST one 7?

This is essentially the same problem as “Counting 4-digit Numbers“, except we are now trying to count 7-digit numbers instead of 4-digit ones. How big is this problem? It doesn’t take much experimentation to figure out that we can’t really proceed by listing out all possible cases like we did for the 4-digit case. There are simply too many cases!

What’s one to do when the number of cases is too many? One can try to reduce the problem to a slightly simpler version. We know that we can figure out the answer when looking at just 4 digits. Could we use that to figure out the answer when looking at 5 digits? Then 6, and then 7?

This gives us the idea of trying to set up a recurrence relation. Can we find a relationship between the number of $n$-digit numbers with at least one 3 and one 7, and the number of $(n-1)$-digit numbers with at least one 3 and one 7? In other words, if we define

$a_n := \text{number of n-digit numbers with at least one 3 and one 7}$,

then we are trying to find a relationship between $a_n$ and $a_{n-1}$.

We can do this by considering the first $n-1$ digits as one block X and the last digit, Y:

If X already contains a 3 and a 7, then Y can be any digit. If X contains a 3 but no 7, then Y must be 7. Similarly, if X contains a 7 but no 3, then Y must be 3. If X does not have any 3s and 7s, then there is no way for the number to contain both a 3 and a 7. Hence, if we define

$b_n := \text{number of n-digit numbers with at least one 3 but no 7}$,
$c_n := \text{number of n-digit numbers with at least one 7 but no 3}$, and
$d_n := \text{number of n-digit numbers with no 3s and 7s}$,

then we have the recurrence relation

$a_n = 10 a_{n-1} + b_{n-1} + c_{n-1}. \hspace{1em} -(1)$

We have a relation between $a_n$ and $a_{n-1}$, but we have introduced 2 auxiliary sequences $(b_n)$ and $(c_n)$. Won’t this cause problems with using $(1)$ to calculate $a_n$?

After some thought, we may realise that we can use the same method as above to set up a recurrence relation for the 2 auxiliary sequences! For example, consider the calculation for $b_n$:

• If X has 3s and 7s already, then the number cannot count toward $b_n$.
• If X has 3s but no 7, then Y can be any digit except 7.
• If X has 7s but no 3, then the number cannot count toward $b_n$.
• If X has no 3s and 7s, then Y must be the number 3.

Hence, we have the recurrence relation

$b_n = 9 b_{n-1} + d_{n-1}. \hspace{1em} -(2)$

Similarly, we have

$c_n = 9c_{n-1} + d_{n-1}. \hspace{1em} - (3)$

How about $d_n$? There is a relationship as well:

\begin{aligned} a_n + b_n + c_n + d_n &= \text{number of n-digit numbers}, \\ d_n &= 9 \times 10^{n-1} - a_n - b_n - c_n. \hspace{1em} -(4). \end{aligned}

Awesome! Now we can use relations $(1)$ to $(4)$ to calculate the values of the sequences. First, we test out the small cases to make sure that our relations are correct:

(* Why is $d_1 = 7$ and not $d_1 = 8$?)

It’s easy to check by hand that the values for $a_n$ in the table are correct. This gives us greater confidence in our recurrence relations! We can fill up the whole table:

Therefore, there are 2,331,952 7-digit numbers with at least one 3 and at least one 7.