Combinações com repetição

As combinações com repetição são parecidas com as combinações clássicas, só que permitimos que os elementos do conjunto base M se repitam.

Definição e fórmula

Vamos começar com um exemplo legal: você entra em uma loja e quer comprar doze garrafinhas de suco para levar a um acampamento. Na prateleira há quatro sabores diferentes. Agora você tem várias possibilidades de comprar as garrafinhas: pode comprar, por exemplo, 5 de laranja, 2 de uva, 1 de maçã e 4 de caju, ou pode comprar exatamente três de cada sabor. Quantas possibilidades diferentes existem de comprar as garrafinhas, de modo que você leve exatamente doze?

Temos, portanto, o conjunto base M = {laranja, uva, maçã, caju} e perguntamos quantas k-uplas, com k = 12, existem que contenham elementos do conjunto M e em que a ordem não importa.

A dedução da fórmula já é bem mais complicada do que nos outros problemas de combinatória. Primeiro, imaginamos a nossa compra como uma sequência de zeros e uns, de modo que o número de uns corresponde ao número de garrafinhas compradas de determinado sabor e o zero separa os sabores. Assim, 111011101111101 nos diz que compramos três de laranja (os três primeiros 1), depois três de uva (0 é o separador, mais três 1), depois cinco de maçã (0 separador e depois cinco 1) e, por fim, uma de caju. O princípio todo é mostrado na figura a seguir:

$$\underset{Lar}{\underbrace{111}}0\underset{Uva}{\underbrace{111}}0\underset{Maç}{\underbrace{11111}}0\underset{Caj}{\underbrace{1}}$$

Se quiséssemos comprar 6 de laranja, 4 de uva, 2 de caju e nenhuma de maçã, a sequência seria assim:

$$\underset{Lar}{\underbrace{111111}}0\underset{Uva}{\underbrace{1111}}00\underset{Caj}{\underbrace{11}}$$

Observe que o comprimento dessa sequência é sempre igual a 15: precisa haver 12 uns para comprarmos 12 garrafinhas no total. E precisa haver três separadores para conseguirmos separar quatro sabores diferentes. Resta calcular quantas sequências de comprimento 15 existem que contêm exatamente três zeros.

Basta calcular o posicionamento dos zeros: quando distribuímos 3 zeros entre os 12 uns, temos uma combinação válida de sucos. Em outras palavras: temos 15 casas e precisamos ocupar 3 delas com zero. As casas restantes serão ocupadas automaticamente com uns.

Esse já é um problema simples de combinações sem repetição. Numeramos as 15 casas com os números {1, …, 15} e agora escolhemos desse conjunto sempre ternas de números, obtendo três índices em que colocaremos o zero. Por exemplo, para a combinação {2, 4, 7} obteríamos a sequência: 101011011111111. Na 2ª, na 4ª e na 7ª posições há zero, o resto são uns. Existem, assim,

$$(\genfrac{}{}{0ex}{}{15}{3})=455$$

maneiras diferentes de distribuir os zeros nas 15 casas e, portanto, também 455 possibilidades diferentes de comprar 12 sucos, se temos quatro sabores diferentes.

Podemos generalizar o raciocínio anterior. Se temos um conjunto de elementos M com n elementos e escolhemos dele k-uplas, em que os elementos podem se repetir, então montamos uma sequência de zeros e uns de comprimento n + k − 1 (k uns e n − 1 zeros) e descobrimos de quantas maneiras podemos distribuir os n − 1 zeros; assim, o número de combinações com repetição, que denotamos por CR_n,k, é igual a

$$C{R}_{n,k}=(\genfrac{}{}{0ex}{}{n+k-1}{n-1})=(\genfrac{}{}{0ex}{}{n+k-1}{k}).$$

A última simplificação pôde ser feita graças às relações básicas entre números binomiais.

Exercícios resolvidos

1. De quantas maneiras é possível distribuir 20 ingressos gratuitos para a estreia de uma comédia entre 10 senhoras aposentadas? Esse é um exemplo de combinações com repetição, porque uma senhora pode receber mais ingressos, potencialmente todos. Só precisamos perceber corretamente o que é n e o que é k. Na verdade, escolhemos combinações de 20 elementos entre 10 senhoras; em outras palavras, criamos uma sequência de zeros e uns de comprimento 29, com 20 uns e 9 zeros. Então n = 10, k = 20. Obtemos o resultado:

$$C{R}_{10,20}=(\genfrac{}{}{0ex}{}{10+20-1}{20})=10.015.005.$$