Daí surge a análise combinatória, o ramo da matemática — matemática discreta, mais especificamente — que estuda maneiras de realizar essas contagens indiretamente. A análise combinatória é muito usada em probabilidade, outro assunto muito interessante que pretendo abordar no futuro, para calcular as chances de um determinado evento ocorrer, como as probabilidades (não muito otimistas) de você ganhar na loteria.
Neste post vou falar sobre conceitos básicos e propor alguns problemas ao final, junto com boas fontes de estudo para quem quiser mais aprofundamento.
Princípio Fundamental da Contagem
Vamos começar com um exemplo simples para mostrar como contar em análise combinatória. Você tem uma luva, duas blusas e três calças. De quantas maneiras pode se vestir, considerando que não pode deixar de vestir nenhuma peça? Sem saber nenhuma técnica de contagem, o jeito é listar as opções:
{(luva, blusa A, calça A), (luva, blusa A, calça B), (luva, blusa A, calça C), (luva, blusa B, calça A), (luva, blusa B, calça B), (luva, blusa B, calça C)}
Um total de 6 possibilidades, sem problemas. E se fossem 5 luvas, 10 blusas e 5 calças, alguém se aventura a listar todas as possibilidades? Mas não se esqueçam que a análise combinatória está aí para nos auxiliar a contar indiretamente, isto é, sem precisar enumerar todos os casos como fizemos acima. Vamos sistematizar melhor o que fizemos para deduzir intuitivamente um princípio fundamental:
1º item: luva, 1 possibilidade
2º item: blusa A ou blusa B, 2 possibilidades
3º item: calça A, calça B ou calça C, 3 possibilidades
Concorda que para cada luva (1, no caso), podemos ter 2 blusas? E para cada uma dessas blusas temos 3 calças? Assim, o número total de combinações é 1 * 2 * 3 = 6. No nosso segundo caso, basta calcular então 5 * 10 * 5 = 250 possibilidades.
E este é o tal Princípio Fundamental da Contagem, ou Princípio Multiplicativo: se determinado acontecimento ocorre em k etapas diferentes e, a primeira etapa pode ocorrer de n1 maneiras diferentes e, para cada uma dessas maneiras, há n2 maneiras diferentes de ocorrer a segunda etapa e assim sucessivamente, então, o número total, n, de ocorrer o acontecimento é dado por:
n = n1 * n2 * ... * nk
Permutações
Uma permutação de n elementos em um conjunto é qualquer sequência formada por esses elementos, diferindo apenas na ordem. Por exemplo, suponha que Maicoujéquisom e 3 irmãos estejam em uma viagem com o pai, havendo 3 assentos traseiros e um assento na frente. De quantos modos os irmãos podem se distribuir no carro? Ou, em outras palavras, qual é a permutação de 4 elementos?
1º assento: 4 possibilidades
2º assento: 3 possibilidades (1 dos irmãos já ocupou o 1º assento)
3º assento: 2 possibilidades
4º assento: 1 possibilidade
Pelo princípio multiplicativo, temos 4 * 3 * 2 * 1 = 24 possibilidades. Como toda permutação de n elementos é dada por n * (n - 1) * (n - 2) * ... * 1, utilizamos a notação n! (lê-se "n fatorial") para simplificar as coisas. O que acabamos de fazer foi determinar a permutação simples de quaisquer n elementos, mas podemos também ter permutações com repetição, completas e circulares.
Apesar de haver métodos para calcular tais sequências, podemos resolver boa parte dos problemas apenas com o princípio multiplicativo. Mais importante do que decorar as fórmulas é dominar os fundamentos, então nos problemas ao final do post vamos tentar nos virar com o que temos por enquanto.
Arranjos
Agora considere os números 2, 4, 5, 7 e 9. Quantos números de 3 algarismos distintos podemos formar com eles? Note que o problema refere-se explicitamente a uma sequência sem repetição, então podemos (ou não) usar a noção de arranjos, assim possibilitando uma maneira de resolvê-lo. Um arranjo de n elementos tomados de p a p é dado por:
A(n, p) = n!/(n - p!)
Utilizando-a, vemos que para resolver o problema basta calcular A(5, 3) = 5 * 4 * 3 *
Para o primeiro algarismo temos 5 possibilidades, 4 para o segundo e 3 para o terceiro, então 5 * 4 * 3 = 60, sem problemas. Para demonstrar o perigo de depender demais das "rotinas prontas", vamos alterar o exemplo acima: suponha que os números agora sejam 0, 4, 5, 7 e 9. A resposta é a mesma? Evidente que não, pois para o primeiro dígito temos apenas 4 possibilidades, excluindo o 0.
Mas então a fórmula acima é inútil? Muito pelo contrário. Se pudermos reduzir o problema a algo que até uma máquina consiga executar, isso nos garante não apenas algoritmos eficientes para funções diversas (principalmente envolvendo probabilidades) como recursos para compreender agrupamentos diferentes. Aliás, vamos usar a fórmula de arranjos já já para determinar a fórmula da combinação.
Combinações
Vejamos agora um outro tipo de agrupamento. Adalberto, Bruno, Cido, Dijkstra e Eduardo querem formar um clube e determinam que, a cada semana, 3 deles serão apontados como líderes. De quantas formas diferentes eles podem fazer isso? Se achou similar ao exemplo acima não é por coincidência: queremos tomar n = 5 elementos de p a p, com p = 3. Mas calma lá, abaixa esse lápis e vamos refletir um pouco.
Concorda que, no caso anterior, o número 245 é diferente de 425? Mas como os 3 líderes têm a mesma importância, não faz diferença a ordem. Assim, podemos considerar o conjunto {Adalberto, Bruno, Cido} igual ao conjunto {Bruno, Adalberto, Cido}, por exemplo. Bem, primeiramente calculamos A(5, 3) = 60 possibilidades.
Só que não é isso que queremos. Dessas 60 possibilidades, temos repetições, como a citada acima. Concordam que se dividirmos 60 pela permutação de 3 elementos quaisquer encontramos o resultado certo? Afinal, 60 = conjuntos * repetições => conjuntos = 60/repetições. Que repetições são essas? Justamente a permutação dos elementos, como {A, B, C}, {A, C, B}, {B, C, A}... e daí chegamos a 60/3! = 10. Generalizando:
$$ C^n_p = \frac{A_{n,p}}{p!} = \frac{n!}{p!(n - p)!} $$
Outra notação utilizada é \( \binom{n}{p} \) , para designar uma combinação de n elementos tomados de p a p. Assim determinamos uma combinação simples. Vou deixar a cargo de vocês estudarem outros tipos de combinação.
Princípio da Casa dos Pombos
Um tópico curto e aparentemente trivial, mas que responde a muitos problemas não apenas de análise combinatória como de outras áreas. Em seu enunciado mais simples: se há m pombos e n casas disponíveis, com m > n, então pelo menos uma casa ficará com pelo menos 2 pombos. Por exemplo, 9 pombos para 8 casas. O que é intuitivo, a não ser que você seja um cruel maltratador de animais e deixe um ou mais pombos de fora.
Exemplo prático: se há 100 pessoas em uma sala, pelo menos quantas fazem aniversário num mesmo mês? No caso, há 100 "pombos" (as pessoas) e 12 "casas" (os meses do ano). Se dividíssemos igualitariamente, teríamos 100/12 = 8,333... pessoas para cada mês, o que não é possível. Usamos então a notação [x], que representa o menor inteiro maior ou menor que x. Assim, [8,333...] = 9, nossa resposta.
Se não ficou claro, vamos a um outro exemplo: no mínimo quantas pessoas deve-se reunir em uma sala para que pelo menos 2 façam aniversário em um mesmo mês? Basta nos lembrarmos do princípio: "se há m pombos e n casas disponíveis, com m > n, então pelo menos uma casa ficará com pelo menos 2 pombos". Há 12 "casas", logo, o menor m > 12 é 13. O que fizemos foi encontrar o menor valor que se encaixa na equação:
[x/12] = 2
Problemas
1. Determine os anagramas da palavra "beijo", isto é, "palavras" diferentes formadas pelas mesmas letras.
2. Quantos números maiores que 1000 podem ser formados com os dígitos 3, 4, 6, 8, 9 se um dígito não pode aparecer mais que uma vez no número?
3. Determine os anagramas da palavra "banana". Note, entretanto, que a troca de letras iguais constitui uma repetição. Generalize para qualquer permutação de n elementos com repetição do elemento a1 n1 vezes, a2 n2 vezes, ..., ak nk vezes. Dica: dê uma olhada novamente em nossa dedução da fórmula da combinação.
4. Quantos números de seis algarismos se podem formar com os algarismos de 1 a 6? Generalize para qualquer permutação na qual é permitida a repetição de elementos, sem que seja necessário utilizar todos em uma mesma sequência.
5. 5 crianças desejam brincar de roda. De quantos modos distintos estas crianças podem formar a roda sem que haja repetição? Observação: o importante aqui é a posição relativa de cada criança, então apenas mudar de lugar não constitui um novo agrupamento se, por exemplo, todas as crianças à direita e à esquerda de A permanecerem as mesmas.
6. Quantos divisores tem o número 2800?
Se quiser a resolução para estes e outros problemas, confira neste post.
Fontes
Análise Combinatória
Uma Introdução à Combinatória - Técnicas de Contagem
Counting and Probability
Postagens
0 comentários:
Postar um comentário