¿Cuántas disposiciones diferentes hay?

Question

¿Cuántas disposiciones diferentes hay de las nueve letras A, A, A, B, B, B, C, C, C en una fila si no hay dos letras iguales adyacentes?

Primero traté de encontrar cuántas maneras de organizar por lo menos dos letras similares son adyacentes (el complementario) luego restar del total de maneras sin restricción. Intenté hacerlo mediante la regla de adición extendida (es decir, con el diagrama de Venn de tres círculos) y ahora estoy confundido sobre cómo calcular cada caso.

Mi intento hasta ahora: que a sea el conjunto de 'dos A adyacentes' que b sea el conjunto de 'dos B adyacentes' que c sea el conjunto de "dos C adyacentes".

Necesito encontrar |complemento de a U b U c| (Sea Z conjunto universal, sin restricción) = |Z| - |a| - |b| - |c| + |ab| + |bc| + |ca| - |abc|

Sé que |a| = |b| = |c| y |ab| = |bc| = |ca| por lo tanto |complemento de a U b U c| = |Z| - 3|a| + 3|ab| -|abc|.

|Z| = 9!/3!3!3!, pero no estoy seguro de cómo calcular |a| o |ab| o |abc|

Answer 1

Existen $\binom{6}{3} = 20$ secuencias de tres $A$ y tres $B$ 's. Consideremos las diez secuencias de tres $A$ y tres $B$ que empiezan por $A$ .

$\color{red}{AAABBB}$

$\color{green}{AABABB}$

$\color{green}{AABBAB}$

$\color{blue}{AABBBA}$

$\color{green}{ABAABB}$

$\color{cyan}{ABABAB}$

$\color{magenta}{ABABBA}$

$\color{green}{ABBAAB}$

$\color{magenta}{ABBABA}$

$\color{blue}{ABBBAA}$

No importa cómo coloquemos $C$ en la secuencia $\color{red}{AAABBB}$ al menos dos letras consecutivas serán iguales.

Sólo hay una forma de colocar el $C$ en las secuencias $\color{blue}{AABBBA}$ y $\color{blue}{ABBBAA}$ ya que nos vemos obligados a colocar un $C$ entre cada par de $B$ y el par de $A$ 's.

El número de maneras en que podemos llenar tres de los siete espacios (el principio, el final y los cinco espacios entre letras consecutivas) de la secuencia $\color{cyan}{ABABAB}$ es $\binom{7}{3}$ .

Debemos colocar un $C$ entre el par de $B$ en las secuencias $\color{magenta}{ABABBA}$ y $\color{magenta}{ABBABA}$ lo que nos deja $\binom{6}{2}$ formas de insertar los dos $C$ en los seis espacios restantes.

Debemos colocar una $C$ entre el par de $A$ y otro $C$ entre el par de $B$ en las secuencias $\color{green}{AABABB}$ , $\color{green}{AABBAB}$ , $\color{green}{ABAABB}$ , $\color{green}{ABBAAB}$ , dejando cinco espacios en los que colocar el resto de $C$ .

Por lo tanto, el número de secuencias de tres $A$ 's, tres $B$ y tres $C$ que empiezan por $A$ que no contengan letras consecutivas iguales es $$1 \cdot 0 + 2 \cdot 1 + 2 \cdot \binom{6}{2} + 4 \cdot \binom{5}{1} + 1 \cdot \binom{7}{3} = 0 + 2 + 30 + 20 + 35 = 87$$ Por simetría, también hay $87$ tales secuencias que comienzan con $B$ . Por lo tanto, el número de secuencias de tres $A$ 's, tres $B$ y tres $C$ que no contengan letras consecutivas iguales es $2 \cdot 87 = 174$ .

Answer 2

Sea $A_i$ sea el conjunto de disposiciones con al menos 2 letras consecutivas de tipo $i$ donde $1\le i\le3$ .

Entonces $\displaystyle|\overline{A_1}\cap\overline{A_2}\cap\overline{A_3}|=|S|-\sum_{i}|A_i|+\sum_{i<j}|A_i\cap A_j|-|A_1\cap A_2\cap A_3|,\;\;$ donde $\displaystyle|S|=\frac{9!}{3!3!3!}=\color{blue}{1680}$ .

1) Encontrar $|A_i|$ contaremos el número de arreglos de AA, A, B, B, B, C, C, C y luego

$\;\;\;$ ajustar por exceso de recuento, lo que da $\displaystyle \frac{8!}{3!3!}-\frac{7!}{3!3!}=\color{blue}{980}$ .

2) Encontrar $|A_i\cap A_j|$ contaremos el número de arreglos de AA, A, BB, B, C, C, C y luego

$\;\;\;$ ajustar por exceso de recuento, lo que da $\displaystyle\frac{7!}{3!}-2\cdot\frac{6!}{3!}+\frac{5!}{3!}=\color{blue}{620}$ .

3) Encontrar $|A_1\cap A_2\cap A_3|$ contaremos el número de arreglos de AA, A, BB, B, CC, C y luego

$\;\;\;$ ajustar por exceso de recuento, lo que da $\displaystyle6!-3\cdot5!+3\cdot4!-3!=\color{blue}{426}$ .

Por lo tanto $\displaystyle|\overline{A_1}\cap\overline{A_2}\cap\overline{A_3}|=1680-3\cdot980+3\cdot620-426=\color{red}{174}$ .

Answer 3

Una forma de encontrar $|a|$ .

Sea $i,k$ sean enteros no negativos y que $j$ ser un positivo entero (véase también el comentario de Joriki).

Sólo mirando $B$ y $C$ hay $\binom{6}{3}$ disposiciones para ellos.

En relación con $iAAAk$ para $i+k=6$ hay $\binom{7}{1}$ soluciones.

En relación con $iAAjAk$ para $i+j+k=6$ hay $\binom{7}{2}$ soluciones.

En relación con $iAjAAk$ para $i+j+k=6$ hay $\binom{7}{2}$ soluciones.

Esto llevó a $\left|a\right|=\binom{6}{3}\left[\binom{7}{1}+\binom{7}{2}+\binom{7}{2}\right]$ .

Entero superior $i$ representa el número de no $A$ que preceden a la primera $A$ y $j$ y $k$ son similares. El contexto debería ser suficiente.