Número de permutaciones de $D,D,D,O,O,O,G,G,G$ tal que no hay dos $D$ son adyacentes y no hay dos $G$ son adyacentes

Aug 19 2020

Tengo el siguiente problema. Ya lo resolví pero no estoy contento con mi solución. Espero una solución más hábil y tal vez alguien pueda ayudar con ella. ¿Hay alguna forma de resolver este problema solo con el método de estrellas / barras?

Calcule el número de formas de permutar todas las letras de $D,D,D,O,O,O,G,G,G$ tal que no hay dos $D$ son adyacentes y no hay dos $G$ son adyacentes.

Mi intento.

por $k=2,3$, dejar $\Delta_k$ denotar el conjunto de permutaciones st solamente $k$ de $D$ son adyacentes, y deje $\Gamma_k$ denotar el conjunto de permutaciones st solamente $k$ de $G$son adyacentes. Dejar$U$ ser el conjunto de todas las permutaciones sin ninguna condición.

Luego $$|U|=\frac{(3+3+3)!}{3!3!3!}=1680.$$ Tenemos $$|\Delta_3|=\frac{(1+3+3)!}{1!3!3!}=140$$ (como $\Delta_3$ es el conjunto de permutaciones de $DDD,O,O,O,G,G,G$), y $$|\Delta_2|+2|\Delta_3|=\frac{(1+1+3+3)!}{1!1!3!3!}=1120$$ ya que este número cuenta las permutaciones de $DD,D,O,O,O,G,G,G$. Por lo tanto$$|\Delta_2|=1120-2(140)=840.$$ similar $|\Gamma_3|=140$ y $|\Gamma_2|=840$.

Queremos encontrar $|\Delta_i\cap\Gamma_j|$. Ya que$\Delta_3\cap\Gamma_3$ es el conjunto de permutaciones de $DDD,O,O,O,GGG$, $$|\Delta_3\cap\Gamma_3|=\frac{(1+3+1)!}{1!3!1!}=20.$$ Ya que $|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|$ cuenta las permutaciones de $DD,D,O,O,O,GGG$, tenemos $$|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|=\frac{(1+1+3+1)!}{1!1!3!1!}=120$$ entonces $$|\Delta_2\cap\Gamma_3|=120-2(20)=80.$$ similar $|\Delta_3\cap\Gamma_2|=80$.

Ahora queremos encontrar $|\Delta_2\cap\Gamma_2|$. Ya que$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|$ cuenta el número de permutaciones de $DD,D,O,O,O,GG,G$, obtenemos $$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|=\frac{(1+1+3+1+1)!}{1!1!3!1!1!}=840.$$ Por lo tanto $$|\Delta_2\cap\Gamma_2|=840-2(80)-2(80)-4(20)=440.$$

Por el principio de inclusión-exclusión tenemos $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=\sum_{k=2}^3|\Delta_k|+\sum_{k=2}^3|\Gamma_k|-\sum_{i=2}^3\sum_{j=2}^3|\Delta_i\cap \Gamma_j|.$$ Por lo tanto $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=2(840)+2(140)-(440+80+80+20)=1340.$$ La pregunta pide el tamaño de $U\setminus(\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3)$, cual es $$|U|-|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=1680-1340=340.$$

Respuestas

4 MathLover Aug 19 2020 at 12:56

No sé si hay una forma más ingeniosa de hacer esto, pero puede ser más simple, incluso usando su enfoque.

Las permutaciones de "DD DGGGOO O" cubren todos los casos de D adyacentes y G adyacentes excepto donde G son adyacentes pero D no lo son.

$i)$ Permutaciones de "DD DGGGOO O" $= \dfrac{8!}{3!3!} - \dfrac{7!}{3!3!} = 980$

[ La resta es para cuidar de DD D y D DD adyacentes considerados diferentes. Por lo tanto, las permutaciones de DDD se cuentan dos veces y deben eliminarse una vez. ]

$ $

$ii)$ Permutaciones de "GG GOO O" y colocación $3$ D está en $3$ de los no adyacentes $6$ lugares

$$= \dfrac{5!}{3!}.{^6}C_3 - \dfrac{4!}{3!}.{^5}C_3 = 360$$

[ La resta es para cuidar de GG G y GG adyacentes considerados diferentes. Entonces, permutaciones GGG y colocar D en$3$ fuera de $5$los lugares se han contado dos veces y deben contarse una vez. ]

$ $

Que te da los arreglos deseados $= 1680 - 980 - 360 = 340$

1 DanielN Aug 20 2020 at 22:27

Empiezo por reformular y modificar ligeramente el problema, luego lo resuelvo bajo esta nueva forma; el pasaje al problema inicial es canónico.

Problema. Considere el conjunto$S=S(d+4)=\{x_1, x_2, x_3, y_1, y_2, y_3, z_1, \ldots, z_{d-2}\}$. Una permutación de$S$ se llama $x,y$- adyacente libre (y posterior de tipo$(1,1)$) si no hay dos $x$y no dos $y$son adyacentes. Determine el número de$x,y$-permutaciones libres adyacentes.

Tenga en cuenta que los elementos $x_1$, $x_2$y $x_3$ son vistos como elementos distintos (y lo mismo para el $y$'s).
El paso del problema a la pregunta inicial viene dado por la fórmula obvia$$ \frac{\text{number of $x, y$-adjacent free permutations of $S$}} {3!\, 3!\, (d-2)!} $$ en el que tomamos $d=3$.

La solución se inclina hacia cálculos algebraicos recursivos (el modelo es el triángulo de Pascal). En el lado positivo, podríamos estar contentos con fórmulas recursivas (generalizaciones, cálculos de otros números similares ...). En el lado negativo, habrá índices de vuelo engorrosos en todas las direcciones.

Notación y descripción de la solución. Dejar$S^{a,b}\subset S$ ser el subconjunto $$ S^{a,b} = \{ x_1,\ldots,x_a, y_1, \ldots, y_b, z_1, \ldots, z_{d-2}\} \subset S $$ con $1\leq a,b\leq3$. Tiene$d+a+b-2$elementos. Denotamos por$P_{(i,j)}^{a,b}$, con $i\leq a$ y $j\leq b$, el conjunto de permutaciones de $S^{a,b}$ exactamente con $i$ adyacente $x$y $j$ adyacente $y$'s, llamadas permutaciones de tipo $(i,j)$. Claramente, el conjunto de todas las permutaciones de$S^{a,b}$ es $$ \bigcup_{\substack{1\leq i\leq a\\1\leq j\leq b}} P_{(i,j)}^{a,b}. $$ Queremos calcular $N_{(1,1)}^{3,3}$, el cardenal de $P_{(1,1)}^{3,3}$. La idea es hacer el cálculo de forma recursiva utilizando la siguiente filtración de$S^{3,3}$: $$ S^{1,1} \subset S^{2,1} \subset S^{3,1} \subset S^{3,2} \subset S^{3,3}. $$ Cada $N_{(i,j)}^{a,b}$ correspondiente al subconjunto $S^{a,b}$ en la filtración se expresa como una combinación lineal con coeficientes enteros de todos los $N$del subconjunto anterior. Una vez que se determinan los coeficientes (usando la combinatoria de la construcción) para todos estos pasajes, el problema está resuelto.

Encontrar los coeficientes. Empecemos por lo que buscamos:$$ N_{(1,1)}^{3,3} = d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2}. $$Los otros coeficientes son todos cero en este caso. La explicación es que una permutación de$S^{3,3}$ de tipo $(1,1)$ sólo se puede emitir a partir de una permutación de $S^{3,2}$ que es de tipo $(1,1)$ o de tipo $(2,1)$. Para una permutación en el primer caso, hay exactamente$d=d+4-4$ posiciones (fuera de $d+4$) dónde $y_3$ se puede insertar (adyacente a ninguno $y_1$ ni $y_2$). En este último caso,$y_3$ debe insertarse entre los dos adyacentes $x$s.

Seguimos con las fórmulas para $N_{(1,1)}^{3,2}$ y $N_{(2,1)}^{3,2}$ usando el pasaje de $S^{3,1}$ a $S^{3,2}$en nuestra filtración. La formula para$N_{(1,1)}^{3,2}$ es casi igual que el anterior: $$ N_{(1,1)}^{3,2} = (d+3-2)\,N_{(1,1)}^{3,1} + N_{(2,1)}^{3,1} = (d+1)\,N_{(1,1)}^{3,1} + N_{(2,1)}^{3,1}. $$ La formula para $N_{(2,1)}^{3,2}$es más complicado. Se lee$$ N_{(2,1)}^{3,2} = 0\,N_{(1,1)}^{3,1} + (d+3-3)\,N_{(2,1)}^{3,1} + 2N_{(3,1)}^{3,1} \\ = d\,N_{(2,1)}^{3,1} + 2N_{(3,1)}^{3,1}. $$ El coeficiente $d+3-3$ viene de la siguiente observación: Si un tipo $(2,1)$ permutación de $S^{3,2}$ se emite de un tipo $(2,1)$ permutación de $S^{3,1}$, luego $y_2$ tiene exactamente $d+3-3$ posibles lugares para insertarse en: $d+3$ es el número total de plazas y $y_2$ no puede ocupar ni el lugar entre el adyacente $x$ni ninguno de los dos lugares adyacentes a $y_1$.

Mirando las dos últimas fórmulas, notamos que a partir de ahora necesitamos todos los $N$corresponde a los subconjuntos restantes de la filtración. Pero son menos y las fórmulas son más fáciles de descifrar. Obtenemos sucesivamente:

para $S^{2,1}\subset S^{3,1}$ $$ N_{(1,1)}^{3,1} = (d+2-4)\,N_{(1,1)}^{2,1} + 0\,N_{(2,1)}^{2,1} $$ $$ N_{(2,1)}^{3,1} = 4\,N_{(1,1)}^{2,1} + (d+2-3)\,N_{(2,1)}^{2,1} $$ $$ N_{(3,1)}^{3,1} = 0\,N_{(1,1)}^{2,1} + 3\,N_{(2,1)}^{2,1} $$
para $S^{1,1}\subset S^{2,1}$ $$ N_{(1,1)}^{2,1} = (d+1-2)\,N_{(1,1)}^{1,1} \quad\text{and}\quad N_{(2,1)}^{2,1} = 2\,N_{(1,1)}^{1,1}. $$

Los cálculos ahora, para obtener$N_{(1,1)}^{3,3}$ es suficiente retroceder comenzando con $N_{(1,1)}^{1,1}=d!$. Realicemos los cálculos enfatizando su carácter algorítmico. Espero que la notación a continuación se explique por sí misma.