Matemática - Análise combinatória

Prévia do material em texto

Princípio fundamental da contagem
Contar é muitas vezes algo simples e corriqueiro em nossas vidas, mas contar também pode ser uma tarefa muito complexa. Por exemplo, sabemos intuitivamente quantas combinações diferentes de vestuário podemos fazer quando temos 1 tênis e 2 camisas, porém, saber quantas são as possíveis combinações de senhas de 4 dígitos contendo letras e números é inviável sem utilizarmos o princípio fundamental da contagem.
No exemplo das combinações de vestuário, o que fazemos intuitivamente é o seguinte processo:
Ou seja, multiplicamos o número de diferentes possibilidades de tênis pelo número de camisas diferentes , o que nos dá 2 possibilidades de combinações. Portanto, quando temos dois eventos independentes que podem ocorrer de n e i maneiras respectivamente, podemos dizer que os dois eventos juntos podem ocorrer de maneiras.
Exemplo 
Quantas são as possibilidades de senhas de 4 dígitos contendo letras minúsculas e números onde o primeiro dígito é uma letra? 
Resolução
Nessa situação, devemos primeiro estipular quantas são as possibilidades para cada dígito da senha:
1º dígito: qualquer letra, ou seja, 26 possibilidades.
2º dígito: qualquer letra ou número, ou seja, 26 + 10 possibilidades
3º dígito: qualquer letra ou número, ou seja, 26 + 10 possibilidades
4º dígito: qualquer letra ou número, ou seja, 26 + 10 possibilidades
Dessa forma, aplicando o princípio fundamental da contagem teremos:
 possibilidades de senhas
Podemos escrever produtos na notação fatorial
Muitas vezes na análise combinatória nos deparamos com produtos como , uma forma de simplificar essa multiplicação é com a notação fatorial, de forma que a representação seja dada por , ou seja:
Uma propriedade importante da notação fatorial é que .
Arranjo simples
Podemos considerar um arranjo simples, por exemplo, a formação de grupos onde a ordem dos elementos que compõem o grupo é importante.
Exemplo
Quantas são as possíveis formas de se montar uma comissão contendo um líder, um vice-líder, um secretário e um tesoureiro a partir de um grupo de quarenta pessoas?
Resolução
Podemos notar que a ordem dos integrantes da comissão é importante para designar qual será o cargo de cada integrante, de forma que podemos formar a comissão das seguintes maneiras:
Podemos escrever esse produto na forma:
Finalmente, podemos definir uma fórmula para calcular o número de grupos onde a ordem dos integrantes importa. Ao formar grupos contendo p integrantes, formados a partir de n elementos, ou seja, o arranjo simples de n elementos, tomados p a p (), temos que:
Permutações
Existem essencialmente permutações simples, permutações com elementos repetidos e permutações circulares. Quando desejamos por exemplo saber quais são os possíveis anagramas da palavra “AVE” estamos diante de uma permutação simples. 
Permutação simples
Suponha que desejamos saber quantas são as possíveis formas de formar uma comissão de 4 integrantes, onde a ordem dos integrantes é importante, a partir de um grupo de 4 pessoas. Nesse caso teremos as seguintes possibilidades de comissões:
Comissão 1: Integrante 1, Integrante 2, Integrante 3, Integrante 4
Comissão 2: Integrante 1, Integrante 2, Integrante 4, Integrante 3
Comissão 3: Integrante 1, Integrante 3, Integrante 2, Integrante 4
Comissão 4: Integrante 1, Integrante 3, Integrante 4, Integrante 2
Comissão 5: Integrante 1, Integrante 4, Integrante 2, Integrante 3
Comissão 6: Integrante 1, Integrante 4, Integrante 3, Integrante 2
Etc...
Podemos calcular de forma mais simples quantas são as possibilidades para a formação das comissões sem listar todas as possibilidades:
Portanto, o número de permutações simples de n elementos pode ser calculado por:
Permutação com elementos repetidos
Suponha que desejamos saber quantos são os possíveis anagramas da palavra PIZZA. Para isso, muitos pensariam primeiramente em realizar o cálculo da quantidade de anagramas possíveis por meio da fórmula da permutação simples, o que daria um total de 5! anagramas. Porém, como podemos perceber, existe a repetição da letra Z na palavra em questão, o que altera a forma com a qual deveremos lidar matematicamente com essa permutação, uma vez que ao escrever duas permutações diferentes, PIZAZ ou PIZAZ é essencialmente a mesma coisa, ao passo que, por exemplo, ao permutarmos as letras que compõe a palavra AVE obteremos sempre palavras diferentes: AVE, AEV, EVA, EAV, VAE, VEA.
Para resolvermos o problema da palavra PIZZA devemos realizar o seguinte processo:
Existem 5 possibilidades de distribuição para cada letra da palavra em questão, uma vez que cada letra pode ocupar qualquer uma das 5 posições. Dessa forma, podemos calcular separadamente de quantas maneiras diferentes podemos distribuir as duas letras Z nas 5 posições. Resumidamente, o que é o mesmo que calcular o arranjo simples de 5 elementos, tomados 2 a 2, tudo isso dividido por 2!, pois as permutações das letras Z e Z são idênticas:
Podemos então calcular de quantas maneiras podemos distribuir as outras 3 letras que não se repetem nas 3 posições restantes:
Portanto o número de anagramas da palavra PIZZA será dado por:
Generalizando, podemos dizer que a permutação de n elementos, onde existem elementos que se repetem um número x, y, z, ... de vezes, pode ser calculada de forma que:
Permutação circular
Suponha que desejamos distribuir 3 elementos em volta de um círculo, de quantas formas diferentes essa distribuição pode ser feita? Provavelmente, a primeira reação ao se deparar com essa pergunta seria realizar uma permutação simples entre os elementos, o que daria um total de 3! maneiras. Porém, quando desejamos permutar elementos em um círculo, não basta fazer uma permutação simples, pois existirão permutações que possuem a mesma distribuição dos elementos, porém rotacionados.
Exemplo
Distribuição dos elementos 1, 2 e 3 em volta de um círculo
1
2
3
3
1
2
2
3
1
1
3
2
3
2
1
2
1
3
Perceba que na primeira linha qualquer um dos círculos pode ser obtido a partir de uma simples rotação de um outro círculo, o que também acontece na segunda linha. Porém, não é possível obter um elemento da segunda linha a partir da rotação de um elemento da primeira linha e vice-versa. Dessa forma, podemos notar que na verdade existem apenas 2 permutações distintas dentre os 6 círculos possíveis.
Generalizando, para calcular o número de permutações circulares de n elementos a partir da fórmula: