Análise Combinatória

1 - Introdução

Foi a necessidade de calcular o número de possibilidades existentes nos chamados jogos de azar que levou ao desenvolvimento da Análise Combinatória, parte da Matemática que estuda os métodos de contagem. Esses estudos foram iniciados já no século XVI, pelo matemático italiano Niccollo Fontana (1500-1557), conhecido como Tartaglia. Depois vieram os franceses Pierre de Fermat (1601-1665) e Blaise Pascal (1623-1662).
A Análise Combinatória visa desenvolver métodos que permitam contar - de uma forma indireta - o número de elementos de um conjunto, estando esses elementos agrupados sob certas condições.

2 - Fatorial

Seja n um número inteiro não negativo. Definimos o fatorial de n (indicado pelo símbolo n! ) como sendo:

n! = n .(n-1) . (n-2) . ... .4.3.2.1 para n ³ 2.

Para n = 0 , teremos : 0! = 1.
Para n = 1 , teremos : 1! = 1

Exemplos:

a) 6! = 6.5.4.3.2.1 = 720
b) 4! = 4.3.2.1 = 24
c) observe que 6! = 6.5.4!
d) 10! = 10.9.8.7.6.5.4.3.2.1
e) 10! = 10.9.8.7.6.5!
f ) 10! = 10.9.8!

3 - Princípio fundamental da contagem - PFC

Se determinado acontecimento ocorre em n etapas diferentes, e se a primeira etapa pode ocorrer de k₁ maneiras diferentes, a segunda de k₂ maneiras diferentes, e assim sucessivamente, então o número total T de maneiras de ocorrer o acontecimento é dado por:
T = k₁. k₂ . k₃ . ... . k_n

Exemplo:
 
O DETRAN decidiu que as placas dos veículos do Brasil serão codificadas usando-se 3 letras do alfabeto e 4 algarismos. Qual o número máximo de veículos que poderá ser licenciado?

Solução: 

Usando o raciocínio anterior, imaginemos uma placa genérica do tipo PWR-USTZ.
Como o alfabeto possui 26 letras e nosso sistema numérico possui 10 algarismos (de 0 a 9), podemos concluir que: para a 1ª posição, temos 26 alternativas, e como pode haver repetição, para a 2ª, e 3ª também teremos 26 alternativas. Com relação aos algarismos, concluímos facilmente que temos 10 alternativas para cada um dos 4 lugares. Podemos então afirmar que o número total de veículos que podem ser licenciados será igual a: 26.26.26.10.10.10.10 que resulta em 175.760.000. Observe que se no país existissem 175.760.001 veículos, o sistema de códigos de emplacamento teria que ser modificado, já que não existiriam números suficientes para codificar todos os veículos. Perceberam?

4 - Permutações simples

4.1 - Permutações simples de n elementos distintos são os agrupamentos formados com todos os n elementos e que diferem uns dos outros pela ordem de seus elementos. 

Exemplo: com os elementos A,B,C são possíveis as seguintes permutações: ABC, ACB, BAC, BCA, CAB e CBA.

4.2 - O número total de permutações simples de n elementos distintos é dado por n!, isto é  
P_n = n!    onde    n! = n(n-1)(n-2)... .1 . 

Exemplos:

a)  P₆ = 6! = 6.5.4.3.2.1 = 720
b) Calcule o número de formas distintas de 5 pessoas ocuparem os lugares de um banco retangular de cinco lugares.
P₅ = 5! = 5.4.3.2.1 = 120

4.3 - Denomina-se ANAGRAMA o agrupamento formado pelas letras de uma palavra, que podem ter ou não significado na linguagem comum.

Exemplo: 

Os possíveis anagramas da palavra REI são:
REI, RIE, ERI, EIR, IRE e IER.

5 - Permutações com elementos repetidos

Se entre os n elementos de um conjunto, existem a elementos repetidos, b elementos repetidos, c elementos repetidos e assim sucessivamente , o número total de permutações que podemos formar é dado por:

Exemplo: 
Determine o número de anagramas da palavra MATEMÁTICA.(não considere o acento)

Solução: 
Temos 10 elementos, com repetição. Observe que a letra M está repetida duas vezes, a letra A três , a letra T, duas vezes. Na fórmula anterior, teremos: n=10, a=2, b=3 e c=2. Sendo k o número procurado, podemos escrever:
k= 10! / (2!.3!.2!) = 151200
Resposta: 151200 anagramas.

6 - Permutações circulares
Dado um conjunto com n elementos , de quantas formas eles podem ser dispostos segundo uma circunferência?
Vamos  considerar duas situações distintas:

I - os elementos estão dispostos na circunferência, de acordo com um sentido determinado.
Neste caso, o primeiro elemento poderá ocupar qualquer ponto na circunferência. Restam (m – 1) elementos que poderão se acomodar de (m-1)(m-2)(m-3). ... .1 = (m-1)! maneiras possíveis. Então, sendo P'(n) o número de permutações circulares de n elementos, teremos P'(n) = (n - 1)!

Exemplo: 
De quantas maneiras quatro pessoas podem sentar-se ao redor de uma mesa circular, considerando-se um único sentido de contagem?

Solução: 
P'(4) = (4 - 1)! = 3! = 3.2.1 = 6. Portanto, 4 pessoas podem acomodar-se de 6 maneiras distintas ao redor de uma mesa circular, considerando-se um único sentido de contagem. Veja a figura a seguir, que mostra as seis posições possíveis:




II - os elementos estão dispostos na circunferência, e o sentido da contagem é indiferente.
Neste caso, teremos que dividir o resultado do item I anterior por 2 pois, existirão posições contadas duas vezes. Veja por exemplo na figura acima que, se o sentido da contagem for indiferente, as posições A e F, B e C e D e E são iguais ou seja: posição A: seqüência 1234 no sentido horário e posição F: mesma seqüência 1234 no sentido anti-horário. Então, se o sentido for indiferente, as posições A e F são iguais; o mesmo poderá se concluir das posições B e C e D e E.

Então, no caso do sentido da contagem ser indiferente (sentido horário ou anti-horário), n elementos poderão ser distribuídos ao redor de uma mesa circular de P'(n) = (n - 1)! / 2   maneiras distintas

7 - Arranjos simples

7.1 - Dado um conjunto com n elementos , chama-se arranjo simples de taxa k , a todo agrupamento de k elementos distintos dispostos numa certa ordem. Dois arranjos diferem entre si, pela ordem de colocação dos elementos. Assim, no conjunto E = {a,b,c}, teremos:
a) arranjos de taxa 2: ab, ac, bc, ba, ca, cb.
b) arranjos de taxa 3: abc, acb, bac, bca, cab, cba.

7.2 - Representando o número total de arranjos de n elementos tomados k a k (taxa k) por A_n,k , teremos a seguinte fórmula:

Obs : é fácil perceber que A_n,n = n! = P_{n .} (Verifique).

Exemplo:

Um cofre possui um disco marcado com os dígitos 0,1,2,...,9. O segredo do cofre é marcado por uma seqüência de 3 dígitos distintos. Se uma pessoa tentar abrir o cofre, quantas tentativas deverá fazer(no máximo) para conseguir abri-lo?

Solução: 

As seqüências serão do tipo xyz. Para a primeira posição teremos 10 alternativas, para a segunda, 9 e para a terceira, 8. Podemos aplicar a fórmula de arranjos, mas pelo princípio fundamental de contagem, chegaremos ao mesmo resultado:
10.9.8 = 720. 
Observe que 720 = A_10,3

8 - Combinações simples

8.1 - Denominamos combinações simples de n elementos distintos tomados k a k (taxa k) aos subconjuntos formados por k elementos distintos escolhidos entre os n elementos dados. Observe que duas combinações são diferentes quando possuem elementos distintos, não importando a ordem em que os elementos são colocados.

Exemplo: 

No conjunto E= {a,b.c,d} podemos considerar:
a) combinações de taxa 2: ab, ac, ad,bc,bd, cd.
b) combinações de taxa 3: abc, abd,acd,bcd.
c) combinações de taxa 4: abcd.

8.2 - Representando por C_n,k o número total de combinações de n elementos tomados k a k  (taxa k) , temos a seguinte fórmula:

 

Nota: o número acima é também conhecido como Número binomial e indicado por:

 

É muito conveniente guardar de memória esta fórmula do número binomial ou número combinatório, pois, em algumas incursões na Matemática Superior - a ser vista na Universidade - ela aparecerá. Já do arranjo simples - visto acima no item 6 - você nunca mais ouvirá falar, pelo menos na Universidade.

Exemplo:

Uma prova consta de 15 questões das quais o aluno deve resolver 10. De quantas formas ele poderá escolher as 10 questões?

Solução: 

Observe que a ordem das questões não muda o teste. Logo, podemos concluir que trata-se de um problema de combinação de 15 elementos com taxa 10. 

Aplicando simplesmente a fórmula chegaremos a: 
C_15,10 = 15! / [(15-10)! . 10!] = 15! / (5! . 10!) = 15.14.13.12.11.10! / 5.4.3.2.1.10! = 3003

Agora que você viu o resumo da teoria, tente resolver os problemas seguintes:

01 - Um coquetel é preparado com duas ou mais bebidas distintas. Se existem 7 bebidas distintas, quantos coquetéis diferentes podem ser preparados?
Resp: 120

02 -  Sobre uma circunferência são marcados 9 pontos distintos. Quantos triângulos podem ser construídos com vértices nos 9 pontos marcados?
Resp: 84

03 - Uma família com 5 pessoas possui um automóvel de 5 lugares. Sabendo que somente 2 pessoas sabem dirigir, de quantos modos poderão se acomodar para uma viagem?
Resp: 48

Exercícios resolvidos:

1 - Um salão tem 6 portas. De quantos modos distintos esse salão pode estar aberto?

Solução:

Para a primeira porta temos duas opções: aberta ou fechada
Para a segunda porta temos também, duas opções, e assim sucessivamente.
Para as seis portas, teremos então, pelo Princípio Fundamental da Contagem - PFC:
N = 2.2.2.2.2.2 = 64
Lembrando que uma dessas opções corresponde a todas as seis portas fechadas, teremos então que o número procurado será igual a 64  - 1 = 63.

Resposta: o salão pode estar aberto de 63 modos possíveis.

2 - Considere que 10 pessoas estão sentadas ao redor de uma mesa circular e que elas pretendam trocar de lugar de todas as formas possíveis, mantendo-se a mesma posição relativa das pessoas na mesa. Supondo que cada troca de todos os lugares poderá  ser feita em um minuto, determine o número de dias necessários para que todas as trocas de lugares sejam finalizadas.

Solução:

Como o problema explicita que deve-se manter a mesma posição relativa das pessoas na mesa , deveremos considerar o sentido de contagem irrelevante e, portanto, segundo o que vimos sobre Permutações Circulares no texto acima, deveremos usar a fórmula 
P'(n) = (n-1)!/2. Então, o número total de maneiras será igual a P'(10) = (10 - 1)!/2 = 9!/2 = (9.8.7.6.5.4.3.2.1) / 2 = 9.8.7.6.5.4.3 ou seja, P'(10) = 181440 maneiras distintas. Ora, se em cada mudança é gasto 1 minuto (conforme enunciado do problema), serão necessários 181440 minutos para que todas as trocas de lugares sejam feitas. Como um dia possui 24 horas e cada hora tem 60 minutos, concluímos que 1 dia = 24 . 60 = 1440 minutos. Então, dividindo 181440 por 1440, obteremos o tempo total necessário em dias, ou seja: 181440/1440 = 126. Portanto, serão necessários 126 dias para que 10 pessoas sentadas ao redor de uma mesa circular troquem de posição, mantendo a mesma posição relativa entre elas. Caso fosse considerado um sentido de arrumação (o sentido horário, por exemplo), a resposta seria o dobro ou seja: 252 dias. Ora, 126 dias representam 34,5% dos dias do ano e 252 dias, 69%. Acho que é devido à esta dificuldade, que as pessoas nas reuniões, procuram sentar-se nos mesmos lugares, todos os dias! eh eh eh ... . Claro que isto é apenas uma brincadeira e ilação matemática. As pessoas procuram sentar-se juntas numa mesa de reunião, por outros motivos. Algumas, querem estar sempre ao lado do Chefe; outras, nem tanto!

Paulo Marques - Feira de Santana - BA - revisado e ampliado em 19/03/2008.

CONTINUAR
VOLTAR