MECANISMOS, INTERCÂMBIOS E COMBINAGENS

ARRANJOS, PERMUTAÇÕES E COMBINAÇÕES

DISCIPLINA: Lógica e Matemática Computacional Profª.: Elda Sena

ARRANJOS SIMPLES

A análise combinatória classifica os agrupamentos em dois tipos fundamentais: os agrupamentos em que se considera a ordem dos elementos – os arranjos e os agrupamentos em que não se considera a ordem dos elementos – as combinações.

Com os elementos do conjunto I = {a,b,c,d}, formemos todas as seqüências possíveis de três elementos distintos:

{a,b,c} {a,b,d} {a,c,d} {b,c,d}

{a,c,b} {a,d,b} {a,d,c} {b,d,c}

{b,a,c} {b,a,d} {c,a,d} {c,b,d}

{b,c,a} {b,d,a} {c,d,a} {c,d,b}

{c,a,b} {d,a,b} {d,a,c} {d,c,b}

{c,b,a} {d,b,a} {d,c,a} {d,b,c}

Tais seqüências são chamadas de arranjos simples dos quatro elementos de I tomados “três a três”.Dois arranjos simples quaisquer se diferenciam ou pela ordem dos elementos ou pela natureza dos elementos que os compõem. Por exemplo:

(a,b,c)  (b,c,a) diferem pela ordem dos elementos

(a,b,c)  ( a,d,b) diferem pela natureza dos elementos.

Fórmula:

Na,p =

PERMUTAÇÕES

Permutações são arranjos ordenados de objetos. São agrupamentos que diferem entre si pela ordem de seus elementos.

Uma fórmula para P(n,r) pode ser escrita usando a função fatorial. Para um inteiro positivo n, fatorial de n é definido como n(n-1)(n-2)... 1 e denotado por n!.

P(n,r)= n!/(n-r)! para 0  r  n.

Exemplo: Quantos números de 4 dígitos sem dígitos repetidos podem ser tomados de um conjunto de 10 dígitos?

P(10,4)= 10!/(10-4)!=10.9.8.7.6!/(6!) = 10.9.8.7= 5.040

Exercício

Calcule o valor de P(7,3).

CASOS PARTICULARES

Três casos particulares podem ocorrer ao computarmos P(n,r) que são as duas condições de fronteira P(n,0) e P(n,n) além de P(n,1).

1)P(n,0) = n!/(n-0)!=n!/n! = 1

significando que existe um único arranjo ordenado de zero objeto – o conjunto vazio.

2)P(n,1) = n!/(n-1)!=n

significando que existe n arranjos ordenados de um objeto.

3)P(n,n) = n!/(n-n)!=n!/0! = n!

significando que existe n! arranjos ordenados de n objetos distintos.

COMBINAÇÕES

Combinações são agrupamentos que diferem uns dos outros apenas pela natureza de seus elementos.Se a ordem for relevante, o problema envolve permutações, se a ordem