5 votos

¿Cómo puedo aplicar el principio de inclusión-exclusión en esta tarea?

Tarea sencilla de combinatoria: Cuántas secuencias existen, que consisten en las letras A, B, C, D, ..., O, P; si ninguna secuencia podría tener cualquiera de estas palabras: PONK, DOBA, COP. Esta tarea es sobre el principio de inclusión-exclusión, pero no puedo entender por qué. Creo que los conjuntos que incluyen PONK, COP o DOBA no tienen elementos comunes, porque sólo hay una letra O. ¿Alguien puede explicarme cómo resolver esta tarea?

Acabo de comprender la complejidad de esta cuestión. Una tarea real también describir, que:

editar: La secuencia no puede tener ninguna de las palabras {PONK, DOBA, COP} también si eliminamos algunas letras. Esto significa que la secuencia A P C O D N E K F ... tampoco debe contarse

4voto

DiGi Puntos 1925

En el problema corregido todavía hay $16!$ secuencias en conjunto. El número que incluye las letras PONK en ese orden (pero no necesariamente adyacentes) puede calcularse como sigue: hay $\binom{16}4$ formas de elegir las cuatro posiciones que deben ocupar las letras P, O, N y K, y entonces hay $12!$ formas de permutar las letras restantes, por lo que hay $\binom{16}412!$ secuencias que contienen ...P...O...N...K...

De forma similar se pueden contar las secuencias que contienen ...D...O...B...A... y las que contienen ...C...O...P... . Sin embargo, los conjuntos $\{\text{P,N,K}\}$ , $\{\text{D,B,A}\}$ y $\{\text{C,P}\}$ son disjuntos por pares, por lo que una secuencia puede contener dos o incluso las tres subsecuencias, y tendremos que realizar el cálculo completo de inclusión-exclusión.

Intentemos contar las secuencias que contienen tanto ...P...O...N...K... como ...D...O...B...A... . Primero elegimos $7$ de la $16$ lugares para las letras P, O, N, K, D, B y A; esto puede hacerse en $\binom{16}7$ formas. La O debe ocupar la tercera de estas siete posiciones. La P y la D deben ocupar las dos primeras, pero pueden hacerlo en cualquier orden. Hay $\binom42$ maneras de elegir las dos posiciones para N y K, que deben ir en ese orden, y B y A ocuparán entonces las posiciones restantes, también en ese orden. Por último, los otros $9$ Las letras pueden permutarse arbitrariamente. Por lo tanto, el total es

$$\binom{16}7\cdot2\cdot\binom42\cdot9!\;.$$

Debería poder utilizar análisis similares para calcular los términos restantes del cálculo de inclusión-exclusión.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X