Cuántas palabras pueden escribirse con $aabbbccdd$ de manera tal que no hay dos iguales letras son adyacentes?

Question

Estoy tratando de contar en esta usando el principio de inclusión-exclusión. He hecho lo siguiente:

• Contando el número de permutaciones de $aabbbccdd$.

1. $9!$

• Contando el número de permutaciones de $aabbbccdd$ sin repeticiones.

2. $\displaystyle\frac{9!}{2!3!2!2!}$

• Ahora supongo que necesito debe contar el número de permutaciones en el que todas las cartas están juntos, lo que es $4!$.

3. $\displaystyle\frac{9!}{2!3!2!2!}-4!$

• Ahora contando el número de permutaciones en las que $a,c,d$ son adyacentes, supongo que este número es $\displaystyle \frac{3\cdot 7!}{3!2!2!}$.

4. $\displaystyle\frac{9!}{2!3!2!2!}-4!-\frac{3\cdot 7!}{3!2!2!}$

• Ahora contando el número de permutaciones en las que hemos permutaciones de 2 $b$'s juntos y, a continuación, el número de permutaciones que han $3$ $b$'s juntos, he a$3\cdot 2/2!$, $\displaystyle\frac{3 \cdot 7!}{2!2!2!}+\frac{6!}{2!2!2!}$

5. $\displaystyle\frac{9!}{2!3!2!2!}-4!-\frac{3\cdot 7!}{3!2!2!}-\frac{3 \cdot 7!}{2!2!2!}-\frac{6!}{2!2!2!}$

• Ahora sé que son las intersecciones de allí. Pero soy incapaz de pensar en algo para contar, supongo que debo agregar el número de intersecciones con el resultado:

6. $\displaystyle \frac{9!}{2!3!2!2!}-\left( 4!-\frac{3\cdot 7!}{3!2!2!}-\frac{3 \cdot 7!}{2!2!2!}-\frac{6!}{2!2!2!}+ \cap_n \right)$

Es esto correcto? Si es así, ¿cómo puedo contar las intersecciones? Supongo que la fórmula se expresa como:

$$\displaystyle \frac{9!}{2!3!2!2!} \cap (4! \cup \frac{3\cdot 7!}{3!2!2!} \cup \frac{3 \cdot 7!}{2!2!2!} \cup \frac{6!}{2!2!2!})$$

Answer 1

Comenzamos por escrito arbitraria de las palabras que contienen sólo $a$, $a$, $c$, $c$, $d$, $d$.

Hay ${6!\over2!2!2!}=90$ tales palabras .

$6$ de estas palabras contienen la prohibida pares $a^2$, $c^2$, y $d^2$. A continuación, necesitamos los tres $b$'s para separar estos pares. Hace $6$.

Hay ${4!\over2!}=12$ palabras que contienen $a^2$, $c^2$, y $d$, $d$ en cualquier orden. En $6$ de estos la $d$'s están emparejados así. De ello se desprende que hay $3\cdot(12-6)=18$ palabras que contienen exactamente dos prohibido pares. Para cada palabra, necesitamos dos $b$'s para separar lo prohibido pares, y hay $5$ ranuras de la izquierda para la tercera $b$. Hace $18\cdot 5=90$.

Hay ${5!\over2!2!}=30$ palabras que contengan $a^2$, y $c$, $c$, $d$, $d$ en cualquier orden. $2\cdot6$ de estas palabras contienen exactamente una de $c^2$$d^2$, y otro $6$ contienen tanto $c^2$$d^2$. De ello se desprende que hay $3\cdot(30-12-6)=36$ palabras que contienen exactamente una prohibido par. Nos necesitamos el uno al $b$ para separar a esta pareja, y hay $6$ ranuras de la izquierda para el resto de los dos $b$'s. Hace $36\cdot{6\choose2}=540$.

Hay $90-6-18-36=30$ palabras que no contienen prohibido par. Esto permite a $7$ ranuras donde el $b$'s puede ser escrita. Hace $30\cdot{7\choose3}=1050$.

Sumando los obtenidos de los recuentos da un gran total de $$N=1686$$ allowed words from $un$, $$, $b$, $b$, $b$, $c$, $c$, $d$, $d$.

Answer 2

Utilizar el principio de inclusión y exclusión, de recorrerse para la tripplet y los tres pares.

$$\left(\tfrac{9!}{3!\;2!^3}-\tfrac{8!\;2}{2!^3}+\tfrac{7!}{2!^3}\right) -\tbinom{3}{1}\left(\tfrac{8!}{3!\;2!^2}-\tfrac{7!\;2}{2!^2}+\tfrac{6!}{2!^2}\right) +\tbinom{3}{2}\left(\tfrac{7!}{3!\;2!}-\tfrac{6!\;2}{2!}+\tfrac{5!}{2!}\right) -\left(\tfrac{6!}{3!}-5!\;2+4!\right)$$

• $\frac{9!}{3!\;2!^3}$ cuenta todas las permutaciones del conjunto múltiple.

• $-\frac{8!\; 2}{\;2!^2}$ sobre excluye la permutación donde dos b son adyacentes.

• $+\frac{7!}{2!^3}$ reincludes permutaciones, donde todos los tres b son adyacentes

• $-{3\choose 1}\left(\frac{8!}{3!\;2!^2}-\frac{7!\;2}{2!^2}+\frac{6!}{2!^2}\right)$ excluye (como el anterior) de donde también un par de a, co d están juntos

• Luego nos reinclude donde también dos pares de esos tres que están juntos.

• Finalmente rexcluding donde también todos los tres están juntos/