Matemática elementar/Análise combinatória

Origem: Wikilivros, livros abertos por um mundo aberto.


Índice

[editar] Análise Combinatória

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


[editar] A Operação Fatorial

A função factorial é uma função que admite apenas um único argumento. Para esse argumento, chamemos-lhe n\,\!, a função factorial 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 factorial é representada pelo simbolo/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 factorial 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 correcta de factorial é dada pelo operador productó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 productó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 factorial 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 exactamente iguais, apenas muda a ordem pela qual as parcelas aparecem.

[editar] 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 factorial do número zero é um. Portanto:


0! \equiv 1


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


[editar] Operações com factoriais

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

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


f(n) = \Biggl\{ \begin{matrix} 1, & para \ n = 0 \\ n \times f(n - 1), & para \ n \ne 0 \end{matrix}


ou, por outro lado:


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


[editar] 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.


[editar] 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


[editar] 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.


[editar] 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' é:


An,K= n! / (n-K)!

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

R: A26,3 = 26!/23! = 26*25*24 = 15600


[editar] 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 é:


Cn,K= 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?

R: C60,6 = 60!/(6!*54!) = 50063860


Nuvola apps edu mathematics.png

Esta página é um esboço de matemática. Ampliando-a você ajudará a melhorar o Wikilivros.
Obtido em "http://pt.wikibooks.org/wiki/Matem%C3%A1tica_elementar/An%C3%A1lise_combinat%C3%B3ria"