Combinatória 08

Permutação circular

Permutação circular é a situação que ocorre quando temos grupos com n elementos distintos formando uma circunferência de círculo.

Exemplo: Seja um conjunto com 4 pessoas K={A,B,C,D}. De quantos modos distintos estas pessoas poderão sentar-se junto a uma mesa circular (pode ser retangular) para realizar o jantar sem que haja repetição das posições?

Se considerássemos todas as permutações simples possíveis com estas 4 pessoas, teriamos 24 grupos, apresentados no conjunto:

Pc={

ABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, BADC,

BCAD, BCDA, BDAC, BDCA, CABD, CADB, CBAD, CBDA,

CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB, DCBA

}

Acontece que junto a uma mesa “circular” temos que:

ABCD=BCDA=CDAB=DABC

ABDC=BDCA=DCAB=CABD

ACBD=CBDA=BDAC=DACB

ACDB=CDBA=DBAC=BACD

ADBC=DBCA=BCAD=CADB

ADCB=DCBA=CBAD=BADC

Existem somente 6 grupos distintos, dados por: Pc={ABCD,ABDC,ACBD,ACDB,ADBC,ADCB}

Fórmula: Pc(n)=(n-1)!

Cálculo para o exemplo: P(4) = (4-1)! = 3! = 6

Abaixo temos um algoritmo que exemplifica a chamada à função que calcula o número de permutações circulares, PermC(n).

Exemplo da Função PermC(n)

algoritmo()

{

inteiro x;

x := PermC(4);

escreva("A permutacao circular

}