Matemática elementar/Análise combinatória

Análise combinatória

Análise combinatória é a parte da matemática que estuda os métodos de contagem.

A operação fatorial

A função fatorial é uma função que admite apenas um único argumento. Para esse argumento, chamemos-lhe $n$, a função fatorial procura todos os números $k$ menores ou iguais a $n$ e maiores que $0$ e multiplica-os entre si. Adicionalmente, é preciso dizer que tanto $n$ como $k$ pertencem ao conjunto dos números naturais $\mathbb{N}$(com uma pequena diferença, $n$ inclui o número zero, $k$ não) e que a função fatorial é representada pelo símbolo/operador $!$ (ponto de exclamação). Definindo tudo isto formalmente:

$f\left(n\right)=n!\mathrm{\forall }n\in {\mathbb{N}}_0$

Mas esta função ainda não nos diz muito acerca do que é de o fatorial de um número, diz-nos apenas como a representar e qual o seu domínio. Assim, não nos é possível saber para um dado valor $n$ qual o valor de $f\left(n\right)$.

A definição correta de fatorial é dada pelo operador produtório da seguinte forma:

$n!=\prod _{k=1}^{n}k\mathrm{\forall }n\in \mathbb{N}$

Note-se que aqui o valor $0$ já não é incluído como um possível valor de $n$.

Isto significa precisamente aquilo que já foi dito antes. Neste caso, a função produtório começa por atribuir a $k$ o valor de $1$; de seguida, vai multiplicar esse mesmo valor pelo próximo valor de $k$, ou seja, $2$; esta operação repete-se até que o valor de $k$ seja igual ao valor de $n$. Dito isto, uma forma mais simples de definir a função fatorial seria:

$n!=1\times 2\times 3\times ...\times (n-3)\times (n-2)\times (n-1)\times n\mathrm{\forall }n\in \mathbb{N}$

Embora a definição mais utilizada seja:

$n!=n\times (n-1)\times (n-2)\times (n-3)\times ...\times 3\times 2\times 1\mathrm{\forall }n\in \mathbb{N}$

Estas duas definições são exatamente iguais, apenas muda a ordem pela qual as parcelas aparecem.

Exemplos

$6!=\prod _{k=1}^{6}k=6\times 5\times 4\times 3\times 2\times 1=720$

ou

$5!=\prod _{k=1}^{5}k=5\times 4\times 3\times 2\times 1=120$

mas

$0!=\prod _{k=1}^0=?$

Acontece que, embora esta função não esteja definida para $n=0$, foi estipulado que o fatorial do número zero é um. Portanto:

$0!\equiv 1$

O que equivale a dizer "0 fatorial está definido como sendo 1".

Operações com fatoriais

Se reparar nos exemplos anteriores, $6!$ não é mais do que $6\times 5!$, o que já nos indica uma operação relativa a fatoriais: a fatorização.

Ainda outra maneira de definir a função fatorial, é utilizar uma função recursiva:

$f(n)=\{\begin{array}{cc}1,& paran=0\\ n\times f(n-1),& paran\ne 0\end{array}$

ou, por outro lado:

$n!=n\times (n-1)!$

Princípio fundamental da contagem

Se um determinado acontecimento ocorre em n etapas diferentes, e se a primeira etapa pode ocorrer de p1 maneiras diferentes, a segunda de p2 maneiras, a terceira de p3 maneiras, até pn, o número total de maneiras de ocorrer o acontecimento é :

T = p1 × p2 × p3 × ...× pn ×

Ex.: Se tivermos um dado de 4 faces e um de 6 faces, logicamente, o primeiro pode apresentar 4 resultados diferentes, e o segundo, 6. Os dois juntos podem apresentar, então, 6*4=24 resultados diferentes.

Permutações simples

Permutações são os agrupamentos de um determinado número de elementos variando apenas a sua ordem. Ex.:

XYZ, XZY, YXZ, YZX,ZXY, ZYX. O número de agrupamentos de uma permutação simples de n elementos é dado por n!.

Ex.: De quantas formas podemos agrupar as sete cores do arco-íris? R: 7! = 5040

Permutações com elementos repetidos

Se formos fazer permutações com n elementos, mas existe um elemento repetido 'a' vezes, outro 'b' vezes, outro 'c' vezes, etc, o número de possibilidades de permutações é:

Pn(a,b,c) = n! / (a! b! c!)

Determine o número de anagramas (combinações de letras formando palavras com ou sem sentido) que podemos formar com PATA. E com MACACA. R: P1= 4!/2! = 12 P2= 6!/(3!*2!) = 60

Obs.: Exemplos de anagramas com PATA: AAPT, AATP, APTA, ATPA, PTAA, TPAA, PATA, TAPA, APAT, ATAP, PAAT, TAAP.

Arranjos simples

Imagine que temos um conjunto de 'n' elementos. O arranjo simples de taxa 'K' é todo agrupamento de 'K' elementos distintos, podendo variar a ordem em que aparecem.

Ex.: A={X,Y,Z}

arranjo de taxa 1: X,Y,Z. arranjo de taxa 2: XY, YX, XZ, ZX, YZ, ZY. arranjo de taxa 3: XYZ, XZY, YXZ, YZX, ZXY, ZYX.

O número total de arranjos de 'n' elementos, taxa 'K' é:

$A_{n,K}=\frac{n!}{(n-K)!}$

Quantos anagramas de três letras podemos formar pelo nosso alfabeto (com 26 letras)? Resposta:

$A_{26;3}=\frac{26!}{23!}=26\times 25\times 24=15600$

Combinações simples

As combinações são parecidas com os arranjos, mas apenas há a preocupação com a existência do elemento (não com a ordem). Ex.:

Combinações de taxa 1 do conjunto A={A,B,C,D} A, B, C, D.

Combinações de taxa 2 do conjunto A={A,B,C,D} AB, AC, AD, BC, BD, CD.

Combinações de taxa 3 do conjunto A={A,B,C,D} ABC, ABD, ACD, BCD.

Combinações de taxa 4 do conjunto A={A,B,C,D} ABCD.

A fórmula é:

$C_{n,K}=\frac{n!}{K!(n-K)!}$

Ex.: Um jogo possui um cartão com 60 números. Deve-se marcar 6 deles. De quantas forma pode-se fazer isso? Resposta:

$C_{60;6}=\frac{60!}{6!54!}=50.063.860$