Combinação Com Repetição Formula

O que é combinação com repetição e quando ela realmente aparece

A combinação com repetição formula serve para contar de quantas formas podemos escolher k elementos de um conjunto de n tipos quando podemos repetir itens e a ordem não importa. O resultado se chama coeficiente binomial generalizado ou número de combinações com repetição, e a fórmula é: C(n, k) = C(n + k - 1, k) = (n + k - 1)! / (k! × (n - 1)!)

É a mesma coisa que contar multiconjuntos. Escolher 3 bolas de sabores entre 5 sabores disponíveis, onde você pode pegar mais de uma bola do mesmo sabor. A ordem das bolas na sacola não muda o resultado.

combinação com repetição formula

Aqui vai a forma prática de calcular. Digamos que você tem n = 5 sabores e quer escolher k = 3 bolas. A conta vira C(5 + 3 - 1, 3) = C(7, 3) = 35. Trinta e cinco possibilidades. Se você fizer isso na mão com fatorial, vai dar no mesmo, mas para números maiores é melhor usar a forma simplificada: (n + k - 1) × (n + k - 2) × ... × n / k!

Isso evita calcular fatoriais enormes. No exemplo acima: 7 × 6 × 5 / 3 × 2 × 1 = 35. A simplificação corta os termos em comum. O que muita gente erra é confundir com permutação com repetição ou com combinação simples. Na combinação simples, cada elemento aparece no máximo uma vez. Aqui, cada elemento pode aparecer quantas vezes quiser. A diferença parece pequena, mas muda o resultado completamente. Para n = 5 e k = 3, a combinação simples dá C(5,3) = 10, enquanto a combinação com repetição dá 35. São espaços diferentes.

Um problema que eu tive na prática foi calcular combinações com repetição para um cenário de loteria simulada onde n = 20 e k = 12. A resposta precisa era C(31, 12), que é 846.709.445. Eu tentei calcular usando logaritmos no Excel para evitar overflow de fatorial, mas o resultado aproximado vinha com erro relativo de quase 0,3 por cento. Resolveu passando para aritmética de inteiros com bibliotecas de big-int ou dividindo o produto em fatores primos antes de multiplicar. Fatorar 31! em primos e cancelar com 12! e 19! deu o valor exato sem aproximação. Outra coisa que merece atenção é o caso em que k = 0. A fórmula funciona e entrega 1, que é o conjunto vazio. Isso é útil em recursões e em problemas dinâmicos onde uma subcategoria pode não selecionar nada. Se seu código não tratar k = 0 explicitamente, ele pode cair em divisão por zero ou retornar NaN dependendo da implementação.

Cálculo prático passo a passo

Vou mostrar com n = 4 e k = 2 para ficar rápido e direto. A conta vira C(4 + 2 - 1, 2) = C(5, 2) = 10. Os multiconjuntos possíveis a partir de {A, B, C, D} escolhendo 2 itens são: AA, AB, AC, AD, BB, BC, BD, CC, CD, DD.

Dezenove se contarmos apenas os com elementos distintos, mas aqui temos repetição, então AA, BB, CC e DD entram. Isso dá 6 combinações sem repetição mais 4 com repetição, totalizando 10. A contagem manual confere com a fórmula. Para valores maiores, como n = 8 e k = 5, a conta é C(12, 5) = 792. Você pode calcular isso rapidamente com uma função nativa de comb em várias linguagens. Em Python, por exemplo, math.comb(12, 5). Em R, choose(12, 5). Em planilhas, COMOINAÇÃO.5(12; 5).

Pegadinhas comuns e como evitar

A primeira pegadinha é aplicar a fórmula quando a ordem importa. Se a ordem dos elementos escolhidos importa, você precisa de permutação com repetição, que é n^k, não combinação com repetição. Trocar esses dois conceitos é o erro mais frequente em exercícios introdutórios. A segunda pegadinha é acreditar que a fórmula funciona para conjuntos onde os elementos são distinguíveis mas têm pesos ou restrições diferentes. Por exemplo, se você tem três sabores de sorvete, mas o chocolate só pode ser escolhido no máximo duas vezes, a fórmula padrão não se aplica. Você precisa decompor o problema em casos ou usar função geratriz. Eu já perdi tempo tentando encaixar restrições assim na fórmula básica e depois descobri que a abordagem por cases era mais rápida.

A terceira pegadinha é tentar usar a combinação com repetição para problemas de distribuição de objetos idênticos em caixas distinguíveis com capacidade limitada. O modelo padrão assume capacidade infinita por caixa. Se houver limites, o método de estrelas e barras com exclusão de inclusion-exclusion entra em cena, e a conta fica bem mais pesada.

Quando usar e quando não usar

Use combinação com repetição quando precisar contar seleções sem ordem e com reposição ilimitada. É comum em problemas de probabilidade com substituição, em otimização combinatória, e em modelagem de amostragem bootstrap. Não use quando os itens tiverem restrições de multiplicity, quando a ordem importar, ou quando o conjunto base for infinito. Para conjuntos infinitos, a ideia precisa ser reformulada, muitas vezes recorrendo a séries formais ou contagem assintótica.

Uma alternativa prática quando a fórmula direta gera números enormes é contar apenas modulo um primo grande, se o objetivo for verificação de igualdade ou criptografia. Para contagem exata em tamanhos moderados, aritmética de big-int é suficiente. Para tamanhos muito grandes, aproximação com Stirling e análise assintótica entrega a ordem de grandeza sem gasto computacional desnecessário.

Implementação rápida

Em Python, a solução mais segura para valores medianos é math.comb(n + k - 1, k). Se precisar de valores ainda maiores, use sympy.binomial ou construa um produto acumulado cancelando fatores de k! em cada passo para manter os inteiros pequenos durante o cálculo. Em planilhas, a função COMOINAÇÃO ou a estrutura COMBINATORIAL resolve para inputs razoáveis. Acima de k = 30 com n grande, o arredondamento de ponto flutuante começa a incomodar, então migre para uma linguagem com suporte a inteiros arbitrários.

O essencial é reconhecer que a combinação com repetição não é mágica, é um ajuste direto do coeficiente binomial. A transformação n -> n + k - 1 é o que sustenta tudo. Se você memoriza essa mudança de variável, o resto é aritmética básica.