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 -digit numbers with at least one 3 and one 7, and the number of -digit numbers with at least one 3 and one 7? In other words, if we define

,

then we are trying to find a relationship between and .

We can do this by considering the first 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

,

, and

,

then we have the recurrence relation

We have a relation between and , but we have introduced 2 auxiliary sequences and . Won’t this cause problems with using to calculate ?

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 :

- If
*X*has 3s and 7s already, then the number cannot count toward . - 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 . - If X has no 3s and 7s, then
*Y*must be the number 3.

Hence, we have the recurrence relation

Similarly, we have

How about ? There is a relationship as well:

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

*(* Why is and not ?)*

It’s easy to check by hand that the values for 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.