Combinação

Uma combinação (do latim combinatio 'resumo' ) ou amostra desordenada é em combinatória uma seleção de objetos de um determinado conjunto básico, que (em contraste com a permutação ) não tem que conter todos os objetos do conjunto básico e em que (em contraste para permutação e variação ) a ordem não é levada em consideração. Se os objetos podem ser selecionados várias vezes, fala-se de combinação com repetição . Se, por outro lado, cada objeto só pode aparecer uma vez, fala-se de uma combinação sem repetição . A determinação do número de combinações possíveis é uma tarefa padrão da contagem combinatória .

Definição de termos

Uma combinação ou amostra desordenada é uma seleção de objetos de um conjunto de objetos para os quais a ordem de seleção não importa. Mesmo que a ordem tenha um papel, fala-se de variação em vez de combinação. Diferentemente disso, as combinações e variações às vezes são resumidas na literatura e uma variação é então chamada de “combinação com consideração da sequência”.${\ displaystyle k}$${\ displaystyle n}$

Em uma combinação com repetição, os objetos podem ser selecionados várias vezes, enquanto em uma combinação sem repetição, cada objeto pode aparecer apenas uma vez. Em um modelo de urna , uma combinação com repetição corresponde a um sorteio das bolas com reposição e uma combinação sem repetição corresponde a um sorteio sem reposição.

Combinação sem repetição

Todas as 10 combinações sem repetir três de cinco objetos

número

Problemas de seleção não repetitivos podem ser investigados de duas maneiras. No caso clássico, parte-se de uma variação sem repetição para a qual a partir de ser selecionados elementos são opções. Agora, no entanto, os próprios elementos selecionados podem ser organizados de maneiras diferentes. Se esses arranjos diferentes forem todos irrelevantes, ou seja, devem sempre contar como a mesma seleção de elementos, temos que dividir o resultado mais uma vez e apenas obtê-lo ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle {\ tfrac {n!} {(nk)!}}}$${\ displaystyle k}$${\ displaystyle k!}$${\ displaystyle k!}$

${\ displaystyle {\ frac {n!} {(nk)! \, k!}} = {\ frac {n (n-1) (n-2) \ ldots (n-k + 1)} {k!}} = {\ binom {n} {nk}} = {\ binom {n} {k}}}$

Possibilidades, cujo número também é conhecido como coeficiente binomial .

Uma segunda abordagem, que é usada em particular para a avaliação dos experimentos de Bernoulli, considera a combinação sem repetição como um problema de arranjo. O número de seleções possíveis pode então ser determinado determinando o número de arranjos mutuamente distinguíveis de objetos selecionados e não selecionados, pelo que estes próprios não devem mais ser distinguíveis um do outro, ou seja, todo o conjunto inicial é apenas "selecionado" nas duas classes de objeto (por exemplo, bola preta com número branco) e "não selecionado" (por exemplo, bola branca com número preto). Se alguém investigar agora quantos arranjos diferentes dessas bolas pretas e brancas existem, em que apenas sua cor deve desempenhar um papel, a fórmula acima resulta de acordo com a fórmula para o número de permutações de elementos, cada um dos quais não pode ser diferenciado por classe . Se é o número de objetos selecionados e o número de objetos não selecionados ou vice-versa, é irrelevante para o resultado; qual dos dois subconjuntos do conjunto inicial é o de interesse não tem influência no número de divisões possíveis. ${\ displaystyle k}$${\ displaystyle nk}$

Exibição de quantidade

Quantidade

${\ displaystyle {\ bigl \ {} (x_ {1}, x_ {2}, \ ldots, x_ {n}) \ mid x_ {i} \ in \ {0,1 \}, x_ {1} + \ ldots + x_ {n} = k {\ bigr \}}}$

é o "conjunto de todas as combinações sem repetição de objetos para a classe " e possui o número de elementos especificado acima. Uma representação alternativa desta multidão é ${\ displaystyle n}$${\ displaystyle k}$

${\ displaystyle {\ bigl \ {} (z_ {1}, z_ {2}, \ ldots, z_ {k}) \ mid 1 \ leq z_ {1} <z_ {2} <\ dotsb <z_ {k- 1} <z_ {k} \ leq n {\ bigr \}}}$.

Exemplos

loteria

Se você quiser selecionar objetos sem repetição e sem considerar a ordem, como é o caso, por exemplo, do sorteio dos números da loteria , há ${\ displaystyle 49}$${\ displaystyle 6}$

${\ displaystyle {\ binom {49} {6}} = {\ frac {49!} {6! \, (49-6)!}} = 13.983.816}$

escolhas possíveis. No caso da loteria, a ordem não importa, por exemplo se primeiro aquele e depois aquele ou primeiro aquele e depois aquele é sorteado, é irrelevante para os números vencedores e a determinação do vencedor da loteria. O número de soluções possíveis é calculado a partir do número de bolas que podem ser sorteadas primeiro e depois . Porém, como a ordem não importa, deve-se levar em consideração que o produto inclui soluções de igual valor. Com três números sorteados é o número de possibilidades , mas como a ordem do sorteio das bolas não importa, o produto deve ser dividido pelo número de ordens de sorteio possíveis . ${\ displaystyle 9}$${\ displaystyle 17}$${\ displaystyle 17}$${\ displaystyle 9}$${\ displaystyle 49}$${\ displaystyle 48}$${\ displaystyle 49 \ cdot 48}$${\ displaystyle 2 = 1 \ cdot 2 = 2!}$${\ displaystyle 49 \ times 48 \ times 47}$${\ displaystyle 6 = 1 \ vezes 2 \ vezes 3 = 3!}$

Número de maneiras

Pintura de parede com várias letras ocultas "Deo gracias"

O afresco Deo Gracias na Igreja do Espírito Santo de Wismar mostra a letra "D" no meio e um "S" no canto inferior direito. Se você seguir apenas passos para a direita ou para baixo, o resultado será sempre o texto "DEOGRACIAS". Você dá um total de nove passos, cinco dos quais você tem que dar um passo para a direita e quatro vezes um passo para baixo. Portanto, há

${\ displaystyle {9 \ choose 5} = {\ frac {9!} {5! \, 4!}} = 126}$

Opções Mas você também pode ir para os outros cantos com o mesmo resultado: cinco vezes para a direita e quatro vezes para cima ou para a esquerda e para baixo ou para a esquerda e para cima. No geral, isso resulta em possibilidades neste exemplo . Essa tarefa geralmente é chamada de Problema de Manhattan , em homenagem ao bairro de Nova York com seu traçado regular de ruas.${\ displaystyle 126 \ cdot 4 = 504}$

Irene Schramm-Biermann Pôr do sol em Manhattan

A imagem à direita também se relaciona com o problema de Manhattan. Trata-se da sequência de letras que compõe a palavra "MANHATTANSUNSET". Comece é M no canto superior esquerdo, o objetivo é o T no canto inferior direito. Você precisa de 7 etapas para a direita e 7 etapas para baixo, de modo que com n = 7 ek = 7 haja exatamente 3.432 maneiras diferentes de ler MANHATTANSUNSET.

Combinação com repetição

Todas as 35 combinações com repetição de três de cinco objetos

número

Os elementos devem ser selecionados a partir de um conjunto de elementos , em que sua ordem ainda deve ser irrelevante, mas agora também podem ser repetidos, como B. é possível ao arrastar com substituição, a seguinte fórmula resulta para o número de possibilidades (ver multi-conjunto ): ${\ displaystyle n}$${\ displaystyle k}$

${\ displaystyle {\ frac {(n + k-1)!} {(n-1)! \, k!}} = {n + k-1 \ escolha k} = {n + k-1 \ escolha n -1} = \ left (\! \! {N \ choose k} \! \! \ Right)}$

Isso pode ser visto quando cada resultado de elementos selecionados de elementos possíveis é representado por uma sequência de símbolos, com símbolos (“N”) representando os elementos do conjunto selecionado e símbolos (“K”) representando os elementos selecionados. A sequência sempre começa com um símbolo N; o número de K símbolos antes do segundo N símbolo corresponde à frequência com que o primeiro dos elementos foi desenhado, o número de K símbolos entre o segundo e o terceiro N símbolos corresponde ao segundo dos elementos, e assim por diante "N" todos os símbolos podem ser combinados livremente, o número de combinações e, portanto, o número de movimentos possíveis corresponde à fórmula dada. ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle n + k}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle n}$

Por exemplo, ao selecionar 3 de 5 elementos (“1”, “2”, “3”, “4”, “5”) com substituição, o resultado “1, 3, 3” corresponde à sequência de símbolos “NKNNKKNN ”, O resultado“ 5, 5, 5 ”da série“ NNNNNKKK ”. Existem combinações possíveis. ${\ displaystyle {n + k-1 \ escolher k} = {7 \ escolher 3} = 35}$

Exibição de quantidade

Quantidade

${\ displaystyle {\ bigl \ {} (x_ {1}, x_ {2}, \ ldots, x_ {n}) \ mid x_ {i} \ in \ {0,1, \ ldots, k \}, x_ {1} + \ ldots + x_ {n} = k {\ bigr \}}}$

é o “conjunto de todas as combinações com repetição de coisas para a classe ” e tem o número de elementos dado acima. Aqui denota o número de ocorrências do -ésimo elemento da amostra. Uma representação alternativa desta multidão é ${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle x_ {i}}$${\ displaystyle i}$

${\ displaystyle {\ bigl \ {} (z_ {1}, z_ {2}, \ ldots, z_ {k}) \ mid 1 \ leq z_ {1} \ leq z_ {2} \ leq \ dotsb \ leq z_ {k-1} \ leq z_ {k} \ leq n {\ bigr \}}}$.

Exemplos

Bijeção entre combinações com repetição de três de cinco objetos (direita) e combinações sem repetição de três de sete objetos (esquerda)

Oráculo Gummy Bear

Uma aplicação disso é o chamado oráculo de ursinhos de goma , no qual se seleciona ursos de uma sacola de ursinhos de goma em cores diferentes. Então aí está ${\ displaystyle k = 5}$${\ displaystyle n = 5}$

${\ displaystyle \ left (\! \! {5 \ choose 5} \! \! \ right) = {\ binom {9} {5}} = {\ frac {9!} {5! \, 4!} } = 126}$

combinações diferentes. São cinco combinações em que todos os ursos têm a mesma cor, combinações com duas cores diferentes, com três cores, com quatro cores e uma com todas as cinco cores. Se a sequência fosse importante ao arrastar, estaríamos lidando com uma “variação com repetição”, ou seja, com possibilidades. Quando questionado sobre o número de possibilidades de escolher quatro canetas de um estoque de canetas em seis cores diferentes, chega-se ao mesmo número ( mentor sem considerar o arranjo). Por outro lado, existem possibilidades com o idealizador “certo” (levando em consideração o acordo) . ${\ displaystyle 40}$${\ displaystyle 60}$${\ displaystyle 20}$${\ displaystyle 5 ^ {5} = 3125}$${\ displaystyle 126}$${\ displaystyle 6 ^ {4} = 1296}$

urna

Uma bola é tirada três vezes de uma urna com cinco bolas numeradas e colocada de volta a cada vez. Assim, você sempre pode escolher entre cinco bolas para os três sorteios. Se você não levar em conta a ordem dos números sorteados, há ${\ displaystyle (n = 5)}$${\ displaystyle (k = 3)}$

${\ displaystyle \ left (\! \! {5 \ choose 3} \! \! \ right) = {\ binom {7} {3}} = {\ frac {7!} {4! \, 3!} } = 35}$

combinações diferentes. Essas combinações com repetição de cinco coisas para a classe três, ou seja, multiconjuntos de três elementos com elementos do conjunto inicial , correspondem exatamente às combinações sem repetição de sete coisas para a classe três, ou seja , o número de subconjuntos de três elementos de um total de sete -elemento conjunto inicial. (A existência de uma bijeção pode ser usada para provar a fórmula para o número de combinações com substituição.) ${\ displaystyle 35}$${\ displaystyle \ {1,2,3,4,5 \}}$${\ displaystyle 35}$

cubo

O uso de vários objetos idênticos, como dados com um a seis olhos , é o mesmo que substituir . Quantos lances diferentes são possíveis com três dados? Em princípio, diferentes lançamentos são possíveis se um lançar um dado após o outro e observar a ordem. Se, por outro lado, você joga todos os três dados ao mesmo tempo, a ordem não pode mais ser definida de forma significativa. Desde quando jogando todos os três dados, ao mesmo tempo, por exemplo, o lance não pode mais ser distinguidos a partir ou não, não é apenas ${\ displaystyle 6 ^ {3} = 216}$${\ displaystyle 1-1-2}$${\ displaystyle 1-2-1}$${\ displaystyle 2-1-1}$

${\ displaystyle \ left (\! \! {6 \ choose 3} \! \! \ right) = {\ binom {8} {3}} = {\ frac {8!} {5! \, 3!} } = 56}$

ninhadas diferentes (distinguíveis). Não confundir com a soma dos olhos, só pode assumir valores diferentes (de a ). ${\ displaystyle 16}$${\ displaystyle 3}$${\ displaystyle 18}$

literatura

• Martin Aigner : Discrete Mathematics . Vieweg, 2006, ISBN 3-8348-9039-1 . 
• Konrad Jacobs , Dieter Jungnickel : Introdução à combinatória . de Gruyter, 2003, ISBN 3-11-016727-1 . 
• Joachim Hartung , Bärbel Elpelt, Karl-Heinz Klösener: Estatística: Ensino e manual de estatística aplicada . Oldenbourg, 2005, ISBN 3-486-57890-1 . 

Links da web

Wikcionário: Combinação  - explicações de significados, origens das palavras, sinônimos, traduções

• VM Mikheev: Combinação . In: Michiel Hazewinkel (Ed.): Enciclopédia de Matemática . Springer-Verlag and EMS Press, Berlin 2002, ISBN 978-1-55608-010-4 (inglês, online ). 
• kfgauss70: Combinações com elementos repetidos . In: PlanetMath . (Inglês)
• Eric W. Weisstein : Combinação . In: MathWorld (inglês).

Evidência individual

1. ↑ Hartung, Elpelt, Klösener: Estatística: ensino e manual de estatística aplicada . S. 96 . 
2. ^ Bronstein, Semendjajew: Taschenbuch der Mathematik . Harri Deutsch, 2008, ISBN 3-8171-2007-9 , pp. 810-811 . 
3. ^ Problema de Manhattan