Objetivos
- Definir Permutação Circular.
- Mostrar como obter a lista com todas as permutações circulares com \(n\) elementos distintos no Sage.
- Mostrar como calcular o número de permutações circulares de \(n\) elementos distintos.
- Exemplificar.
Seção 6.5 Permutações Circulares
Definição 6.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 6.5.2.
Observe que os três círculos da (Figura 6.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{.}\)
Afirmação 6.5.4.
O número total de permutações circulares com 3 elementos distintos é 2.
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 6.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 6.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.
Teorema 6.5.6.
O número de permutações circulares com \(n\) elementos distintos é
\begin{equation*}
PC_n = (n-1)!
\end{equation*}
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 6.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 6.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 6.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.
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.
(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).
Quantas peças há no trominó, supondo \(n = 6\text{?}\)
Resposta.
Solução.
76
Observe que os números estão em disposição circular, então vamos separar as peças em três tipos:
- Todos os lados com o mesmo valor. Cada peça pode ser formada de uma única forma, assim temos 6 peças desse tipo.
- Dois lados possuem um valor e o terceiro lado possui um valor diferente. Uma vez decidido qual valor será usado duas vezes, cada peça pode ser formada de uma única forma, pois o número de permutações circulares com 3 elementos é 2, mas duas entradas são iguais, logo precisamos dividir por 2. Nesse caso temos \(2\times C_6^2\) modos de formar as peças.
- 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. Nesse 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*}
