permutações

Novo M´odulo de MD

2014

Unidade 3

Matem´atica Discreta
T´opicos de Combinat´oria de Contagem
Texto da Semana 14, Parte 2

Permuta¸ co ˜es Circulares

Sum´ ario 1 Permuta¸co
˜es circulares
1.1 Caso n = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Caso n = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Caso n gen´erico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Exerc´ıcios resolvidos

2
4
6
7
10

Continuamos com o estudo das configura¸co˜es que ocorrem com mais frequˆencia nos problemas de contagem. Abordamos, agora, as permuta¸c˜oes circulares. Mais especificamente, definimos e exemplificamos as permuta¸c˜oes circulares e aplicamos o Pk1 para a contagem direta do n´ umero de permuta¸co˜es circulares. Como consequˆencia desta abordagem, vamos determinar uma f´ormula para o n´ umero de permuta¸c˜oes circulares. Ap´os estudar esta aplica¸c˜aos do Pk1, vamos estar convencidos da importˆancia da f´ormula obtida, na resolu¸c˜ao de problemas de contagem.

1

Novo M´odulo de MD

1

2014

Unidade 3

Permuta¸co
˜es circulares
Considere o seguinte problema:
De quantas maneiras 2 meninas — Ana e Beatriz — podem formar uma roda de ciranda?

Resolu¸c˜ ao: Neste problema, os objetos b´asicos s˜ao as 2 meninas, que vamos denotar por A e B, e as configura¸co˜es s˜ao as rodas de ciranda que podem ser formadas com estas meninas. As rodas podem ser representadas por uma circunferˆencia rotulada x1 x2 onde x1 , x2 representam as meninas.
Seja X o conjunto de tais rodas. Neste caso, n˜ao temos nenhuma dificuldade em listar todos os elementos de X e cont´a-los diretamente. Na verdade, pensando um pouco, conclu´ımos imediatamente que
A
(1)
B
´e a u
´nica roda poss´ıvel e que |X| = 1.
Aparentemente, poder´ıamos tamb´em formar a roda dada na figura
B
(2)
A
mas embora (1) e (2) sejam figuras diferentes, elas representam a mesma que a roda, pois a