Combinação

Em matemática, combinação é uma seleção de itens de um conjunto que tem membros distintos, de modo que a ordem de seleção não importa (ao contrário de permutações). Por exemplo, dado três frutos, diga uma maçã, uma laranja e uma pêra, há três combinações de duas que podem ser extraídas deste conjunto: uma maçã e uma pêra; uma maçã e uma laranja; ou uma pêra e uma laranja. Mais formalmente, um k- Não.combinação de um conjunto S é um subconjunto de k elementos distintos de S. Assim, duas combinações são idênticas se e somente se cada combinação tiver os mesmos membros. (O arranjo dos membros em cada conjunto não importa.) Se o conjunto tiver n elementos, o número de k-combinações, denotado por $(n,k)}$ ou $Não. C_{k}^{n}}$, é igual ao coeficiente binomial

$${displaystyle {binom {n}{k}}={frac {n(n-1)dotsb (n-k+1)}{k-1)dotsb 1}},}$$

que pode ser escrito usando fatores como ${displaystyle textstyle {frac {n!}{k!(n-k)!}}}$ sempre $Não.$, e que é zero quando $- Sim.$. Esta fórmula pode ser derivada do fato de que cada um k-combinação de um conjunto S de n membros $Não!$ permutações assim $Não. P_{k}^{n}=C_{k}^{n}times K!$ ou $Não. C_{k}^{n}=P_{k}^{n}/k!}$. O conjunto de todos k-combinações de um conjunto S é muitas vezes denotado por ${displaystyle textstyle {binom Não.$.

Uma combinação é uma combinação de n coisas tomadas k de cada vez sem repetição. Para se referir a combinações nas quais a repetição é permitida, os termos k-combinação com repetição, k-multiconjunto ou k-seleção, são freqüentemente usado. Se, no exemplo acima, fosse possível ter duas de qualquer tipo de fruta, haveria mais 3 2 seleções: uma com duas maçãs, uma com duas laranjas e uma com duas peras.

Embora o conjunto de três frutas seja pequeno o suficiente para escrever uma lista completa de combinações, isso se torna impraticável à medida que o tamanho do conjunto aumenta. Por exemplo, uma mão de pôquer pode ser descrita como uma combinação de 5 (k = 5) de cartas de um baralho de 52 cartas (n = 52). As 5 cartas da mão são todas distintas, e a ordem das cartas na mão não importa. Existem 2.598.960 dessas combinações, e a chance de tirar qualquer mão aleatoriamente é 1 / 2.598.960.

Número de k-combinações

Subconjuntos de 3 elementos de um conjunto de 5 elementos

O número de k-combinações de um determinado conjunto S de n elementos é frequentemente denotado em textos combinatórios elementares por $(n,k)}$, ou por uma variação como $Não. C_{k}^{n}}$, $Não. {}_{n}C_{k}}$, $Não. {}^{n}C_{k}}$, $Não. C_{n,k}}$ ou mesmo $Não. C_{n}^{k}}$ (a última forma é padrão em textos franceses, romenos, russos, chineses e polacos). O mesmo número no entanto ocorre em muitos outros contextos matemáticos, onde é denotado por $Não.$ (muitas vezes lido como "n escolher k"); notavelmente ocorre como um coeficiente na fórmula binomial, daí seu nome coeficiente binomial. Um pode definir $Não.$ para todos os números naturais k ao mesmo tempo pela relação

$${displaystyle (1+X)^{n}=sum _{kgeq 0}{binom {n}{k}}X^{k},}$$

da qual fica claro que

$$- Não. Não. Não.$$

e mais,

$$- Sim.$$

para k > n.

Para ver que esses coeficientes contam k-combinações de S, pode-se primeiro considerar uma coleção de n variáveis distintas X _s rotulado pelos elementos s de S e expanda o produto sobre todos os elementos de < i>S:

$${displaystyle prod _{sin S}(1+X_{s});}$$

tem 2ⁿ termos distintos correspondentes a todos os subconjuntos de S, cada subconjunto dando o produto das variáveis correspondentes X_s. Agora definindo todos os X_s iguais à variável não rotulada X, para que o produto se torne (1 + X)ⁿ, o termo para cada k- combinação de S torna-se X^k, de modo que o coeficiente dessa potência no resultado é igual ao número de tais k-combinações.

Os coeficientes binomiais podem ser calculados explicitamente de várias maneiras. Para obter todos eles para as expansões até (1 + X)ⁿ, pode-se usar (além dos casos básicos já fornecidos) a relação de recursão

$$- Sim. {n-1}{k-1}}+{binom {n-1}{k}},}$$

para 0 < k < n, que segue de (1 + X)ⁿ = (1 + X)^{n − 1}(1 + X); isso leva à construção do triângulo de Pascal.

Para determinar um coeficiente binomial individual, é mais prático usar a fórmula

$${displaystyle {binom {n}{k}}={frac {n(n-1)(n-2)cdots (n-k+1)}{k!}}}}$$

O numerador dá o número de k-permutações de n, ou seja, de sequências de k elementos distintos de S, enquanto o denominador dá o número de tais k-permutações que dão a mesma k-combinação quando a ordem é ignorada.

Quando k excede n/2, a fórmula acima contém fatores comuns ao numerador e ao denominador, e cancelá-los fornece a relação

$$- Sim. Não.$$

para 0 ≤ k ≤ n. Isso expressa uma simetria que é evidente a partir da fórmula binomial, e também pode ser entendida em termos de k-combinações tomando o complemento de tal combinação, que é um (n − k)-combinação.

Finalmente existe uma fórmula que exibe esta simetria diretamente, e tem o mérito de ser fácil de lembrar:

$${displaystyle {binom {n}{k}}={frac Não!$$

onde n! denota o fatorial de n. É obtido da fórmula anterior multiplicando o denominador e o numerador por (n − k)!, então certamente é computacionalmente menos eficiente do que essa fórmula.

A última fórmula pode ser entendida diretamente, considerando o n! permutações de todos os elementos de S. Cada uma dessas permutações fornece uma k-combinação selecionando seus primeiros k elementos. Existem muitas seleções duplicadas: qualquer permutação combinada dos primeiros elementos k entre si e dos elementos finais (n − k) entre um ao outro produz a mesma combinação; isso explica a divisão na fórmula.

Das fórmulas acima seguem as relações entre números adjacentes no triângulo de Pascal em todas as três direções:

$$[displaystyle {binom {n}{k}}={begin{cases}{binom Não. {n-k+1}{k}}&quad Não. }}k>0\{binom Não. {n}{n-k}}&quad Não. 0end{cases}}.}$$

Juntamente com os casos básicos $Não é verdade. Não.$, estes permitem calcular sucessivamente todos os números de combinações do mesmo conjunto (uma linha no triângulo de Pascal), de k-combinações de conjuntos de tamanhos crescentes e de combinações com um complemento de tamanho fixo n - Sim. k.

Exemplo de combinações de contagem

Como um exemplo específico, pode-se calcular o número de mãos de cinco cartas possíveis de um baralho padrão de cinquenta e duas cartas como:

$${displaystyle {52 choose 5}={frac {52times 51times 50times 49times 48}{5times 4times 3times 2times 1}}={frac {311{,}875{,}200}{120}}=2{,}598{,}960.}$$

Alternativamente, pode-se usar a fórmula em termos de fatoriais e cancelar os fatores no numerador contra partes dos fatores no denominador, após o que apenas a multiplicação dos fatores restantes é necessária:

$$,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, {4}})}{{cancel {5}}times {cancel {4}}horas {3}}horas {2}}\[5pt]&={26times 17times 10times 49times 12}\[5pt]&=2{,}598{,}960.end{alignedat}}}$$

Outra computação alternativa, equivalente à primeira, é baseada na escrita

$${displaystyle {n choose k}={frac {(n-0)}{1}}times {frac {(n-1)}{2}}times {frac {(n-2)}{3}}times cdots times {frac {(n-(k-1))}{k}},}$$

que dá

$${displaystyle {52 choose 5}={frac {52}{1}}times {frac {51}{2}}times {frac {50}{3}}times {frac {49}{4}}times {frac {48}{5}}=2{,}598{,}960.}$$

Quando avaliado na seguinte ordem, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, pode ser calculado usando apenas aritmética inteira. A razão é que quando cada divisão ocorre, o resultado intermediário que é produzido é em si um coeficiente binomial, de modo que nunca ocorre nenhum resto.

Usar a fórmula simétrica em termos de fatoriais sem realizar simplificações fornece um cálculo bastante extenso:

$$[excluída]{52 coose 5}&={frac {n!}{k!(n-k)!}}={frac {52!}{5!(52-5)!}}={frac {52!}{5!47!}}[6pt]&={tfrac {80,658,175,170,943,878,571,660,636, 258,623,241.511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\[6pt]&=2{,}598{,}960.$$

Enumerando k-combinações

Um pode enumerar tudo k-combinações de um determinado conjunto S de n elementos em alguma ordem fixa, que estabelece uma bijeção de um intervalo de $Não.$ inteiros com o conjunto daqueles k- Combinações. Assumindo S é ordenado, por exemplo S 1, 2,... n }, há duas possibilidades naturais para ordenar sua k-combinações: comparando primeiro os seus pequenos elementos (como nas ilustrações acima) ou comparando primeiro os seus maiores elementos. A última opção tem a vantagem de adicionar um novo elemento maior a S não vai mudar a parte inicial da enumeração, mas apenas adicionar o novo k-combinações do conjunto maior após os anteriores. Repetindo este processo, a enumeração pode ser estendida indefinidamente com k-combinações de conjuntos cada vez maiores. Se além disso os intervalos dos inteiros forem tomados para começar em 0, então o k-combinação em um determinado lugar Eu... na enumeração pode ser computado facilmente de Eu..., e a bijeção assim obtida é conhecida como sistema de números combinatórios. Também é conhecido como "rank" / "ranking" e "unranking" em matemática computacional.

Existem muitas maneiras de enumerar k combinações. Uma maneira é visitar todos os números binários menores que 2ⁿ. Escolha os números com k bits diferentes de zero, embora isso seja muito ineficiente mesmo para n pequenos (por exemplo, n = 20 exigiria visitar cerca de um milhão de números enquanto o número máximo de k combinações permitidas é de cerca de 186 mil para k = 10). As posições desses 1 bits em tal número é uma combinação k específica do conjunto { 1,..., n }. Outra maneira simples e rápida é rastrear os números de índice k dos elementos selecionados, começando com {0.. k−1} (baseado em zero) ou {1.. k} (baseado em um) como a primeira combinação k permitida e, em seguida, movendo-se repetidamente para a próxima combinação k permitida, incrementando a última número de índice se for menor que n-1 (baseado em zero) ou n (baseado em um) ou o último número de índice x que é menor que o número do índice seguinte menos um se tal índice existir e redefinir os números do índice após x para {x+1, x +2,...}.

Número de combinações com repetição

A k- Não.combinação com repetiçõesou k- Não.multicombinaçãoou multisubconjunto de tamanho k de um conjunto S de tamanho n é dado por um conjunto de k não necessariamente elementos distintos de S, quando a ordem não é tomada em consideração: duas sequências definem o mesmo multiconjunto se um pode ser obtido a partir do outro permutando os termos. Em outras palavras, é uma amostra de k elementos de um conjunto de n elementos que permitem duplicatas (ou seja, com substituição) mas desconsiderando diferentes ordenamentos (por exemplo, {2,1,2} = {1,2,2}). Associe um índice a cada elemento S e pensar nos elementos de S como tipos de de objetos, então podemos deixar $Não. x_{i}}$ denota o número de elementos do tipo Eu... em um multisubset. O número de multisubsets de tamanho k é então o número de inteiros nonnegativos (so permitindo zero) soluções da equação Diophantine:

$$Não. x_{1}+x_{2}+ldots +x_{n}=k.}$$

Se S tiver n elementos, o número desses k-multisubconjuntos é denotado por

$${displaystyle left(!! {n}{k}}!!right)}$$

uma notação análoga ao coeficiente binomial que conta k-subconjuntos. Esta expressão, n escolha múltipla k, também pode ser dada em termos de coeficientes binomiais:

$${displaystyle left(!! {n}{k}}!!right)={binom {n+k-1}{k}}.}$$

Essa relação pode ser facilmente provada usando uma representação conhecida como estrelas e barras.

Prova

Uma solução da equação Diofantina acima pode ser representada por $Não. x_{1}}$ estrelas, um separador (a bar), então ${displaystyle x_{2}}$ mais estrelas, outro separador, e assim por diante. O número total de estrelas nesta representação é k e o número de barras é n - 1 (desde que uma separação em n peças precisa de separadores n-1). Assim, uma string de k + n - 1 (ou n + k - 1) símbolos (estrelas e barras) corresponde a uma solução se houver k estrelas na corda. Qualquer solução pode ser representada pela escolha k fora de k + n - 1 posições para colocar estrelas e preencher as posições restantes com barras. Por exemplo, a solução $Não. x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5}$ da equação $Não. x_{1}+x_{2}+x_{3}+x_{4}=10}$ (n = 4 k = 10) pode ser representado por

$${displaystyle bigstar bigstar bigstar |bigstar bigstar |bigstar bigstar bigstar bigstar bigstar bigstar. ?$$

O número de tais cordas é o número de maneiras de colocar 10 estrelas em 13 posições, $- Sim. {13}{10}}={binom {13}{3}}=286,}$ que é o número de 10-multisubsets de um conjunto com 4 elementos.

Bijeção entre 3 subconjuntos de um 7-set (esquerda) e 3 multisets com elementos de um 5-set (direita).
Isso ilustra que $- Sim. {7}{3}}=left(!!{binom {5}{3}}!right)}$.

Tal como acontece com coeficientes binomiais, existem várias relações entre essas expressões multiescolha. Por exemplo, ${displaystyle ngeq 1,kgeq 0$,

$${displaystyle left(!! {n}{k}}!right)=left(!!{binom {k+1}{n-1}}!!right).}$$

Exemplo de contagem de multisubconjuntos

Por exemplo, se você tiver quatro tipos de donuts (n = 4) em um menu para escolher e quiser três donuts (k = 3), o número de maneiras de escolher os donuts com repetição pode ser calculado como

$${displaystyle left(!! {4}{3}}!!right)={binom {4+3-1}{3}}=******************************************************************************************************************************************************************************************************************************************************* {6}{3}}={frac {6times 5times 4}{3times 2times 1}}=20.}$$

Este resultado pode ser verificado listando todos os 3-multisubsets do conjunto S = {1,2,3,4}. Isso é exibido na tabela a seguir. A segunda coluna lista os donuts que você realmente escolheu, a terceira coluna mostra as soluções de inteiros nonnegative $Não. [x_{1},x_{2},x_{3},x_{4}]}$ da equação $Não. x_{1}+x_{2}+x_{3}+x_{4}=3}$ e a última coluna dá as estrelas e barras representação das soluções.

Não.	3-multiset	Solução Eq.	Estrelas e bares
1	{1,1}	[3,0,0,0]	${displaystyle bigstar bigstar bigstar ||||}$
2	{1,2}	[2,1,0,0]	${displaystyle bigstar bigstar |bigstar ||}$
3	{1,3}	[2,0,1,0]	${displaystyle bigstar bigstar |bigstar |}$
4	{1,1,4}	[2,0,0,1]	${displaystyle bigstar bigstar |||bigstar }$
5	{1,2,2}	[1,2,0,0]	${displaystyle bigstar |bigstar bigstar ||=}$
6	{1,2,3}	[1,1,0]	${displaystyle bigstar |bigstar |bigstar |}$
7	{1,2,4}	[1,1,1]	${displaystyle bigstar |bigstar ||bigstar }$
8	{1,3,3}	[1,0,2,0]	${displaystyle bigstar |bigstar bigstar |}$
9	{1,3,4}	[1,0,1]	${displaystyle bigstar |bigstar |bigstar |bigstar }$
10.	(1,4,4)	[1,0,0,2]	${displaystyle bigstar |||bigstar bigstar }$
11	(2,2,2)	[0,3,0,0]	${displaystyle |bigstar bigstar bigstar ||}$
12	(2,2,3)	[0,2,1,0]	${displaystyle |bigstar bigstar |bigstar |}$
13	(2,2,4)	[0,2,0,1]	${displaystyle |bigstar bigstar |bigstar }$
14	(2,3,3)	[0,1,2,0]	$|bigstar |bigstar bigstar |}$
15	(2,3,4)	[0,1,1]	$|bigstar |bigstar |bigstar }$
16.	{2,4}	[0,1,2]	$|bigstar |bigstar }$
17.	3,3,3	[0,0,3,0]	$|bigstar bigstar bigstar bigstar |}$
18.	{3,3,4}	[0,0,2,1]	$|bigstar bigstar |bigstar }$
19	{3,4,4}	[0,0,1,2]	$|bigstar |bigstar |bigstar }$
20.	{4,4}	[0,0,0,3]	$|bigstar bigstar bigstar bigstar }$

Número de combinações k para todo k

O número de k-combinações para todos k é o número de subconjuntos de um conjunto de n elementos. Existem várias maneiras de ver que este número é 2ⁿ. Em termos de combinações, $_{0leq (k}leq) Não. {n}{k}}=2^{n}}$, que é a soma da na linha (contando de 0) dos coeficientes binomiais no triângulo de Pascal. Estas combinações (subconjuntos) são enumeradas pelos 1 dígitos do conjunto de números de base 2 que contam de 0 a 2ⁿ− 1, onde cada posição de dígito é um item do conjunto de n.

Dadas 3 cartas numeradas de 1 a 3, existem 8 combinações distintas (subconjuntos), incluindo o conjunto vazio:

$$Não. |{};{1};{2};{1,2};{3};{2,3};{1,2,3}}|=2^{3}=8}$$

Representando esses subconjuntos (na mesma ordem) como numerais de base 2:

• 0 – 000
• 1 – 001
• 2 – 010
• 3 – 011
• 4 – 100
• 5 – 101
• 6 – 110
• 7 – 111

Probabilidade: amostragem de uma combinação aleatória

Existem vários algoritmos para escolher uma combinação aleatória de um determinado conjunto ou lista. A amostragem de rejeção é extremamente lenta para grandes tamanhos de amostra. Uma maneira de selecionar um k-combinação eficiente de uma população de tamanho n é para iterar através de cada elemento da população, e em cada passo escolha esse elemento com uma probabilidade de mudança dinâmica de $- Sim. (k-#{text{samples) escolhido}}}{n-#{text{samples visitou}}}}}}}}}$ (ver amostragem do reservatório). Outro é escolher um inteiro não negativo aleatório menos do que ${displaystyle textstyle {binom Não.$ e convertê-lo em uma combinação usando o sistema de números combinatórios.

Número de maneiras de colocar objetos em caixas

Uma combinação também pode ser considerada como uma seleção de dois conjuntos de itens: aqueles que vão para a lixeira escolhida e aqueles que vão para a lixeira não escolhida. Isso pode ser generalizado para qualquer número de compartimentos com a restrição de que cada item deve ir para exatamente um compartimento. O número de maneiras de colocar objetos em caixas é dado pelo coeficiente multinomial

$${displaystyle {n choose k_{1},k_{2},ldotsk_{m}}={frac {n!}{k_{1}!,k_{2}!cdots k_{m}!}},}$$

Onde? n é o número de itens, m é o número de caixas, e $Não. k_{i}}$ é o número de itens que entram em bin Eu....

Uma maneira de ver por que essa equação é para primeiro número os objetos arbitrariamente de 1 para n e colocar os objetos com números ${displaystyle 1,2,ldotsk_{1}}$ na primeira caixa em ordem, os objetos com números $Não. k_{1}+1,k_{1}+2,ldotsk_{2}}$ para a segunda lixeira em ordem, e assim por diante. Há $Não!$ numeração distinta, mas muitos deles são equivalentes, porque apenas o conjunto de itens em um lixo importa, não sua ordem nele. Cada permutação combinada de conteúdo de cada bins produz uma maneira equivalente de colocar itens em caixas. Como resultado, cada classe de equivalência consiste em $Não. k_{1}!,k_{2}!cdots k_{m}!$ numeração distinta, e o número de classes de equivalência é ${displaystyle textstyle {frac {n!}{k_{1}!,k_{2}!cdots k_{m}!}}$.

O coeficiente binomial é o caso especial onde k os itens vão para o bin escolhido e os restantes $Não. Não.$ itens vão para o bin unchosen:

$${displaystyle {binom {n}{k}}={n} choose k,n-k}={frac {n!}{k!(n-k)!}}.}$$