Permutacije

Permutacije

Avtor: E-um (vsebinsko), Skupina NAUK (tehnično)

Uvod

A si že kdaj zjutraj, ko si čakal na avtobus, razmišljal, na koliko različnih načinov lahko vsi potniki, ki čakajo na postaji, vstopijo na avtobus? V tem poglavju se bomo naučili izračunati število razporeditev vseh danih elementov (npr. ljudi, živali, števil, črk, ...) v vrsto.

Živali v trgovini

Nekega dne so se v trgovini srečali zajec, pes, mačka in miš. Na koliko različnih načinov se lahko postavijo v vrsto pred blagajno?


Pred blagajno se lahko postavijo na različnih načinov.


Preveri

Pravilno

Napačno

Pomagaj si s spodnjo animacijo. Živali premikaj s pomocjo modrih pik.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Rešitev

Živali se lahko postavijo v vrsto na različnih načinov.

Živali v trgovini

Vemo, da sta pes in mačka ter mačka in miš "eksplozivni kombinaciji". Koliko od naštetih razporeditev je takih, pri katerih ne bo prišlo do incidenta v vrsti?


Takih razporeditev je .


Preveri

Pravilno

Take razporeditve so:

- pes, miš, zajec, mačka,
- miš, pes, zajec, mačka,
- mačka, zajec, pes, miš in
- mačka, zajec, miš, pes.

Napačno

Pomagaj si s spodnjo animacijo. Živali premikaj s pomocjo modrih pik.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Rešitev

Take razporeditve so . To so:

- pes, miš, zajec, mačka,
- miš, pes, zajec, mačka,
- mačka, zajec, pes, miš in
- mačka, zajec, miš, pes.

Kaj je permutacija

V prvotni nalogi smo razmišljali o tem, na koliko različnih načinov lahko (vse) štiri živali razporedimo v vrsto. Take razporeditve imenujemo permutacije štirih elementov. V drugem delu naloge smo med 24 permutacijami iskali tiste permutacije, ki so zagotavljale mir v vrsti. Ključno je bilo, da smo v vrsto razporedili vse elemente obravnavane množice živali, pri čemer je bil njihov vrstni red ključnega pomena.


Dogovor:


 
Razporeditve vseh danih elementov v vrsto imenujemo PERMUTACIJE. Vrstni red razporejanja JE pomemben!


Vse naloge tega poglavja lahko rešiš z upoštevanjem pravila produkta. Reševanje nalog tega tipa bomo poenostavili s tem, da bomo izpeljali dva obrazca.

Permutacije brez ponavljanja

V naslednjih primerih bomo razporejali v vrsto vse dane med seboj različne elemente.


Tekmovanje v teku


Razporedi knjige


Kroglice v vrsto

Tekmovanje v teku

Šest sošolcev se je pomerilo v teku. Na koliko različnih načinov lahko prispejo na cilj, če jih več ne more biti uvrščenih na isto mesto?


Na cilj lahko prispejo na različnih načinov.


Preveri

Pravilno

Za prvo mesto imamo ŠEST možnosti, za drugo mesto PET, za tretje mesto ŠTIRI, za četrto mesto TRI, za peto mesto DVE IN za zadnje mesto le še ENO možnost. Torej lahko prispejo na cilj na različnih načinov.

1.MESTOin2.MESTOin3.MESTOin4.MESTOin5.MESTOin6.MESTO
=

Napačno

Za prvo mesto imamo ŠEST možnosti, za drugo mesto PET možnosti,...

Rešitev

Za prvo mesto imamo ŠEST možnosti, za drugo mesto PET, za tretje mesto ŠTIRI, za četrto mesto TRI, za peto mesto DVE IN za zadnje mesto le še ENO možnost. Torej lahko prispejo na cilj na različnih načinov.

1.MESTOin2.MESTOin3.MESTOin4.MESTOin5.MESTOin6.MESTO
=

Tekmovanje v teku

 
Dogovorimo se, da bomo produkt prvih n naravnih števil označili z (beremo "n fakulteta" oz. "n faktorialno"). Torej: ...
Prav je, da definiramo tudi , in sicer takole: .


Razmisli!
Sedaj, ko si spoznal pojem fakulteta, še enkrat poglej k našim tekačem. Poskusi zapisati rešitev naloge s pravkar spoznanim simbolom.


Tekači lahko prispejo na cilj na različnih načinov.


Preveri

Pravilno

Napačno

Še enkrat poskusi.

Rešitev

Tekači lahko prispejo na cilj na različnih načinov.

Vaja

Dopolni! Navodilo: namesto "krat" piši *.

0! = 1

1! = 1

2! = 2 * 1 = 2

3! = =

4! = =

5! = =

6! = =

7! = =

8! = =

9! = =

10! = =


Preveri

Pravilno

Napačno

Poskusi ponovno.

Rešitev

3! = 3*2*1 = 6

4! = 4*3*2*1 = 24

5! = 5*4*3*2*1 = 120

6! = 6*5*4*3*2*1 = 720

7! = 7*6*5*4*3*2*1 = 5040

8! = 8*7*6*5*4*3*2*1 = 40320

9! = 9*8*7*6*5*4*3*2*1 = 362880

10! = 10*9*8*7*6*5*4*3*2*1 = 3628800

Vaja

Ugotovi, ali so naslednje enakosti pravilne ali napačne.

1.

2.

3.

4.

5.

6.


Preveri

Pravilno

Odlično!

Napačno

To pa ne bo držalo! Pravilno si rešil le od 6 primerov.

Rešitev

1.
2.
3.
4.
5.
6.

Razporedi knjige

Z uporabo dogovora na desni strani reši spodnjo nalogo.


Na koliko različnih načinov lahko na knjižno polico razporedimo pet različnih knjig?


Na knjižno polico lahko pet različnih knjig razporedimo na različnih načinov.


Preveri

Pravilno

Napačno

Še enkrat poskusi.

Rešitev

Za prvo mesto imamo PET možnosti, za drugo mesto ŠTIRI, za tretje mesto TRI, za četrto mesto DVE IN za peto mesto ENO možnost. Torej lahko knjige razporedimo na različnih načinov.

1.MESTOin2.MESTOin3.MESTOin4.MESTOin5.MESTO

 
Dogovorimo se, da bomo produkt prvih n naravnih števil označili z (beremo "n fakulteta" oz. "n faktorialno"). Torej: ...
Prav je, da definiramo tudi , in sicer takole: .

Kroglice v vrsto

Z uporabo dogovora na desni strani reši spodnjo nalogo.


Na koliko različnih načinov lahko razporedimo v vrsto raznobarvnih kroglic?


raznobarvnih kroglic lahko v vrsto razporedimo na različnih načinov.


Preveri

Pravilno

Napačno

Še enkrat poskusi.

Rešitev

Za prvo mesto imamo možnosti, za drugo možnosti, za tretje možnosti, ..., za -vo mesto možnosti IN za -to mesto možnost. Torej lahko kroglice razporedimo v vrsto na ... različnih načinov.

1.MESTOin2.MESTOin3.MESTO...-vo MESTO-to MESTO

 
Dogovorimo se, da bomo produkt prvih n naravnih števil označili z (beremo "n fakulteta" oz. "n faktorialno"). Torej: ...
Prav je, da definiramo tudi , in sicer takole: .

Ugotovitev

Ugotovili smo:


 

Vseh različnih elementov (ljudi, knjig, števil, ...) lahko razporedimo v vrsto na

različnih načinov. (S označimo število permutacij brez ponavljanja elementov.)

Reši sam

Katere so vse permutacije brez ponavljanja elementov A, B in C!


ABC, ACB, BAC, BCA, CAB
ABC, ACB, BAC
ABC, ACB, BAC, BCA, CAB, CBA

Pravilno

Napačno

Še enkrat poskusi.

Rešitev

ABC


ACB


BAC


BCA


CAB


CBA

Test

1. Na koliko različnih načinov lahko čakajo v vrsti na sladoled trije ljudje?


2. Kokoška je vali šest jajčk. Na koliko različnih načinov (glede na vrstni red) lahko pokukajo na svet piščančki?


3. Koliko različnih besed s sedmimi črkami lahko sestavimo iz črk besede TRIGLAV, če se črke ne smejo ponavljati?


Preveri

Pravilno

Odlično!

Napačno

Poskusi ponovno. Pravilno si rešil le od 3 primerov.

Rešitev

1. Na različnih načinov.
2. Na različnih načinov.
3. različnih besed.

Permutacije s ponavljanjem

V naslednjih primerih boš spet razporejal v vrsto vse dane elemente, vendar bodo nekateri med njimi med seboj enaki.


Knjige


Več knjig


Še več knjig


Skoraj že preveč knjig

Knjige

Na koliko različnih načinov lahko na knjižno polico razporedimo eno fizikalno in tri enake matematične knjige?


Na različnih načinov.


Preveri

Pravilno

Napačno

Še enkrat poskusi.

Rešitev

Preštejmo vse možne razporeditve: FMMM, MFMM, MMFM, MMMF, pri čemer smo s F označili fizikalno, z M pa matematično knjigo. Knjige torej lahko razporedimo na različne načine. Kako pa bi to izračunali? Če bi bile matematične knjige med seboj različne, bi v vrsto razporejali štiri različne knjige, za kar bi imeli različnih možnosti. Ker pa so knjige med seboj enake, je vseh možnih razporeditev -krat manj, kot bi jih bilo, če bi bile vse knjige med seboj različne. Torej lahko naše knjige razporedimo na različne načine.

Več knjig

Na koliko različnih načinov lahko na knjižno polico razporedimo deset knjig, med katerimi so štiri enake?


Na različnih načinov.


Preveri

Pravilno

Napačno

Še enkrat poskusi.

Rešitev

Na knjižno polico razporejamo deset knjig. Če bi bile vse med seboj različne, bi jih lahko razporedili na različnih načinov. Če imamo pri eni od permutacij enake knjige na določenih mestih in jih med sabo zamenjamo – permutiramo (na načinov), dobimo isto permutacijo s ponavljanjem. Zato je teh -krat manj. Torej lahko knjige razporedimo na različnih načinov.

Še več knjig

Na koliko različnih načinov lahko na knjižno polico razporedimo knjig, med katerimi je enakih?


Na različnih načinov
Na različnih načinov
Na različnih načinov

Pravilno

Napačno

Še enkrat poskusi.

Rešitev

Na knjižno polico razporejamo knjig. Če bi bile vse med seboj različne, bi jih lahko razporedili na različnih načinov. Če imamo pri eni od permutacij enakih knjig na določenih mestih in jih med sabo zamenjamo – permutiramo (na načinov), dobimo isto permutacijo s ponavljanjem. Zato je teh -krat manj. Torej lahko knjige razporedimo na različnih načinov.

Skoraj že preveč knjig

Na koliko različnih načinov lahko na knjižno polico razporedimo knjig: enakih fizikalnih in enakih matematičnih ?


Na različnih načinov
Na različnih načinov
Na različnih načinov

Pravilno

Napačno

Še enkrat poskusi.

Rešitev

Na knjižno polico razporejamo knjig. Če bi bile vse med seboj različne, bi jih lahko razporedili na različnih načinov. Ker je fizikalnih knjig med seboj enakih, je možnih razporeditev -krat manj. Ker je tudi matematičnih knjig med seboj enakih, je možnih razporeditev še -krat manj. Torej lahko knjige razporedimo na različnih načinov.

Ugotovitev

Ugotovili smo:


 

Vse elemente, med katerimi se nekateri ponavljajo, lahko razporedimo v vrsto na

različnih načinov, kjer števila , , ..., določajo, kolikokrat se kateri element ponovi. (S označimo število permutacij s ponavljanjem elementov.)

Reši sam

Katere so vse permutacije s ponavljanjem elementov A, A, B in C!


AABC, ABAC, ACAB, BAAC, BCAA, CABA, CBAA
AABC, AACB, ACAB, ACBA, BAAC, BACA, BCAA, CAAB, CABA, CBAA
AABC, AACB, ABAC, ABCA, ACAB, ACBA, BAAC, BACA, BCAA, CAAB, CABA, CBAA

Pravilno

Napačno

Še enkrat poskusi.

Rešitev

AABC


AACB


ABAC


ABCA


ACAB


ACBA


BAAC


BACA


BCAA


CAAB


CABA


CBAA

Test

1. Na koliko različnih načinov lahko Špela na vrv za obešanje perila obesi sedem brisač, med katerimi so tri enake?


2. Na koliko različnih načinov lahko osmim otrokom razdelimo naslednja darila: dve enaki rumeni žogi, štiri enake modre žoge, eno zeleno in eno rdečo žogo?


3. Koliko različnih besed z devetimi črkami lahko sestavimo iz črk besede RABARBARA?


Preveri

Pravilno

Odlično!

Napačno

Poskusi ponovno. Pravilno si rešil od treh primerov.

Rešitev

1. Na različnih načinov.
2. Na različnih načinov.
3. različnih besed.

Zapomni si!

(miselni_vzorec_permutacije.jpg)

Naloga

Pazljivo preberi besedilo in ga dopolni.


Zarja razporeja frnikule v vrsto. Tri različne zelene, dve različni rdeči in štiri različne modre frnikule lahko razporedi na ! = različnih načinov. Tri različne zelene, dve različni rdeči in štiri enake modre frnikule lahko razporedi na !/ ! = različnih načinov. Tri različne zelene, dve enaki rdeči in štiri enake modre frnikule lahko razporedi na !/( ! · !) = različnih načinov. Tri enake zelene, dve enaki rdeči in štiri enake modre frnikule pa lahko razporedi na !/( ! · ! · !) = različnih načinov.


Preveri

Pravilno

Napačno

Poskusi ponovno ali poglej rešitev.

Rešitev

Zarja razporeja frnikule v vrsto. Tri različne zelene, dve različni rdeči in štiri različne modre frnikule lahko razporedi na 9 ! = 362880 različnih načinov. Tri različne zelene, dve različni rdeči in štiri enake modre frnikule lahko razporedi na 9 !/ 4 = 15120 različnih načinov. Tri različne zelene, dve enaki rdeči in štiri enake modre frnikule lahko razporedi na 9 !/( 2 ! · 4 !) = 7560 različnih načinov. Tri enake zelene, dve enaki rdeči in štiri enake modre frnikule pa lahko razporedi na 9 !/( 3 ! · 2 ! · 4 !) = 1260 različnih načinov.

Razstava fotografij

V poglavju Pravilo vsote in produkta smo spoznali dijake, ki so se odpravili na maturantski izlet v Grčijo. Naši maturantje so varno prispeli na Santorini. Poglejmo, kako se je začel njihov teden, poln dogodivščin.


Dijaki so že prvi večer imeli kar nekaj fotografij. Odločili so se, da bodo najboljše fotografije razstavili v hotelski klubski sobi, kjer si bo lahko vsak izbral tiste, ki bi jih želel za spomin. Tako so se dogovorili, da bodo že prvi večer razstavili v vrsto štiri različne fotografije z ladje, dve različni fotografiji iz Aten in tri različne fotografije s Santorinija.


Na koliko različnih načinov lahko dijaki razstavijo fotografije?


Preveri

Pravilno

Točno! Razporejamo vseh DEVET med seboj različnih fotografij, pri čemer JE vrstni red pomemben. Torej računamo število permutacij brez ponavljanja devetih elementov. Fotografije lahko razporedijo na različnih načinov.
Nalogo pa lahko rešimo tudi s pravilom produkta:

1.FOTOGRAFIJAin2.FOTOGRAFIJAin3.FOTOGRAFIJAinin8.FOTOGRAFIJAin9.FOTOGRAFIJA
\cdot\cdot\cdot\cdot\cdot

Napačno

Ne bo držalo! Razporejamo vseh DEVET med seboj različnih fotografij, pri čemer JE vrstni red pomemben. Na koliko različnih načinov torej lahko razstavimo fotografije?

Razstava fotografij

Na koliko različnih načinov pa lahko razstavijo fotografije, če morajo biti na začetku fotografije z ladje, nato iz Aten in na koncu s Santorinija?

(bazen.JPG)
Bazen na ladji


Preveri

Pravilno

Točno! Na začetku razporedimo v vrsto vse ŠTIRI med seboj različne fotografije z ladje (na različnih načinov) IN za njimi obe DVE med seboj različni fotografiji iz Aten (na različnih načinov) IN na koncu vse TRI med seboj različne fotografije s Santorinija (na različnih načinov). Fotografije torej lahko razporedimo na različnih načinov. Nalogo pa lahko rešimo tudi s pravilom produkta:

LinLinLinLinAinAinSinSinS
\cdot\cdot\cdot\cdot\cdot\cdot\cdot

V tabeli so z L označene fotografije z Ladje, z A fotografije iz Aten in s S fotografije s Santorinija.)

Napačno

Ne bo držalo! Na začetku razporedimo v vrsto vse ŠTIRI med seboj različne fotografije z ladje (na različnih načinov) IN za njimi obe DVE med seboj različni fotografiji iz Aten (na različnih načinov) IN na koncu vse TRI med seboj različne fotografije s Santorinija (na različnih načinov). Na koliko različnih načinov torej lahko razstavimo fotografije?

Razstava fotografij

Na koliko različnih načinov lahko razstavijo fotografije, če morajo biti te ločene po krajih, kjer so nastale?


Preveri

Pravilno

Točno! Fotografije, ki jih razstavljamo, so nastale v TREH različnih krajih (na ladji, v Atenah in na Santoriniju). Skupine fotografij torej lahko permutirajo na različnih načinov. Hkrati lahko permutirajo tudi vse ŠTIRI med seboj različne fotografije z ladje (na različnih načinov) IN obe DVE med seboj različni fotografiji iz Aten (na različnih načinov) IN vse TRI med seboj različne fotografije s Santorinija (na različnih načinov). Fotografije torej lahko razporedimo na različnih načinov.

Napačno

Ne bo držalo! Fotografije, ki jih razstavljamo, so nastale v TREH različnih krajih (na ladji, v Atenah in na Santoriniju). Skupine fotografij torej lahko permutirajo na 3! različnih načinov. Hkrati lahko permutirajo tudi vse ŠTIRI med seboj različne fotografije z ladje (na različnih načinov) IN obe DVE med seboj različni fotografiji iz Aten (na različnih načinov) IN vse TRI med seboj različne fotografije s Santorinija (na različnih načinov). Na koliko različnih načinov torej lahko razstavimo fotografije?

Razstava fotografij

Na koliko različnih načinov lahko razstavijo fotografije, če morajo biti fotografije s Santorinija skupaj?

(atene.JPG)
Atene


Preveri

Pravilno

Točno! Fotografije s Santorinija morajo stati skupaj, zato vzemimo te tri fotografije kot en element. Vseh možnih razporeditev je v tem primeru . Hkrati lahko permutirajo tudi vse tri fotografije s Santorinija, in sicer na različnih načinov. Fotografije torej lahko razporedimo na različnih načinov.

Napačno

Ne bo držalo! Fotografije s Santorinija morajo stati skupaj, zato vzemimo te tri fotografije kot en element. Vseh možnih razporeditev je v tem primeru . Hkrati lahko permutirajo tudi vse tri fotografije s Santorinija, in sicer na različnih načinov. Na koliko različnih načinov torej lahko razporedimo fotografije?

Razstava fotografij

Dijaki so si med razstavljenimi fotografijami izbrali tiste, ki so jih želeli za spomin. Tako je bila stena klubske sobe spet prazna. Naslednji dan so se odločili, da jih bodo spet razstavili, vendar bodo tistih fotografij, po katerih je večje povpraševanje, razstavili po več enakih. Tokrat bodo postavili v vrsto štiri enake fotografije z ladje, dve različni fotografiji iz Aten in tri enake fotografije s Santorinija.


Na koliko različnih načinov lahko dijaki razstavijo fotografije?


Preveri

Pravilno

Točno! Razporejamo vseh DEVET fotografij, med katerimi so ŠTIRI fotografije z ladje med seboj enake, enako velja za TRI fotografije s Santorinija. Vrstni red razporejanja JE pomemben. Torej računamo število permutacij s ponavljanjem devetih elementov, kjer se en element ponovi štirikrat, drugi pa trikrat. Fotografije lahko razporedijo na različnih načinov.

Napačno

Ne bo držalo! Razporejamo vseh DEVET fotografij, med katerimi so ŠTIRI fotografije z ladje med seboj enake, enako velja za TRI fotografije s Santorinija. Vrstni red razporejanja JE pomemben. Na koliko različnih načinov torej lahko razporedimo fotografije?

Naši dijaki so ves teden izmenjevali fotografije tako, da so domov prinesli poln album, ki jih bo spominjal na nepozabna doživetja.

Dodatne naloge

1. naloga

Poveži!



Preveri

Pravilno

Napačno

Poskusi ponovno.

Dodatne naloge

2. naloga

Zapiši vse permutacije črk besede:


a) KRT


KRT, KTR, RKT, RTK
KRT, KTR, RKT, RTK, TKR in TRK, KTR
KRT, KTR, RKT, RTK, TKR in TRK

Pravilno

Napačno

Še enkrat poskusi.

Rešitev

KRT, KTR, RKT, RTK, TKR in TRK

Dodatne naloge

2. naloga

Zapiši vse permutacije črk besede:


b) ARARA.


AAARR, AARAR, AARRA, ARAAR, ARARA, ARRAA, RAAAR, RAARA, RARAA, RRAA
AAARR, AARAR, AARRA, ARAAR, ARARA, RAAAR, RAARA, RARAA, RRAAA
AAARR, AARAR, AARRA, ARAAR, ARARA, ARRAA, RAAAR, RAARA, RARAA, RRAAA

Pravilno

Napačno

Še enkrat poskusi.

Rešitev

AAARR, AARAR, AARRA, ARAAR, ARARA, ARRAA, RAAAR, RAARA, RARAA, RRAAA

Dodatne naloge

3. naloga

Koliko različnih besed s sedmimi črkami lahko sestavimo iz črk besede MO JSTER, če se črke ne smejo ponavljati in


a) ni dodatnih pogojev?


b) se mora beseda začeti s samoglasnikom?


Odgovor a):


Odgovor b):


Preveri

Pravilno

Napačno

b) odgovor je napačen.

Napačno

a) odgovor je napačen.

Napačno

Poskusi ponovno. Oba odgovora sta napačna.

Rešitev

Odgovor a): 5040
Odgovor b): 1440

Dodatne naloge

4. naloga

Koliko različnih besed s šestimi črkami lahko sestavimo iz črk besede BANANA?


Odgovor:


Preveri

Pravilno

Napačno

Poskusi ponovno.

Rešitev

Odgovor je 60.

Dodatne naloge

5. naloga

Na koliko različnih načinov se lahko deset sošolcev postavi v vrsto za malico?


Odgovor:


Preveri

Pravilno

Napačno

Poskusi ponovno.

Rešitev

Odgovor je 3628800.

Dodatne naloge

6. naloga

Na konjski dirki tekmuje osem konjev. Koliko različnih izidov tekme je možnih?


Odgovor:


Preveri

Pravilno

Napačno

Poskusi ponovno.

Rešitev

Odgovor je 40320.

Dodatne naloge

7. naloga

Na koliko različnih načinov lahko razporedimo na knjižno polico tri različne romane in pet različnih priročnikov, če morajo romani stati skupaj?


Odgovor:


Preveri

Pravilno

Napačno

Poskusi ponovno.

Rešitev

Odgovor je 4320.

Dodatne naloge

8. naloga

Na koliko različnih načinov lahko razporedimo v vrsto tri različne stožce, pet enakih piramid in dve različni krogli?


Odgovor:


Preveri

Pravilno

Napačno

Poskusi ponovno.

Rešitev

Odgovor je 30240.

Dodatne naloge

9. naloga

Imamo dve enaki rdeči, tri enake rumene in štiri enake modre zastavice. Koliko različnih signalov lahko tvorimo, če za vsak signal porabimo vse zastavice?


Odgovor:


Preveri

Pravilno

Napačno

Poskusi ponovno.

Rešitev

Odgovor je 1260.
0%
0%