Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
From your annotation, it appears you also want no leading zero. Is this correct? –  Mario Carneiro Dec 18 '12 at 5:07
    
yes in case of leading zero it is other number –  Arsen Dec 18 '12 at 5:09
    

2 Answers 2

up vote 2 down vote accepted

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$$

share|improve this answer
    
Don't you want $L(1)=K-1$? Since there are $K$ possible strings of length $1$, $L(1)+M(1)=K$. –  Mario Carneiro Dec 18 '12 at 5:23
    
@MarioCarneiro: You are right. OP said leading zeros were not allowed, so I subtracted it, but the correct one is M(1)=0, leaving only $K-1$ strings of length $1$. Will fix. –  Ross Millikan Dec 18 '12 at 5:29
    
But your definition says $M(n)$ is the number of strings that end in zero. Thus $M(n)=1$ and $L(n)=K-1$. I assumed the reason for defining both functions was to assist in the recursion, and then to take $L(n)$ as the answer at the end. BTW, is there a closed-form solution? –  Mario Carneiro Dec 18 '12 at 5:35
    
I have tryed to implement this solution but for example N=5 K=10 output is 79461 but the right answer is 87480. even for N=2, K=10 the output is 81 but must be 90 –  Arsen Dec 18 '12 at 5:42
    
@Arsen: I forgot to say that you need to add together $L(n)$ and $M(n)$ to get the answer, as all the strings in $M$ also count. So for $N=2, K=10, L(2)=81, M(2)=9$ for a total of $90$. For $N=5, K=10,$ I get $L(5)=79461, M(5)=8019$, for a total of $87480$ –  Ross Millikan Dec 18 '12 at 14:02

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}}. $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.