dos ceros sucesivos

Question

Estoy tratando de resolver un problema de programación, pero no sé cómo encontrar el número de números que no contienen dos ceros sucesivos. Por favor, ayúdenme. para una mayor comprensión he incluido parte del problema en el mensaje.

Consideremos los números basados en K, que contienen exactamente N dígitos. Definimos que un número es válido si su notación basada en K no contiene dos ceros sucesivos. Por ejemplo:

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.

Gracias.

Answer 1

Dejemos que $L(n)$ sea el número de cadenas con un alfabeto de $K$ caracteres que no terminan en $0$ y no tienen dos sucesivos $0$ 's. Sea $M(n)$ sea el número de cadenas con un alfabeto de $K$ caracteres que terminan en $0$ y no tienen dos sucesivos $0$ 's. Entonces $L(1)=K-1, M(1)=0$ (debido a la ausencia de cero inicial) $, L(n)=(K-1)(L(n-1)+M(n-1)), M(n)=L(n-1)$ la tercera porque se puede añadir cualquier carácter distinto de cero a una cadena aceptable para obtener una cadena aceptable que no termine en cero, y se puede añadir un cero a cualquier cadena aceptable que no termine en cero para obtener una cadena aceptable que termine en cero. Esto hace que un $2 \times 2$ matriz que toma $(L(n)\ M(n))^T$ a $(L(n+1)\ M(n+1))^T$ por lo que podrías encontrar los valores y vectores propios de esa matriz. Para obtener la respuesta final, se toma $L(n)+M(n)$ .

Añadido: para obtener una forma cerrada representamos la recursión como $$\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}$$

Esto tiene valores propios $\lambda_{\pm}=\frac 32 (3 \pm \sqrt {13})$ con los correspondientes vectores propios $\begin {pmatrix} 9+3\sqrt {13} \\ 1 \end {pmatrix},\begin {pmatrix} 9-3\sqrt {13} \\ 1 \end {pmatrix}$ . A partir de $\begin {pmatrix} L(0) \\ M(0) \end {pmatrix}=\begin {pmatrix} K-1 \\ 0 \end {pmatrix}$ obtenemos $$\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$$

Answer 2

Para contar el $k$ -cadenas de caracteres (es decir, cadenas de caracteres en el alfabeto $0, 1, 2, \ldots, k-1$ ) de longitud $n$ sin dos $0$ en una fila que no empiece por $0$ primero elegimos el número de dígitos no nulos que queremos tener - llamémosle $m$ . A continuación, elija cualquier cadena en $m$ dígitos utilizando los dígitos $1, 2, \ldots, k-1$ (pero no $0$ ). Ahora, elija cualquier subconjunto de tamaño $n-m$ de estos dígitos, e insertar un $0$ a la derecha de cada uno. El resultado es una cadena que no empieza por $0$ y no tiene dos $0$ 's adyacentes, y cada una de estas cadenas se obtiene de forma única con este proceso. Esto da la respuesta

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