Ir ao conteúdo principal

Análise Combinatória e Probabilidade: Com Aplicações no SageMath

Ricardo Machado, Gabriel Guedes

Seção 1.6 Permutações Circulares

Definição 1.6.1.

O número de permutações circulares de \(n\) elementos, é o número de maneiras de organizar \(n\) objetos distintos ao longo de um círculo fixo, isto é, não pode ser retirado do plano e virado, mas pode ser rotacionado. Abaixo, temos as duas possíveis permutações circulares envolvendo três elementos distintos.
Figura 1.6.2. Três representações de uma permutação circular com 3 elementos distintos.
Figura 1.6.3. Três representações de outra permutação circular com 3 elementos distintos.
O número de permutações circulares com \(n\) elementos distintos é denotado por:
\begin{equation*} PC_n ~~\text{ ou }~~ PC(n). \end{equation*}
Numere as \(n\) posições em um círculo. Assim, temos \(n!\) maneiras de colocar os \(n\) objetos distintos nas \(n\) posições. Uma vez feito isto, devemos dividir o número total de permutações pelo número de posições equivalentes por rotação, que é \(n\text{.}\) Portanto,
\begin{equation*} PC_n = \frac{n!}{n} = (n-1)!. \end{equation*}

Tecnologia 1.6.5.

A lista com todas as permutações circulares, pode ser obtida com o seguinte comando:
O número de permutações circulares com 10 elementos pode ser calculado da seguinte forma:

Exemplo 1.6.6.

Quantas rodas de ciranda podem ser formadas com 8 pessoas?
Solução.
Basta calcular o número de permutações circulares de 8 elementos.
\begin{equation*} PC(8) = 7! = 5040. \end{equation*}

Exemplo 1.6.7.

Quantas rodas de ciranda podem ser formadas com 8 pessoas, se duas determinadas pessoas não podem ficar juntas?
Solução.
Calculamos o número de permutações circulares com 8 elementos, \(PC(8)\text{.}\) Agora, subtraímos desse total, o número de permutações de 8 elementos, na qual, dois deles estão juntos.
Figura 1.6.8. Duas formas de organizar os elementos 1 e 2.
O que dá um total de \(PC(7)\times 2\) permutações circulares, pois temos duas formas de permutar os dois elementos que estão juntos, depois disso, olhamos para a roda de ciranda como se tivesse apenas 7 elementos. Portanto a resposta é
\begin{equation*} PC(8)-PC(7)\times2 = 5040 - 720\times 2 = 3600. \end{equation*}
Numere as \(n\) posições em um círculo. Temos \(PR_n^{\beta_1, \beta_2, \ldots, \beta_k}\) maneiras de colocar os \(n\) objetos nas \(n\) posições.
A condição \(\mathrm{MDC}(\beta_1, \beta_2, \dots, \beta_k) = 1 \) garante que não há simetria periódica no arranjo circular que tornaria permutações distintas por rotação equivalentes. Se \(\mathrm{MDC}(\beta_1, \beta_2, \dots, \beta_k) > 1\text{,}\) algumas permutações seriam contadas múltiplas vezes, e a fórmula precisaria ser ajustada. Como não há simetria periódica, devemos dividir \(PR_n^{\beta_1, \beta_2, \ldots, \beta_k}\) pelo número de posições equivalentes por rotação, que é \(n\text{.}\) Portanto,
\begin{equation*} PCR_n^{\beta_1, \beta_2, \ldots, \beta_k} = \frac{n!}{\beta_1 ! \beta_2 ! \cdots \beta_k !}\times \frac{1}{n} = \frac{(n-1)!}{\beta_1 ! \beta_2 ! \cdots \beta_k !}. \end{equation*}

Exemplo 1.6.10.

Na escola infantil ABC, as mesas são circulares e comportam exatamente 6 cadeiras. Considere que estão disponíveis as seguintes cadeiras para serem dispostas ao redor de uma dessas mesas: 2 cadeiras vermelhas, 2 cadeiras azuis, 1 cadeira amarela e 1 cadeira rosa. De quantas maneiras distintas é possível organizar essas cadeiras ao redor da mesa, considerando que permutações circulares equivalentes não devem ser contadas mais de uma vez?
Resposta.
30
Solução.
Como \(\mathrm{MDC}(2,2,1,1)=1\text{,}\) podemos aplicar diretamente o Teorema 1.6.9. Assim, a resposta é dada por
\begin{equation*} PCR_{6}^{2, 2} = \frac{5!}{2!2!} = \frac{5\times 4 \times 3 \times 2 \times 1}{4} = 5\times 3\times 2 = 30. \end{equation*}

Nota 1.6.11.

A fórmula geral, sem a restrição no MDC, para calcular o número de permutações circulares com repetição pode ser encontrada no livro: Handbook of discrete and combinatorial mathematics de Kenneth Rosen [6.3]. Abaixo, na Tecnologia 1.6.12, este cálculo pode ser feito usando o SageMath.

Tecnologia 1.6.12.

No campo "Lista": Digite os elementos em uma lista, separados por vírgula (ex: ['A','A','B','C'] ou [1, 2, 2, 3]).
Clique no botão "Update": O sistema irá:
  • Verificar se a fórmula simplificada (Teorema 1.6.9) pode ser usada.
  • Calcular o número exato de permutações circulares distintas, mesmo em casos com repetições ou simetrias.
Figura 1.6.13.

Exercícios Exercícios

1.

De quantos modos 7 meninos e 7 meninas podem formar uma roda de ciranda de modo que pessoas de mesmo sexo não fiquem juntas?
Resposta.
3628800
Solução.
Existem \(PC_7 = 6!\) maneiras de formar uma roda com as meninas. Depois disso, os \(7\) meninos devem ser postos nos \(7\) lugares entre as meninas, isto pode ser feito de \(7!\) maneiras. No total são \(6!\times 7! = 3628800\) rodas de cirandas possíveis.

2.

De quantos modos 18 casais podem formar uma roda de ciranda de modo que cada homem permaneça ao lado de sua mulher?
Resposta.
93241325150797824000
Solução.
Considere cada casal como uma coisa só. Assim, temos \(PC_{18}\) maneiras de formar uma roda com os \(18\) casais. Depois disso, cada casal tem duas escolhas: marido à direita da esposa ou marido à esquerda da esposa. Portanto, no total são \(PC_{18}\times 2^{18}\) rodas de cirandas possíveis.

3.

(Fundação CEFETMINAS - Prefeitura de Barbacena - Enfermeiro - 2016). Em uma empresa, as reuniões ocorrem em uma sala de mesa circular, segundo os seguintes critérios:
  • O presidente e o vice-presidente sempre se sentam um ao lado do outro.
  • Os três gerentes sempre se sentam um ao lado do outro.
Considerando-se uma reunião com 9 pessoas, o número de maneiras que elas poderão ocupar os assentos de tal forma que esses critérios sejam cumpridos é
\begin{equation*} a) 720. \quad b) 1440. \quad c) 1680. \quad d) 3360. \end{equation*}
Resposta.
\(b) 1440.\)
Solução.
Considere o presidente e o vice-presidente como uma coisa só, isto pode ser organizado de \(2!\) maneiras. Considere, também, os três gerentes como uma coisa só, isto pode ser organizado de \(3!\) maneiras. Para as \(9\) pessoas que serão organizadas em uma mesa circular, ainda faltam \(4\) pessoas, mas o círculo formado é equivalente a um círculo com \(6\) lugares, devido aos agrupamentos mencionados. Portanto, o total de maneiras que as \(9\) pessoas poderão ocupar os assentos é
\begin{equation*} PC_6 \times 2! \times 3! = 5!\times 2\times 6 = 1440. \end{equation*}

4.

(POTI - Nível 3). De quantas maneiras podemos colocar 20 pessoas em uma roda-gigante com 10 lugares, cada um para duas pessoas, se:
  1. a ordem dentro de cada lugar é relevante?
  2. a ordem dentro de cada lugar não é relevante?
Resposta.
  1. \(\displaystyle 2\times 19!\)
  2. \(\displaystyle \dfrac{19!}{2^9}\)
Solução.
item a. Cada banco da roda-gigante pode ser dividido em duas partes, totalizando 20 assentos numerados. Uma vez feito isso, para cada permutação possível das 20 pessoas, há apenas uma forma de distribuí-las nesses assentos. No entanto, como a roda-gigante é circular e possui 10 bancos dispostos em círculo, precisamos considerar as simetrias geradas pela rotação da roda. Assim, devemos dividir o total de permutações, dado por \(20!\text{,}\) pelo número de posições equivalentes por rotação, que é 10. Portanto, o número de maneiras de colocar as 20 pessoas na roda-gigante é
\begin{equation*} \frac{20!}{10} = 2\times 19!. \end{equation*}
item b. Se a ordem não é relevante, basta dividir por \(2! = 2\) em cada lugar, obtendo
\begin{equation*} \frac{2\times 19!}{2^{10}} = \frac{19!}{2^9}. \end{equation*}

5.

(Portal da Obmep) Dos 12 estudantes da uma turma, seis serão escolhidos para participar de um debate em uma mesa circular. José, Cléber, Márcia e Luíza só irão se forem juntos; de tal forma que Márcia e Luíza vão sentar lado a lado e o José e o Cléber nunca irão sentar lado a lado à mesa. De quantas maneiras distintas podem se sentar?
Resposta.
4032
Solução.
Observe que precisamos separar em dois casos.
1º Caso: José, Cléber, Márcia e Luíza não participam do debate. Neste caso temos \(C_8^6\) maneiras de escolher as pessoas que vão participar do debate e \(PC_6\) maneiras de organizar as pessoas na mesa circular. No total não \(C_8^6\times PC_6 = 28\times 120=3360\) maneiras.
2º Caso: José, Cléber, Márcia e Luíza participam do debate. Neste caso, vamos contar sem a restrição de José e Cléber não sentarem juntos e subtrair dos casos em que eles sentam juntos. Em ambos os casos precisamos escolher 2 pessoas de 8 disponíveis para completar a mesa.
Sem a restrição de José e Cléber não sentarem juntos temos duas maneiras de colocar Márcia e Luíza juntas na mesa e temos mais 4 pessoas para colocar na mesa. Então, são \(2\times PC_5\) maneiras de organizar essas 6 pessoas.
Contando os casos em que José e Cléber sentam juntos, temos duas maneiras de colocar Márcia e Luíza e duas maneiras de colocar José e Cléber juntos na mesa. Uma vez feita esssa escolhas, ficamos com o equivalente a 4 pessoas para serem organizadas numa mesa circular, ou seja, são \(2\times 2\times PC_4\) maneiras. Assim, a quantidade de maneiras do 2º caso é dada por:
\begin{align*} C_8^2\times(2\times PC_5-2\times 2\times PC_4)=\amp~ 2\times C_8^2(P_4-2\times P_3)\\ =\amp~2\times 28(24-2\times 6)\\ =\amp~672. \end{align*}
Portanto, juntando os dois casos, o número total de maneiras é
\begin{equation*} 3360+672=4032. \end{equation*}

6.

(AIME 1996)
Duas casas de um tabuleiro \(7\times7\) são pintadas de amarelo e as outras são pintadas de verde. Duas pinturas são ditas equivalentes se uma é obtida a partir de uma rotação aplicada no plano do tabuleiro. Quantas pinturas inequivalentes existem?
Resposta.
300
Solução.
Vamos separar a contagem em três casos:
  1. Um dos quadrados pintados de amarelo é o quadrado central;
  2. Os dois quadrados pintados de amarelo são simetricos;
  3. Os dois quadrados pintados de amarelo não são semétricos (sem o central pintado de amarelo).
Agora, vamos calcuar o total de maneiras de pintar os dois quadrados de amarelo em cada caso.
  1. No primeiro caso, como o central é amarelo, o outro quadrado amarelo pode ocupar qualquer um dos 48 quadrados do tabuleiro. Como são quatro posições equivalentes por rotação, precisamos dividir por 4. Assim, o total de maneiras de pintar duas casas de amarelo é:
    \begin{equation*} \frac{48}{4} = 12. \end{equation*}
  2. No segundo caso, como os dois quadrados amarelos precisam ser simétricos, o quadrado central não pode ser pintado. O primeiro quadrado pode ser escolhido de 48 maneiras, uma vez feita essa escolha, o segundo já está determinado. Agora, precisamos "descontar" a ordem dos quadrados amarelos e a simetria do tabuleiro. São dois quadrados e neste caso as posições equivalentes por rotação são duas. Portanto, precisamos dividir por \(2!\cdot 2\text{:}\)
    \begin{equation*} \frac{48}{2!\cdot 2} = 12 \end{equation*}
  3. No terceiro caso, o primeiro quadrado amarelo pode ser escolhido de 48 maneiras e o segundo de 46 maneiras (nem pode ser o central, nem o simétrico ao primeiro). Como são dois quadrados e as posições equivalentes por rotação são 4, precisamos dividir por \(2!\cdot 4\text{:}\)
    \begin{equation*} \frac{48\cdot 46}{8} = 276 \end{equation*}
Como os três casos são excludentes e cobrem todas as posibilidades, a resposta é:
\begin{equation*} 12+12+276 = 300. \end{equation*}

7.

Na escola infantil ABC, as mesas são circulares e comportam exatamente 6 cadeiras. Para uma dessas mesas, estão disponíveis as seguintes cadeiras: 2 vermelhas, 2 azuis, 1 amarela e 1 rosa. Deseja-se organizar essas cadeiras ao redor da mesa e acomodar 6 crianças, uma em cada cadeira. Sabe-se que uma das crianças se recusa a sentar em cadeira vermelha. De quantas maneiras distintas é possível realizar essa disposição, considerando que:
  • cadeiras de mesma cor são indistinguíveis entre si;
  • permutações circulares equivalentes (isto é, rotações da mesma configuração) não devem ser contadas mais de uma vez?
Resposta.
14400
Solução.
Temos um total de \(PCR_{6}^{2,2} = 30\) maneiras de colocar as 6 cadeiras na mesa. Uma vez feito isto, temos 4 opções de cadeiras para a criança que não quer uma cadeira vermelha. Depois disto, temos \(5!\) maneiras de ordenas as outras 5 crianças. No total são
\begin{equation*} PCR_6^{2,2}\times 4 \times 5! = 30\times 4\times 120 = 14400. \end{equation*}

8.

Um artesão está montando um colar circular contendo exatamente 5 contas brancas, 3 contas pretas e 1 conta dourada. Todas as contas de mesma cor são idênticas. Por uma questão de design, o artesão exige que a conta dourada fique posicionada imediatamente entre duas contas pretas. Duas montagens são consideradas iguais se uma pode ser obtida da outra por rotação. De quantas maneiras distintas este colar pode ser montado?
Resposta.
6
Solução.
Para garantir que a conta dourada fique entre duas pretas, devemos uni-las em um único bloco indissociável. Como as contas pretas são idênticas, existe apenas uma forma de montar esse bloco: \(B = (\text{Preta, Dourada, Preta})\text{.}\)
O problema se reduz a organizar circularmente as peças restantes junto com o novo bloco. O novo multiconjunto de peças a ser organizado possui: 5 contas brancas, 1 conta preta (a que sobrou) e 1 bloco \(B\text{.}\)
Temos um total de \(n = 7\) elementos, com multiplicidades \((5, 1, 1)\text{.}\) Como \(\text{mdc}(5, 1, 1) = 1\text{,}\) o arranjo não possui simetrias rotacionais, e podemos aplicar a fórmula direta para o caso de \(\text{mdc} = 1\text{:}\)
\begin{equation*} PCR_7^{5,1,1} = \frac{1}{7} \cdot PR_7^{5,1,1} = \frac{1}{7} \cdot \frac{7!}{5! \, 1! \, 1!} = \frac{42}{7} = 6. \end{equation*}
Portanto, existem 6 colares distintos possíveis.

9.

Em uma vitrine circular giratória, um decorador deve dispor 9 taças: 4 vermelhas, 3 azuis e 2 verdes (taças de mesma cor são indistinguíveis). Para criar um contraste visual, a única exigência é que as duas taças verdes não fiquem lado a lado. Sabendo que a vitrine pode girar livremente, quantas disposições visualmente distintas podem ser criadas?
Resposta.
105
Solução.
Podemos resolver este problema dividindo-o em duas etapas: primeiro posicionamos as taças vermelhas e azuis, e em seguida usamos os espaços gerados por elas para inserir as verdes separadas.
Etapa 1: Organizar as 4 taças vermelhas e 3 azuis em círculo. O multiconjunto é \(S = \{\{V,V,V,V,A,A,A\}\}\text{,}\) com \(n = 7\text{.}\) Como \(\text{mdc}(4, 3) = 1\text{,}\) não há configurações com simetria de rotação. O número de maneiras de dispô-las é:
\begin{equation*} PCR_7^{4,3} = \frac{1}{7} \cdot \frac{7!}{4! \, 3!} = \frac{35}{7} = 5. \end{equation*}
Etapa 2: Inserir as taças verdes. Como o arranjo base das 7 taças não possui simetria, os 7 "espaços" (lacunas) entre elas são posições geometricamente distinguíveis. Para que as 2 taças verdes não fiquem juntas, basta escolhermos 2 dessas 7 lacunas para inseri-las. O número de maneiras de fazer essa escolha é:
\begin{equation*} C_7^2 = \frac{7!}{2! \, 5!} = 21. \end{equation*}
Pelo Princípio Multiplicativo, o total de disposições é \(5 \times 21 = 105\text{.}\)

10.

Uma roleta de brinquedo possui 8 setores idênticos. O fabricante pinta os setores usando 3 vermelhos, 3 pretos e 2 verdes. Após a pintura, 8 fichas são encaixadas na roleta (uma em cada setor): 4 fichas idênticas com a letra "A" e 4 fichas idênticas com a letra "B". Se as fichas com a letra "A" não podem ser colocadas em setores verdes, de quantas maneiras distintas a roleta completa (pintura + fichas) pode ser configurada, a menos de rotação?
Resposta.
1050
Solução.
Etapa 1: Contar os padrões de pintura da roleta. As cores formam o multiconjunto \(\{V^3, P^3, G^2\}\text{,}\) com \(n=8\text{.}\) Como \(\text{mdc}(3, 3, 2) = 1\text{,}\) usamos a fórmula direta:
\begin{equation*} PCR_8^{3,3,2} = \frac{1}{8} \cdot \frac{8!}{3! \, 3! \, 2!} = \frac{560}{8} = 70. \end{equation*}
Existem 70 padrões distintos de roleta.
Etapa 2: Distribuir as fichas. Ao fixar qualquer uma das 70 pinturas, a roleta deixa de ter simetria rotacional. Isso transforma cada um dos 8 setores em posições únicas no espaço relativo da roleta. Sabemos que há exatamente 2 setores verdes e 6 setores não-verdes (vermelhos e pretos). As 4 fichas "A" devem ser obrigatoriamente alocadas nos 6 setores não-verdes. O número de maneiras de escolher essas posições é:
\begin{equation*} C_6^4 = \frac{6!}{4! \, 2!} = 15. \end{equation*}
Uma vez posicionadas as fichas "A", as 4 fichas "B" ocupam as 4 posições restantes de maneira única (pois são idênticas).
Portanto, para cada uma das 70 roletas, há 15 formas de distribuir as fichas. O total de configurações é \(70 \times 15 = 1050\text{.}\)

11.

A cada 100 anos, os líderes das 9 nações dos Reinos Flutuantes se reúnem ao redor da Roda Celeste, uma mesa mística em formato circular com 9 assentos equidistantes. Cada líder representa uma nação que envia representantes segundo suas tradições. Distribuição dos representantes:
  • 3 representantes do Reino da Chama (indistinguíveis: sempre usam a mesma máscara de fogo).
  • 3 representantes do Reino das Marés (indistinguíveis: cobertos por mantos azuis ondulantes).
  • 2 representantes do Reino das Rochas (indistinguíveis: petrificados, imóveis como estátuas).
  • 1 Rainha do Reino dos Ventos (distinta, a única mulher do conselho e sempre senta ao lado de alguém do Reino da Chama ou da Rocha, jamais entre dois representantes do Mar).
Regras do Conselho:
  • A ordem circular é relevante, mas rotações equivalentes não contam como diferentes.
  • Representantes do mesmo reino são indistinguíveis.
  • A Rainha do Vento deve estar sentada ao lado de pelo menos um representante do Reino da Chama ou da Rocha.
De quantas maneiras distintas é possível dispor os 9 representantes ao redor da Roda Celeste, respeitando todas as condições descritas?
Resposta.
500
Solução.
Vamos começar determinando o número total de disposições circulares possíveis dos representantes dos reinos.
Temos os seguintes elementos:
  • 3 representantes do Reino da Chama (C);
  • 3 representantes do Reino das Marés (M);
  • 2 representantes do Reino das Rochas (R);
  • 1 Rainha do Reino dos Ventos (Q).
Como estamos lidando com uma disposição circular de 9 elementos, com repetições, utilizamos a fórmula de permutação circular com repetição:
\begin{equation*} PCR_{9}^{3,3,2} = \frac{(9 - 1)!}{3! \cdot 3! \cdot 2!} = \frac{8!}{3! \cdot 3! \cdot 2!} = \frac{40320}{6 \cdot 6 \cdot 2} = \frac{40320}{72} = 560 \end{equation*}
Agora, vamos contar as disposições em que a Rainha dos Ventos não está sentada ao lado de algum representante do Reino da Chama ou do Reino das Rochas. Isso significa que ela deve estar entre dois representantes do Reino das Marés — ou seja, formando o bloco MQM.
Consideramos então o bloco MQM como uma única entidade. Com isso, temos 7 elementos restantes a organizar ao redor da mesa circular:
  • MQM (bloco fixo que inclui a Rainha);
  • 3 representantes do Reino da Chama (C);
  • 2 representantes do Reino das Rochas (R);
  • 1 representante restante do Reino das Marés (M).
O total de maneiras de dispor esses 7 elementos em círculo, levando em conta as repetições, é dado por:
\begin{equation*} PCR_{7}^{3,2} = \frac{(7 - 1)!}{3! \cdot 2!} = \frac{6!}{6 \cdot 2} = \frac{720}{12} = 60. \end{equation*}
Finalmente, para obter o número de disposições em que a Rainha do Reino dos Ventos está ao lado de pelo menos um representante do Reino da Chama ou das Rochas, subtraímos da quantidade total o número de arranjos em que ela está isolada entre dois representantes das Marés:
\begin{equation*} {PCR}_{9}^{3,3,2} - \text{PCR}_{7}^{3,2} = 560 - 60 = 500. \end{equation*}
Portanto, existem 500 disposições distintas nas quais a Rainha do Reino dos Ventos está sentada ao lado de pelo menos um representante do Reino da Chama ou do Reino das Rochas.
<Anterior^TopPróximo>
Feito com PreTeXt
Powered by Runestone