Análise combinatória - Combinações com repetição

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 requerem esquecer 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 o que separa garotos de homens em matemática!

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 \(a^{i_1}b^{i_2}c^{i_3}\), onde \(i_j\) 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³: 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ão há p uns e n - 1 zeros. Logo:

\(CR^n_p = C^{p + n - 1}_p\)

Voltando ao nosso exemplo, há \(C^{3 + 3 - 1}_3 = C^{5}_3 = 10\) 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 primeiro 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!

Fontes

Matemática Essencial: Médio: Análise Combinatória
Uma introdução à Combinatória - Técnicas de Contagem