MAT1030 – Diskret matematikk
Forelesning 20: Kombinatorikk
Roger Antonsen
Matematisk Institutt, Universitetet i Oslo
7. april 2008
Kombinatorikk
Kombinatorikk er studiet av opptellinger,kombinasjonerog permutasjoner.
Vi finner svar p˚a spørsm˚al “Hvor mange m˚ater ...?” uten ˚a telle. Viktig del av f.eks. kompleksitetsanalyse av algoritmer.
Hvor myetidbruker en algoritme? Hvor myeplassbruker en algoritme?
Grunnleggende, nyttig og fascinerende matematikk som dere m˚a beherske.
Vi skal i dag gjøre oss ferdige med kapittel 9. Først litt repetisjon.
MAT1030 – Diskret matematikk 7. april 2008 2
Kombinatorikk
Kombinatorikk er studiet av opptellinger,kombinasjonerog permutasjoner.
Vi finner svar p˚a spørsm˚al “Hvor mange m˚ater ...?” uten ˚a telle. Viktig del av f.eks. kompleksitetsanalyse av algoritmer.
Hvor myetidbruker en algoritme? Hvor myeplassbruker en algoritme?
Grunnleggende, nyttig og fascinerende matematikk som dere m˚a beherske.
Vi skal i dag gjøre oss ferdige med kapittel 9. Først litt repetisjon.
MAT1030 – Diskret matematikk 7. april 2008 2
Kombinatorikk
Kombinatorikk er studiet av opptellinger,kombinasjonerog permutasjoner.
Vi finner svar p˚a spørsm˚al “Hvor mange m˚ater ...?” uten ˚a telle.
Viktig del av f.eks. kompleksitetsanalyse av algoritmer.
Hvor myetidbruker en algoritme? Hvor myeplassbruker en algoritme?
Grunnleggende, nyttig og fascinerende matematikk som dere m˚a beherske.
Vi skal i dag gjøre oss ferdige med kapittel 9. Først litt repetisjon.
MAT1030 – Diskret matematikk 7. april 2008 2
Kombinatorikk
Kombinatorikk er studiet av opptellinger,kombinasjonerog permutasjoner.
Vi finner svar p˚a spørsm˚al “Hvor mange m˚ater ...?” uten ˚a telle.
Viktig del av f.eks. kompleksitetsanalyse av algoritmer.
Hvor myetidbruker en algoritme? Hvor myeplassbruker en algoritme?
Grunnleggende, nyttig og fascinerende matematikk som dere m˚a beherske.
Vi skal i dag gjøre oss ferdige med kapittel 9. Først litt repetisjon.
MAT1030 – Diskret matematikk 7. april 2008 2
Kombinatorikk
Kombinatorikk er studiet av opptellinger,kombinasjonerog permutasjoner.
Vi finner svar p˚a spørsm˚al “Hvor mange m˚ater ...?” uten ˚a telle.
Viktig del av f.eks. kompleksitetsanalyse av algoritmer.
Hvor myetidbruker en algoritme?
Hvor myeplassbruker en algoritme?
Grunnleggende, nyttig og fascinerende matematikk som dere m˚a beherske.
Vi skal i dag gjøre oss ferdige med kapittel 9. Først litt repetisjon.
MAT1030 – Diskret matematikk 7. april 2008 2
Kombinatorikk
Kombinatorikk er studiet av opptellinger,kombinasjonerog permutasjoner.
Vi finner svar p˚a spørsm˚al “Hvor mange m˚ater ...?” uten ˚a telle.
Viktig del av f.eks. kompleksitetsanalyse av algoritmer.
Hvor myetidbruker en algoritme?
Hvor myeplassbruker en algoritme?
Grunnleggende, nyttig og fascinerende matematikk som dere m˚a beherske.
Vi skal i dag gjøre oss ferdige med kapittel 9. Først litt repetisjon.
MAT1030 – Diskret matematikk 7. april 2008 2
Kombinatorikk
Kombinatorikk er studiet av opptellinger,kombinasjonerog permutasjoner.
Vi finner svar p˚a spørsm˚al “Hvor mange m˚ater ...?” uten ˚a telle.
Viktig del av f.eks. kompleksitetsanalyse av algoritmer.
Hvor myetidbruker en algoritme?
Hvor myeplassbruker en algoritme?
Grunnleggende, nyttig og fascinerende matematikk som dere m˚a beherske.
Vi skal i dag gjøre oss ferdige med kapittel 9. Først litt repetisjon.
MAT1030 – Diskret matematikk 7. april 2008 2
Kombinatorikk
Kombinatorikk er studiet av opptellinger,kombinasjonerog permutasjoner.
Vi finner svar p˚a spørsm˚al “Hvor mange m˚ater ...?” uten ˚a telle.
Viktig del av f.eks. kompleksitetsanalyse av algoritmer.
Hvor myetidbruker en algoritme?
Hvor myeplassbruker en algoritme?
Grunnleggende, nyttig og fascinerende matematikk som dere m˚a beherske.
Vi skal i dag gjøre oss ferdige med kapittel 9.
Først litt repetisjon.
MAT1030 – Diskret matematikk 7. april 2008 2
Kombinatorikk
Kombinatorikk er studiet av opptellinger,kombinasjonerog permutasjoner.
Vi finner svar p˚a spørsm˚al “Hvor mange m˚ater ...?” uten ˚a telle.
Viktig del av f.eks. kompleksitetsanalyse av algoritmer.
Hvor myetidbruker en algoritme?
Hvor myeplassbruker en algoritme?
Grunnleggende, nyttig og fascinerende matematikk som dere m˚a beherske.
Vi skal i dag gjøre oss ferdige med kapittel 9.
Først litt repetisjon.
MAT1030 – Diskret matematikk 7. april 2008 2
Repetisjon
Inklusjons- og eksklusjonsprinsippet:
|A| +
|B|
−
|A∩B|
=
|A∪B|
Hvis vi først teller opp elementene iAog deretter elementene iB, har vi talt elementene i A∩B to ganger.
For ˚a f˚a antall elementer iA∪B m˚a vi derfor trekke fra det vi har talt for mye, nemlig antallet iA∩B.
MAT1030 – Diskret matematikk 7. april 2008 3
Repetisjon
Inklusjons- og eksklusjonsprinsippet:
|A| +
|B|
−
|A∩B|
=
|A∪B|
Hvis vi først teller opp elementene iAog deretter elementene iB, har vi talt elementene i A∩B to ganger.
For ˚a f˚a antall elementer iA∪B m˚a vi derfor trekke fra det vi har talt for mye, nemlig antallet iA∩B.
MAT1030 – Diskret matematikk 7. april 2008 3
Repetisjon
Inklusjons- og eksklusjonsprinsippet:
|A|
+
|B|
−
|A∩B|
=
|A∪B|
Hvis vi først teller opp elementene iAog deretter elementene iB, har vi talt elementene i A∩B to ganger.
For ˚a f˚a antall elementer iA∪B m˚a vi derfor trekke fra det vi har talt for mye, nemlig antallet iA∩B.
MAT1030 – Diskret matematikk 7. april 2008 3
Repetisjon
Inklusjons- og eksklusjonsprinsippet:
|A| +
|B|
−
|A∩B|
=
|A∪B|
Hvis vi først teller opp elementene iAog deretter elementene iB, har vi talt elementene i A∩B to ganger.
For ˚a f˚a antall elementer iA∪B m˚a vi derfor trekke fra det vi har talt for mye, nemlig antallet iA∩B.
MAT1030 – Diskret matematikk 7. april 2008 3
Repetisjon
Inklusjons- og eksklusjonsprinsippet:
|A| +
|B|
−
|A∩B|
=
|A∪B|
Hvis vi først teller opp elementene iAog deretter elementene iB, har vi talt elementene i A∩B to ganger.
For ˚a f˚a antall elementer iA∪B m˚a vi derfor trekke fra det vi har talt for mye, nemlig antallet iA∩B.
MAT1030 – Diskret matematikk 7. april 2008 3
Repetisjon
Inklusjons- og eksklusjonsprinsippet:
|A| +
|B|
−
|A∩B|
=
|A∪B|
Hvis vi først teller opp elementene iAog deretter elementene iB, har vi talt elementene i A∩B to ganger.
For ˚a f˚a antall elementer iA∪B m˚a vi derfor trekke fra det vi har talt for mye, nemlig antallet iA∩B.
MAT1030 – Diskret matematikk 7. april 2008 3
Repetisjon
Inklusjons- og eksklusjonsprinsippet:
|A| +
|B|
−
|A∩B|
=
|A∪B|
Hvis vi først teller opp elementene iAog deretter elementene iB, har vi talt elementene i A∩B to ganger.
For ˚a f˚a antall elementer iA∪B m˚a vi derfor trekke fra det vi har talt for mye, nemlig antallet iA∩B.
MAT1030 – Diskret matematikk 7. april 2008 3
Repetisjon
Inklusjons- og eksklusjonsprinsippet:
|A| +
|B|
−
|A∩B|
=
|A∪B|
Hvis vi først teller opp elementene iAog deretter elementene iB, har vi talt elementene i A∩B to ganger.
For ˚a f˚a antall elementer iA∪B m˚a vi derfor trekke fra det vi har talt for mye, nemlig antallet iA∩B.
MAT1030 – Diskret matematikk 7. april 2008 3
Repetisjon
Multiplikasjonsprinsippet:
Hvis vi skal treffe en serie uavhengige valg, vil det totale antall muligheter være produktet av antall muligheter ved hvert valg.
|A×B|=|A| · |B|
Antall elementer i det kartesiske produktetA×B er antall elementer i A multiplisert med antall elementer iB.
Begge prinsippene kan generaliseres til flere enn to mengder.
Generaliseringen av inklusjons- og eksklusjonsprinsippet ses lett ved hjelp av Venn-diagrammer.
Generaliseringen av multiplikasjonsprinsippet blir
|A1×A2× · · · ×An|=|A1| · |A2| · · · |An|
MAT1030 – Diskret matematikk 7. april 2008 4
Repetisjon
Multiplikasjonsprinsippet:
Hvis vi skal treffe en serie uavhengige valg, vil det totale antall muligheter være produktet av antall muligheter ved hvert valg.
|A×B|=|A| · |B|
Antall elementer i det kartesiske produktetA×B er antall elementer i Amultiplisert med antall elementer i B.
Begge prinsippene kan generaliseres til flere enn to mengder.
Generaliseringen av inklusjons- og eksklusjonsprinsippet ses lett ved hjelp av Venn-diagrammer.
Generaliseringen av multiplikasjonsprinsippet blir
|A1×A2× · · · ×An|=|A1| · |A2| · · · |An|
MAT1030 – Diskret matematikk 7. april 2008 4
Repetisjon
Multiplikasjonsprinsippet:
Hvis vi skal treffe en serie uavhengige valg, vil det totale antall muligheter være produktet av antall muligheter ved hvert valg.
|A×B|=|A| · |B|
Antall elementer i det kartesiske produktetA×B er antall elementer i Amultiplisert med antall elementer i B.
Begge prinsippene kan generaliseres til flere enn to mengder.
Generaliseringen av inklusjons- og eksklusjonsprinsippet ses lett ved hjelp av Venn-diagrammer.
Generaliseringen av multiplikasjonsprinsippet blir
|A1×A2× · · · ×An|=|A1| · |A2| · · · |An|
MAT1030 – Diskret matematikk 7. april 2008 4
Repetisjon
Multiplikasjonsprinsippet:
Hvis vi skal treffe en serie uavhengige valg, vil det totale antall muligheter være produktet av antall muligheter ved hvert valg.
|A×B|=|A| · |B|
Antall elementer i det kartesiske produktetA×B er antall elementer i Amultiplisert med antall elementer i B.
Begge prinsippene kan generaliseres til flere enn to mengder.
Generaliseringen av inklusjons- og eksklusjonsprinsippet ses lett ved hjelp av Venn-diagrammer.
Generaliseringen av multiplikasjonsprinsippet blir
|A1×A2× · · · ×An|=|A1| · |A2| · · · |An|
MAT1030 – Diskret matematikk 7. april 2008 4
Repetisjon
Multiplikasjonsprinsippet:
Hvis vi skal treffe en serie uavhengige valg, vil det totale antall muligheter være produktet av antall muligheter ved hvert valg.
|A×B|=|A| · |B|
Antall elementer i det kartesiske produktetA×B er antall elementer i Amultiplisert med antall elementer i B.
Begge prinsippene kan generaliseres til flere enn to mengder.
Generaliseringen av inklusjons- og eksklusjonsprinsippet ses lett ved hjelp av Venn-diagrammer.
Generaliseringen av multiplikasjonsprinsippet blir
|A1×A2× · · · ×An|=|A1| · |A2| · · · |An|
MAT1030 – Diskret matematikk 7. april 2008 4
Repetisjon
Multiplikasjonsprinsippet:
Hvis vi skal treffe en serie uavhengige valg, vil det totale antall muligheter være produktet av antall muligheter ved hvert valg.
|A×B|=|A| · |B|
Antall elementer i det kartesiske produktetA×B er antall elementer i Amultiplisert med antall elementer i B.
Begge prinsippene kan generaliseres til flere enn to mengder.
Generaliseringen av inklusjons- og eksklusjonsprinsippet ses lett ved hjelp av Venn-diagrammer.
Generaliseringen av multiplikasjonsprinsippet blir
|A1×A2× · · · ×An|=|A1| · |A2| · · · |An|
MAT1030 – Diskret matematikk 7. april 2008 4
Repetisjon
Multiplikasjonsprinsippet:
Hvis vi skal treffe en serie uavhengige valg, vil det totale antall muligheter være produktet av antall muligheter ved hvert valg.
|A×B|=|A| · |B|
Antall elementer i det kartesiske produktetA×B er antall elementer i Amultiplisert med antall elementer i B.
Begge prinsippene kan generaliseres til flere enn to mengder.
Generaliseringen av inklusjons- og eksklusjonsprinsippet ses lett ved hjelp av Venn-diagrammer.
Generaliseringen av multiplikasjonsprinsippet blir
|A1×A2× · · · ×An|=|A1| · |A2| · · · |An|
MAT1030 – Diskret matematikk 7. april 2008 4
Repetisjon
Multiplikasjonsprinsippet:
Hvis vi skal treffe en serie uavhengige valg, vil det totale antall muligheter være produktet av antall muligheter ved hvert valg.
|A×B|=|A| · |B|
Antall elementer i det kartesiske produktetA×B er antall elementer i Amultiplisert med antall elementer i B.
Begge prinsippene kan generaliseres til flere enn to mengder.
Generaliseringen av inklusjons- og eksklusjonsprinsippet ses lett ved hjelp av Venn-diagrammer.
Generaliseringen av multiplikasjonsprinsippet blir
|A1×A2× · · · ×An|=|A1| · |A2| · · · |An|
MAT1030 – Diskret matematikk 7. april 2008 4
Repetisjon
Multiplikasjonsprinsippet:
Hvis vi skal treffe en serie uavhengige valg, vil det totale antall muligheter være produktet av antall muligheter ved hvert valg.
|A×B|=|A| · |B|
Antall elementer i det kartesiske produktetA×B er antall elementer i Amultiplisert med antall elementer i B.
Begge prinsippene kan generaliseres til flere enn to mengder.
Generaliseringen av inklusjons- og eksklusjonsprinsippet ses lett ved hjelp av Venn-diagrammer.
Generaliseringen av multiplikasjonsprinsippet blir
|A1×A2× · · · ×An|=|A1| · |A2| · · · |An|
MAT1030 – Diskret matematikk 7. april 2008 4
Eksempel - det er 2
nbinære tall av lengde n
0
0
1
1
00
0
01
1 0
10
0
11
1 1
000
0
001
1 0
010
0
011
1 1 0
100
0
101
1 0
110
0
111
1 1 1
0 0000
1 0001
0
0 0010
1 0011
1 0
0 0100
1 0101
0
0 0110
1 0111
1 1 0
0 1000
1 1001
0
0 1010
1 1011
1 0
0 1100
1 1101
0
0 1110
1 1111
1 1 1
00000
0 00001
0 1
00010
0 00011
1 0 1
00100
0 00101
0 1
00110
0 00111
1 1 1 0
01000
0 01001
0 1
01010
0 01011
1 0 1
01100
0 01101
0 1
01110
0 01111
1 1 1 1 0
10000
0 10001
0 1
10010
0 10011
1 0 1
10100
0 10101
0 1
10110
0 10111
1 1 1 0
11000
0 11001
0 1
11010
0 11011
1 0 1
11100
0 11101
0 1
11110
0 11111
1 1 1 1 1
MAT1030 – Diskret matematikk 7. april 2008 5
Eksempel - det er 2
nbinære tall av lengde n
0
0
1
1
00
0
01
1 0
10
0
11
1 1
000
0
001
1 0
010
0
011
1 1 0
100
0
101
1 0
110
0
111
1 1 1
0 0000
1 0001
0
0 0010
1 0011
1 0
0 0100
1 0101
0
0 0110
1 0111
1 1 0
0 1000
1 1001
0
0 1010
1 1011
1 0
0 1100
1 1101
0
0 1110
1 1111
1 1 1
00000
0 00001
0 1
00010
0 00011
1 0 1
00100
0 00101
0 1
00110
0 00111
1 1 1 0
01000
0 01001
0 1
01010
0 01011
1 0 1
01100
0 01101
0 1
01110
0 01111
1 1 1 1 0
10000
0 10001
0 1
10010
0 10011
1 0 1
10100
0 10101
0 1
10110
0 10111
1 1 1 0
11000
0 11001
0 1
11010
0 11011
1 0 1
11100
0 11101
0 1
11110
0 11111
1 1 1 1 1
MAT1030 – Diskret matematikk 7. april 2008 5
Eksempel - det er 2
nbinære tall av lengde n
0
0
1
1
00
0
01
1 0
10
0
11
1 1
000
0
001
1 0
010
0
011
1 1 0
100
0
101
1 0
110
0
111
1 1 1
0 0000
1 0001
0
0 0010
1 0011
1 0
0 0100
1 0101
0
0 0110
1 0111
1 1 0
0 1000
1 1001
0
0 1010
1 1011
1 0
0 1100
1 1101
0
0 1110
1 1111
1 1 1
00000
0 00001
0 1
00010
0 00011
1 0 1
00100
0 00101
0 1
00110
0 00111
1 1 1 0
01000
0 01001
0 1
01010
0 01011
1 0 1
01100
0 01101
0 1
01110
0 01111
1 1 1 1 0
10000
0 10001
0 1
10010
0 10011
1 0 1
10100
0 10101
0 1
10110
0 10111
1 1 1 0
11000
0 11001
0 1
11010
0 11011
1 0 1
11100
0 11101
0 1
11110
0 11111
1 1 1 1 1
MAT1030 – Diskret matematikk 7. april 2008 5
Eksempel - det er 2
nbinære tall av lengde n
0
0
1
1
00
0
01
1 0
10
0
11
1 1
000
0
001
1 0
010
0
011
1 1 0
100
0
101
1 0
110
0
111
1 1 1
0 0000
1 0001
0
0 0010
1 0011
1 0
0 0100
1 0101
0
0 0110
1 0111
1 1 0
0 1000
1 1001
0
0 1010
1 1011
1 0
0 1100
1 1101
0
0 1110
1 1111
1 1 1
00000
0 00001
0 1
00010
0 00011
1 0 1
00100
0 00101
0 1
00110
0 00111
1 1 1 0
01000
0 01001
0 1
01010
0 01011
1 0 1
01100
0 01101
0 1
01110
0 01111
1 1 1 1 0
10000
0 10001
0 1
10010
0 10011
1 0 1
10100
0 10101
0 1
10110
0 10111
1 1 1 0
11000
0 11001
0 1
11010
0 11011
1 0 1
11100
0 11101
0 1
11110
0 11111
1 1 1 1 1
MAT1030 – Diskret matematikk 7. april 2008 5
Eksempel - det er 2
nbinære tall av lengde n
0
0
1
1
00
0
01
1 0
10
0
11
1 1
000
0
001
1 0
010
0
011
1 1 0
100
0
101
1 0
110
0
111
1 1 1
0 0000
1 0001
0
0 0010
1 0011
1 0
0 0100
1 0101
0
0 0110
1 0111
1 1 0
0 1000
1 1001
0
0 1010
1 1011
1 0
0 1100
1 1101
0
0 1110
1 1111
1 1 1
00000
0 00001
0 1
00010
0 00011
1 0 1
00100
0 00101
0 1
00110
0 00111
1 1 1 0
01000
0 01001
0 1
01010
0 01011
1 0 1
01100
0 01101
0 1
01110
0 01111
1 1 1 1 0
10000
0 10001
0 1
10010
0 10011
1 0 1
10100
0 10101
0 1
10110
0 10111
1 1 1 0
11000
0 11001
0 1
11010
0 11011
1 0 1
11100
0 11101
0 1
11110
0 11111
1 1 1 1 1
MAT1030 – Diskret matematikk 7. april 2008 5
Eksempel - det er 2
nbinære tall av lengde n
0
0
1
1
00
0
01
1 0
10
0
11
1 1
000
0
001
1 0
010
0
011
1 1 0
100
0
101
1 0
110
0
111
1 1 1
0 0000
1 0001
0
0 0010
1 0011
1 0
0 0100
1 0101
0
0 0110
1 0111
1 1 0
0 1000
1 1001
0
0 1010
1 1011
1 0
0 1100
1 1101
0
0 1110
1 1111
1 1 1
00000
0 00001
0 1
00010
0 00011
1 0 1
00100
0 00101
0 1
00110
0 00111
1 1 1 0
01000
0 01001
0 1
01010
0 01011
1 0 1
01100
0 01101
0 1
01110
0 01111
1 1 1 1 0
10000
0 10001
0 1
10010
0 10011
1 0 1
10100
0 10101
0 1
10110
0 10111
1 1 1 0
11000
0 11001
0 1
11010
0 11011
1 0 1
11100
0 11101
0 1
11110
0 11111
1 1 1 1 1
MAT1030 – Diskret matematikk 7. april 2008 5
Eksempel - { a, b, c } × { 0, 1, 2 } × { F , G }
Multiplikasjonsprinsippet gir oss følgende:
|{a,b,c} × {0,1,2} × {F,G}|
=|{a,b,c}| · |{0,1,2}| · |{F,G}|
= 3·3·2
= 18
Vi kan illustrere det slik:
ha, 0, Fi
F
ha, 0, Gi
G 0
ha, 1, Fi
F
ha, 1, Gi
1 G
ha, 2, Fi
F
ha, 2, Gi
G 2
a
hb, 0, Fi
F
hb, 0, Gi
G 0
hb, 1, Fi
F
hb, 1, Gi
1 G
hb, 2, Fi
F
hb, 2, Gi
G 2 b
hc, 0, Fi
F hc, 0, Gi
G 0
hc, 1, Fi
F hc, 1, Gi
1 G
hc, 2, Fi
F hc, 2, Gi
G 2 c
MAT1030 – Diskret matematikk 7. april 2008 6
Eksempel - { a, b, c } × { 0, 1, 2 } × { F , G }
Multiplikasjonsprinsippet gir oss følgende:
|{a,b,c} × {0,1,2} × {F,G}|
=|{a,b,c}| · |{0,1,2}| · |{F,G}|
= 3·3·2
= 18
Vi kan illustrere det slik:
ha, 0, Fi
F
ha, 0, Gi
G 0
ha, 1, Fi
F
ha, 1, Gi
1 G
ha, 2, Fi
F
ha, 2, Gi
G 2
a
hb, 0, Fi
F
hb, 0, Gi
G 0
hb, 1, Fi
F
hb, 1, Gi
1 G
hb, 2, Fi
F
hb, 2, Gi
G 2 b
hc, 0, Fi
F hc, 0, Gi
G 0
hc, 1, Fi
F hc, 1, Gi
1 G
hc, 2, Fi
F hc, 2, Gi
G 2 c
MAT1030 – Diskret matematikk 7. april 2008 6
Eksempel - { a, b, c } × { 0, 1, 2 } × { F , G }
Multiplikasjonsprinsippet gir oss følgende:
|{a,b,c} × {0,1,2} × {F,G}|
=|{a,b,c}| · |{0,1,2}| · |{F,G}|
= 3·3·2
= 18
Vi kan illustrere det slik:
ha, 0, Fi
F
ha, 0, Gi
G 0
ha, 1, Fi
F
ha, 1, Gi
1 G
ha, 2, Fi
F
ha, 2, Gi
G 2
a
hb, 0, Fi
F
hb, 0, Gi
G 0
hb, 1, Fi
F
hb, 1, Gi
1 G
hb, 2, Fi
F
hb, 2, Gi
G 2 b
hc, 0, Fi
F hc, 0, Gi
G 0
hc, 1, Fi
F hc, 1, Gi
1 G
hc, 2, Fi
F hc, 2, Gi
G 2 c
MAT1030 – Diskret matematikk 7. april 2008 6
Eksempel - { a, b, c } × { 0, 1, 2 } × { F , G }
Multiplikasjonsprinsippet gir oss følgende:
|{a,b,c} × {0,1,2} × {F,G}|
=|{a,b,c}| · |{0,1,2}| · |{F,G}|
= 3·3·2
= 18
Vi kan illustrere det slik:
ha, 0, Fi
F
ha, 0, Gi
G 0
ha, 1, Fi
F
ha, 1, Gi
1 G
ha, 2, Fi
F
ha, 2, Gi
G 2
a
hb, 0, Fi
F
hb, 0, Gi
G 0
hb, 1, Fi
F
hb, 1, Gi
1 G
hb, 2, Fi
F
hb, 2, Gi
G 2 b
hc, 0, Fi
F hc, 0, Gi
G 0
hc, 1, Fi
F hc, 1, Gi
1 G
hc, 2, Fi
F hc, 2, Gi
G 2 c
MAT1030 – Diskret matematikk 7. april 2008 6
Eksempel - { a, b, c } × { 0, 1, 2 } × { F , G }
Multiplikasjonsprinsippet gir oss følgende:
|{a,b,c} × {0,1,2} × {F,G}|
=|{a,b,c}| · |{0,1,2}| · |{F,G}|
= 3·3·2
= 18
Vi kan illustrere det slik:
ha, 0, Fi
F
ha, 0, Gi
G 0
ha, 1, Fi
F
ha, 1, Gi
1 G
ha, 2, Fi
F
ha, 2, Gi
G 2
a
hb, 0, Fi
F
hb, 0, Gi
G 0
hb, 1, Fi
F
hb, 1, Gi
1 G
hb, 2, Fi
F
hb, 2, Gi
G 2 b
hc, 0, Fi
F hc, 0, Gi
G 0
hc, 1, Fi
F hc, 1, Gi
1 G
hc, 2, Fi
F hc, 2, Gi
G 2 c
MAT1030 – Diskret matematikk 7. april 2008 6
Eksempel - { a, b, c } × { 0, 1, 2 } × { F , G }
Multiplikasjonsprinsippet gir oss følgende:
|{a,b,c} × {0,1,2} × {F,G}|
=|{a,b,c}| · |{0,1,2}| · |{F,G}|
= 3·3·2
= 18
Vi kan illustrere det slik:
ha, 0, Fi
F
ha, 0, Gi
G 0
ha, 1, Fi
F
ha, 1, Gi
1 G
ha, 2, Fi
F
ha, 2, Gi
G 2
a
hb, 0, Fi
F
hb, 0, Gi
G 0
hb, 1, Fi
F
hb, 1, Gi
1 G
hb, 2, Fi
F
hb, 2, Gi
G 2 b
hc, 0, Fi
F hc, 0, Gi
G 0
hc, 1, Fi
F hc, 1, Gi
1 G
hc, 2, Fi
F hc, 2, Gi
G 2 c
MAT1030 – Diskret matematikk 7. april 2008 6
Eksempel - { a, b, c } × { 0, 1, 2 } × { F , G }
Multiplikasjonsprinsippet gir oss følgende:
|{a,b,c} × {0,1,2} × {F,G}|
=|{a,b,c}| · |{0,1,2}| · |{F,G}|
= 3·3·2
= 18
Vi kan illustrere det slik:
ha, 0, Fi
F
ha, 0, Gi
G 0
ha, 1, Fi
F
ha, 1, Gi
1 G
ha, 2, Fi
F
ha, 2, Gi
G 2
a
hb, 0, Fi
F
hb, 0, Gi
G 0
hb, 1, Fi
F
hb, 1, Gi
1 G
hb, 2, Fi
F
hb, 2, Gi
G 2 b
hc, 0, Fi
F hc, 0, Gi
G 0
hc, 1, Fi
F hc, 1, Gi
1 G
hc, 2, Fi
F hc, 2, Gi
G 2 c
MAT1030 – Diskret matematikk 7. april 2008 6
Eksempel - { a, b, c } × { 0, 1, 2 } × { F , G }
Multiplikasjonsprinsippet gir oss følgende:
|{a,b,c} × {0,1,2} × {F,G}|
=|{a,b,c}| · |{0,1,2}| · |{F,G}|
= 3·3·2
= 18
Vi kan illustrere det slik:
ha, 0, Fi
F
ha, 0, Gi
G 0
ha, 1, Fi
F
ha, 1, Gi
1 G
ha, 2, Fi
F
ha, 2, Gi
G 2
a
hb, 0, Fi
F
hb, 0, Gi
G 0
hb, 1, Fi
F
hb, 1, Gi
1 G
hb, 2, Fi
F hb, 2, Gi
G 2 b
hc, 0, Fi
F hc, 0, Gi
G 0
hc, 1, Fi
F hc, 1, Gi
1 G
hc, 2, Fi
F
hc, 2, Gi
G 2 c
MAT1030 – Diskret matematikk 7. april 2008 6
Mer repetisjon
Definisjon (Permutasjon)
En permutasjon en endring av rekkefølgen av elementene i en ordnet mengde.
Vi sier ogs˚a at enpermutasjon av en mengde er en ordning av elementene i mengden.
Eksempel
Permutasjonene av {A,B,C} er
ABC,ACB,BAC,BCA,CAB,CBA.
Det er n! permutasjoner av en mengde medn elementer. Og vi vet (selvfølgelig) at n! =n·(n−1)·(n−2)· · ·1
I eksempelet har vi 3 elementer og 3! = 3·2·1 = 6 permutasjoner.
MAT1030 – Diskret matematikk 7. april 2008 7
Mer repetisjon
Definisjon (Permutasjon)
En permutasjon en endring av rekkefølgen av elementene i en ordnet mengde.
Vi sier ogs˚a at enpermutasjon av en mengde er en ordning av elementene i mengden.
Eksempel
Permutasjonene av {A,B,C} er
ABC,ACB,BAC,BCA,CAB,CBA.
Det er n! permutasjoner av en mengde medn elementer. Og vi vet (selvfølgelig) at n! =n·(n−1)·(n−2)· · ·1
I eksempelet har vi 3 elementer og 3! = 3·2·1 = 6 permutasjoner.
MAT1030 – Diskret matematikk 7. april 2008 7
Mer repetisjon
Definisjon (Permutasjon)
En permutasjon en endring av rekkefølgen av elementene i en ordnet mengde. Vi sier ogs˚a at en permutasjon av en mengde er en ordning av elementene i mengden.
Eksempel
Permutasjonene av {A,B,C} er
ABC,ACB,BAC,BCA,CAB,CBA.
Det er n! permutasjoner av en mengde medn elementer. Og vi vet (selvfølgelig) at n! =n·(n−1)·(n−2)· · ·1
I eksempelet har vi 3 elementer og 3! = 3·2·1 = 6 permutasjoner.
MAT1030 – Diskret matematikk 7. april 2008 7
Mer repetisjon
Definisjon (Permutasjon)
En permutasjon en endring av rekkefølgen av elementene i en ordnet mengde. Vi sier ogs˚a at en permutasjon av en mengde er en ordning av elementene i mengden.
Eksempel
Permutasjonene av {A,B,C} er
ABC,ACB,BAC,BCA,CAB,CBA. Det er n! permutasjoner av en mengde medn elementer.
Og vi vet (selvfølgelig) at n! =n·(n−1)·(n−2)· · ·1
I eksempelet har vi 3 elementer og 3! = 3·2·1 = 6 permutasjoner.
MAT1030 – Diskret matematikk 7. april 2008 7
Mer repetisjon
Definisjon (Permutasjon)
En permutasjon en endring av rekkefølgen av elementene i en ordnet mengde. Vi sier ogs˚a at en permutasjon av en mengde er en ordning av elementene i mengden.
Eksempel
Permutasjonene av {A,B,C} erABC,ACB,BAC,BCA,CAB,CBA.
Det er n! permutasjoner av en mengde medn elementer. Og vi vet (selvfølgelig) at n! =n·(n−1)·(n−2)· · ·1
I eksempelet har vi 3 elementer og 3! = 3·2·1 = 6 permutasjoner.
MAT1030 – Diskret matematikk 7. april 2008 7
Mer repetisjon
Definisjon (Permutasjon)
En permutasjon en endring av rekkefølgen av elementene i en ordnet mengde. Vi sier ogs˚a at en permutasjon av en mengde er en ordning av elementene i mengden.
Eksempel
Permutasjonene av {A,B,C} erABC,ACB,BAC,BCA,CAB,CBA. Det er n! permutasjoner av en mengde medn elementer.
Og vi vet (selvfølgelig) at n! =n·(n−1)·(n−2)· · ·1
I eksempelet har vi 3 elementer og 3! = 3·2·1 = 6 permutasjoner.
MAT1030 – Diskret matematikk 7. april 2008 7
Mer repetisjon
Definisjon (Permutasjon)
En permutasjon en endring av rekkefølgen av elementene i en ordnet mengde. Vi sier ogs˚a at en permutasjon av en mengde er en ordning av elementene i mengden.
Eksempel
Permutasjonene av {A,B,C} erABC,ACB,BAC,BCA,CAB,CBA. Det er n! permutasjoner av en mengde medn elementer.
Og vi vet (selvfølgelig) at n! =n·(n−1)·(n−2)· · ·1
I eksempelet har vi 3 elementer og 3! = 3·2·1 = 6 permutasjoner.
MAT1030 – Diskret matematikk 7. april 2008 7
Mer repetisjon
Definisjon (Permutasjon)
En permutasjon en endring av rekkefølgen av elementene i en ordnet mengde. Vi sier ogs˚a at en permutasjon av en mengde er en ordning av elementene i mengden.
Eksempel
Permutasjonene av {A,B,C} erABC,ACB,BAC,BCA,CAB,CBA. Det er n! permutasjoner av en mengde medn elementer.
Og vi vet (selvfølgelig) at n! =n·(n−1)·(n−2)· · ·1
I eksempelet har vi 3 elementer og 3! = 3·2·1 = 6 permutasjoner.
MAT1030 – Diskret matematikk 7. april 2008 7
Plan for dagen
Mer om permutasjoner og ordnet utvalg nPr
Mer om kombinasjoner nr
“n velgr” Binomialkoeffisientene
Pascals trekant
Generalisering av første kvadratsetning (a+b)2=a2+ 2ab+b2 Oppsummering av kombinatoriske prinsipper
Eksempler og oppgaver
MAT1030 – Diskret matematikk 7. april 2008 8
Plan for dagen
Mer om permutasjoner og ordnet utvalg nPr
Mer om kombinasjoner nr
“n velgr” Binomialkoeffisientene
Pascals trekant
Generalisering av første kvadratsetning (a+b)2=a2+ 2ab+b2 Oppsummering av kombinatoriske prinsipper
Eksempler og oppgaver
MAT1030 – Diskret matematikk 7. april 2008 8
Plan for dagen
Mer om permutasjoner og ordnet utvalg nPr Mer om kombinasjoner nr
“n velgr”
Binomialkoeffisientene Pascals trekant
Generalisering av første kvadratsetning (a+b)2=a2+ 2ab+b2 Oppsummering av kombinatoriske prinsipper
Eksempler og oppgaver
MAT1030 – Diskret matematikk 7. april 2008 8
Plan for dagen
Mer om permutasjoner og ordnet utvalg nPr Mer om kombinasjoner nr
“n velgr” Binomialkoeffisientene
Pascals trekant
Generalisering av første kvadratsetning (a+b)2=a2+ 2ab+b2 Oppsummering av kombinatoriske prinsipper
Eksempler og oppgaver
MAT1030 – Diskret matematikk 7. april 2008 8
Plan for dagen
Mer om permutasjoner og ordnet utvalg nPr Mer om kombinasjoner nr
“n velgr” Binomialkoeffisientene
Pascals trekant
Generalisering av første kvadratsetning (a+b)2=a2+ 2ab+b2 Oppsummering av kombinatoriske prinsipper
Eksempler og oppgaver
MAT1030 – Diskret matematikk 7. april 2008 8
Plan for dagen
Mer om permutasjoner og ordnet utvalg nPr Mer om kombinasjoner nr
“n velgr” Binomialkoeffisientene
Pascals trekant
Generalisering av første kvadratsetning (a+b)2=a2+ 2ab+b2
Oppsummering av kombinatoriske prinsipper Eksempler og oppgaver
MAT1030 – Diskret matematikk 7. april 2008 8
Plan for dagen
Mer om permutasjoner og ordnet utvalg nPr Mer om kombinasjoner nr
“n velgr” Binomialkoeffisientene
Pascals trekant
Generalisering av første kvadratsetning (a+b)2=a2+ 2ab+b2 Oppsummering av kombinatoriske prinsipper
Eksempler og oppgaver
MAT1030 – Diskret matematikk 7. april 2008 8
Plan for dagen
Mer om permutasjoner og ordnet utvalg nPr Mer om kombinasjoner nr
“n velgr” Binomialkoeffisientene
Pascals trekant
Generalisering av første kvadratsetning (a+b)2=a2+ 2ab+b2 Oppsummering av kombinatoriske prinsipper
Eksempler og oppgaver
MAT1030 – Diskret matematikk 7. april 2008 8
Ordnet utvalg
Vi skal n˚a se p˚a det som kallesordnet utvalgfra en mengde. Eksempel
Oppgave:
I et barneskirenn er det med 20 barn.
Det er lov til ˚a opplyse om hvem som tok de tre første plassene, mens resten ikke skal rangeres.
Hvor mange forskjellige resultatlister kan man f˚a?
MAT1030 – Diskret matematikk 7. april 2008 9
Ordnet utvalg
Vi skal n˚a se p˚a det som kallesordnet utvalgfra en mengde.
Eksempel
Oppgave:
I et barneskirenn er det med 20 barn.
Det er lov til ˚a opplyse om hvem som tok de tre første plassene, mens resten ikke skal rangeres.
Hvor mange forskjellige resultatlister kan man f˚a?
MAT1030 – Diskret matematikk 7. april 2008 9
Ordnet utvalg
Vi skal n˚a se p˚a det som kallesordnet utvalgfra en mengde.
Eksempel
Oppgave:
I et barneskirenn er det med 20 barn.
Det er lov til ˚a opplyse om hvem som tok de tre første plassene, mens resten ikke skal rangeres.
Hvor mange forskjellige resultatlister kan man f˚a?
MAT1030 – Diskret matematikk 7. april 2008 9
Ordnet utvalg
Vi skal n˚a se p˚a det som kallesordnet utvalgfra en mengde.
Eksempel Oppgave:
I et barneskirenn er det med 20 barn.
Det er lov til ˚a opplyse om hvem som tok de tre første plassene, mens resten ikke skal rangeres.
Hvor mange forskjellige resultatlister kan man f˚a?
MAT1030 – Diskret matematikk 7. april 2008 9
Ordnet utvalg
Vi skal n˚a se p˚a det som kallesordnet utvalgfra en mengde.
Eksempel Oppgave:
I et barneskirenn er det med 20 barn.
Det er lov til ˚a opplyse om hvem som tok de tre første plassene, mens resten ikke skal rangeres.
Hvor mange forskjellige resultatlister kan man f˚a?
MAT1030 – Diskret matematikk 7. april 2008 9
Ordnet utvalg
Vi skal n˚a se p˚a det som kallesordnet utvalgfra en mengde.
Eksempel Oppgave:
I et barneskirenn er det med 20 barn.
Det er lov til ˚a opplyse om hvem som tok de tre første plassene, mens resten ikke skal rangeres.
Hvor mange forskjellige resultatlister kan man f˚a?
MAT1030 – Diskret matematikk 7. april 2008 9
Ordnet utvalg
Vi skal n˚a se p˚a det som kallesordnet utvalgfra en mengde.
Eksempel Oppgave:
I et barneskirenn er det med 20 barn.
Det er lov til ˚a opplyse om hvem som tok de tre første plassene, mens resten ikke skal rangeres.
Hvor mange forskjellige resultatlister kan man f˚a?
MAT1030 – Diskret matematikk 7. april 2008 9
Eksempel (Fortsatt)
Løsning:
Det fins 20 mulige vinnere, deretter 19 mulige andreplasser og til sist 18 mulige tredjeplasser.
Det fins alts˚a 20·19·18 = 6840 forskjellige resultatlister.
Legg merke til at
20·19·18 = 20·19·18·17·16· · ·2·1
17·16· · ·2·1 = 20! (20−3)!
Vi skal n˚a definere dette mer generelt og bruke notasjonen 20P3 for dette tallet.
MAT1030 – Diskret matematikk 7. april 2008 10
Eksempel (Fortsatt)
Løsning:
Det fins 20 mulige vinnere, deretter 19 mulige andreplasser og til sist 18 mulige tredjeplasser.
Det fins alts˚a 20·19·18 = 6840 forskjellige resultatlister. Legg merke til at
20·19·18 = 20·19·18·17·16· · ·2·1
17·16· · ·2·1 = 20! (20−3)!
Vi skal n˚a definere dette mer generelt og bruke notasjonen 20P3 for dette tallet.
MAT1030 – Diskret matematikk 7. april 2008 10
Eksempel (Fortsatt) Løsning:
Det fins 20 mulige vinnere, deretter 19 mulige andreplasser og til sist 18 mulige tredjeplasser.
Det fins alts˚a 20·19·18 = 6840 forskjellige resultatlister. Legg merke til at
20·19·18 = 20·19·18·17·16· · ·2·1
17·16· · ·2·1 = 20! (20−3)!
Vi skal n˚a definere dette mer generelt og bruke notasjonen 20P3 for dette tallet.
MAT1030 – Diskret matematikk 7. april 2008 10
