Variasjon (kombinatorikk)
En variasjon (fra latin variatio "endring" ) eller ordnet prøve er i kombinatorikk et utvalg av objekter fra et sett i en bestemt rekkefølge . Hvis objekter kan velges flere ganger, snakker man om en variant med repetisjon , hvert objekt kan bare vises en gang, av en variant uten repetisjon . Bestemmelsen av antall mulige variasjoner er en standard oppgave for å telle kombinatorikk .
Definisjon av begreper
En variant eller ordnet prøve er et utvalg av objekter fra et sett med objekter, hvor rekkefølgen på utvalget spiller en rolle. Hvis alle tilgjengelige objekter er valgt, gjelder følgende , så i stedet for en variant av en permutasjon spiller ikke sekvensen en rolle i valget av objektene til en kombinasjon .
Når det gjelder en variant med repetisjon, kan objekter velges mer enn en gang, mens i tilfelle en variant uten repetisjon kan hvert objekt bare vises en gang. I en urnemodell tilsvarer en variasjon med repetisjon en tegning av kulene med erstatning og en variasjon uten repetisjon tilsvarer en uavgjort uten erstatning.
Avvik fra dette, er variasjoner og kombinasjoner noen ganger oppsummert i litteraturen, og en variant kalles da "kombinasjon med hensyn til sekvensen". Spesielt i engelsk bruk kombineres variasjoner og permutasjoner og variasjoner da "k-permutasjoner" ( k-permutasjoner kalt).
Variasjon uten repetisjon
Antall
I en variant uten repetisjon er fra (med gjenstander ) som skal plasseres ledige seter, har hvert objekt bare lov til å innta et sted på det meste. Det er mulige objekter for første gang, objekter for andreplassen og så videre opp til -th-stedet som det fremdeles er mulige objekter for. Så generelt er det
mulige ordninger. Notasjonene og , som kalles fallende fakta , eksisterer også for dette nummeret . Med vilje fakultet for utpekt.
Mengdevisning
den mengden
er "settet med alle varianter uten gjentakelse av objekter for klassen " og har antall elementer spesifisert ovenfor.
Eksempler
- Hvis en urn med fem forskjellige baller trekkes tre ganger uten å erstatte, er forskjellige valg mulig: med den første tegningen fem alternativer, så bare fire og for den tredje tegningen bare tre alternativer.
- Hvis alle fem ballene skal velges, er det et tilsvarende antall totale muligheter, dvs. antall permutasjoner av alle fem ballene.
Variasjon med repetisjon
Antall
I tilfelle en variasjon med repetisjon, blir objekter valgt fra objekter i samsvar med sekvensen, hvor objekter også kan velges flere ganger. Følgelig, siden hvert av objektene kan vises på hvert av stedene for utvalget, er det
mulige ordninger.
Mengdevisning
Mengden
er "settet med alle variasjoner med repetisjon av objekter i en klasse ". Det er det foldede kartesiske produktet av settet med seg selv og har antall elementer gitt ovenfor.
Eksempler
- Hvis en urn med fem forskjellige baller trekkes tre ganger med erstatning, er forskjellige valg mulig.
- Med en firesifret PIN - kode eller en kombinasjonslås med fire ringer og ti sifre hver, er det totalt forskjellige variasjoner (0000–9999).
- I digital teknologi består binære tall bare av to sifre og . Med en ordning av slike sifre kan forskjellige variasjoner oppstå tilsvarende . For eksempel koder et firesifret binært tall forskjellige tilstander.
litteratur
- Martin Aigner : Diskret matematikk . Vieweg, 2006, ISBN 3-8348-9039-1 .
- Konrad Jacobs , Dieter Jungnickel : Introduksjon til kombinatorikk . de Gruyter, 2003, ISBN 3-11-016727-1 .
- Joachim Hartung , Bärbel Elpelt, Karl-Heinz Klösener: Statistikk: Undervisning og håndbok for anvendt statistikk . Oldenbourg, 2005, ISBN 3-486-57890-1 .
Individuelle bevis
- ^ A b Bronstein, Semendjajew: Taschenbuch der Mathematik . Harri Deutsch, 2008, ISBN 3-8171-2007-9 , pp. 810-811 .
- ↑ Hartung, Elpelt, Klösener: Statistikk: undervisning og håndbok for anvendt statistikk . S. 96 .
- ↑ Aigner: Diskret matematikk . S. 7 .