seleccionar secuencia sin "ABCD"

Hay un número infinito de cupones que llevan una de las letras A,B,C,D. Encuentre el número de formas para seleccionar 10 de estos cupones para que no haya una secuencia de "ABCD", lo que significa que después de seleccionar un cupón 'A' y un cupón 'B' y un cupón "C" no puede seleccionar un cupón 'D' inmediatamente.

Intenté como primero todas las combinaciones posibles son iguales 4 10 y luego consideraron la secuencia "ABCD" juntos por medio 4 los lugares consecutivos se fijan, por lo que el total de puestos disponibles se reduce a 7 . En 7 formas en que podemos colocar "ABCD" y luego permanecer 6 lugares como seleccionar cualquier número de 4 , lo que equivale 4 6 . Pero no funciona. Buscando ayuda amable.

Su razonamiento se ve bien, pero en realidad contiene un problema de doble conteo: podría tener no una sino dos subsecuencias ABCD, por lo que también debe tener en cuenta eso.
señor, entendí su punto, pero si hay "ABCD" una o dos veces en ambos casos, fallará, por lo que consideré solo un "ABCD" y debería manejar automáticamente otro incluso para dos subsecuencias de "ABCD".
Ese es exactamente el problema. En su cálculo, la secuencia ABCDXXABCD se cuenta dos veces como parte de las secuencias de la forma ABCDXXXXXX y de las de la forma XXXXXXABCD.
Este tutorial explica cómo escribir matemáticas en este sitio.

Respuestas (2)

Como dije en los comentarios, debe ajustar el conteo doble al volver a agregar las secuencias que contienen dos copias de A B C D . Puede colocar estas dos copias en 6 diferentes maneras y elige los dos números restantes, por lo que tienes 6 ⋅ 4 2 tales secuencias. Por lo tanto, el número total debe ser

4 10 − 7 ⋅ 4 6 + 6 ⋅ 4 2 .

Gracias, tenía una pequeña duda si la secuencia es "ABC" y todavía hay 10 lugares, ¿seguirá siendo la misma?
@Rajakr No, porque la secuencia ABC podría aparecer hasta tres veces. Sin embargo, aún puede utilizar el principio de inclusión-exclusión.

Quiero darte una herramienta más poderosa para resolver este tipo de preguntas. Lo aprendí de @Markus Scheuer. (Puedes revisar sus respuestas para mejorar tus habilidades de combinatoria).

Repasemos nuestra pregunta. En primer lugar, esta pregunta es más como una pregunta de relación de recurrencia. Escribo esta respuesta para dar otra perspectiva, por cierto, la respuesta de @b00n heT es más elegante y concisa que mi respuesta para esta pregunta.

Nuestro método se llama método Goulden-Jackson, es un artículo poco detallado, por lo que no entraré en detalles para explicarlo. Mire: Método de conglomerados de Goulden-Jackson .

Nuestro método dice que nuestro alfabeto es V = { A , B , C , D } . Además, nuestra mala palabra es A B C D . Ahora,

A ( z ) = 1 1 − d z − peso ( C )

A ( z ) será nuestra función generadora para encontrar nuestra relación de recurrencia. d en A ( z ) es igual al número de elementos en V .

w mi i gramo h t ( C ) = w mi i gramo h t [ ( A B C D ) ] = − z 4 , porque no hay ninguna superposición en A B C D . Puede encontrar cómo calcularlo en el enlace dado.

Por eso ,

A ( z ) = 1 1 − 4 z + z 4

es la expansión de A ( z ) , https://www.wolframalpha.com/input/?i=forma+expandida+de+%281+%2F+%281-4x+%2Bx%5E4%29%29

Ves que el coeficiente de X 10 es igual a 1020000 , que es igual a la respuesta de @b00n heT

seleccionar secuencia sin "ABCD"
RespuestasAquíPolítica de privacidad1y, 0v