Posted 02/01/2016

----------------------
Previous    Next
----------------------

This problem is about counting certain $n$-digit integers. Yes, we do count everything and we don't have bottom line!

Suppose $a(n)$ is the number of $n$-digit even integers that do not have two zeros in a row.
Suppose $b(n)$ is the number of $n$-digit odd integers that do not have two zeros in a row.

Clearly, $a(1)=b(1)=5$ because we have $\{0,2,4,6,8\}$ and $\{1,3,5,7,9\}$. $a(3)=441$ because there are $450$ even 3-digit integers and $9$ of them have two consecutive zeros, namely $100,200,\cdots,900$.


Find $a(n)$ and $b(n)$.


A more general problem is that how many $n$-digit integers that are congruent to $j$ mod $k$ and do not have $m$ zeros in a row.