Número de permutações de $D,D,D,O,O,O,G,G,G$ de modo que não haja dois $D$ são adjacentes e não há dois $G$ são adjacentes

Aug 19 2020

Eu tenho o seguinte problema. Já resolvi, mas não estou satisfeito com a minha solução. Espero uma solução mais inteligente e talvez alguém possa ajudar com isso. Existe uma maneira de resolver este problema apenas com o método de estrelas / barras?

Calcule o número de maneiras de permutar todas as letras de $D,D,D,O,O,O,G,G,G$ de modo que não haja dois $D$ são adjacentes e não há dois $G$ são adjacentes.

Minha tentativa.

Para $k=2,3$, deixei $\Delta_k$ denotam o conjunto de permutações st apenas $k$ do $D$ são adjacentes, e deixe $\Gamma_k$ denotam o conjunto de permutações st apenas $k$ do $G$são adjacentes. Deixei$U$ ser o conjunto de todas as permutações sem quaisquer condições.

Então $$|U|=\frac{(3+3+3)!}{3!3!3!}=1680.$$ Nós temos $$|\Delta_3|=\frac{(1+3+3)!}{1!3!3!}=140$$ (Como $\Delta_3$ é o conjunto de permutações de $DDD,O,O,O,G,G,G$), e $$|\Delta_2|+2|\Delta_3|=\frac{(1+1+3+3)!}{1!1!3!3!}=1120$$ uma vez que este número conta as permutações de $DD,D,O,O,O,G,G,G$. Portanto$$|\Delta_2|=1120-2(140)=840.$$ similarmente $|\Gamma_3|=140$ e $|\Gamma_2|=840$.

Nós queremos encontrar $|\Delta_i\cap\Gamma_j|$. Desde a$\Delta_3\cap\Gamma_3$ é o conjunto de permutações de $DDD,O,O,O,GGG$, $$|\Delta_3\cap\Gamma_3|=\frac{(1+3+1)!}{1!3!1!}=20.$$ Desde a $|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|$ conta as permutações de $DD,D,O,O,O,GGG$, temos $$|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|=\frac{(1+1+3+1)!}{1!1!3!1!}=120$$ então $$|\Delta_2\cap\Gamma_3|=120-2(20)=80.$$ similarmente $|\Delta_3\cap\Gamma_2|=80$.

Agora queremos encontrar $|\Delta_2\cap\Gamma_2|$. Desde a$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|$ conta o número de permutações de $DD,D,O,O,O,GG,G$, Nós temos $$|\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.$$ Conseqüentemente $$|\Delta_2\cap\Gamma_2|=840-2(80)-2(80)-4(20)=440.$$

Pelo princípio de inclusão-exclusão, temos $$|\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|.$$ Portanto $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=2(840)+2(140)-(440+80+80+20)=1340.$$ A pergunta pergunta sobre o tamanho de $U\setminus(\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3)$, qual é $$|U|-|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=1680-1340=340.$$

Respostas

4 MathLover Aug 19 2020 at 12:56

Não sei se existe uma maneira mais engenhosa de fazer isso, mas pode ser mais simples, mesmo usando a sua abordagem.

Permutações de "DD DGGGOO O" cobrem todos os casos de Ds adjacentes e Gs adjacentes, exceto onde Gs são adjacentes, mas D não são.

$i)$ Permutações de "DD DGGGOO O" $= \dfrac{8!}{3!3!} - \dfrac{7!}{3!3!} = 980$

[ A subtração é para cuidar de DD D adjacente e D DD considerados diferentes. Assim, as permutações DDD são contadas duas vezes e precisam ser retiradas uma vez. ]

$ $

$ii)$ Permutações de "GG GOO O" e colocação $3$ D's em $3$ do não adjacente $6$ lugares

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

[ A subtração é para cuidar de GG G adjacente e G GG considerados diferentes. Assim, as permutações GGG e a colocação de D em$3$ fora de $5$lugares foram contados duas vezes e precisam ser contados uma vez. ]

$ $

Isso dá a você os arranjos desejados $= 1680 - 980 - 360 = 340$

1 DanielN Aug 20 2020 at 22:27

Eu começo redefinindo e modificando ligeiramente o problema, então resolvo-o sob esta nova forma; a passagem para o problema inicial é canônica.

Problema. Considere o conjunto$S=S(d+4)=\{x_1, x_2, x_3, y_1, y_2, y_3, z_1, \ldots, z_{d-2}\}$. Uma permutação de$S$ é chamado $x,y$- adjacente livre (e posterior do tipo$(1,1)$) se não houver dois $x$de e não dois $y$são adjacentes. Determine o número de$x,y$- permutações livres adjacentes.

Observe que os elementos $x_1$, $x_2$e $x_3$ são vistos como elementos distintos (e o mesmo para o $y$'s).
A passagem do problema para a questão inicial é dada pela fórmula óbvia$$ \frac{\text{number of $x, y$-adjacent free permutations of $S$}} {3!\, 3!\, (d-2)!} $$ em que tomamos $d=3$.

A solução se inclina para cálculos algébricos recursivos (o modelo sendo o triângulo de Pascal). Do lado positivo, podemos ficar felizes com fórmulas recursivas (generalizações, cálculos de outros números semelhantes ...). Do lado negativo, haverá índices pesados de voos em todas as direções.

Notação e descrição da solução. Deixei$S^{a,b}\subset S$ seja o subconjunto $$ S^{a,b} = \{ x_1,\ldots,x_a, y_1, \ldots, y_b, z_1, \ldots, z_{d-2}\} \subset S $$ com $1\leq a,b\leq3$. Tem$d+a+b-2$elementos Denotado por$P_{(i,j)}^{a,b}$, com $i\leq a$ e $j\leq b$, o conjunto de permutações de $S^{a,b}$ com exatamente $i$ adjacente $x$'areia $j$ adjacente $y$de, chamadas permutações de tipo $(i,j)$. Claramente, o conjunto de todas as permutações de$S^{a,b}$ é $$ \bigcup_{\substack{1\leq i\leq a\\1\leq j\leq b}} P_{(i,j)}^{a,b}. $$ Queremos calcular $N_{(1,1)}^{3,3}$, o cardeal de $P_{(1,1)}^{3,3}$. A ideia é fazer o cálculo recursivamente usando a seguinte filtragem 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}$ correspondendo ao subconjunto $S^{a,b}$ na filtração é expressa como uma combinação linear com coeficientes inteiros de todos os $N$do subconjunto anterior. Uma vez que os coeficientes são determinados (usando a combinatória da construção) para todas essas passagens, o problema está resolvido.

Encontrando os coeficientes. Vamos começar com o que estamos procurando:$$ N_{(1,1)}^{3,3} = d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2}. $$Os outros coeficientes são todos zero neste caso. A explicação é que uma permutação de$S^{3,3}$ do tipo $(1,1)$ só pode ser emitido a partir de uma permutação de $S^{3,2}$ que é do tipo $(1,1)$ ou do tipo $(2,1)$. Para uma permutação no primeiro caso, há exatamente$d=d+4-4$ posições (fora de $d+4$) Onde $y_3$ pode ser inserido (adjacente a nenhum $y_1$ nem $y_2$) No último caso,$y_3$ deve ser inserido entre os dois adjacentes $x$'s.

Procuramos com as fórmulas para $N_{(1,1)}^{3,2}$ e $N_{(2,1)}^{3,2}$ usando a passagem de $S^{3,1}$ para $S^{3,2}$em nossa filtração. A fórmula para$N_{(1,1)}^{3,2}$ é quase igual ao 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}. $$ A fórmula para $N_{(2,1)}^{3,2}$é mais complicado. Lê$$ 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}. $$ O coeficiente $d+3-3$ vem da seguinte observação: Se um tipo $(2,1)$ permutação de $S^{3,2}$ é emitido de um tipo $(2,1)$ permutação de $S^{3,1}$, então $y_2$ tem exatamente $d+3-3$ possíveis locais a serem inseridos em: $d+3$ é o número total de lugares e $y_2$ não pode ocupar o lugar entre o adjacente $x$nem qualquer um dos dois lugares adjacentes a $y_1$.

Olhando para as duas últimas fórmulas, notamos que a partir de agora precisamos de todos os $N$'s correspondendo aos subconjuntos restantes da filtração. Mas eles são menos e as fórmulas mais fáceis de descobrir. Obtemos sucessivamente:

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}. $$

Os cálculos agora, para obter$N_{(1,1)}^{3,3}$ é suficiente voltar para trás começando com $N_{(1,1)}^{1,1}=d!$. Vamos realizar os cálculos enfatizando seu caráter algorítmico. Espero que a notação abaixo seja autoexplicativa.