- 999 (Registered)
-
(0 Reviews)
Kombinatorik
Indledning
Kombinatorik omhandler bestemmelse af antal valgmuligheder (f.eks. antallet af måder man kan trække 2 bolde fra en skål med 5 bolde). Kombinatorik kan ofte bruges til at bestemme antallet af elementer i en hændelse, hvilket er afgørende for bestemmelse af sandsynligheden (kombinatorisk sandsynlighed). I dette modul vil følgende begreber inden for emnet kombinatorik blive behandlet:
- Valgmuligheder
- Tælletræ
- Multiplikationsprincippet for valgmuligheder
- Fakultet
- Kombinationer
- Permutationer
- Kombinationer
Valgmuligheder
Tælletræ (oversigt over valgmuligheder)
Når der ved et eksperiment forekommer flere stokastiske variabler, vil det give anledning til mange valgmuligheder. For at få et overblik over alle valgmuligheder kan det være praktisk at lave et tælletræ. Som eksempel kan man bruge et tælletræ til at visualisere de forskellige sammensætninger, man kan opnå for en menu, hvor der er en forret (variabel 1), hovedret (variabel 2) og dessert (variabel 3). Her er vist et eksempel, hvor der er to valgmuligheder ved hver ret:
Multiplikationsprincippet for antal valgmuligheder
Antallet af valgmuligheder kan nemt bestemmes, når man ved, hvor mange valgmuligheder der er for hver variabel, idet det samlede antal valgmuligheder er givet som produktet af disse. Dette kaldes multiplikationsprincippet for antal valgmuligheder:
Multiplikationsprincippet for antal valgmuligheder
Hvis man har to variabler X og Y, hvor X kan have n forskellige værdier, og Y kan have m forskellige værdier, er det samlede antal valgmuligheder givet som n·m.
For en tre-retters menu, hvor der er 2 forskellige retter at vælge imellem ved forret, hovedret og dessert, giver multiplikationsprincippet 8 valgmuligheder. Det samme kan man tælle sig frem til ud fra et tælletræ (antallet af “blade”).
ØVELSE: MULTIPLIKATIONSPRINCIPPET
Fakultet (antal rækkefølger)
En vigtig regneoperation indenfor kombinatorik er fakultet, der er defineret som:
Fakultet
Fakultet af et positivt heltal n er defineret som produktet af tallet og alle positive hele tal, som er mindre end tallet:
$$ n! = n \cdot (n-1) … 2 \cdot 1 $$
Fakultet af tallet 0 er defineret til at være 1:
$$ 0! = 1 $$
Fakultet kan i sig selv anvendes til at bestemme antallet af rækkefølger af en række elementer. For eksempel i hvor mange forskellige rækkefølger kan man opstille bogstaverne A, B og C. Svaret er 3! = 6 (ABC, ACB, BAC, BCA, CAB og CBA).
Kombinationer
Kombinationer (antal udtagninger, hvor der ikke skelnes mellem rækkefølger)
Når der skelnes mellem, hvem der udtages, men der ikke skelnes mellem rækkefølgen, kaldes antallet af muligheder for kombinationer:
Kombinationer
Antallet af forskellige udtagninger af r elementer fra en pulje på n elementer kaldes for kombinationer og kan bestemmes med følgende formel:
$$ K(n,r) = \frac{n!}{r!(n-r)!}$$
I tilfældet, hvor 10 elever udtages fra en klasse på 15, vil antallet af kombinationer være givet som:
$$ K(15,10) = \frac{15!}{10!(15-10)!} = 3.003 $$
Permutationer (antal udtagninger, hvor der skelnes mellem rækkefølger)
Hvis man udtager 10 elever fra en klasse på 15, kan dette gøres på mange forskellige måder. Når der både skelnes mellem, hvem der udtages, og i hvilken rækkefølge udtagning foretages, kaldes antallet af muligheder for permutationer:
Permutationer
Antallet af rækkefølger man kan trække r elementer ud af en pulje på n elementer kaldes for permutationer og kan bestemmes med følgende formel:
$$ P(n,r) = \frac{n!}{(n-r)!}$$
I tilfældet, hvor 10 elever udtages fra en klasse på 15, vil antallet af permutationer være givet som:
$$ P(15,10) = \frac{15!}{(15-10)!} = \frac{15!}{5!} = 10.897.286.400 $$
Det vil sige, der er over 10 milliarder måder, man kan udtager 10 elever fra en klasse på 15 elever!
Opsamling
I dette modul er blevet behandlet emnet kombinatorik. Modulet har givet en forståelse for følgende:
- Valgmuligheder
- Multiplikationsprincippet for valgmuligheder
- Fakultet
- Kombinationer (binomialkoefficienter)
- Permutationer