Relaciones de recurrencia: Cuántos números entre 1 y 10.000.000 no tienen la cadena 12 o 21

Question

Por lo que la cuestión es (a resolver con relaciones de recurrencia: ¿Cuántos números entre 1 y 10.000.000 no tienen la cadena 12 o 21?

Así que mi solución: $a_n=10a_{n-1}-2a_{n-2}$ . En $10a_{n-1}$ representa el número de cadenas de longitud n de dígitos del 0 al 9, y el $2a_{n-2}$ representan las cadenas de longitud n con las 12 o 21 cadenas incluidas.

Sólo quería saber si mi recursión es correcta, si es así, podré resolver el resto.

Gracias de antemano.

Answer 1

Examinamos un problema ligeramente distinto, a partir del cual se puede responder a su pregunta.

Llamar a una cadena de dígitos bien si no tiene $12$ o $21$ en él. Deje que $a_n$ sea el número de cadenas buenas de longitud $n$ . Sea $b_n$ sea el número de cadenas buenas de longitud $n$ que terminan en $1$ o un $2$ Entonces $a_n-b_n$ es el número de cadenas buenas de longitud $n$ que no terminan con $1$ o $2$ .

Tenemos $$a_{n+1}=10(a_n-b_n) +9b_n.$$ Para una buena cadena de longitud $n+1$ se obtiene añadiendo cualquier dígito a una cadena buena que no termine en $1$ o $2$ , ou añadiendo cualquier dígito excepto el prohibido a una cadena buena que termine en $1$ o $2$ .

También tenemos $$b_{n+1}=2(a_n-b_n) + b_n.$$ Pues obtenemos una buena cadena de longitud $n+1$ que termina en $1$ o $2$ añadiendo $1$ o $2$ a una cadena que no termine con ninguno de los dos, o tomando una cadena que termine con $1$ (respectivamente, $2$ ) y añadiendo un $1$ (respectivamente, $2$ ).

Las dos recurrencias se simplifican en $$a_{n+1}=10a_n-b_n\qquad\text{ and}\qquad b_{n+1}=2a_n-b_n.$$ A efectos de cálculo, son los siguientes suficientemente bueno . Realmente no necesitamos una recurrencia para el $a_i$ solo. Sin embargo, su pregunta se refiere quizás a la $a_i$ por lo que eliminamos el $b$ 's.

Una forma estándar de hacerlo es incrementar $n$ en la primera recurrencia, y obtener $$a_{n+2}=10a_{n+1}-b_{n+1}.$$ Pero $b_{n+1}=2a_n-b_n$ Así que $$a_{n+2}=10a_{n+1}-2a_n+b_n.$$ Pero $b_n=10a_n-a_{n+1}$ y, por lo tanto $$a_{n+2}=9a_{n+1}+8a_n.$$

Observación: Hubiera sido mejor $b_n$ como en el caso anterior, y $c_n$ el número de cadenas que no terminan en $1$ o $2$ y olvidarse de $a_n$ por completo durante un tiempo.

Answer 2

Veo que André respondió a esto mientras yo estaba fuera poniendo $52$ millas en mi bicicleta, pero permítanme sugerir una ruta muy ligeramente diferente a la misma recurrencia que me ocurrió durante mi paseo. Utilizaré el mismo bien terminología y la misma definición de $a_n$ y dejaré que $c_n$ sea el número de cadenas buenas de longitud $n$ que no terminan en $1$ o $2$ .

Supongamos que $\sigma$ es una buena cadena de longitud $n\ge 1$ . No importa cuál sea el último dígito de $\sigma$ es, hay al menos $9$ dígitos que puedo añadir a $\sigma$ para hacer una buena cadena de longitud $n+1$ y si el último dígito de $\sigma$ no es $1$ o $2$ puedo añadir cualquiera de los $10$ dígitos. Esto tiene en cuenta todas las posibles cadenas buenas de longitud $n+1$ Así que $a_{n+1}=9a_n+b_n$ . ¿Cuántos de ellos no terminan en $1$ o $2$ ? Precisamente las que se obtienen añadiendo uno de los $8$ dígitos en $\{0,3,4,5,6,7,8,9\}$ a una buena cadena de longitud $n$ de los cuales hay $8a_n$ . Así, $b_{n+1}=8a_n$ Así que $b_n=8a_{n-1}$ y

$$a_{n+1}=9a_n+b_n=9a_n+8a_{n-1}\;.$$

Así, tenemos

$$\left\{\begin{align*} &a_0=1\\ &a_1=10\\ &a_n=9a_{n-1}+8a_{n-2}\quad\text{for}\quad n\ge 2\;. \end{align*}\right.$$

---

Eso es todo lo lejos que tenía que ir, pero yo tenía curiosidad acerca de una forma cerrada para $a_n$ . Mediante técnicas estándar se puede descubrir que

$$a_n=\frac1{226}\left(\left(113+11\sqrt{113}\right)\left(\frac{9+\sqrt{113}}2\right)^n+\left(113-11\sqrt{113}\right)\left(\frac{9-\sqrt{113}}2\right)^n\right)\;.$$

Ahora $$\left|\frac{9-\sqrt{113}}2\right|<1\quad\text{and}\quad\left|\frac{113-11\sqrt{113}}{226}\right|<0.02\;,$$

y $a_n$ es siempre un número entero, por lo que para $n\ge 1$ $a_n$ es el número entero más próximo a

$$\frac{113+11\sqrt{113}}{226}\left(\frac{9+\sqrt{113}}2\right)^n\;.\tag{1}$$

$(1)$ es aproximadamente $(1.017396477611)(9.815072906367)^n$ .

Para $n=7$ esto equivale aproximadamente a $8,927,809.995842$ que redondea a $8,927,810$ el valor correcto, por lo que la aproximación es bastante buena.