Probabilidade e Estatística/Análise combinatória

Análise Combinatória

Princípios básicos de contagem

Princípio da Adição

Suponhamos um procedimento executado em $k\!\;$ fases. A fase 1 tem $n_{1}\!\;$ maneiras de ser executada, a fase 2 possui $n_{2}\!\;$ maneiras de ser executada e a fase $k\!\;$ tem $n_{k}\!\;$ modos de ser executada. As fases são excludentes entre si, ou seja, não é possível que duas ou mais das fases sejam realizadas em conjunto. Logo, todo o procedimento tem $n_{1}+n_{2}+...+n_{k}\!\;$ maneiras de ser realizado.

Exemplo

Deseja-se fazer uma viagem para a cidade A ou para a cidade B. Existem 5 caminhos possíveis para a cidade A e 3 possíveis caminhos para a cidade B. Logo, para esta viagem, existem no total 5 + 3 = 8 caminhos possíveis.

Princípio da Multiplicação

Suponhamos um procedimento executado em $k\!\;$ fases, concomitantes entre si. A fase 1 tem $n_{1}\!\;$ maneiras de ser executada, a fase 2 possui $n_{2}\!\;$ maneiras de ser executada e a fase $k\!\;$ tem $n_{k}\!\;$ modos de ser executada. A fase 1 poderá ser seguida da fase 2 até a fase k, uma vez que são concomitantes. Logo, há $n_{1}\cdot n_{2}\cdot ...n_{k}\!\;$ maneiras de executar o procedimento.

Exemplo

Supondo uma viagem para a cidade C, mas para chegar até lá você deve passar pelas cidades A e B. Da sua cidade até a cidade A existem 2 caminhos possíveis; da cidade A até a B existem 4 caminhos disponíveis e da cidade B até a C há 3 rotas possíveis. Portanto, há 2 x 4 x 3 = 24 diferentes caminhos possíveis de ida da sua cidade até a cidade C.

Os princípios enunciados acima são bastante intuitivos. Contudo, apresentaremos ainda alguns exemplos um pouco mais complexos de aplicação.

• Quantos números naturais pares de três algarismos distintos podemos formar?

Inicialmente, devemos observar que não podemos colocar o zero como primeiro algarismo do número. Como os números devem ser pares, existem apenas 5 formas de escrever o último algarismo $\left(0,2,4,6,8\right)\!\;$. Contudo, se colocamos o zero como último algarismo do número, nossas escolhas para distribuição dos algarismos mudam. Portanto, podemos pensar na construção desse número como um processo composto de 2 fases excludentes entre si.

Fixando o zero como último algarismo do número, temos as seguintes possibilidades de escrever os demais algarismos:

• 1º algarismo: 9 possibilidades $\left(1,2,3,4,5,6,7,8,9\right)\!\;$;
• 2º algarismo: 8 possibilidades $\left(1,2,3,4,5,6,7,8,9\right)\!\;$, porém excluímos a escolha feita para o 1º algarismo;
• 3º algarismo: 1 possibilidade (fixamos o zero).

Logo, há 9 x 8 x 1 = 72 formas de escrever um número de três algarismos distintos tendo o zero como último algarismo.

Sem fixar o zero, temos:

• 3º algarismo: 4 possibilidades $\left(2,4,6,8\right)\!\;$
• 1º algarismo: 8 possibilidades $\left(1,2,3,4,5,6,7,8,9\right)\!\;$, excluindo a escolha feita para o último algarismo;
• 2º algarismo: 8 possibilidades $\left(0,1,2,3,4,5,6,7,8,9\right)\!\;$, porém excluindo as escolhas feitas para o primeiro e último algarismos.

Portanto, temos 8 x 8 x 4 = 256 maneiras de escrever um número de três algarismos distintos sem zero no último algarismo.

Ao todo, temos 72 + 256 = 328 formas de escrever o número.

Permutação Simples

A permutação simples é o número total de ordenações possíveis de n elementos: $Pn=n!$

1. Quantos números naturais de quatro algarismos distintos podem ser formados com os algarismos 3,4,5,6,7,8 e 9?

1º algarismo: 7 possibilidades;

2º algarismo: 6 possibilidades;

3º algarismo: 5 possibilidades;

4º algarismo: 4 possibilidades;

Então é simples, basta multiplicar-se as possibilidades.

7.6.5.4 = 840 formas de escrever um número de quatro algarismos distintos.

Esta página é um esboço de matemática. Ampliando-a você ajudará a melhorar o Wikilivros.

Arranjo

Arranjo é um caso especial de permutação: uma ordenação de n elementos de tamanho p.

A fórmula usada para arranjo simples é a seguinte:

$A_{n}^{p}={\frac {n!}{\left(n-p\right)!}}$

Combinação simples

Cada subconjunto com p elementos é chamado de uma combinação simples de classe p dos n objetos $a_{1}$, $a_{2}$, ... , $a_{n}$. A fórmula usada para a combinação simples é a seguinte: ${n \choose p}={\frac {n!}{(n-p)!p!}}$