Combinações sem repetição

Combinações sem repetição respondem a uma pergunta básica de contagem em estatística e matemática discreta: dados n itens distintos, quantos grupos diferentes de tamanho k você pode formar quando nenhum item aparece duas vezes e a ordem da seleção não importa? Essa quantidade é o coeficiente binomial C(n,k), também escrito n escolhe k. Não há amostragem, nem rede, nem arredondamento dependente de data: cada par válido (n, k) produz o mesmo inteiro todas as vezes.

O que as combinações sem repetição contam

Combinações sem repetição contam de quantas formas você pode escolher um subconjunto de k itens de um conjunto de n itens distintos quando cada item aparece no máximo uma vez e a ordem da seleção não importa. Na linguagem de sala de aula isso é n escolhe k; na notação estatística é o coeficiente binomial C(n,k). A identidade clássica diz que C(n,k) é o fatorial de n dividido pelo fatorial de k vezes o fatorial de (n menos k).

Essa mesma quantidade aparece como coeficiente na expansão binomial de (x mais y) elevado a n, e como o número de k-subconjuntos de um conjunto de n elementos. Como a ordem é ignorada, escolher Alice e depois Bob é a mesma combinação que escolher Bob e depois Alice, então a contagem é estritamente menor que a permutação correspondente P(n,k) sempre que k for pelo menos dois.

Como a repetição é proibida, você não pode escolher a mesma pessoa duas vezes: essa é a diferença em relação às combinações com repetição, também chamadas combinações de multiconjuntos, cuja contagem é C(n+k−1, k). Casos de fronteira fazem parte da definição: C(n,0) e C(n,n) valem ambos um, C(n,1) iguala n, e C(0,0) é um pela convenção do produto vazio. Se k é maior que n não existe k-subconjunto de um n-conjunto, então esta calculadora rejeita o par em vez de devolver zero ou um binomial generalizado.

A implementação nunca amostra, nunca depende do relógio e nunca arredonda: avalia o produto reduzido de (n menos k mais um) até n, dividido passo a passo de um até k, com aritmética BigInt exata para que coeficientes grandes permaneçam inteiros precisos em vez de estourar a mantissa de um ponto flutuante.

Usos em sala, amostragem e competições

Professores de estatística usam combinações sem repetição ao apresentar amostragem sem reposição: o número de comitês distintos de k pessoas de uma turma de n, o número de mãos de k cartas de um baralho de 52, ou o número de formas de retirar k unidades defeituosas de um lote de n em um esquema hipergeométrico. Esses problemas compartilham o mesmo inteiro C(n,k); esta página é escrita para quem busca essa frase de forma explícita, inclusive aprendizes que acabaram de ouvir para não confundir com combinações que permitem repetição.

Geradores de prova podem fixar o caminho de sucesso com n igual a dez e k igual a três, que produz cento e vinte, e o caminho de rejeição com qualquer k que exceda n, que deve falhar em vez de devolver zero. Programadores de competição e sandboxes de entrevista precisam de um oráculo exato para problemas de contagem de combinações sem reimplementar aritmética de multiprecisão em cada harness de linguagem.

Landings irmãos podem tratar permutações, combinações com repetição ou uma calculadora nCr genérica; este landing é especificamente o enunciado sem repetição. Combine a contagem com o seu próprio código de listagem se precisar dos subconjuntos reais; esta capacidade devolve somente o inteiro.