Calcule el número de secuencias de 7 dígitos que contienen una subcadena consecutiva de 5 dígitos.

Question

Digamos que cualquier secuencia de 7 dígitos, incluso 0000000 es un número válido. Calcule el número de secuencias que contienen una subcadena consecutiva de 5 dígitos. Por ejemplo, "23456" y "12345"?

Lo abordé como (donde X puede estar (0-9)): lo que me da un total de 1800, sin embargo, la respuesta es 1700. ¿Puede por favor indicar qué conté en exceso y compartir una manera inteligente de abordar una pregunta similar?

  0 1 2 3 4 X X 
 1 2 3 4 5 X X
 2 3 4 5 6 X X
 3 4 5 6 7 X X
 4 5 6 7 8 X X
 5 6 7 8 9 X X 

 X 0 1 2 3 4 X  
 X 1 2 3 4 5 X 
 X 2 3 4 5 6 X 
 X 3 4 5 6 7 X 
 X 4 5 6 7 8 X 
 X 5 6 7 8 9 X

 X X 0 1 2 3 4  
 X X 1 2 3 4 5 
 X X 2 3 4 5 6 
 X X 3 4 5 6 7 
 X X 4 5 6 7 8 
 X X 5 6 7 8 9
 

Answer 1

Sí, ustedes son overcounting el número de cadenas de este tipo: por ejemplo, $0 1 2 3 4 5 6$ es contada en tres tiempos: como miembro de $0 1 2 3 4 X X$, de $X 1 2 3 4 5 X$, y de $X X 2 3 4 5 6$.

Como se explica en los comentarios a la derecha de la herramienta a utilizar es la inclusión-exclusión principio.

Sugerencia. Deje $S(01234)$ el conjunto de 7 dígitos secuencias que contienen una copia de la cadena de $01234$ a continuación, a partir de su esquema, $$|S(01234)|=3\cdot 10\cdot 10=300.$$

Por la inclusión-exclusión principio, el número de 7 dígitos secuencias que contienen al menos un 5 dígitos consecutivos subcadena en orden crecientees $$\begin{align}&|S(01234)|+|S(12345)|+\dots+|S(56789)|\\&- |S(012345)|-|S(123456)|-\dots-|S(456789)|\end{align}.$$ P. S. con el fin De solicitar la inclusión-exclusión en el principio, usted debe considerar las intersecciones de los conjuntos de $S(\cdot)$. Tenga en cuenta que $$S(01234)\cap S(12345)=S(012345),\\ S(01234)\cap S(23456)=S(0123456),\\ S(01234)\cap S(34567)=\emptyset,\\ S(01234)\cap S(12345)\cap S(23456)=S(0123456) .$$

Answer 2

Estás contando algunas cadenas dos veces.

Por ejemplo, $$xx56789$$ and $$x45678x$$ both results in $$3456789