Hopp til innhald
Oppgåve

Introduksjon til kombinatorikk

Her skal du jobbe litt meir med oppteljingar.

4.2.1

Ta utgangspunkt i øvinga vi gjorde på teorisida der vi testa kor mange par vi kunne lage med teljebrikker av fem ulike fargar.

a) Kor mange grupper med tre brikker kan du lage dersom du kan bruke den same fargen fleire gonger og rekkjefølgja på brikkene er viktig? (Det vil seie at du til dømes må telje med både gul-blå-gul og gul-gul-blå.)

Løysing

Vi har 5 moglegheiter for den første brikka, 5 moglegheiter for den andre og 5 moglegheiter for den tredje. Altså har vi  5·5·5=53=125  moglege grupper på tre brikker.

b) Kor mange grupper med fire brikker kan du lage dersom du kan bruke den same fargen fleire gonger og rekkjefølgja på brikkene er viktig?

Løysing

Vi har 5 moglegheiter for den første brikka, 5 moglegheiter for den andre, 5 moglegheiter for den tredje og 5 moglegheiter for den fjerde. Altså har vi  5·5·5·5=54=625  moglege grupper på fire brikker.

c) Kor mange grupper med fem brikker kan du lage dersom du kan bruke den same fargen fleire gonger og rekkjefølgja på brikkene er viktig?

Løysing

Etter det same mønsteret som over får vi no  5·5·5·5·5=55=3125.

d) Lag ein formel for kor mange grupper med n brikker av fem ulike fargar du kan lage dersom du kan bruke same farge fleire gonger og rekkjefølgja på brikkene er viktig.

Løysing

Om vi går ut frå at vi har nok brikker, har vi fem moglegheiter på alle plassane, og vi får etter mønster av oppgåve c) 5n ulike grupper.

4.2.2

Du har framleis teljebrikker med fem ulike fargar.

a) Kor mange grupper med tre brikker kan du lage dersom du ikkje kan bruke den same fargen fleire gonger og rekkjefølgja brikkene ligg i, er viktig?

Løysing

Her har vi 5 val for den første plassen. For kvart av desse vala har vi 4 val, sidan vi ikkje kan ha den same fargen som på førsteplass. På den tredje plassen har vi 3 val, sidan vi allereie har brukt opp to fargar. Det gir  5·4·3=60  moglegheiter.

b) Kor mange grupper med fire brikker kan du lage dersom du ikkje kan bruke den same fargen fleire gonger og rekkjefølgja brikkene ligg i, er viktig?

Løysing

Vi held fram på dei gruppene vi laga i b). For kvar av desse har vi to val, sidan vi har brukt tre fargar allereie. Då får vi  5·4·3·2=120  moglegheiter.

c) Kor mange grupper med fem brikker kan du lage dersom du ikkje kan bruke den same fargen fleire gonger og rekkjefølgja brikkene ligg i, er viktig?

Løysing

For kvar av dei 120 moglegheitene vi fann i c), har vi berre eitt val – det betyr at vi har 120 moglegheiter her òg.

4.2.3

Vi held fram med teljebrikker i fem fargar.

Kor mange grupper med tre brikker kan du lage dersom du ikkje kan bruke same farge fleire gonger og rekkjefølgja brikkene ligg i, ikkje har noka betydning? (Det vil seie at du til dømes må sjå på gul-raud-blå, gul-blå-raud, raud-gul-blå, raud-blå-gul, blå-gul-raud og blå-raud-gul som same gruppe.) Bruk brikker, og prøv deg fram.

Løysing

Trudde du at dette ville vere veldig mange brikker og vart litt motlaus?

Ikkje fortvil, her ser du kva kombinasjonar du kan ha:

Det er ti grupper med tre teljebrikker i kvar. Ingen av gruppene har nokon like kombinasjonar. Gruppene har fargane blå, gul, raud, grøn og lilla. Foto.
Bilete: Tove Annette Holter / CC0

Det var altså berre 10 ulike, akkurat like mange som når vi laga par.

Seinare skal vi lære korleis vi kan rekne ut dette og sjå på kvifor vi får 10 moglegheiter med både par og grupper på tre.

4.2.4

Kan du lage eit program som hjelper deg å finne alle løysingane vi fann på teorisida? Seinare skal vi sjå på at Python har innebygde kommandoar for å gjere dette, men førebels er oppgåva di å la Python leite fram para slik du gjorde med teljebrikkene. Hugs at det lønner seg å lage ei oppskrift (ein algoritme) før du gir deg i kast med sjølve programmet.

Løysing nummer 1 – algoritme

1. Vi må lage ei liste over alle brikkene vi har.
2. Vi må ha ei tom liste for å leggje inn para.
3. Vi må gå gjennom lista og ta kvar brikke og pare ho med kvar brikke i lista.
4. Vi må leggje alle desse para inn i lista.
5. Vi skriv ut lista over desse para.
6. Vi finn lengda på lista for å finne talet på par.

Løysing nummer 1 – program
Python
1Brikker = ["gul", "grøn", "blå", "raud", "lilla"]
2    #lagar liste over kva brikker vi har
3
4AllePar = [] #lagar ei tom liste for alle para
5
6for i in range(len(Brikker)):
7    for j in range(len(Brikker)):   #går gjennom og finn alle para
8        Par = [Brikker[i],Brikker[j]] #lagar ei liste med det aktuelle paret
9        AllePar.append(Par) #legg para inn i lista over alle moglegheitene
10
11print(AllePar)
12print(f"Talet på par er {len(AllePar)}.")
Løysing nummer 2 – algoritme

Her kan vi velje å bruke algoritmen frå løysing nummer 1, og så tek vi ut dei para som har like brikker. Vi endrar litt på punkt 4 for å løyse dette:

1. Vi må lage ei liste over alle brikkene vi har.
2. Vi må ha ei tom liste for å leggje inn para.
3. Vi må gå gjennom lista og ta kvar brikke og pare ho med kvar brikke i lista.
4. Vi må leggje para der brikkene har ulik farge inn i lista.
5. Vi skriv ut lista over desse para.
6. Vi finn lengda på lista for å finne talet på par.

Løysing nummer 2 – program
Python
1Brikker = ["gul", "grøn", "blå", "raud", "lilla"]
2    #lagar liste over kva brikker vi har
3
4AllePar = [] #lagar ei tom liste for alle para
5
6for i in range(len(Brikker)):
7    for j in range(len(Brikker)):   #går gjennom og finn alle para
8        Par = [Brikker[i],Brikker[j]] #lagar ei liste med det aktuelle paret
9        if Brikker[i] != Brikker[j]:
10            AllePar.append(Par)
11
12print(AllePar)
13print(f"Talet på par er {len(AllePar)}.")
Løysing nummer 3 – algoritme

Her må vi òg endre litt på algoritmen. Her endrar vi punkt 3 for å berre lage par med ulike brikker. (Vi kunne òg ha valt å fjerne dei para som har like fargekombinasjonar, men eit slikt program vil bruke mykje lengre tid.)

1. Vi må lage ei liste over alle brikkene vi har.
2. Vi må ha ei tom liste for å leggje inn para.
3. Vi må gå gjennom lista og ta kvar brikke og pare ho med kvar brikke som kjem etterpå i lista.
4. Vi må leggje desse para inn i lista.
5. Vi skriv ut lista over desse para.
6. Vi finn lengda på lista for å finne talet på par.

Løysing nummer 3 – program
Python
1Brikker = ["gul", "grøn", "blå", "raud", "lilla"]
2    #lagar liste over kva brikker vi har
3
4AllePar = [] #lagar ei tom liste for alle para
5
6for i in range(len(Brikker)):
7    for j in range(len(Brikker)):   #går gjennom og finn alle para
8        if j > i: #passar på at vi ikkje bruker nokon kombinasjonar om igjen
9            Par = [Brikker[i],Brikker[j]] #lagar ei liste med det aktuelle paret
10            AllePar.append(Par)
11
12print(AllePar)
13print(f"Talet på par er {len(AllePar)}.")
Løysing nummer 4 – algoritme

Her bruker vi algoritmen frå løysing nummer 3, men vi legg til dei like para:

1. Vi må lage ei liste over alle brikkene vi har.
2. Vi må ha ei tom liste for å leggje inn para.
3. Vi må gå gjennom lista og ta kvar brikke og pare ho med kvar brikke som kjem etterpå i lista.
4. Vi må leggje desse para inn i lista.
5. Vi må leggje inn para med like brikker i lista.
6. Vi skriv ut lista over alle para.
7. Vi finn lengda på lista for å finne talet på par.

Løysing nummer 4 – program
Python
1Brikker = ["gul", "grøn", "blå", "raud", "lilla"]
2    #lagar liste over kva brikker vi har
3
4AllePar = [] #lagar ei tom liste for alle para
5
6for i in range(len(Brikker)):
7    for j in range(len(Brikker)):   #går gjennom og finn alle para
8        if j > i: #passar på at vi ikkje bruker nokon kombinasjonar om igjen
9            Par = [Brikker[i],Brikker[j]] #lagar ei liste med det aktuelle paret
10            AllePar.append(Par)
11for i in range(len(Brikker)):
12    AllePar.append([Brikker[i],Brikker[i]])
13
14print(AllePar)
15print(f"Talet på par er {len(AllePar)}.")

4.2.5

No kan du prøve å løyse oppgåve 4.2.1–4.2.3 med programmering.

Har du laga program som er litt annleis enn løysingane? Hugs då på at ein kan løyse oppgåver på mange ulike måtar, både i programmering og elles i matematikken. Kanskje er programmet ditt endå meir effektivt enn vårt?