Permutação

Uma permutação é um arranjo ordenado de elementos de um conjunto.

Uma r-permutação é um arranjo de r elementos distintos escolhidos de um conjunto.

Exemplo: Seja S={A,B,C}. As sequências

ABC

BCA

CAB

São permutações de S. As sequências

AB

BC

CA

                Muitos problemas de contagens podem ser convertidos em problemas de enumeração das permutações de um dado conjunto.

Exemplos:

a)      De quantas maneiras uma fila com 3 estudantes pode ser composta a partir de um grupo com 5 estudantes?

 

N=n1.n2.n3=5.4.3=60

b)      E uma fila envolvendo todos os estudantes?

N=n1.n2.n3.n4.n5

N=5.4.3.2.1=120

Notação: P(n,r) representa o número de r-permutação distintas possíveis de elementos de um conjunto com cardinalidade n.

Teorema: Sejam n e r inteiros positivos com r=<n. Então,

P(n,r)=n(n-1)(n-2)...(n-r+1)

Demostre utilizando o princípio do produto e a indução matemática.

O número de r-permutações de n elementos é dado por;

P(n,r)=n!/(n-r)!

Lembrete: n!~n.(n-1)!, 0!~1

Exemplos:

a)      Em uma corrida com 8 atletas quantos pódios distintos podem ocorrer caso não existam empates?

P(8,3) = 8!/ (8-3)!= 336

 

b)      Quantas permutações das letras A, B, C, D, E, F, G, H existem com ABC ocorrendo em sequência?

S= {ABC, D, E, F, G, H}

Assim;

P(6,6) = 6!= 720