Há alguns problemas de contagem muito interessantes que não podem ser resolvidos apenas com os conhecimentos básicos de análise combinatória. Alguns requeremesquecer o glamour e contar na raça mesmo, outros uma sofisticação maior. Nesta mini-aula de dois posts vamos aprender sobre combinações com repetição e distribuição de objetos em caixas, ambos conceitos bem úteis para a OBM/OBMEP.
Introdução
Considere o seguinte problema: Dados os números 2, 4, 7, 9 e 10, quantos produtos diferentes é possível estabelecer multiplicando quaisquer 2 deles, se cada fator pode aparecer mais de uma vez nesse produto?
Inicialmente somos tentados a achar que a resposta é uma combinação de 5 elementos tomados de 2 a 2, mas nessa contagem ignoramos os produtos de dois números iguais. Um desses produtos é 2 x 2. Poderíamos considerar que estamos combinando 10 elementos ao invés de 5, mas nesse caso contaríamos o mesmo produto mais de uma vez.
Outra questão: De quantos modos podemos particionar um número em n parcelas, tal que a soma dessas parcelas resulte no número original? Por exemplo, particionar 6 em 3 parcelas?
Esse tipo de problema corresponde a encontrar o número de soluções (inteiras positivas ou não-negativas, dependendo do problema) da equação:
x + y + z = 6
Para responder essas e outras questões, vamos explorar dois conceitos de análise combinatória: combinações com repetição e distribuição de objetos em caixas. Bem... claro, no desespero você poderia tentar dividir em casos e contar um por um, mas é isso que separa garotos de matemáticos.
Pré-requisitos
Naturalmente, um conhecimento básico de análise combinatória é necessário aqui — em especial, combinações. Dê uma olhada nesta breve introdução para ter alguma base ou refrescar a memória.
Combinações com repetição
Vejamos uma outra versão do primeiro problema apresentado na introdução: consideremos 3 objetos a, b, c. De quantas formas é possível combiná-los, tomando-os em grupos de 3, se pudermos repetir objetos em um mesmo grupo?
Primeiro, vamos estabelecer algumas notações para facilitar o raciocínio. Cada grupo será representado por um monômio na forma ai1bi2ci3 , onde ij representa o número de vezes que o j-ésimo elemento aparece no grupo. Algumas representações (note que omitimos os termos com grau zero):
a
i
1
b
i
2
c
i
3
i
j
- a³: O grupo é formado por três objetos "a".
- abc: O grupo é formado por um objeto "a", um objeto "b" e um objeto "c".
- b²c: O grupo é formado por dois objetos "b" e um objeto "c".
- c³: O grupo é formado por três objetos "c".
Além disso, cada grupo também pode ter uma representação binária. Usamos uma fila de uns para mostrar quantas vezes o objeto é repetido no grupo e zeros para dividir os objetos:
- a³: 11100
- abc: 10101
- b²c: 01101
- c³: 00111
Podemos observar algumas coisas interessantes:
- O número de uns não varia, sendo sempre igual a 3. Isso porque, em cada grupo, deve obrigatoriamente haver 3 objetos.
- O número de zeros também não varia, sendo sempre igual a 2. Para dividir os objetos em 3 sub-sequências, precisamos de 2 zeros.
- O número total de elementos corresponde à soma da quantidade de uns com a quantidade de zeros. Isso resulta em 5 elementos no total.
Assim, vemos que há 5 espaços para serem preenchidos por 3 uns. Os 2 espaços restantes serão preenchidos por zeros.
 |
| Podemos posicionar cada um desses 3 uns em qualquer uma das 5 posições. |
Exemplo de distribuição:
 |
| Posicionamos o primeiro um na primeira posição, o segundo na terceira e o terceiro na quinta. Como consequência, a segunda e quarta posição são ocupadas por zeros. |
Generalizando, se tivermos n objetos combinados de p a p, com repetição permitida, entãohá p uns e n - 1 zeros. Logo:
R
n
p
=
C
p+n−1
p
Voltando ao nosso exemplo, há
combinações possíveis para os 3 objetos tomados de 3 a 3. Podemos listá-las: {a, a, a}, {a, a, b}, {a, a, c}, {b, b, b}, {b, b, a}, {b, b, c}, {c, c, c}, {c, c, a}, {c, c, b}, {a, b, c}. Sim, contamos todas!
Como exercício, resolva o problema apresentado na introdução.
Como exercício, resolva o problema apresentado na introdução.
O que vem por aí
A seguir, vamos explorar o problema de distribuir objetos em caixas — relativamente simples, mas talvez não tão simples quanto se imagina. Clique aqui para continuar!
Nenhum comentário:
Postar um comentário