Análise Combinatória

IME ITA

Apostila ITA

B 01
Combinações e Permutações
Introdução
Neste capítulo são apresentadas as ferramentas básicas que nos permitem determinar o número de elementos de conjuntos formados de acordo com certas regras, sem que seja necessário enumerar seus elementos.
A procura por técnicas de contagem está diretamente vinculada à história da
Matemática e à forma pela qual as pessoas tem seu primeiro contato com esta disciplina. A primeira técnica matemática aprendida por uma criança é “contar”, ou seja, enumerar os elementos de um conjunto de forma a determinar quantos são os seus elementos. As operações aritméticas são também motivadas (e aprendidas pelas crianças) através de sua aplicação a problemas de coragem.
Por exemplo, a operação de adição é sempre introduzida em conexão com um problema de contagem:

Fig. 1

A figura 1 ilustra um princípio básico de contagem, que podemos chamar de
“Princípio da Adição”:
Se A e B são dois conjuntos disjuntos, com p e q elementos, respectivamente, entre A ∪ B possui p + q elementos.
A seguir apresentamos o “Princípio da Multiplicação”, que, ao lado do “Princípio da Adição”, constitui a ferramenta básica para resolver os problemas de contagem abordados a nível de 2º grau. Para motivar tal princípio, consideramos o exemplo a seguir. Numa sala há 3 homens e 4 mulheres. De quantos modos é possível selecionar um casal homem-mulher? Chamado os homens de h1 , h2 , h3 e as mulheres de m1 , m2 , m3 , m4 é fácil ver que há 4 casais nos quais o homem é h1 , outros 4 nos quais o homem é h2 e outros 4 nos quais o homem é h 3 . O número de casais é portanto
4 + 4 + 4 = 3 × 4 = 12 .

Matemática

O exemplo acima ilustra o Princípio Fundamental da Enumeração ou Princípio da
Multiplicação, o qual diz:
Se uma decisão d1 pode ser tomada de x maneiras e se, uma vez tomada a decisão d1 , a decisão d2 puder ser tomada de y maneiras então o número de maneiras de se tomarem as decisões d1 e d2 é xy .