Ir ao conteúdo principal

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

Seção 1.5 Permutações Circulares

Definição 1.5.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). Notação:
\begin{equation*} PC_n ~~\text{ ou }~~ PC(n). \end{equation*}

Nota 1.5.2.

Observe que os três círculos da (Figura 1.5.3) são equivalentes, ou seja, representam a mesma permutação circular, pois o segundo círculo pode ser obtido a partir do primeiro por uma rotação de \(-\frac{2\pi}{3}\) e o terceiro círculo pode ser obtido a partir do primeiro por uma rotação de \(-2\times\frac{2\pi}{3}\text{.}\)
Figura 1.5.3. Três círculos que representam a mesma permutação circular.

Demonstração.

Observe que as permutações simples (1, 2, 3), (3, 1, 2) e (2, 3 ,1) podem ser identificadas com os círculos da (Figura 1.5.3), colocando o primeiro elemento na parte mais alta do círculo, o segundo elemento do lado direito e o terceiro elemento do lado esquerdo. Portanto essas três permutações simples, correspondem a apenas uma permutação circular.
Observe que as permutações simples (1, 3, 2), (2, 1, 3) e (3, 2 ,1) podem ser identificadas com os círculos da (Figura 1.5.5), da mesma forma que foi feito no caso anterior. Portanto essas três permutações simples, correspondem a apenas uma permutação circular.
Figura 1.5.5. Três circulos que representam a mesma permutação circular.
Como não temos mais casos, o número total de permutações circulares com três elementos é 2.

Demonstração.

Se não considerássemos equivalentes disposições que possam coincidir por rotação, teríamos \(n!\) disposições.
Como para cada disposição, temos \(n\) disposições equivalentes, dividindo o total de permutações por \(n\text{,}\) obtemos
\begin{equation*} PC(n) = \frac{n!}{n} = (n-1)! \end{equation*}

Tecnologia 1.5.7.

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.5.8.

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). \end{equation*}

Exemplo 1.5.9.

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.5.10. 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. \end{equation*}

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

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

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.\)

4.

(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*}

5.

(VESTIBULAR UFPE – UFRPE / 1998 2ª ETAPA)
Semelhante ao dominó, mas feito de pedras triangulares equiláteras, o jogo de trominó apresenta na face triangular superior um certo número de pontos com repetições, escolhidos de 1 a n, dispostos ao longo de cada aresta (ver figura).
Figura 1.5.11. Uma das peças com os valores 1, 2 e 4.
Quantas peças há no trominó, supondo \(n = 6\text{?}\)
Resposta.
76
Solução.
Observe que os números estão em disposição circular, então vamos separar as peças em três tipos:
  1. Todos os lados com o mesmo valor. Cada peça pode ser formada de uma única forma, assim temos 6 peças desse tipo.
  2. Dois lados possuem um valor e o terceiro lado possui um valor diferente. Para formar cada peça deste tipo, precisamos escolher dois números de seis disponíveis, uma vez feita esta escolha temos duas maneiras de escolher qual número será usado duas vezes. No total são \(C_6^2\times 2\) modos de formar essas peças, já que qualquer permutações desses números não gera uma nova peça.
  3. Cada lado possui um valor diferente. Neste caso, cada peça pode ser formada de duas formas, pois o número de permutações circulares com 3 elementos é 2. Neste caso temos \(2\times C_6^3\) modos de formar as peças.
Portanto, o número de soluções é:
\begin{equation*} 6 + 2\times C_6^2 + 2\times C_6^3 = 76. \end{equation*}