Kombination

En kombination (fra latin combinatio 'resumé' ) eller uordnet prøve er i kombinatorik et udvalg af objekter fra et givet basissæt, som (i modsætning til permutation ) ikke behøver at indeholde alle objekter i basissættet, og hvori (i kontrast til til permutation og variation ) ordren tages ikke i betragtning. Hvis objekter kan vælges flere gange, taler man om en kombination med gentagelse . Hvis hvert objekt derimod kun må vises en gang, taler man om en kombination uden gentagelse . Bestemmelsen af ​​antallet af mulige kombinationer er en standardopgave at tælle kombinatorik .

Definition af termer

En kombination eller uordnet prøve er et udvalg af objekter fra et sæt objekter, for hvilken rækkefølgen ikke er vigtig. Hvis ordren alligevel skal spille en rolle, taler man om en variation i stedet for en kombination. Afvigende fra dette er kombinationer og variationer undertiden opsummeret i litteraturen, og en variation kaldes derefter "kombination med hensyn til sekvensen".${\ displaystyle k}$${\ displaystyle n}$

I en kombination med gentagelse kan objekter vælges flere gange, mens hvert objekt kun vises en gang i en kombination uden gentagelse. I en urnemodel svarer en kombination med gentagelse til en tegning af kuglerne med udskiftning, og en kombination uden gentagelse svarer til en uafgjort uden udskiftning.

Kombination uden gentagelse

Alle 10 kombinationer uden at gentage tre ud af fem objekter

nummer

Ikke-gentagne udvælgelsesproblemer kan undersøges på to måder. I det klassiske tilfælde starter man ud fra en variation uden gentagelse, for hvilken den fra de valgte elementer er muligheder. Nu kan de valgte elementer imidlertid selv arrangeres på forskellige måder. Hvis disse forskellige arrangementer alle er irrelevante, dvs. altid skal tælle som det samme udvalg af elementer, er vi nødt til at opdele resultatet en gang til og kun få det ${\ 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}}}$

Muligheder, hvis antal også er kendt som den binomiale koefficient .

En anden tilgang, der især anvendes til evaluering af Bernoulli-eksperimenter, betragter kombinationen uden gentagelse som et arrangementsproblem. Antallet af mulige valg kan derefter bestemmes ved at bestemme antallet af gensidigt skelne arrangementer af valgte og ikke-valgte objekter, hvorved disse selv ikke længere skal kunne skelnes fra hinanden, dvs. hele det oprindelige sæt er kun "valgt" i de to objektklasser (f.eks. sort kugle med hvidt nummer) og "ikke valgt" (f.eks. hvid kugle med sort nummer). Hvis man nu undersøger, hvor mange forskellige arrangementer af disse sorte og hvide kugler der er, hvor kun deres farve skal spille en rolle, resulterer ovenstående formel i henhold til formlen for antallet af permutationer af elementer, som hver ikke kan differentieres efter klasse . Uanset om det er antallet af valgte objekter og antallet af ikke-valgte objekter eller omvendt, er det irrelevant for resultatet; hvilket af de to undersæt i det oprindelige sæt, der er det, der har interesse, har ingen indflydelse på antallet af mulige divisioner. ${\ displaystyle k}$${\ displaystyle nk}$

Mængdevisning

Beløbet

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

er "sæt af alle kombinationer uden gentagelse af objekter til klassen " og har antallet af elementer, der er angivet ovenfor. En alternativ repræsentation af denne skare er ${\ 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 \}}}$.

Eksempler

lotto

Hvis du vil vælge fra objekter uden gentagelse og uden at overveje rækkefølgen, som det er tilfældet, for eksempel med tegningen af lotterinumrene , er der ${\ displaystyle 49}$${\ displaystyle 6}$

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

mulige valg. I tilfælde af lotteri betyder ordren ikke noget, for eksempel om først den ene og derefter den ene eller først den ene og derefter den ene er trukket, er irrelevant for vindende numre og bestemmelsen af ​​lotterivinderen. Antallet af mulige løsninger beregnes ud fra antallet af bolde, der kan trækkes først og derefter . Da ordren ikke betyder noget, skal det dog tages i betragtning, at produktet inkluderer løsninger af samme værdi. Med tre tegn trukket er antallet af muligheder , men fordi rækkefølgen af ​​tegningen af ​​kuglerne ikke betyder noget, skal produktet divideres med antallet af mulige tegningsordrer . ${\ displaystyle 9}$${\ displaystyle 17}$${\ displaystyle 17}$${\ displaystyle 9}$${\ displaystyle 49}$${\ displaystyle 48}$${\ displaystyle 49 \ cdot 48}$${\ displaystyle 2 = 1 \ cdot 2 = 2!}$${\ displaystyle 49 \ gange 48 \ gange 47}$${\ displaystyle 6 = 1 \ gange 2 \ gange 3 = 3!}$

Antal måder

Vægmaleri med flere skjulte bogstaver "Deo gracias"

Den Deo Gracias fresco i Wismar Helligåndskirken viser bogstavet "D" i midten og et "S" nederst til højre. Hvis du kun tager skridt til højre eller nedad, er resultatet altid teksten "DEOGRACIAS". Du tager i alt ni trin, hvoraf fem skal du tage et skridt til højre og fire gange et skridt ned. Derfor er der

${\ displaystyle {9 \ vælg 5} = {\ frac {9!} {5! \, 4!}} = 126}$

Muligheder. Men du kan også gå til de andre hjørner med det samme resultat: fem gange til højre og fire gange op eller til venstre og ned eller til venstre og op. Samlet set resulterer dette i muligheder i dette eksempel . Denne opgave kaldes normalt Manhattan-problemet , opkaldt efter New York-bydelen med sit regelmæssige gadelayout.${\ displaystyle 126 \ cdot 4 = 504}$

Irene Schramm-Biermann Manhattan solnedgang

Billedet til højre vedrører også Manhattan-problemet. Dette handler om rækkefølgen af ​​bogstaver, der udgør ordet "MANHATTANSUNSET". Start er M øverst til venstre, målet er T nederst til højre. Du har brug for 7 trin til højre og 7 trin ned, så der med n = 7 og k = 7 er der nøjagtigt 3432 forskellige måder at læse MANHATTANSUNSET på.

Kombination med gentagelse

Alle 35 kombinationer med gentagelse af tre ud af fem objekter

nummer

Skal elementer vælges fra et sæt af elementer , hvorved deres rækkefølge stadig skal være irrelevant, men de kan nu også gentages, såsom B. er mulig, når du trækker med udskiftning, følgende formel resulterer i antallet af muligheder (se multisæt ): ${\ displaystyle n}$${\ displaystyle k}$

${\ displaystyle {\ frac {(n + k-1)!} {(n-1)! \, k!}} = {n + k-1 \ vælg k} = {n + k-1 \ vælg n -1} = \ venstre (\! \! {N \ vælg k} \! \! \ Højre)}$

Dette kan ses, når hvert resultat af udvalgte elementer fra mulige elementer er repræsenteret af en sekvens af symboler, hvor symboler (“N”) repræsenterer elementerne i det valgte sæt og symboler (“K”), der repræsenterer de valgte elementer. Sekvensen begynder altid med et N-symbol; antallet af K-symboler før det andet N-symbol svarer til frekvensen, hvormed det første af elementerne blev trukket, antallet af K-symboler mellem det andet og tredje N-symbol svarer til det andet af elementerne, og så videre "N" alle symboler kan kombineres frit, antallet af kombinationer og dermed antallet af mulige bevægelser svarer til den givne formel. ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle n + k}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle n}$

For eksempel, når du vælger 3 ud af 5 elementer (“1”, “2”, “3”, “4”, “5”) med erstatning, svarer resultatet “1, 3, 3” til symbolsekvensen “NKNNKKNN ”, Resultatet“ 5, 5, 5 ”i serien“ NNNNNKKK ”. Der er mulige kombinationer. ${\ displaystyle {n + k-1 \ vælg k} = {7 \ vælg 3} = 35}$

Mængdevisning

Beløbet

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

er "sæt af alle kombinationer med gentagelse af ting til klassen " og har antallet af elementer angivet ovenfor. Her angiver antallet af forekomster af det tredje element i prøven. En alternativ repræsentation af denne skare er ${\ 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 \}}}$.

Eksempler

Binding mellem kombinationer med gentagelse af tre ud af fem objekter (højre) og kombinationer uden gentagelse af tre ud af syv objekter (venstre)

Gummy Bear Oracle

En anvendelse af dette er det såkaldte gummy bear oracle , hvor man vælger bjørne fra en pose gummy bears i forskellige farver. Så der er ${\ displaystyle k = 5}$${\ displaystyle n = 5}$

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

forskellige kombinationer. Der er fem kombinationer, hvor alle bjørne har samme farve, kombinationer med to forskellige farver, med tre farver, med fire farver og en med alle fem farver. Hvis sekvensen var vigtig, når man trak, ville man have at gøre med en "variation med gentagelse", det vil sige med mulighederne. Når man bliver spurgt om antallet af muligheder for at vælge fire penne fra et lager af penne i seks forskellige farver, kommer man til det samme nummer ( mastermind uden at overveje arrangementet). På den anden side er der muligheder med den “rigtige” mastermind (under hensyntagen til arrangementet) . ${\ displaystyle 40}$${\ displaystyle 60}$${\ displaystyle 20}$${\ displaystyle 5 ^ {5} = 3125}$${\ displaystyle 126}$${\ displaystyle 6 ^ {4} = 1296}$

urne

En bold trækkes tre gange fra en urne med fem nummererede bolde og sættes tilbage hver gang. Så du kan altid vælge mellem fem bolde til alle tre uafgjort. Hvis du ikke tager hensyn til rækkefølgen af ​​de trukkede numre, er der ${\ displaystyle (n = 5)}$${\ displaystyle (k = 3)}$

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

forskellige kombinationer. Disse kombinationer med gentagelse af fem ting for klasse tre, dvs. tre-element multisæt med elementer fra det oprindelige sæt , svarer nøjagtigt til kombinationerne uden gentagelse af syv ting for klasse tre, dvs. antallet af tre-element undergrupper på i alt syv -elementets indledende sæt. (Eksistensen af ​​en sammenhæng kan bruges til at bevise formlen for antallet af kombinationer med erstatning.) ${\ displaystyle 35}$${\ displaystyle \ {1,2,3,4,5 \}}$${\ displaystyle 35}$

terning

Brug af flere identiske objekter, såsom terninger med et til seks øjne , er det samme som at udskifte dem . Hvor mange forskellige kast er mulige med tre terninger? I princippet er forskellige kast mulige, hvis man kaster den ene dør efter den anden og overholder rækkefølgen. Hvis du derimod kaster alle tre terninger på samme tid, kan rækkefølgen ikke længere defineres meningsfuldt. Da fx kastet af alle tre terninger på samme tid ikke kan skelnes fra eller ikke længere, er der kun ${\ displaystyle 6 ^ {3} = 216}$${\ displaystyle 1-1-2}$${\ displaystyle 1-2-1}$${\ displaystyle 2-1-1}$

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

forskellige (skelne) kuld. For ikke at forveksle med summen af ​​øjnene, kan dette kun tage forskellige værdier (fra til ). ${\ displaystyle 16}$${\ displaystyle 3}$${\ displaystyle 18}$

litteratur

• Martin Aigner : Diskret matematik . Vieweg, 2006, ISBN 3-8348-9039-1 . 
• Konrad Jacobs , Dieter Jungnickel : Introduktion til kombinatorik . de Gruyter, 2003, ISBN 3-11-016727-1 . 
• Joachim Hartung , Bärbel Elpelt, Karl-Heinz Klösener: Statistik: Undervisning og vejledning i anvendt statistik . Oldenbourg, 2005, ISBN 3-486-57890-1 . 

Weblinks

Wiktionary: Kombination  - forklaringer på betydninger, ordets oprindelse, synonymer, oversættelser

• VM Mikheev: Kombination . I: Michiel Hazewinkel (red.): Encyclopedia of Mathematics . Springer-Verlag og EMS Press, Berlin 2002, ISBN 978-1-55608-010-4 (engelsk, online ). 
• kfgauss70: Kombinationer med gentagne elementer . I: PlanetMath . (Engelsk)
• Eric W. Weisstein : Kombination . På: MathWorld (engelsk).

Individuelle beviser

1. ↑ Hartung, Elpelt, Klösener: Statistik: undervisning og manual for anvendt statistik . S. 96 . 
2. ^ Bronstein, Semendjajew: Taschenbuch der Mathematik . Harri Deutsch, 2008, ISBN 3-8171-2007-9 , pp. 810-811 . 
3. ^ Manhattan-problem