Inclusión-principio de exclusión de problemas

Question

Tengo un enorme problema con la inclusión-exclusión principio. Sé que la fórmula, pero siempre no sabe cómo usarlo, cómo para denotar todas las cosas. Espero que pasará cuando hago algunos ejercicios. Me quedé con estos dos:

1. ¿Cuántos son los $8$-números de dos dígitos (sin $0$ en cualquier posición) que no tienen subsequence $121$?

2. Encontrar el número de permutaciones del conjunto: $\left\{1,2,3,4,5,6,7\right\}$, que no tiene cuatro consecutivos elementos en orden ascendente.

Y aquí están mis propuestas de soluciones:

1. En general, hay $9^8$ números de este tipo. Vamos a pensar acerca de los números que tienen al menos un subsequence: $121$. Elegimos el lugar por primera $1$ de esta larga. Hay seis posibilidades. Después de elegir el lugar para $1$ establecer $21$ después de este dígito, y el resto de las cifras son, sin restricciones. Así que tenemos $6\cdot 9^5$ números con al menos una subsequence $121$, por lo que los números sin que esta larga se $9^8-6\cdot 9^5$. Es eso correcto?
2. Deje $X$ ser un conjunto de todas las permutaciones de un conjunto dado. $|X|=7!$. Deje $A_i$ ser un conjunto de permutaciones que tienen los números: $i, \ i+1, \ i+2, \ i+3$ consecutivos en orden ascendente. En otras palabras, se han larga de este formulario. Por lo tanto $|A_i|=4\cdot 3!$, porque se elige uno de los $4$ lugares para $i$ y el resto a $3$ de los dígitos sin restricciones. Otra observación es que para $i_1<...<i_k$ tenemos $\displaystyle |A_{i_1}\cap ... \cap A_{i_k} |=(3-i_k+i_1) \cdot (3-i_k+i_1)!$ que es simple, sólo porque el conjunto es $\left\{1,2,3,4,5,6,7 \right\}$. $A_{i_1}\cap ... \cap A_{i_k}$ es un conjunto de permutaciones que han larga: $i_1,...,i_k,...,i_{k+3}$ así que elige el lugar para $i_1$, esta larga a partir de este lugar y permuting el resto de los dígitos.

Por la forma en que me pregunto si era posible para resolver este problema, en general, me refiero a que si se trataba de la forma $\left\{1,..,n \right\}$ para cualquier número natural $n$?

De vuelta al problema. Ahora, lo que yo quiero contar es, por exclusión-inclusión principio, esta suma: $\displaystyle \sum_{k=0}^{4}(-1)^kS_k$ donde $\displaystyle S_k=\sum_{i_1<...<i_k\le 4}|A_{i_1}\cap ... \cap A_{i_k}|$, e $S_0=|X|$. La última observación: $A_{i_1}\cap ... \cap A_{i_k}=A_{i_1}\cap A_{i_k}$ (que de nuevo no sería tan fácil, en general, por desgracia) y vamos a hacer esto:

$$\sum_{k=0}^{4}(-1)^kS_k=|X|-|A_1|-|A_2|-|A_3|-|A_4|+|A_1\cap A_2|+|A_1\cap A_3|+|A_1\cap A_4|+|A_2\cap A_3|+|A_2\cap A_4|+|A_3\cap A_4|-|A_1\cap A_2\cap A_3|-|A_1\cap A_2\cap A_4|-|A_1\cap A_3\cap A_4|-|A_2\cap A_3\cap A_4|+|A_1\cap A_2\cap A_3\cap A_4|=\\=|X|-|A_1|-|A_2|-|A_3|-|A_4|+|A_1\cap A_2| + |A_2 \cap A_3|+|A_3\cap A_4|= \\ =7!-4\cdot 4\cdot 3! + 3\cdot 2\cdot 2!=4956$$

Es eso correcto? Me temo que no :-( Mientras se espera por la respuesta voy a escribir un programa que cuenta estas permutaciones y comprobar si es una buena respuesta.

Yo estaría muy agradecido por cualquier ayuda, respondiendo a mi pregunta, consejos y sugerencias acerca de este tipo de problemas. Realmente quiero terminar de comprender este principio.

Saludos

Answer 1

Para el primer problema, que no acababa de uso de inclusión/exclusión. Que nos permiten contar el número que contienen la subcadena $121$. De su $6\cdot 9^5$ tenemos que restar las secuencias que han sido el doble cómputo por $6\cdot 9^5$.

Cuántas secuencias hay que tienen dos o más cadenas de la forma $121$? Es más complicado de lo que parece. Hemos contado $121121xy$ dos veces, pero también nos han contado $12121xyz$ dos veces.

Después de hacer la resta, parece que va ha restado mucho, por ejemplo, las secuencias de $1212121x$, por lo que tendrá que añadir.

Answer 2

Creo que me gustaría resolver el primer problema, por medio de relaciones recursivas.

Digamos que usted tiene un n dígitos de la secuencia que contiene los números enteros del 1 al 9 sólo, y usted quiere encontrar T(n), que se define como el número de secuencias que no contienen una larga "121".

Lo que yo haría es que tenga que dividir en los siguientes casos:

Caso 1: Si T(n) se inicia con nada, a excepción de 1 a continuación, usted tiene efectivamente 8T(n-1) ya que hay 8 opciones para el primer número y T(n-1) opciones para el (n-1) término de la secuencia.

Caso 2: Si T(n) se inicia con 1 a continuación, usted mira el segundo número. Si se inicia con nada, excepto la 2, a continuación, usted tiene 8T(n-2) por razones similares.

Caso 3: Si T(n) comienza con "12", a continuación, el tercer número no puede ser "1" o es una infracción de la relación para que usted tenga 8T(n-3).

Por lo tanto, usted tiene la relación T(n)=8[T(n-1)+T(n-2)+T(n-3)]. Usted puede encontrar los valores de T(1), T(2) y T(3) (que será de 9, 9x9=81 y 9^3-1=728) y resolver para T(8). :)

Espero que esta ayuda, y por favor dime si he cometido un error en cualquier lugar.