Cuántos números enteros entre el $1$ $10^n$ contienen $14$?

Question

Cómo podemos obtener una fórmula para calcular el número de enteros entre el $1$ $10^n$ que contienen el número de $14$ (como una cadena)?

Por ejemplo, hay $20$ enteros de $1$ $1000$que contienen al menos un $14$:

"14","114","140","141","142","143","144","145","146","147","148","149","214","314","414","514","614","714","814","914"

Answer 1

Hay $\binom{n-k}{k}$ arreglos de $k$ "$14$"s y $10^{n-2k}$ otros dígitos.

Por lo tanto, la inclusión-exclusión dice que hay $$ \sum_{k=1}^{\lfloor n/2\rfloor}(-1)^{k-1}\binom{n-k}{k}10^{n-2k}\etiqueta{1} $$ los números de $1$ $10^n$que contienen "$14$".

Aquí están algunos de los primeros valores. $$ \begin{array}{r|l} n&\text{count}\\ \hline 2&1\\ 3&20\\ 4&299\\ 5&3970\\ 6&49401\\ 7&590040 \end{array}\etiqueta{2} $$

---

La Generación De La Función

Multiplicar $(1)$ $x^n$ y la suma: $$ \begin{align} &\sum_{n=0}^\infty\sum_{k=1}^\infty(-1)^{k-1}\binom{n-k}{n-2k}10^{n-2k}x^n\\ &=\sum_{n=0}^\infty\sum_{k=1}^\infty(-1)^{n-k-1}\binom{-k-1}{n-2k}10^{n-2k}x^{n-2k}x^{2k}\\ &=\sum_{k=1}^\infty(-1)^{k-1}\frac{x^{2k}}{(1-10x)^{k+1}}\\ &=\frac1{10x-1}\frac{\frac{x^2}{10x-1}}{1-\frac{x^2}{10x-1}}\\ &=\frac{x^2}{1-20x+101x^2-10x^3}\tag{3} \end{align} $$ que tiene la serie de Taylor $x^2+20x^3+299x^4+3970x^5+49401x^6+590040x^7+\dots$

---

La Forma Cerrada

El denominador en $(3)$ dice que $c_n$ satisface $$ c_n=20c_{n-1}-101c_{n-2}+10c_{n-3}\etiqueta{4} $$ El polinomio característico de a $(4)$ es $$ x^3-20x^2+101x-10\etiqueta{5} $$ cuyas raíces son $$ \left\{10,5+\sqrt{24},5-\sqrt{24}\right\}\etiqueta{6} $$ Podemos solucionar $(4)$ en la forma estándar para tales recurrencias para obtener $$ c_n=10^n-\frac{(5+\sqrt{24})^{n+1}}{2\sqrt{24}}+\frac{(5-\sqrt{24})^{n+1}}{2\sqrt{24}}\etiqueta{7} $$

Answer 2

Si el número de longitud-$n$ los números que contengan $14$$f(n)$; llamar a estos números "buenos", entonces tenemos la recurrencia $$f(n)=10 f(n-1)-f(n-2)+10^{n-2}$$ for $n \geq 3$: the argument is that we can construct length-$n$ good numbers from length-$(n-1)$ good numbers by appending any digit, or by appending $14$ to any length-$(n-2)$ number; this double-counts numbers with multiple $14$s ending in $14$, so we subtract $f(n-2) dólares a cuenta de esto.

Esto le da a la secuencia de $$0, 1, 20, 299, 3970, 49401, 590040, 6850999, 77919950, 872348501, \ldots.$$

Answer 3

Esta es una variante Rebecca de Piedra de la respuesta. Deje $G(n)$ contar el número de "buena" de longitud-$n$ cadenas que contienen un $14$, y deje $B(n)$ contar el número de "malo" de las cadenas que no. Claramente

$$G(n)+B(n)=10^n$$

Usted puede crear una mala cadena de longitud $n$ anexando cualquier dígito que desea una mala cadena de longitud $n-1$, a menos que la cadena más corta que termina en un $1$, en cuyo caso no se puede anexar un $4$. El número de cadenas de este tipo (que termina en un $1$)$B(n-2)$. Así

$$B(n)=10B(n-1)-B(n-2)$$

con los valores de partida $B(1)=10$$B(2)=99$. Esto le da a los "malos" de la secuencia

$$10, 99, 980, 9701, 96030, 950599, 9409960, 93149001,\ldots$$

que es A004189 en la OEIS, donde se observó que

$$B(n)={(5+\sqrt{24})^{n+1}-(5-\sqrt{24})^{n+1}\over2\sqrt{24}}$$

Así

$$G(n)=10^n-{(5+\sqrt{24})^{n+1}\over2\sqrt{24}}+{(5-\sqrt{24})^{n+1}\over2\sqrt{24}}$$

como robjohn encontrado.

Answer 4

Podría no ser una solución que usted desea, pero este pequeño fragmento de código en Javascript que hace su trabajo. Esto devuelve 20 como un resultado por 1000. 299 para 10000.

 var count = 0;
 for (i = 0; i < 1000; i++) {
 if (i.toString().search("14") != -1) {
     count++;
 }
 }
 alert(count);