Kombinatorik uden gentagelse forstås som de forskellige sæt, der kan dannes med «n» -elementer, valgt fra x i x. Hvert sæt skal afvige fra det forrige i mindst et af dets elementer (rækkefølgen betyder ikke noget), og disse kan ikke gentages.
Kombinatorik uden gentagelse er almindelig brug i statistik og matematik. Dette passer til mange virkelige livssituationer, og dets anvendelse er ret ligetil.
Tag for eksempel en studerende, der har en eksamen med 4 spørgsmål. Af de 4 spørgsmål skal han vælge tre. Hvor mange forskellige kombinationer kunne den studerende lave? Hvis vi tænker lidt, ville vi se (uden at anvende formlen), at den studerende kunne vælge, hvordan de 3 spørgsmål skulle besvares på fire forskellige måder.
- Sæt / mulighed 1: Besvar spørgsmål 1,2,3.
- Sæt / mulighed 2: Besvar spørgsmål 1,2,4.
- Sæt / mulighed 3: Besvar spørgsmål 1,3,4.
- Sæt / mulighed 4: Besvar spørgsmål 2,3,4.
Som vi kan se, kan den studerende danne 4 sæt (n) med 3 elementer (x). Derfor fortæller kombinatorikken uden gentagelse os, hvordan vi skal danne eller gruppere en endelig mængde data / observationer i grupper af en bestemt størrelse uden at nogen af elementerne kan gentages i hver gruppe. Dette er den største forskel mellem det kombinerende med gentagelse (elementer i hver gruppe kan gentages) og det kombinerende uden gentagelse (intet element kan gentages i hver gruppe)
For at fremhæve i dette eksempel, at det er et tilfælde af kombinatorik uden gentagelse, da den studerende ikke kan vælge at stille nogle af spørgsmålene mere end én gang. Derfor kan elementerne i sætene ikke gentages.
I det foregående tilfælde, da det samlede antal elementer er lille, og mængden af sættet er høj, er antallet af muligheder lille og kan let udledes uden at anvende formlen. I tilfælde af direkte anvendelse af formlen ville tælleren være 24 (4 * 3 * 2 * 1) og nævneren ville være 6 (3 * 2 * 1 * 1), som vi ville nå frem til beregningen på samme måde uden at tænke på, hvordan vi kunne gruppere disse fire spørgsmål i sæt på tre.
Hvordan beregnes kombinatorik uden gentagelse?
Formlen for kombinatoriet uden gentagelse er:
Hvor:
- n = Samlede observationer
- x = Antal valgte emner
Eksempel på kombinatorisk uden gentagelse
Lad os forestille os en militærpeloton på 12 soldater. Hærens kaptajn ønsker at danne grupper på 2 soldater for at infiltrere bag fjendens linjer på forskellige punkter, hvor mange forskellige grupper kunne han danne?
For at løse problemet skal vi først identificere det samlede antal elementer. I dette tilfælde er der i alt 12 soldater, derfor har vi allerede vores n. Da kaptajnen vil have grupper på 2, ved vi allerede, hvad vores x er. Når vi ved dette, kunne vi erstatte i formlen og have antallet af gruppekombinationer på 2.
- n = 12
- x = 2
Ved udskiftning:
Hvis vi anvender faktorielt for nævneren, ville vi have 12 * 11 * 10 * … * 1 = 479.001.600. For nævneren har vi 2 * 1 * 10 * 9 * 8… * 1 = 7.257.600. Vores kombinationsnummer er = 479,001,600 / 7,257,600 = 66.
Som vi kan se, kan kaptajnen danne 66 forskellige par soldater blandt de 12, han har.