4
$\begingroup$

I am trying to solve a programming problem, but i dont know how to find number of numbers that dont contain two successive zeros. Please help me. for deeper understanding i included part of the problem in message.

Let’s consider K-based numbers, containing exactly N digits. We define a number to be valid if its K-based notation doesn’t contain two successive zeros. For example:

1010230 is a valid 7-digit number; 1000198 is not a valid number;  0001235 is not a 7-digit number, it is a 4-digit number. 

Thank you!

  • 0
    http://acm.timus.ru/problem.aspx?space=1&num=10092014-12-10

2 Answers 2

2

Let $L(n)$ be the number of strings with an alphabet of $K$ characters that don't end in $0$ and don't have two successive $0$'s. Let $M(n)$ be the number of strings with an alphabet of $K$ characters that end in $0$ and don't have two successive $0$'s. Then $L(1)=K-1, M(1)=0$(because of no leading zero)$, L(n)=(K-1)(L(n-1)+M(n-1)), M(n)=L(n-1)$ the third because you can add any non-zero character to an acceptable string to get an acceptable string that doesn't end in zero, and you can add a zero to any acceptable string that doesn't end in zero to get an acceptable string that ends in zero. This makes a $2 \times 2$ matrix that takes $(L(n)\ M(n))^T$ to $(L(n+1)\ M(n+1))^T$ so you might find the eigenvalues and eigenvectors of that matrix. To get the final answer, you take $L(n)+M(n)$.

Added: to get a closed form we represent the recursion as $\begin {pmatrix} L(n) \\ M(n) \end {pmatrix}=\begin {pmatrix} 9 & 9 \\ 1 & 0 \end {pmatrix}\begin {pmatrix} L(n-1) \\ M(n-1) \end {pmatrix}$

This has eigenvalues $\lambda_{\pm}=\frac 32 (3 \pm \sqrt {13})$ with corresponding eigenvectors $\begin {pmatrix} 9+3\sqrt {13} \\ 1 \end {pmatrix},\begin {pmatrix} 9-3\sqrt {13} \\ 1 \end {pmatrix}$. Starting from $\begin {pmatrix} L(0) \\ M(0) \end {pmatrix}=\begin {pmatrix} K-1 \\ 0 \end {pmatrix}$ we get $\begin {pmatrix} L(n) \\ M(n) \end {pmatrix}= \frac{K-1}{6\sqrt{13}}\begin {pmatrix} 9+3\sqrt {13} \\ 1 \end {pmatrix}\lambda_+^n-\frac{K-1}{6\sqrt{13}}\begin {pmatrix} 9-3\sqrt {13} \\ 1 \end {pmatrix}\lambda_-^n$

  • 0
    @MarioCarneiro: OP said strings starting with zero were not allowed, which is why $M(1)=0$. Yes, defining the two functions makes the recursion easier, but you have to add them to get the final answer.2012-12-18
0

To count the $k$-ary strings (that is, strings on the alphabet $0, 1, 2, \ldots, k-1$) of length $n$ with no two $0$'s in a row that do not start with $0$, first choose the number of nonzero digits we would like to have - call this $m$. Then choose any string on $m$ digits using the digits $1, 2, \ldots, k-1$ (but not $0$). Now choose any subset of size $n-m$ of these digits, and insert a $0$ to the right of each. The result is a string that does not start with $0$ and has no two $0$'s adjacent, and every such string is attained uniquely with this process. This gives the answer

$\sum_{m=0}^n (k-1)^m {m \choose {n-m}}. $