Análise combinatória

Na matemática, a análise combinatória é a vertente que estuda a resolução dos problemas que envolvem contagem, utilizada principalmente em problemas de estatística e probabilidade.

Princípio fundamental da contagem

Para entender melhor o princípio fundamental da contagem, consideremos a seguinte situação:

Adrian possui 3 camisetas, 2 bonés e 3 bermudas. De quantas formas distintas ele poderá se vestir?

Observe que para tal problema, para cada camiseta, teremos 2 possibilidades de bonés e para cada boné e camiseta, teremos 2 possibilidades de bermudas, como na figura abaixo:

Podemos concluir então que Adrian terá possibilidades de se vestir, o que resulta em possibilidades.

De acordo com o princípio fundamental da contagem, um evento composto por etapas independentes terá o número de combinações determinado pelo produto das possibilidades de cada conjunto.

–Fatorial

Na matemática, fatorial é a operação dada pelos produtos dos números positivos inteiros de um número natural n, na forma “n!”, que é operada da maneira . Tal operação é muito utilizada na análise combinatória para problemas de contagens e combinações.

Exemplos:

;

;

.

Zero fatorial

Por definição matemática, , para melhor ordenação do conjunto solução de todas as operações fatoriais.

Permutação

Permutação simples

Podemos definir permutação como qualquer sequência reordenada proveniente de uma sequência ordenada, de modo que se um conjunto X é uma permutação de Y, então ambos possuem os mesmos elementos, ordenados de maneiras distintas.

Escrevemos a permutação de n elementos pela forma , de modo que .

Exemplo:

Permutação com repetição

Sempre que em uma permutação de elementos de um conjunto, tal conjunto contiver elementos iguais, calculamos a permutação de n elementos por n! dividido pelo fatorial de quantos elementos repetidos de mesma característica. De forma que em , é a permutação de n elementos e m e v são as quantidades de repetições de elementos contidos em n, de modo que determinado elemento se repete m vezes e outro se repete v vezes.

Exemplo:

Quantos anagramas pode-se formar com a palavra ARROZ?

Primeiramente constatamos que , pois arroz possui 5 letras. Contudo, devemos nos atentar à letra R que aparece 2 vezes na palavra, de modo que temos

Permutação circular

Para se entender melhor a permutação circular, considere a seguinte afirmação:

Uma família possui 4 pessoas, os pais e dois filhos. No horário de almoço de domingo, essa família irá ocupar uma mesa circular. De quantas formas essa família pode se sentar em torno da mesa, levando em conta que os pais sempre se sentam juntos (adjacente)?

Sabendo que os pais estarão sempre juntos, podemos tratá-los como um único elemento.

Considerando os pais como um só elemento, passamos a ter somente três elementos, de modo que teremos a possibilidade de cada filho se sentar à direita dos pais (que ficam juntos) ou à esquerda, sendo esta uma possibilidade, e também a possibilidade dos filhos trocarem de lugar, ou seja, mais uma possibilidade. Sendo assim, duas possibilidades para a ordenação.

Assim, a permutação circular só se dá pela alteração posicional de um elemento em relação a outro.

Podemos calcular a permutação circular pela fórmula , sendo m a quantidade de elementos.

Arranjos

Arranjos simples

Arranjos simples são formas de agrupamentos de elementos nas quais a ordem dos elementos é levada em consideração, ou seja, a ordenação de dois elementos pode ter mais de uma indicação, dependendo da ordem em que estão dispostos. No arranjo simples não existirá repetição de elementos no agrupamento.

Simbolizamos o arranjo de n elementos distribuídos em k possibilidades de ordenação pela forma:

A_n,k (lê-se “Arranjo de n elementos tomados k a k”).

Observação

Para um arranjo simples, quando o número de elementos do conjunto a ser ordenado é igual ao número de possibilidades com as quais o conjunto pode ser distribuído, calculamos o arranjo simples como uma permutação sem repetição.

Exemplo:

Distribuição de 3 pessoas em 3 cadeiras

Temos três possibilidades de pessoas para a cadeira 1, duas possibilidades de pessoas para cadeira 2 e uma pessoa para cadeira 3,

Assim, temos que .

Já para um arranjo em que o número de elementos é maior do que o número de possibilidades com as quais o conjunto pode ser distribuído, temos a fórmula:

.

Exemplo:

Distribuição de quatro pessoas em duas cadeiras

.

Podemos observar no exemplo acima que não precisamos abrir todo fatorial, uma vez que podemos “cortá-lo” com um valor equivalente no denominador da divisão, caso exista. Mais um exemplo disso:

.

Arranjos com repetição

No arranjo com repetição os elementos de um conjunto podem aparecer de forma repetida em um agrupamento ou subconjunto, já que a ordem importa.

Podemos calcular o arranjo com repetição pela fórmula:

.

Exemplo:

Seja P um conjunto com elementos: P ={A,B,C,D}. Tomando os agrupamentos de dois em dois, considerando o arranjo com repetição, quantos agrupamentos podemos obter em relação ao conjunto P?

Temos que , , .

Ficamos, então, com .

Combinação

Na análise combinatória, a combinação é como o arranjo, diferenciando-se somente pela ordem que gera um resultado ser indiferente, ou seja, a ordem não irá importar. Assim sendo, um conjunto solução {X, Y, Z} é considerado igual ao conjunto solução {Y, X, Z} que será igual ao {Z, X, Y} que será igual ao {Y, Z, X}, igual ao {X, Z, Y} que, por fim, será igual ao {Z, Y, X}.

Podemos entender a combinação com outro exemplo, na formação de pratos de salada a partir de tomates, alfaces, picles e cebolas. Vamos imaginar que queremos montar uma salada com dois ingredientes. Dentro do prato a ordem dos ingredientes não importa e, portanto, usamos a combinação para fazer o cálculo. Dessa forma temos quatro ingredientes tomados três a três. As soluções: {cebola, tomate, alface}={cebola, alface, tomate}={tomate, cebola, alface}={tomate, alface, cebola}={alface, tomate, cebola}={alface, cebola, tomate}, {picles, tomate, alface}={picles, alface, tomate}={tomate, picles, alface}={tomate, alface, picles}={alface, tomate, picles}={alface, picles, tomate}.

A combinação de n elementos tomados k a k é dada pela fórmula:

Exemplo:

Utilizando a combinação simples e considerando o conjunto I={A, B, C, D, E, F}, encontre quantos subconjuntos é possível formar tomando os elementos de 2 em 2.