Análise Combinatória

1

Análise Combinatória

1) Princípio Fundamental da Contagem

Se uma decisão 1 d pode ser tomada de x maneiras e se, uma vez tomada a decisão 1 d ,

a decisão 2 d puder ser tomada de y maneiras então o número de maneiras de se tomarem as

decisões d1 e d2 é x × y .

Exemplo:

Uma pessoa possui 4 camisas e 5 calças. De quantas maneiras poderá se vestir usando

uma camisa e uma calça?

Solução:

1 d : escolher uma camisa

2 d : escolher uma calça

Como 1 d pode ser tomada de 4 maneiras e, depois disso, 2 d pode ser tomada de 5 maneiras, o

número de maneiras dessa pessoa se vestir (isto é tomar as decisões 1 d e 2 d ) é 4×5 = 20 .

Logo terá 20 maneiras distintas de realizar a tarefa.

2) Permutações Simples

Dados n objetos distintos 1 2 , , ..., n a a a de quantos modos é possível ordená-los?

Por exemplo, para os objetos 1, 4, 5 há 6 ordenações: 145, 154, 415, 451, 541, 514. No

caso geral temos n modos de escolher o objeto que ocupará o primeiro lugar, n −1 modos de

escolher o objeto que ocupará o segundo lugar, n − 2 modos de escolher o objeto que ocupará o

terceiro lugar, ..., 1 modo de escolher o objeto que ocupará o último lugar. Portanto,

O número de modos de ordenar n objetos distintos é:

n × (n −1)× (n − 2)× ... ×1 = n!

Cada ordenação dos n objetos é chamada de permutação simples de n objetos e o

número de permutações simples de n objetos distintos é representado por P n! n = (Atenção:

0!= 1, define-se 1 0 P = ).

Exemplos:

1. Quantos são os anagramas da palavra “VESTIBULAR”?

Solução:

Cada anagrama de VESTIBULAR nada mais é que uma ordenação das letras V, E, S, T, I,

B, U, L, A, R. Assim, o número de anagramas de VESTIBULAR é 10! 3628800. 10 P = =

2

2. Quantos são os anagramas da palavra VESTIBULAR que começam e terminam por

consoante?

Solução:

A consoante inicial pode ser escolhida de 6 maneiras, a consoante final de 5 maneiras e as

8 letras restantes podem ser arrumadas entre essas duas consoantes de 8! 8 P = modos. A

resposta é 6× 5×8!= 1209600 .

3) Permutação de Elementos nem Todos Distintos

Quantos anagramas possui a palavra “MATEMÁTICA”? A resposta não é 10! 10 P = . Pelo

fato de “MATEMÁTICA” ter letras repetidas, obtemos um número de anagramas menor do que

obteríamos se as letras fossem distintas. M ATEM ATICA 1 2 e M ATEM ATICA 2 1 seriam

anagramas diferentes, por exemplo.

O número de anagramas de “MATEMÁTICA” será representado por 2, 3, 2

10 P ou  





  



2, 3, 2

10

,

número de permutações de 10 letras das quais 2 são iguais a M, 3 iguais a A e 2 iguais a T.

Para determinar o número de anagramas de “MATEMÁTICA” pensamos do seguinte

modo:

Se as letras fossem distintas, obteríamos 10! 10 P = anagramas. Como os M são iguais,

contamos cada anagrama 2! vezes. Analogamente contamos cada anagrama 3! vezes por serem

iguais os A e 2! vezes por serem iguais os T. Para sabermos o número correto de anagramas

temos que descontar as vezes que contamos o mesmo anagrama. Logo,

151200

2!3! 2!

10! 2,3, 2

10 P = =

4) Permutações Circulares

De quantos modos podemos formar uma roda com 5 crianças?

À primeira vista parece que para formar uma roda com as cinco crianças basta escolher

uma ordem para elas, o que poderia ser feito de 5!= 120 modos. Entretanto, as rodas ABCDE e

EABCD são iguais, pois na roda o que importa é a posição relativa das crianças entre si e a roda

3

ABCDE pode ser “virada” na roda EABCD. Como cada roda pode ser “virada” de cinco modos, a

nossa contagem 120 rodas contou cada roda 5 vezes e a resposta é 24

5

120

= .

Importante:

Repare que nas permutações simples importam os lugares que os objetos ocupam ao

passo que nas permutações circulares o que importa é apenas a posição relativa dos objetos

entre si.

Podemos contar os casos de uma permutação circular da seguinte maneira:

(PC) = (n −1)! n

No exemplo anterior poderíamos contar o número de rodas com cinco crianças da