Matematika 3 - 10.4 Permutacije

Permutacije bez ponavljanja

Zanimljivost

Permutacija dolazi od latinske riječi permutatio, što znači promjena, zamjena. Pojam su poznavali još stari Indijci. U Europu ga je uveo britanski matematičar Andre Tacqet 1566. godine. U današnjem značenju pojam permutacija je ušao u upotrebu tek nakon Jakoba Bernoullija (koji ga spominje u djelu Ars Conjectandi objavljenom nakon njegove smrti).

Permutacija

Permutacija ili premještanje elemenata $n$ -članog skupa je uređena $n$ -torka svih elemenata (važan je poredak elemenata).

Pogledajte sljedeću animaciju pa odgovorite na pitanja.

Kolekcija zadataka #1

Pri permutiranju svih elemenata $n$ -članog skupa (kao u animaciji) redoslijed elemenata je važan.

Pomoć:

Razlikuju se slučajevi kada su elementi na različitim mjestima.

null

Elementi skupa (kao u animaciji) mogu se ponavljati.

Pomoć:

Ne može ista osoba biti istovremeno na dva mjesta (na dvije stolice).

null

Promatramo permutacije svih elemenata skupa.

Pomoć:

Radi se o uređenim $n$ -torkama.

null

Broj permutacija svih elemenata

n

-članog skupa jednak je

Koristite se kraćim zapisom umnoška prvih

n

prirodnih brojeva.

gdje je

ukupan

broj elemenata danog skupa.

null

Permutacije bez ponavljanja

Broj permutacija bez ponavljanja skupa od $n$ elemenata jednak je $P_{n} = n! .$

Kolekcija zadataka #2

Na koliko načina možemo složiti $5$ različitih knjiga na hrpu?

To je moguće učiniti na

!

načina što je jednako

Izračunajte

5!

null

Koliko različitih brojeva možemo dobiti od parnih znamenaka tako da se ni jedna znamenka ne ponavlja? Pripazite na nulu koja je paran broj.

Na prvo mjesto može doći bilo koja znameka iz skupa $\{2, 4, 6, 8\}$ pa je moguće to učiniti na $4$ načina. Nakon toga permutiramo 4 preostala parna broja. Prema načelu umnoška vrijedi $4 \cdot 4! = 96 .$

Koliko boja permutiramo ako je broj svih mogućih permutacija različitih boja jednak $720 ?$

Imamo

Traži se

n

za koji vrijedi

n! = 720

različitih

boja jer je

! =

null

Možemo li zadatak s permutacijama riješiti koristeći se formulom varijacija bez ponavljanja?

Prije nego što odgovorimo na to pitanje, razmislimo što bi bio $r$ ako tražimo ukupan broj uređenih $n$ -torki?

r =

Ukupan broj elemenata koje permutiramo.

pa u formuli za varijacije

n

-tog razreda od

n

elemenata imamo

Ako znamo da ima

r

faktora, koliko ih je sada ako je

n = r ?

faktora.

Dakle,

V_{n}^{r} = V_{n}^{n} = n (n - 1) \cdot . . . \cdot (n - (n - 1)) =

Umnožak prvih

n

prirodnih brojeva.

Iz prikaza s pomoću faktorijela

V_{n}^{r} = \frac{n!}{(n - r)!} \Rightarrow V_{n}^{n} = \frac{n!}{(n - n)!} = \frac{n!}{0!} .

Nakon izjednačavanja rezultata slijedi jednakost

\frac{n!}{0!} = n!

iz koje možemo vidjeti smisao definiranja

0! =

null

Permutacije s ponavljanjem

Od koliko se slova sastoji riječ PERMUTACIJE?

Riječ se sastoji od

Prebrojite sva slova riječi.

slova

od kojih se

Koliko se slova ponavlja?

slovo

ponavlja. To je slovo

Koje se slovo ponavlja?

u riječi se ponavlja

puta.

null

Ako bismo ova dva slova "e" razlikovali, tada bismo imali ukupno

! = 39 916 800

permutacija tih slova.
Koliko imamo različitih slova?
Ima

različitih

slova.

null

Pogledajmo primjere permutacije tih slova na slici.

Koliko imamo ukupno istih permutacija?

što

znači da ukupan broj permutacija od

11

elemenata trebamo

kako

bismo dobili točan broj permutacija (kada se slovo "E" ponavlja dvaput).
Broj permutacija od

11

slova od kojih su dva jednaka jednak je

Pomoć:

$11!$ podijelite s dva.

null

Primjer 1.

Izračunajmo koliko ima permutacija elemenata skupa $\{1, 1, 1, 3, 5, 7\} .$

Uočimo kakvi su elementi skupa te odgovorimo na sljedeća pitanja.

Skup ima

Prebrojite koliko ima elemenata dani skup.

elemenata.

Od toga su

jednaka.

null

Koji elementi ne permutiraju?

Kada bismo razlikovali ove jedinice, u svih nabrojenih šest permutacija, mjesta ne mijenjaju brojevi

Permutacija brojki od kojih su tri iste.

1

3

5

7

null

Brojka $1$ izmjenjuje se na istim pozicijama (prvoj, trećoj i petoj). Na koliko je načina moguće permutirati te tri boje brojke $1 ?$

To je moguće učiniti na

Koliko se boja izmjenjuje?

! =

Izračunjate

3!

načina.

null

$6$ jednakih permutacija prikazujemo samo jednom $1 3 1 5 1 7$ pa se ukupan broj permutacija umanjuje $6$ puta.

Riješimo zadatak do kraja. Koliki je ukupan broj permutacija zadanog skupa od šest elemenata ako se tri ponavljaju?

6!

3!

\frac{6!}{3!}

6! - 3!

null

Konačno je rješenje

Izračunajte

\frac{6!}{3!} .

null

Permutacije s ponavljanjem

Broj permutacija s ponavljanjem skupa od $n$ elemenata gdje je $n_{1}$ jednakih elemenata prve vrste, $n_{2}$ jednakih elemenata druge vrste pa sve do $n_{k}$ jednakih elemenata $k$ -te vrste jednak je $P_{n}^{n_{1}, n_{2}, . . ., n_{k}} = \frac{n!}{n_{1}! \cdot n_{2}! \cdot . . . \cdot n_{k}!} .$

Primjer 2.

Roditelji su kupili $30$ sadnica cvijeća: $15$ maćuhica, $10$ dalija i $5$ begonija. Na koliko ih načina mogu rasporediti u vrtu?

Cvijeće

Ukupno imamo $30$ $(n = 30)$ elemenata skupa od kojih su tri različita $(k = 3) .$ Elemenata prve vrste ima $15 (n_{1} = 15),$ druge vrste $10 (n_{2} = 10)$ i treće vrste $5 (n_{3} = 5) .$

Iz formule za ukupan broj permutacija s ponavljanjem slijedi rješenje: $P_{n}^{n_{1}, n_{2}, n_{3}} = \frac{n!}{n_{1}! \cdot n_{2}! \cdot n_{3}!} = \frac{30!}{15! \cdot 10! \cdot 5!} = 4.658179126 \cdot 10^{11} .$

Kolekcija zadataka #3

Izračunjate

P_{10}^{4,3} =

null

Koliko se peteroznamenkastih parnih brojeva može dobiti s pomoću znamenaka $1,$ $2,$ $4,$ $4,$ $6 ?$

Izračunajmo najprije koliko se svih peteroznamenkastih brojeva može dobiti s pomoću znamenaka

1,

2,

4,

4,

6 :

Izračunajte

\frac{5!}{2!} .

null

Brojevi koji na zadnjemu mjestu imaju znamenku $1$ su neparni. Da bismo dobili samo parne brojeve trebamo od ukupnog broja permutacija

sve

čiji

ćemo ukupan broj dobiti ako permutiramo brojeve

2,

4,

4,

6

(bez zadnje znamenke

1

jer je broj neparan).

null

Ukupan broj tih permutacija jest

Izračunajte

\frac{4!}{2!} .

Peteroznamenkastih parnih brojeva sa znamenkama

1,

2,

4,

4,

6

ima

Izračunajte

\frac{5!}{2!} - \frac{4!}{2!} .

null

Imate $10$ Legovih kockica. Na koliko načina možete složiti te kockice ako je $5$ bijelih i $5$ crvenih kockica?

To je moguće učiniti na

Izračunajte

\frac{10!}{5! \cdot 5!} .

načina.

null

...i na kraju

Ponovimo permutacije i varijacije!

I u jednima i u drugima je važan poredak, odnosno brojimo ukupan broj uređenih $r$ -torki ili $n$ -torki.

	Permutacije bez ponavljanja	Permutacije s ponavljanjem	Varijacije bez ponavljanja	Varijacije s ponavljanjem
Svi elementi skupa	DA	DA	NE	NE
Elementi se ponavljaju	NE	DA	NE	DA
Oznaka	$P_{n}$	$P_{n}^{n_{1}, n_{2}, . . ., n_{k}}$	$V_{n}^{r}$	$\bar{V_{n}^{r}}$
Formula	$n!$	$\frac{n!}{n_{1}! \cdot n_{2}! \cdot . . . \cdot n_{k}!}$	$\frac{n!}{(n - r)!}$	$n^{r}$

Razlikujete li zadatke s permutacijama i varijacijama?

Zaigrajte igru labirinta. Za svaki zadatak trebate pogoditi je li riječ o permutacijama ili o varijacijama, s ponavljanjem ili bez ponavljanja, a zatim zadatak točno riješiti. Nakon toga otvorit će vam se vrata prema izlazu. Ako pogriješite, vraćate se na lakši zadatak iz istog područja. Ako niste svladali neko od područja, nakon tri pitanja vraćate se na početni položaj. Na početnom položaju dobijete povratnu informaciju koje gradivo trebate ponoviti i tek onda se možete vratiti u labirint i početi ispočetka.

Povećaj interaktivni prikaz

Na početku...

Permutacije bez ponavljanja

Zanimljivost

Permutacija

Kolekcija zadataka #1

Permutacije bez ponavljanja

Kolekcija zadataka #2

Permutacije s ponavljanjem

Primjer 1.

Permutacije s ponavljanjem

Primjer 2.

Kolekcija zadataka #3

...i na kraju