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!\qquad \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\qquad \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 \left(n-3\right)\times \left(n-2\right)\times \left(n-1\right)\times n\qquad \forall n\in \mathbb {N}$

Embora a definição mais utilizada seja:

$n!=n\times \left(n-1\right)\times \left(n-2\right)\times \left(n-3\right)\times ...\times 3\times 2\times 1\qquad \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)={\Biggl \{}{\begin{matrix}1,&para\ n=0\\n\times f(n-1),&para\ n\neq 0\end{matrix}}$

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$

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