Numa sorveteria com 7 sabores, quantas formas diferentes existem de escolher 4 bolas de sorvete — sem importar a ordem no cone, podendo pedir o mesmo sabor mais de uma vez? Esse é um problema de combinação com repetição.
No artigo sobre arranjos com repetição, vimos que quando a ordem importa e a repetição é permitida, a contagem é \(n^r\). Agora damos o último passo da série: a ordem não importa mais, mas a repetição ainda é permitida. A fórmula muda — e a técnica para derivá-la é elegante o suficiente para ter nome próprio: estrelas e barras.
Por que combinações com repetição? #
Selecionar elementos com repetição sem considerar a ordem é uma operação central em computação e estatística:
- Multisets em programação:
collections.Counterdo Python armazena multisets — coleções onde um elemento pode aparecer mais de uma vez, sem que a ordem importe. O número de multisets de tamanho \(r\) sobre um vocabulário de \(n\) elementos é exatamente \(CR(n, r)\). - Distribuição de recursos idênticos: alocar \(r\) tokens, créditos ou tarefas idênticas entre \(n\) processos ou servidores sem considerar a sequência de entrega é um problema de \(CR(n, r)\) — base de modelos de escalonamento e balanceamento de carga.
- Análise de histogramas: um histograma com \(r\) amostras distribuídas em \(n\) categorias é contado por \(CR(n, r)\). Isso é a base de testes estatísticos de aderência (qui-quadrado) e de estimativas de diversidade em aprendizado de máquina.
- Programação inteira: contar soluções inteiras não-negativas de \(x_1 + x_2 + \cdots + x_n = r\) é equivalente a \(CR(n, r)\) — conexão direta com problemas de otimização e análise de espaços de estado.
- Compressão de dados: agrupar sequências por frequência de símbolos (sem levar em conta a posição de cada símbolo) usa \(CR\) para estimar o número de classes de equivalência — fundamento da entropia de Shannon.
Da combinação simples à combinação com repetição #
O diagrama abaixo completa a árvore de decisão da série, acrescentando o sexto e último tipo de agrupamento clássico:
flowchart TD
A["n tipos de elementos"] --> B{"Repetição
permitida?"}
B -->|"Não — todos distintos"| C{"Usar todos?"}
C -->|"Sim"| D["Permutação Simples
P_n = n!"]
C -->|"Não — escolher r"| E{"Ordem importa?"}
E -->|"Sim"| F["Arranjo Simples
A(n,r) = n!/(n-r)!"]
E -->|"Não"| G["Combinação Simples
C(n,r) = n!/(r!(n-r)!)"]
B -->|"Sim — com repetição"| H{"Usar todos?"}
H -->|"Sim — multiconjunto fixo"| I["Permutação com Repetição
n!/(n₁!·n₂!·…·nₖ!)"]
H -->|"Não — escolher r"| K{"Ordem importa?"}
K -->|"Sim"| J["Arranjo com Repetição
AR(n,r) = nʳ"]
K -->|"Não"| L["Combinação com Repetição
CR(n,r) = C(n+r-1,r)"]
Combinação com Repetição #
Uma combinação com repetição de \(n\) elementos tomados \(r\) a \(r\) — doravante representada por \(CR(n,r)\) — é uma seleção de \(r\) elementos sem considerar a ordem, onde cada elemento pode aparecer mais de uma vez:
$$CR(n, r) = \binom{n + r - 1}{r} = \binom{n + r - 1}{n - 1}$$Observação: ao contrário da combinação simples, \(r\) pode ser maior que \(n\) — podemos selecionar mais elementos do que os tipos disponíveis, simplesmente repetindo alguns.
O Método das Estrelas e Barras #
Como derivar a fórmula? A ideia é codificar cada distribuição como uma sequência de dois tipos de símbolos — ★ (estrela) e | (barra) — e contar essas sequências. ★ e | formam um alfabeto de dois símbolos, exatamente como 1 e 0 numa sequência binária: ★ representa “uma unidade alocada” e | representa “mudança de caixa”. No artigo sobre permutações com repetição, vimos que arranjar \(k\) símbolos de um tipo e \(m\) de outro produz \(\binom{k+m}{k}\) sequências distintas — esse resultado é o que usaremos aqui.
Exemplo motivador: distribuir 5 bolas idênticas em 3 caixas numeradas. Cada distribuição corresponde a uma sequência de 5 estrelas (★) e 2 barras (|), onde as barras separam as caixas:
$$\underbrace{★★}_{C_1} \;|\; \underbrace{★}_{C_2} \;|\; \underbrace{★★}_{C_3} \quad\longrightarrow\quad ★\,★\,|\,★\,|\,★\,★$$A sequência tem 5 estrelas e 2 barras — total de 7 símbolos. Contar as distribuições equivale a escolher quais 2 posições (entre as 7) recebem a barra:
$$C(7, 2) = C(5+3-1,\; 3-1) = \binom{7}{2} = 21$$Generalização: \(r\) estrelas em \(n\) caixas usam \(n-1\) barras, formando uma sequência de \(r + n - 1\) símbolos. Escolher as \(r\) posições das estrelas (ou as \(n-1\) das barras) dá:
$$CR(n, r) = \binom{n + r - 1}{r}$$Três Formulações Equivalentes #
A beleza do método das estrelas e barras é revelar que três problemas de enunciados muito diferentes são, na verdade, o mesmo problema de contagem:
Os três problemas abaixo têm exatamente \(CR(n,r) = \binom{n+r-1}{r}\) soluções:
- Seleção com repetição: escolher \(r\) elementos de \(n\) tipos (sem considerar a ordem, repetição permitida).
- Distribuição de objetos idênticos: colocar \(r\) bolas indistinguíveis em \(n\) caixas distintas (caixas podem ficar vazias).
- Equações inteiras: soluções inteiras não-negativas de \(x_1 + x_2 + \cdots + x_n = r\).
Reconhecer qual das três leituras se encaixa no enunciado é a habilidade central para resolver problemas com \(CR\).
Exemplos Resolvidos #
4 sorvetes de 7 sabores #
Enunciado: Uma sorveteria oferece 7 sabores. De quantas formas diferentes é possível pedir 4 bolas de sorvete, sem se importar com a ordem e podendo repetir o mesmo sabor?
Solução: A ordem das bolas no cone não importa (chocolate + morango = morango + chocolate), e a repetição é permitida (quatro bolas de chocolate é uma opção válida). Aplicamos a combinação com repetição com \(n = 7\) sabores e \(r = 4\) bolas:
$$CR(7, 4) = \binom{7 + 4 - 1}{4} = \binom{10}{4} = \mathbf{210}$$Voltando ao exemplo da abertura: há \(\mathbf{210}\) pedidos distintos possíveis.
Python: itertools.combinations_with_replacement
itertools.combinations_with_replacement
Python oferece diretamente a função que gera combinações com repetição —
itertools.combinations_with_replacement(iterable, r):
from itertools import combinations_with_replacement
from math import comb
sabores = ["chocolate", "morango", "baunilha", "limão",
"maracujá", "uva", "coco"] # 7 sabores
# Gera todos os pedidos de 4 bolas
pedidos = list(combinations_with_replacement(sabores, 4))
print(len(pedidos)) # 210 = CR(7, 4)
print(pedidos[0]) # ('baunilha', 'baunilha', 'baunilha', 'baunilha')
print(pedidos[-1]) # ('uva', 'uva', 'uva', 'uva')
# Verificação pela fórmula
print(comb(7 + 4 - 1, 4)) # 210Note que combinations_with_replacement sempre devolve tuplas em ordem
não-decrescente — exatamente porque a ordem não importa. Dois pedidos com os
mesmos sabores mas em ordens diferentes aparecem como uma única tupla.
5 bolas em 3 caixas #
Enunciado: De quantas maneiras é possível distribuir 5 bolas idênticas em 3 caixas distintas (caixas podem ficar vazias)?
Solução: Bolas idênticas em caixas distintas é a segunda leitura das equivalências clássicas: \(n = 3\) caixas, \(r = 5\) bolas.
$$CR(3, 5) = \binom{3 + 5 - 1}{5} = \binom{7}{5} = \binom{7}{2} = \mathbf{21}$$O método das estrelas e barras confirma: 5 estrelas e 2 barras, escolher 2 posições entre 7.
A conexão fica clara quando nomeamos as caixas do exemplo anterior com variáveis. Seja \(x_1\) o número de bolas na caixa 1, \(x_2\) o número na caixa 2 e \(x_3\) o número na caixa 3. Cada distribuição válida é exatamente uma solução inteira não-negativa de:
$$x_1 + x_2 + x_3 = 5, \quad x_i \geq 0$$Por exemplo, a distribuição ★★ | ★ | ★★ corresponde à solução \((x_1, x_2, x_3) = (2, 1, 2)\). A sequência de estrelas e barras ★ ★ | ★ | ★ ★ e a equação \(2 + 1 + 2 = 5\) carregam a mesma informação — são duas notações para o mesmo objeto.
Isso generaliza imediatamente: soluções inteiras não-negativas de \(x_1 + x_2 + \cdots + x_n = r\) são o mesmo que distribuições de \(r\) bolas em \(n\) caixas, e portanto são contadas por \(CR(n, r)\). A variável \(x_i\) é o “contador” da caixa \(i\); a equação é apenas a exigência de que o total de bolas seja \(r\).
Do mesmo modo, o exemplo da sorveteria pode ser escrito com variáveis: se \(s_i\) é o número de bolas do sabor \(i\) pedidas, contar pedidos de 4 bolas de 7 sabores é o mesmo que contar soluções de \(s_1 + s_2 + \cdots + s_7 = 4\) com \(s_i \geq 0\) — e o resultado é \(CR(7, 4) = 210\), como já vimos.
Soluções inteiras de \(x + y + z + w = 9\) #
Enunciado: Quantas soluções inteiras não-negativas tem a equação \(x + y + z + w = 9\)?
Solução: Temos \(n = 4\) variáveis (equivalentes a 4 caixas) e \(r = 9\) (equivalente a 9 bolas a distribuir):
$$CR(4, 9) = \binom{4 + 9 - 1}{9} = \binom{12}{9} = \binom{12}{3} = \mathbf{220}$$Soluções de \(x_1 + x_2 + x_3 = 10\) com \(x_2 \geq 4\) #
Enunciado: Quantas soluções inteiras não-negativas tem \(x_1 + x_2 + x_3 = 10\) com a restrição \(x_2 \geq 4\)?
Solução: A restrição \(x_2 \geq 4\) é tratada por substituição: definimos \(y_2 = x_2 - 4 \geq 0\), que “absorve” o mínimo obrigatório de \(x_2\). A equação se transforma:
$$x_1 + (y_2 + 4) + x_3 = 10 \implies x_1 + y_2 + x_3 = 6$$Agora temos \(n = 3\) variáveis e \(r = 6\), todas não-negativas:
$$CR(3, 6) = \binom{3 + 6 - 1}{6} = \binom{8}{6} = \binom{8}{2} = \mathbf{28}$$Soluções de \(x + y + z + w \leq 5\) #
Enunciado: Quantas soluções inteiras não-negativas tem \(x + y + z + w \leq 5\)?
Solução — Método 1 (soma direta por casos): separamos por valor total \(k = 0, 1, \ldots, 5\) e aplicamos o Princípio Aditivo:
$$\sum_{k=0}^{5} CR(4, k) = \binom{3}{0} + \binom{4}{1} + \binom{5}{2} + \binom{6}{3} + \binom{7}{4} + \binom{8}{5} = 1 + 4 + 10 + 20 + 35 + 56 = 126$$Solução — Método 2 (variável de folga): introduzimos \(f = 5 - (x+y+z+w) \geq 0\), que transforma a desigualdade em igualdade:
$$x + y + z + w + f = 5 \implies CR(5, 5) = \binom{9}{5} = \mathbf{126} \checkmark$$O método da variável de folga é mais elegante: em vez de somar 6 parcelas, resolve-se em uma única aplicação da fórmula.
Tabela-Resumo #
A tabela abaixo reúne todos os seis tipos de agrupamento da série e o resultado central deste artigo:
| Sem repetição | Com repetição | |
|---|---|---|
| Usa todos os \(n\) elementos | Permutação Simples: \(n!\) | Permutação c/ Repetição: \(\dfrac{n!}{n_1!\cdots n_k!}\) |
| Escolhe \(r\) — ordem importa | Arranjo Simples: \(\dfrac{n!}{(n-r)!}\) | Arranjo c/ Repetição: \(n^r\) |
| Escolhe \(r\) — ordem não importa | Combinação Simples: \(\dfrac{n!}{r!(n-r)!}\) | Combinação c/ Repetição: \(\dbinom{n+r-1}{r}\) |
Resultados específicos deste artigo:
| Resultado | Fórmula |
|---|---|
| Combinação com repetição | \(CR(n,r) = \dbinom{n+r-1}{r}\) |
| Equivalência com distribuição de objetos idênticos | \(r\) bolas em \(n\) caixas → \(CR(n,r)\) |
| Equivalência com soluções inteiras não-negativas | \(x_1 + \cdots + x_n = r,; x_i \geq 0\) → \(CR(n,r)\) |
| Desigualdade: \(x_1 + \cdots + x_n \leq r,; x_i \geq 0\) via variável de folga | \(CR(n+1, r)\) |
Exercícios #
Os exercícios a seguir percorrem as três formulações equivalentes do \(CR(n,r)\): seleção com repetição, distribuição de objetos idênticos e soluções de equações com restrições. Estão ordenados do mais simples ao mais complexo.
Exercício 1 — Distribuição de laranjas
De quantas maneiras podemos distribuir 6 laranjas idênticas entre 2 pessoas (cada pessoa pode ficar sem laranja)?
As laranjas são idênticas (a ordem entre elas não importa) e cada pessoa pode receber qualquer quantidade, inclusive zero. Isso é equivalente a contar soluções inteiras não-negativas de \(a + b = 6\), com \(n = 2\) e \(r = 6\):
$$CR(2, 6) = \binom{7}{6} = \binom{7}{1} = \mathbf{7}$$As distribuições são: (0,6), (1,5), (2,4), (3,3), (4,2), (5,1), (6,0) — exatamente 7. ✓
Exercício 2 — Docinhos de festa
Uma confeitaria oferece 8 variedades de docinhos. De quantas formas é possível comprar 12 docinhos, podendo repetir variedades e sem se importar com a ordem?
Seleção com repetição: \(n = 8\) variedades, \(r = 12\) docinhos:
$$CR(8, 12) = \binom{8 + 12 - 1}{12} = \binom{19}{12} = \binom{19}{7} = \mathbf{50{.}388}$$
Exercício 3 — Bolas em caixas não vazias
De quantas maneiras é possível colocar 20 bolas idênticas em 5 caixas distintas sem deixar nenhuma caixa vazia?
A restrição “nenhuma caixa vazia” significa que cada caixa recebe pelo menos 1 bola. Fazemos a substituição \(x_i^* = x_i - 1 \geq 0\), que absorve o mínimo de 1 por caixa. A soma total diminui em 5:
$$x_1 + \cdots + x_5 = 20,\; x_i \geq 1 \;\implies\; x_1^* + \cdots + x_5^* = 15,\; x_i^* \geq 0$$$$CR(5, 15) = \binom{5 + 15 - 1}{15} = \binom{19}{15} = \binom{19}{4} = \mathbf{3{.}876}$$
Exercício 4 — Soma dos dígitos
Quantos inteiros entre 1 e 100.000 têm soma dos algarismos igual a 6?
Todo inteiro nessa faixa pode ser representado como uma sequência de 5 algarismos \(d_1 d_2 d_3 d_4 d_5\) com \(d_i \geq 0\) (incluindo zeros à esquerda: 6 vira 00006). O número 100.000 tem soma de algarismos 1, portanto não entra na contagem. Queremos soluções inteiras não-negativas de \(d_1 + d_2 + d_3 + d_4 + d_5 = 6\). Como a soma é 6 e nenhum dígito pode exceder 9, a restrição \(d_i \leq 9\) é satisfeita automaticamente:
$$CR(5, 6) = \binom{5 + 6 - 1}{6} = \binom{10}{6} = \binom{10}{4} = \mathbf{210}$$
Exercício 5 — Soluções inteiras positivas com desigualdade
Quantas soluções inteiras positivas (\(x, y, z \geq 1\)) tem \(x + y + z < 10\)?
Passo 1 — eliminar o \(\geq 1\): seja \(x^* = x - 1,; y^* = y - 1,; z^* = z - 1 \geq 0\). A desigualdade vira \(x^* + y^* + z^* < 7\), ou seja \(\leq 6\).
Passo 2 — transformar a desigualdade em igualdade: introduzimos variável de folga \(u = 6 - (x^* + y^* + z^*) \geq 0\):
$$x^* + y^* + z^* + u = 6, \quad x^*, y^*, z^*, u \geq 0$$Agora temos \(n = 4\) variáveis e \(r = 6\):
$$CR(4, 6) = \binom{4 + 6 - 1}{6} = \binom{9}{6} = \binom{9}{3} = \mathbf{84}$$Próximos passos #
A combinação com repetição completa a tríade dos agrupamentos com repetição e fecha o quadro de seis tipos de contagem da série. A limitação de todos esses instrumentos é trabalhar com contagens simples: quantos há? O próximo passo natural é entender como esses coeficientes se relacionam entre si — as identidades que os conectam, como a recorrência de Pascal e o Binômio de Newton, temas dos próximos artigos da série.
