Poglavlje 1
ELEMENTI KOMBINATORIKE

KOMBINATORIKA je grana grana matematike koja se bavi osnovnim svojstvima konačnih skupova i metodama prebrojavanja. Poznati kombinatorni problemi su: problem izbora upravnog odbora, problem mostova u Konigsbergu, problem magičnih kvadrata, problem 4 boje. Zadatak ovog poglavlja je da se upozanju metode prebrojavanja koje će se iskoristiti za računanje vjerojatnosti slučajnih dogadaja.

1.1 UVOD

MOTIV 1.1

(a) Kolika je suma prvih 1000 prirodnih brojeva?
(b) Dokažite da vrijedi formula

 n
∑  k =  1n(n + 1)    ∀n ∈ ℕ.
        2
k=1

TEOREM 1.1 AKSIOM MATEMATIČKE INDUKCIJE (AMI)

Neka je skup prirodnih brojeva. Ako je M , i vrijedi:

onda je M = .

AMI primijenjujemo pri dokazivanju općenite valjanosti formula koje sadrže varijablu n .

PRIMJER 1.1 motiv

Dokažite da vrijedi formula

∑n      1
   k =  2n(n + 1)    ∀n ∈ ℕ.
k=1

Rješenje:
Neka je M = {                        }
         ∑n     1
  n ∈ ℕ :k=1k = 2n(n + 1).
Pomoću AMI želimo dokazati da je M = .
(B.I) baza indukcije: 1 M:

 1
∑  k  =   11(1+ 1)
k=1       2
   1  =   1.
(P.I.) pretpostavka indukcije m M:
∑m     1
   k = --m(m  + 1).
k=1    2
(K.I.) Treba dokazati da (P.I.) implicira da je m + 1 M tj.
m∑+1     1
    k = 2(m + 1 )(m +  2).
k=1
Računamo:
m∑+1       ∑m
    k  =      k + (m + 1)
k=1       k=1
       =  (P.I.)
          1-
       =  2 m (m  + 1)+ (m + 1)
          1
       =  2-(m + 1)(m + 2).

Zaključujemo prema AMI da je  M = .

Definicija 1.1

(FAKTORIJEL)

Za prirodan broj n , definiramo prirodan broj ”n faktorijela” u oznaci n! sa:

n! = 1⋅ 2⋅3 ⋅...⋅n,

a dogovorno 0! = 1.

(BINOMNI KOEFICIJENT)

Neka su n,k ,k n. Binomni koeficijent je prirodni broj u oznaci

( )
 nk (”n povrh k”) definiran na sljedeći način:

(  )
 n  =  n(n---1)⋅...⋅(n---k-+-1)=  ---n!----,
 k           1 ⋅2⋅ ...⋅k          k!(n - k)!

a dogovorno: (  )
  n0 = 1, ( )
 00 = 1.

NAPOMENA 1.1 Stirlingova formula

Za približno izračunavanje faktorijela velikih brojeva možemo primijeniti aproksimativnu Stirlingovu formulu:

      n   -n√ ----
n! ≈ n  ⋅e    2πn.

PRIMJER 1.2 Izračunajte 5! pomoću Stirlingove formule. Kolika je greška aproksimacije?

Rješenje:
Pomoću Stirlingove formule računamo 5! 55 e-5√ ----
  2π5 = 118.019. Kako je po definiciji 5! = 1 2 3 4 5 = 120 greška aproksimacije je 1.981.

PRIMJER 1.3

T: Svojstva binomnih koeficijenata:

Rješenje:
D: tko želi znati više

TEOREM 1.2 (BINOMNI TEOREM)

Neka su a,b ,n . Binomni teorem izražava razvoj n-te potencije binoma formulom:

           n
      n   ∑   (n)  k n-k
(a + b)  =      k  a b   ,    ∀n ∈ ℕ
          k=0
.

Dokaz: tko želi znati više
Tvrdnja se dokazuje pomoću aksioma matematičke indukcije (AMI). Neka je

     {                                }
                    n   ∑n (n )  kn- k
M  =  n ∈ ℕ : (a + b) =     k  a b      .
                        k=0
Treba dokazati da je M = .
(B.I) 1 M:
             ∑1 ( )
(a + b)1  =       1k  a1b1- k
             k=0
   a+ b  =   b+ a.
(P.I.) m M:
      m    m∑  (m  ) k m -k
(a + b) =       k  a b
           k=0
(K.I.) Treba pokazati koristeći (P.I.) da je m + 1 M tj.
             m+1 (      )
(a + b)m+1 = ∑     m + 1  akbm+1 -k.
                     k
             k=0
Računamo
(a+ b)m+1   =  (a+  b)m (a+ b)

            =  P.I.
               ∑m ( m )
            =           akbm-k *(a + b)
               k=0  k
               ∑m ( m )            ∑m ( m )
            =           ak+1bm-k +         akbm+1 -k
               k=0  k              k=0  k
   m∑-1(   )            (  )          (  )          ∑m (   )
=        m  ak+1bm -k +  m   am+1b0 +  m   a0bm+1 +      m  akbm+1 -k
    k=0  k               m              0           k=1  k
    m  (     )             (  )        (  )           m (   )
=  ∑      m    akbm+1 -k +  m   am+1b0  m   a0bm+1 + ∑    m  akbm+1 -k
   k=1   k - 1              m           0            k=1  k
   (   )          m  (      )   (   )            (  )
=    m   a0bm+1 +  ∑  [  m     +  m   ]akbm+1 -k +  m   am+1b0
     0                 k - 1      k               m
   (       )      k=1   m (      )   (   )            (      )
=    m +  1  a0bm+1 + ∑  [   m    +   m  ]akbm+1 -k +   m + 1  am+1b0
       0                   k - 1      k                m + 1
   (       )          k=m1(       )            (      )
     m +  1   0 m+1   ∑    m + 1   k m+1 -k    m  + 1   m+1  0
=      0     a b    +        k    a b       +  m  + 1  a    b
       (       )      k=1
   m+∑1   m + 1    k m+1-k
=          k     a b     .
    k=0
Zaključujemo prema AMI da je  M = .

1.2 PRINCIPI PREBROJAVANJA

MOTIV 1.2

U gradu ima 8 studentskih restorana ravnomjerno rasporedenih u 4 gradske četvrti. U okolini svakog restorana nalaze se dvije sportske dvorane. Student želi unajmiti stan. Na koliko načina može odabrati četvrt, studentski restoran i sportsku dvoranu ako: a) nije bitno ni da studentski restoran bude u istoj četvrti niti dvorana; b) nije bitno da studentski restoran bude u istoj četvrti ali dvorana treba biti; c) sve bude u najbližoj okolini.

TEOREM 1.3 (PRINCIP SUME)

Neka konačni skupovi imaju ni elemenata, ni ,i = 1,2,..,k, |Si| = ni i neka su disjunktni za svaki izbor ij, SiSj = .
Ako je S = S1 S2 ... Sk, onda skup S ima n=n1 + n2 + ... + nk elemenata:

|S1 ∪S2 ∪ ...∪ Sk| = |S1|+  |S2|+ ...+ |Sk |.

TEOREM 1.4 (PRINCIP PRODUKTA)

Neka konačni skupovi Si imaju ni elemenata, ni ,i = 1,2,..,k,
|Si| = ni. Ako je S = S1 × S2 × ... × Sk (kartezijev produkt skupova), onda skup S ima n=n1 n2 ... nk elemenata (uredenih k-torki s=(s1,s2,...,sk)):

|S1 × S2 × ...× Sk| = |S1|⋅|S2|⋅...⋅|Sk|.

PRIMJER 1.4

Bacamo dvije igraée kocke različite boje.
(a) Koliko različitih ishoda ima ako bacamo jednu za drugom?
(b) Na koliko različitih načina mogu pasti ako ih bacamo zajedno?

Rješenje:
S1 ima n1 = 6 elemenata, S2 ima n2 = 6 elemenata.
(a) S = S1 S2,  |S| = |S1| + |S2| = n1 + n2 = 12.
(b) S = S1 × S2,  |S| = |S1|⋅|S2| = n1n2 = 36.

Princip produkta ili osnovni princip kombinatorike ima drugu interpretaciju u teoremu o uzastopnom prebrojavanju.

TEOREM 1.5 ( TEOREM O UZASTOPNOM PREBROJAVANJU)

Proučavamo uredene k-torke. Neka prvi element uredene k-torke možemo izabrati na n1 načina, a za već izabrani prvi element, drugi možemo izabrati na n2 načina i tako dalje do k-tog koji možemo izabrati na nk načina. Tada uredenu k-torku možemo izabrati na n=n1 n2 ... nk načina.

PRIMJER 1.5 motiv

U gradu ima 8 studentskih restorana ravnomjerno rasporedenih u 4 gradske četvrti. U okolini svakog restorana nalaze se dvije sportske dvorane. Student želi unajmiti stan. Na koliko načina može odabrati četvrt, studentski restoran i sportsku dvoranu ako: a) nije bitno ni da studentski restoran bude u istoj četvrti niti dvorana; b) nije bitno da studentski restoran bude u istoj četvrti ali dvorana treba biti; c) sve bude u najbližoj okolini.

Rješenje:
a) n = 4816=512,
b) n = 484=128
c) n = 422=16.

1.3 PERMUTACIJE BEZ PONAVLJANJA

MOTIV 1.3

Koliko se lozinki duljine 4 znaka može formirati od slova v i c (mala slova) i brojeva 1 i 5, ako nije dozvoljeno ponavljanje znakova?

Definicija 1.2 Neka skup S ima n različitih elemenata. Svaka uredena n-torka elemenata skupa S zove se permutacija skupa S.

T: Broj svih n-članih permutacija je

P (n) = n! = n ⋅(n - 1)⋅(n - 2)⋅...⋅2⋅ 1, tj. n! = 1 ⋅2...(n- 2)(n - 1)⋅n

D: Prema teoremu o uzastopnom prebrojavanju, prvi element možemo izabrati na n načina, drugi možemo izabrati na (n - 1) načina, treći na (n - 2) načina itd.

D: tko želi znati više

Pomoću AMI po n : Neka je M = {n : Pn = n!}.
(B.I) Provjeravamo je li 1 M. Za n = 1 broj uredenih jednorki iz skupa koji ima samo 1 element jednak P1 = 1. Prema formuli n! = 1! = 1 za n = 1; Tako je 1 M.
(P.I) Pretpostavimo m M,
tj. vrijedi formula V m = m!.
(K.I) U koraku indukcije trebamo pokazati da je m + 1 M.
tj. treba pokazati da vrijedi Pm+1 = (m + 1)!.
Skup svih permutacija od m + 1 element možemo podijeliti na m + 1 podskupova u kojima su permutacije s fiksnim prvim elementom npr. a1, sve permutacije s fiksnim prvim elementom a2 itd. Tako je

Pm+1  = (m + 1)⋅Pm  = (P.I.) = (m + 1)⋅ m! = (m + 1)!,
pa smo pokazali da je m + 1 M.
Prema AMI zaključujemo da je M = .

PRIMJER 1.6 motiv

Koliko se lozinki duljine 4 znaka može formirati od slova v i c (mala slova) i brojeva 1 i 5, ako nije dozvoljeno ponavljanje znakova.

Rješenje:
Svaka lozinka je jedna permutacija bez ponavljanja n = 4-članog skupa S = {v,c,1,5}. Ukupan broj permutacija bez ponavljanja je P(4) = 4! = 1 2 3 4 = 24. Možemo formirati 24 lozinke.

PRIMJER 1.7

Koliko ima svih četveroznamenkastih brojeva sastavljenih od znamenki skupa S={1,2,3,4} takvih da se znamenke ne ponavljaju?

Rješenje:
Svaki 4-znamenkasti broj je permutacija n = 4-članog skupa S. Broj permutacija je P(4) = 4! = 1 2 3 4 = 24.

1.3.1 PERMUTACIJE S PONAVLJANJEM

MOTIV 1.4

Koliko se lozinki duljine 4 znaka može formirati od slova v i c (mala slova) i brojeva 1 i 5, ako sa slovo v ponovi 2 puta?

MOTIV 1.5

Eksperiment koji ima k=3 ishoda ponavljamo n=7 puta. Koliko je mogućih nizova eksperimenata takvih da se prvi ishod dogodi 1 put, drugi ishod 2 puta, a treć ishod 4 puta?

Definicija 1.3

Neka skup S ima n elemenata od kojih je n1 jedne vrste, n2 druge vrste, ... , nk k-te vrste, n = n1 + n2 + ... + nk. Uredena n-torka elemenata skupa S zove se n-člana permutacija s ponavljanjem.

T: Broj n-članih permutacija s ponavljanjem je

--
P n(n1,n2,...,nk) = ----n!----.
                   n1!n2!...nk!

tko želi znati više

D: Pretpostavimo da su svi elementi u permutaciji sa ponavljanjem različiti i da imamo permutaciju bez ponavljanja od n = n1 + n2 + ... + nk elemenata. Ukupan broj tih permutacija je (n1 + n2 + ... + nk)! . U permutaciji s ponavljanjem možemo zamijeniti mjesta na kojima su elementi prve vrste na n1! načina i pri tom se permutacija neće promijeniti. Slično zaključujemo i za elemnte druge, ..., k-te vrste. Za svaku permutaciju s ponavljanjem postoji n1!n2!...nk! permutacija bez ponavljanja u kojima se ne mijenja poredak različitih elemnata skupa S. Mijenjajući poredak različitih elemenata dobili bismo ukupan broj permutacija bez ponavljanja od n = n1 + n2 + ... + nk elemenata. Stoga je ukupan broj permutacija bez ponavljanja jednak (n1 + n2 + ... + nk)! = n1!n2!...nk!Pn(n1,n2,...,nk). Otuda slijedi da je ukupan broj permutacija s ponavanjem dan formulom

--                     n!
P n(n1,n2,...,nk) = ----------.
                   n1!n2!...nk!

PRIMJER 1.8 motiv

Koliko se lozinki duljine 4 znaka može formirati od slova v (malo slovo) i brojeva 1 i 5, ako se slovo v ponovi 2 puta?

Rješenje:
Lozinka je je 4-člana permutacija s ponavljanjem elemenata iz skupa S = {v,v,1,5}, tako da je n = n1 + n2 + n3 = 2 + 1 + 1 = 4. Broj permutacija s ponavljanjem je Pn(n1,n2,...,nk) = P4(2,1,1) = -4!-
2!1!1! = 12. Možemo formirati 12 lozinki.

PRIMJER 1.9

Koliko ima peteroznamenkastih brojeva sastavljenih od znamenki iz skupa S = {1,2,3,4}, takvih da se znamenke ponavljaju i to znamenka 1 dva puta?

Rješenje:
Svaki 5-znamenkasti broj je 5-člana permutacija s ponavljanjem elemenata tako da je n = n1 + n2 + n3 + n4 = 2 + 1 + 1 + 1 = 5. Broj permutacija je Pn(n1,n2,...,nk) = P5(2,1,1,1) = -5!---
2!1!1!1! = 60.

PRIMJER 1.10

U kutiji je 10 kuglica: 4 crne, 2 bijele, 2 crvene, 1 zelene i 1 plava. Izvlačim ih jednu po jednu i slažem po redu u niz. (zapišemo i vratimo). Koliko mogućih nizova možemo napraviti?

Rješenje:
Svaki niz duljine 10 je permutacija s ponavljanjem, tako da je n = n1 + n2 + n3 + n4 + n5 = 4 + 2 + 2 + 1 + 1 = 10. Broj permutacija je Pn(n1,n2,...,nk) = P10(4,2,2,1,1) = 4!12!02!!1!1! = 604800.

PRIMJER 1.11

Koliko različitih riječi se može napraviti od slova u riječi VIVAMARIA?

Rješenje: P9(2,2,3).

PRIMJER 1.12 Uzorak s vraćanjem

Skup S ima n elemenata od kojih je n1 jedne vrste, n2druge vrste, ... , nk k-te vrste, n=n1 + n2 + ... + nk. Uredena r-torka ima r1 elemenata prve skupine, r2 elemenata druge skupine, ...,rk elemenata k - te skupine r=r1+r2+...+rk. Broj uredenih r-torki s vraćanjem je:

--
P r(r1,r2,...,rk)⋅(n1)r1(n2)r2 ⋅...⋅(nk )rk.

Ako je n veliki a r mali u odnosu na n možemo odrediti broj uredenih r-torki s vraćanjem:

--
Pr(r1,r2,...,rk).

PRIMJER 1.13

U velikoj kutiji su crvene, bijele i plave olovke. Na koliko načina možemo izabrati uzorak od 9 olovaka takav da su 2 crvene, 3 bijele i 4 plave olovke.

Rješenje:
Koristimo formulu za uzorak s vraćanjem (veliki n u odnosu na r).
Osnovni skup je velik n(nepoznat)). Uzorak je uredena r-torka sastavljena od r = r1 + r2 + r3 =2+3+4=9 olovaka.
Broj uzoraka je broj uzoraka s vraćanjem je P9(4,2,3).

PRIMJER 1.14 motiv

Ponavljamo eksperiment koji ima k=3 ishoda n=7 puta a da se uvjeti eksperimenta ne mijenjaju. Broj mogućih nizova eksperimenata takvih da se prvi ishod dogodi n1 = 1 puta, n2 = 2 puta,...,k-ti ishod nk = 4 puta je:

P-n(n1,n2,...,nk ),
--             7!
P7(1,2,4) = --------.
            1!⋅2!⋅4!
jer je broj različitih nizova eksperimenata jednak broju uzoraka s vraćanjem.

1.4 VARIJACIJE BEZ PONAVLJANJA

MOTIV 1.6

(a) Koliko se lozinki duljine 4 znaka može formirati od slova v i c (mala slova) i brojeva 1 i 5, ako nije dozvoljeno ponavljanje znakova
(b) Koliko se lozinki duljine 3 znaka može formirati od slova v i c (mala slova) i brojeva 1 i 5, ako nije dozvoljeno ponavljanje znakova

Definicija 1.4 Neka skup S ima n različitih elemenata. Uredena r-torka (r n) elemenata skupa S zove se varijacija r-tog razreda od n elemenata.

T: Broj svih varijacija r-tog razreda od n elemenata je

 (r)                                     n!
Vn  = n (n - 1)(n - 2)⋅...⋅(n - r + 1 ) = (n---r)!.
V n(n) = P(n) = n!

D: Prema teoremu o uzastopnom prebrojavanju, prvi element možemo izabrati na n načina, drugi možemo izabrati na (n - 1) načina, treći na (n - 2) načina, r-ti na (n - r + 1) način.

D: tko želi znati više

Pomoću AMI po n : Neka je M = {n : V n(r) = --n!-
(n-r)!, 1 r n}.
(B.I) Provjeravamo je li 1 M. Za n = 1 parametar 1 r n može poprimiti samo vrijednost r = 1 pa je broj uredenih jednoorki iz skupa koji ima samo 1 element jednak V 1(1) = 1. Prema formuli -n!--
(n- r)! = -1!--
(1- 1)! = 1 za n = 1; Tako je 1 M.
(P.I) Pretpostavimo m M,
pa tada za svaki dani 1 r m vrijedi formula V m(r) = --m!--
(m-r)!.
(K.I) U koraku indukcije trebamo pokazati da je m + 1 M.
(i) Ako je r = 1 onda je očito broj svih uredenih jeednorki iz skupa koji ima m + 1 element jednak V m+1(1) = m + 1. Prema formuli -n!--
(n- r)! = -(m+1-)!-
(m+1 -1)! = (m + 1) za n = m + 1 i r = 1.
Tako je m + 1 M za r = 1.
(ii) Ako je 2 r m + 1 treba pokazati da vrijedi V m+1(r) = -(m+1-)!--
(m+1 -r)!.
Za svaki fiksni r možemo skup svih varijacija podijeliti na m + 1 podskupove u kojima su varijacije s fiksnim prvim elementom npr. a1, sve varijacije s fiksnim prvim elementom a2 itd. Tako je

V (r) =  (m  + 1)⋅V (r-1) = (P.I.) = (m + 1)⋅ ----m!------= --(m-+-1)!-.
 m+1             m                        (m  - r + 1)!  (m + 1 - r)!
Tako smo pokazali da je m + 1 M za 2 r m + 1.
Prema AMI zaključujemo da je M = .

PRIMJER 1.15 motiv

(a) Koliko se lozinki duljine 4 znaka može formirati od slova v i c (mala slova) i brojeva 1 i 5, ako nije dozvoljeno ponavljanje znakova
(b) Koliko se lozinki duljine 3 znaka može formirati od slova v i c (mala slova) i brojeva 1 i 5, ako nije dozvoljeno ponavljanje znakova

Rješenje:
(a) Lozinka duljine 4 znaka je jedna varijacija 4.tog razreda od n = 4-članog skupaS = {v,c,1,5} tj. permutacija bez ponavljanja od 4 elementa. Broj varijacija je V 4(4) = P(4) = 4! = 24. Možemo formirati 24 lozinke. (b) Lozinka duljine 3 znaka je jedna varijacija 3-eg razreda od n = 4-članog skupaS = {v,c,1,5}. Broj varijacija je V 4(3) =   4!
(4-3)! = 24. Možemo formirati 24 lozinke.

PRIMJER 1.16

Koliko ima dvoznamenkastih brojeva sastavljenih od znamenki iz skupa S={1,2,3,4}, takvih da se znamenke ne ponavljaju?

Rješenje:
Svaki 2-znamenkasti broj je varijacija 2-og razreda od n = 4-članog skupa S. Broj varijacija je V 4(2) = --4!-
(4-2)! = 12..

PRIMJER 1.17

Koliko ima četveroznamenkastih brojeva sastavljenih od znamenki iz skupa S={0,1,2,5,7}, takvih da se znamenke ne ponavljaju?

Rješenje:
Svaki 4-znamenkasti broj je varijacija 4-og razreda od n = 5 elemeata. Broj varijacija je V 5(4) = --5!--
(5- 4)! = 120.
Nula ne može biti na prvom mjestu pa od V 5(4) moramo oduzeti sve varijacije 3-eg razreda od 4 elementa V 4(3) = (44-!3)! = 24. Traženih brojeva ima V 5(4) -V 4(3) = 120 - 24 = 96.

PRIMJER 1.18

Koliko ima četveroznamenkastih brojeva djeljivih s 5 sastavljenih od znamenki iz skupa S = {0,1,2,5,7}, takvih da se znamenke ne ponavljaju?

Rješenje:
Broj je djeljiv s 5 ako mu je zadnja znamenka 0 ili 5.
Prvo, fiksiramo zadnju znamenku 5.
Svaki takav troznamenkasti broj je varijacija 3-eg razreda od n = 4-članog skupa
S = {0,1,2,7}. Broj varijacija je V 4(3) = --4!--
(4- 3)! = 24.
Nula ne može biti na prvom mjestu pa od V 4(3) moramo oduzeti sve varijacije 2-og razreda od 3 elementa iz skupa {1,2,7} V 3(2) = (33-!2)! = 6.
Zatim, fiksiramo zadnju znamenku 0. Svaki takav 3-znamenkasti broj je varijacija 3-eg razreda od n = 4-članog skupa
S = {1,2,5,7}, pa ih ukupno ima V 4(3) = (44-!3)! = 24.
Ukupan broj traženih brojeva je V 4(3) - V 3(2) + V 4(3) = 24 - 6 + 24 = 42.

PRIMJER 1.19

Na koliko se načina u razredu u kojem je 30 učenika može odabrati glumačka družina za ”Crvenkapicu”? Likovi su Crvenkapica, vuk, baka i lovac.

Rješenje: V 30(4).

1.4.1 VARIJACIJE S PONAVLJANJEM

MOTIV 1.7

Koliko se lozinki duljine 4 znaka može formirati od slova v i c (mala slova) i brojeva 1 i 5, ako je dozvoljeno ponavljanje znakova.

Definicija 1.5

Neka skup S ima n različitih elemenata. Uredena r-torka elemenata n-članog skupa S ali tako da se elementi mogu i ponavljati (r može biti i veće od n) zove se varijacija s ponavljanjem r-tog razreda od n elemenata.

T: Broj varijacija s ponavljanjem r-tog razreda od n elemenata

V-(r) = nr.
  n

D: Prema teoremu o uzastopnom prebrojavanju, prvi element možemo izabrati na n načina, drugi možemo izabrati na n načina, treći na n načina, itd., r-ti na n načina jer je dozvoljeno ponavljanje elemenata iz skupa S.

D: tko želi znati više

Pomoću AMI po r : Neka je M = {r : V n(r) = nr, n }.
(B.I) Provjeravamo je li 1 M. Za r = 1 broj uredenih jednorki iz skupa koji ima samo n element jednak V n(1) = n. Prema formuli nr = n1 = n za r = 1; pa je 1 M.
(P.I) Pretpostavimo da je m M,
tj. vrijedi formula V m(r) = nm.
(K.I) U koraku indukcije trebamo pokazati da je m + 1 M.
tj. treba pokazati da vrijedi V n(m+1) = nm+1.
Skup svih varijacija s ponavljanjem možemo podijeliti na n podskupova u kojima su varijacije s ponavljanjem s fiksnim prvim elementom npr. a1, sve varijacije s fiksnim prvim elementom a2 itd. Tako je

--(m+1)     --(m)               m    m+1
V n     = n⋅V n   = (P.I.) = n⋅ n  = n    .
Pokazali da je m + 1 M za n .
Prema AMI zaključujemo da je M = .

PRIMJER 1.20 motiv

(a) Koliko se lozinki duljine 4 znaka može formirati od slova v i c (mala slova) i brojeva 1 i 5, ako je dozvoljeno ponavljanje znakova. (b) Koliko se lozinki duljine 3 znaka može formirati od slova v i c (mala slova) i brojeva 1 i 5, ako je dozvoljeno ponavljanje znakova.

Rješenje:
(a) Lozinka je varijacija s ponavljanjem 4-tog razreda od n = 4-članog skupa S = v,c,1,5. Broj varijacija je V 4(4) = 44 = 256. Možemo formirati 256 lozinki.
(b) Lozinka je varijacija s ponavljanjem 3-tog razreda od n = 4-članog skupa S = v,c,1,5. Broj varijacija je V 4(3) = 43 = 64. Možemo formirati 256 lozinki.

PRIMJER 1.21

Koliko ima dvoznamenkastih brojeva sastavljenih od znamenki iz skupa S = {1,2,3,4}, takvih da se znamenke ponavljaju?

Rješenje:
Svaki takav dvoznamenkasti broj je varijacija s ponavljanjem 2-og razreda od n = 4-članog skupa S. Broj varijacija je V 4(2) = 42 = 16.

PRIMJER 1.22 Razdioba različitih predmeta

Svaka razdioba r različitih predmeta na n različitih mjesta je varijacija s ponavljanjem r-tog razreda od n elemenata. Broj razdioba je: V n(r).

PRIMJER 1.23

3 kuglice različitih boja rasporedujemo u 6 kutija. Koliko razdioba možemo dobiti?

Rješenje: V 6(3)

PRIMJER 1.24

Uočimo da je izbor r kuglica iz jedne kutije u kojoj je n različitih kuglica s vraćanjem u kutiju (a poredak je važan), analogan rasporedu r različitih kuglica u n različitih kutija.

PRIMJER 1.25

Iz kutije u kojoj je šest kuglica različitih boja izvlačimo tri kuglice jednu po jednu s vraćanjem ponovo u kutiju. Koliko različitih uzoraka možemo dobiti tim postupkom?

Rješenje: V 6(3).

PRIMJER 1.26

Listić sportske prognoze ima 10 parova. Svaki par može dobiti oznaku 0,1 ili 2 (poraz, neriješeno,pobjeda domaćina). Koliko listića treba ispuniti da bi sigurno jedan listić bio dobitni?

Rješenje: S = {0,1,2}, n = 3.
Listić je varijacija s ponavljanjem r = 10-og razreda od n = 3 elementa. Broj varijacija je V 3(10) = 310 = 59049.

1.5 KOMBINACIJE BEZ PONAVLJANJA

MOTIV 1.8

U skladištu je 100 proizvoda, 70 proizvoda prve klase, 20 proizvoda druge klase i 10 proizvoda treće klase. Kontrolor testira tri proizvoda i daje pozitvnu ocjenu ako su svi proizvodi prve klase. Na osnovu koliko posto svih uzoraka će kontrolor dati pozitivnu ocjenu proizvoda?

Definicija 1.6 Neka skup S ima n različitih elemenata. Svaki r-člani podskup (r n) (redoslijed elemenata u skupu nije bitan) n-članog skupa S zove se kombinacija r-tog razreda od n elemenata.

T: Broj svih kombinacija r-tog razreda je

D: (i) Budući da u r-članom skupu redoslijed nije bitan onda broj uredenih r-torki od n elemenata moramo podijeliti s brojem permutacija r-članog skupa.
(ii) Prema teoremu o uzastopnom prebrojavanju, prvi element možemo izabrati na n načina, drugi možemo izabrati na (n - 1) načina, treći na (n - 2) načina, r-ti na (n - r + 1) način.

D: tko želi znati više

Pomoću AMI po n :
Neka je M = {n : Cn(r) = (n-n!r)!⋅r!, 1 r n}.
(B.I) Provjeravamo je li 1 M. Za n = 1 parametar 1 r n može poprimiti samo vrijednost r = 1 pa je broj jednočlanih podskupova iz skupa koji ima samo 1 element jednak C1(1) = 1. Prema formuli (n-nr!)!⋅r! = (1-1!1)!⋅1! = 1 za n = 1; Tako je 1 M.
(P.I) Pretpostavimo m M,
pa tada za svaki dani 1 r m vrijedi formula Cm(r) = (mm-!r)!⋅r!.
(K.I) U koraku indukcije trebamo pokazati da je m + 1 M.
(*) Ako je r = 1 onda je očito broj svih jednočlanih podskupova iz skupa koji ima m + 1 element jednak Cm+1(1) = m + 1. Prema formuli (n-nr!)!⋅r! = (m(m++11-1))!!⋅r! = (m + 1) za n = m + 1 i r = 1.
Pokazali smo da je m + 1 M za r = 1.
(**) Ako je 2 r < m + 1 treba pokazati da vrijedi Cm+1(r) = -(m+1-)!--
(m+1 -r)!⋅r!.
Za svaki fiksni r možemo skup svih kombinacija podijeliti na dva podskupa u kojima su kombinacije bez ponavljanja koje sadrže fiksni element npr. a1, i podskup u kojem su kombinacije bez ponavljanja koje ne sadrže fiksni element a1. Tako je

                                       m!              m!            m + 1!
C(mr+)1 =  ⋅C (mr- 1)+C (mr)= (P.I.) = -------------------+ ----------=  --------------.
                               (m  - r + 1) ⋅(r - 1)! (m  - r)⋅r!   (m + 1 - r)!⋅ r!
Tako smo pokazali da je m + 1 M za 2 r < m + 1.
(***) Ako je r = m + 1 onda je očito broj svih m + 1 -članih podskupova iz skupa koji ima m + 1 element jednak Cm+1(m+1) = 1. Prema formuli --n!---
(n- r)!⋅r! = ------(m+1)!-----
(m+1- (m+1 ))!⋅(m+1)! = 1 za n = m + 1 i r = m + 1.
Vrijedi m + 1 M za r = m + 1.

Prema AMI zaključujemo da je M = .

PRIMJER 1.27

Loto ima 39 brojeva. Izvlači se slučajno 7 brojeva. Koliko različitih listića s kombinacijama 7 brojeva treba ispuniti da se dobije jedan siguran pogodak?

Rješenje: S = {1,2,3,...,39}, n = 39.
Listić je kombinacija 7-og razreda (r = 7) od 39 elemenata. Broj kombinacija je C39(7) = (39)
 7 = 39⋅38⋅37⋅36⋅35⋅34⋅33-
      7! = 15380937. Treba ispuniti 15380937 listića da bi bili sigurni da ćemo imati jedan dobitak.

PRIMJER 1.28

U ravnini je 5 točaka od kojih 3 nikada ne leže na istom pravcu.
a) Koliko pravaca odreduju te točke?
b) Koliko trokuta odreduju te točke?

Rješenje: S = {1,2,3,4,5}, n = 5.
a) Pravac je kombinacija 2-og razreda (r = 2) od 5 elemenata. Broj kombinacija je C5(2) = (5)
 2 = 5⋅4
 2! = 10. Točke odreduju 10 pravaca.
b) Trokut je kombinacija 3-eg razreda (r = 3) od 5 elemenata. Broj kombinacija je C5(3) = ( )
 5
 3 = 5⋅4⋅3
 3! = 10. Točke odreduju 10 trokuta.

PRIMJER 1.29 Uzorak bez vraćanjem

Skup S ima n elemenata od kojih je n1 jedne vrste, n2druge vrste, ... , nk k-te vrste, n=n1 + n2 + ... + nk. Uredena r-torka ima r1 elemenata prve skupine, r2 elemenata druge skupine, ...,rk elemenata k - te skupine r=r1+r2+...+rk

Broj uredenih r-torki bez vraćanja je: Cn1r1 Cn 2r2... Cn krk.

PRIMJER 1.30

Studenti dva turnusa biraju po tri predstavnika u Klub studenata prve godine GF.  Prvi turnus ima 20 studenata, a drugi 30 studenata. Koliko moguće je različitih sastava Kluba studenata?

Rješenje:
Koristimo formulu za uzorak bez vraćanja (koristimo teorem o uzastopnom prebrojavanju i broj kombinacija ri-razreda od ni elemenata).
n = n1 + n2 =20+30,r = r1 + r2 =3+3.
Ukupan broj načina da se dobije 6-člani Klub je
C20(3) C30(3) = (20)
  3(30)
  3 = 4628400.

PRIMJER 1.31

U skupu od 27 proizvoda 7 je neispravnih. Na koliko načina se može dobiti uzorak koji se sastoji od 5 dobrih i 3 neispravna proizvoda?

Rješenje:
Koristimo formulu za uzorak bez vraćanja (koristimo teorem o uzastopnom prebrojavanju i broj kombinacija ri-razreda od ni elemenata).
S = 20T + 7D, n = nT + nD; nT = 20, nD = 7.
Uzorak r = 5T + 3D,  r = rT + rD; rT = 5, rD = 3.
Broj traženih uzoraka je C20(5) C7(3) = (20)
 5(7 )
  3 = 542640.

PRIMJER 1.32

Ako želimo ispitati kvalitetu 10 proizvoda od kojih je 6 ispravnih i 4 neispravna uzimamo uzorak od tri proizvoda. Koliko uzoraka ima u kojima
a) nema neispravnih proizvoda
b) ima jedan neispravan proizvod
c) ima barem dva ispravna proizvoda?

Rješenje: Koristimo formulu za uzorak bez vraćanja.
a) Osnovni skup ima n = 10 elemenata; n = nT + nD = 6+4. Uzorak bez neispravnih proizvoda ima r = rT + rD = 3 + 0.
Broj uzoraka koji nemaju neispravnih proizvoda je: C6(3) C4(0) =20.
b) Osnovni skup ima n = 10 elemenata; n = nT + nD = 6 + 4. Uzorak s 1 neispravnim proizvodom ima r = rT + rD = 2 + 1.
Broj uzoraka koji imaju 1 neispravni proizvod je: C6(2) C4(1) = 60 .
c) Osnovni skup ima n = 10 elemenata; n = nT + nD = 6 + 4. Uzorak s bar dva ispravna proizvoda može biti ako ima 1 ili 0 neispravna proizvoda.
Broj uzoraka s bar 2 ispravna proizvoda je:
c) = a) + b) = C6(3) C4(0) + C6(2) C4(1) = 20 + 60 = 80 .

PRIMJER 1.33 motiv

U skladištu je 100 proizvoda, 70 proizvoda prve klase, 20 proizvoda druge klase i 10 proizvoda treće klase. Kontrolor testira tri proizvoda i daje pozitvnu ocjenu ako su svi proizvodi prve klase. Na osnovu koliko posto svih uzoraka će kontrolor dati pozitivnu ocjenu proizvoda?

Rješenje:
Broj uzoraka veličine r = 3 od n = 100 elemenata je C100(3) =161700.
Koristimo formulu za uzorak bez vraćanja.
Osnovni skup ima n = 100 = n1 + n2 + n3 = 70 + 20 + 10 proizvoda
Uzorak prve klase ima r = r1 + r2 + r3 = 3 + 0 + 0 = 3 proizvoda.
Broj uzoraka prve klase je: C70(3) C20(0) C10(0) =54740.
Kontrolor će dati pozitivnu ocjenu u 51641774000 = 0.3385 ili u 33,8% slučajeva.

1.5.1 KOMBINACIJE S PONAVLJANJEM
tko želi znati više

MOTIV 1.9

Na koliko načina možmo rasporediti 3 bagera (jednaki) na 6 gradilišta?

Definicija 1.7

Neka skup S ima n različitih elemenata. Svaki r-člani podskup (r ), n-članog skupa S gdje se elementi mogu i ponavljati (redoslijed elemenata u r-torci nije bitan) zove se kombinacija s ponavljanjem r-tog razreda od n elemenata.

T: Broj svih kombinacija s ponavljanjem r-tog razreda od n elemenata je

D: tko želi znati više

(i) Pomoću AMI po s = n + r - 1 :
Neka je M = {s = n + r - 1 : Cn(r) = (     )
 n+r-1
   r,n,r }.
(B.I) Provjeravamo je li 1 M.
Za s = 1 tj. n + r = 1, parametari su r = 1,n = 1. Broj 1-čl. podskupova iz skupa koji ima samo 1 element jednak je C1(1) = 1. Prema formuli (n+r-1 )
   r = ---1!--
(1-1)!⋅1! = 1 za s = 1; pa je s = 1 M.
(P.I) Pretpostavimo da s = m M,
tj. za n + r - 1 = m vrijedi formula Cn(r) = (n+r -1)
    r.
(K.I) U koraku indukcije trebamo pokazati da je s = m + 1 M
tj. da za n + r - 1 = m + 1 vrijedi formula Cn(r) = (n+r-1)
   r.

(*) Ako je r = 1 onda je očito broj svih 1-članih podskupova s ponavljanjem iz skupa koji ima n = m + 1 element jednak Cm+1(1) = m + 1. Prema formuli (n+r-1)
   r = (m+1 )
   1 = (m + 1) za n = m + 1 i r = 1.
Pokazali smo da je s = m + 1 M za r = 1.
(**) Ako je n = 1 onda je očito broj svih m + 1-članih podskupova s ponavljanjem iz skupa koji ima n = 1 element jednak C1(m+1) = 1. Prema formuli (      )
 n+rr- 1 = (    )
 mm++11 = 1 za n = 1 i r = m + 1.
Tako je s = m + 1 M za n = 1.
(***) U ostalim slučajevima, skup svih kombinacija s ponavljanjem možemo podijeliti na dva podskupa u kojima su kombinacije sa ponavljanjem koje sadrže fiksni element npr. a1, i kombinacije sa ponavljanjem koje ne sadrže fiksni element a1.
Zato je

                      (          )   (         )           (          )
C(r)= C-(r- 1) + C(r) =   n + r - 2  +  n + r - 2  = (P.I.) =  n + r - 1  .
 n      n       n- 1      r - 1           r                      r
Pokazali smo da je s = m + 1 M za 2 r i 2 n.

Prema AMI zaključujemo da je M = .

(ii) Pokazat ćemo na primjeru n = 3, r = 2 da formula vrijedi.
Neka je skup S = {1,2,3}. Sve kombinacije  s ponavljanjem 2-og razreda od 3 elementa su (elemente smo poredali po uzlaznim vrijednostima):
{1,1} {1,2} {1,3} {2,2} {2,3} {3,3}.
Tih kombinacija ima C3(2) =6.
Definirajmo preslikavanje koje će ovim podskupovima pridijeliti podskupove dobivene tako da prvom članu podskupa dodamo 0, a drugom članu 1.

{1,1}→{1,2}

{1,2}→{1,3}

{1,3}→{1,4}

{2,2}→{2,3}

{2,3}→{2,4}

{3,3}→{3,4}.

Slike su kombinacije bez ponavljanja 2-og razreda od 4-članog skupa {1,2,3,4}. Preslikavanje je bijekcija izmedu skupa svih kombinacija s ponavljanjem 2-razreda od 3 elementa i kombinacija 2-razreda od 4 elementa. Budući da postoji bijekcija, ti su skupovi jednakobrojni pa vrijedi C3(2) = C4(2) = 6.

(ii) Uočimo da je izbor r kuglica iz jedne kutije u kojoj je n različitih kuglica s vraćanjem u kutiju, analogan rasporedu r jednakih kuglica u n različitih kutija. Svaki raspored kako se r kuglica može rasporediti u n kutija je kombinaciju s ponavljanjem r-tog razreda od n elemenata. Zamislimo da imamo n kutija poredanih u niz i da u njih bacamo k kuglica.
Problem je sada kao da slažemo kuglice i pregrade izmedu njih. Jedan raspored možemo gledati kao uredenu n - 1 + r -torku gdje imamo n - 1 izbor pregrada i r izbora za kuglice.  Svaki takav raspored je permutacija s ponavljanjem od n - 1 + r elementata od kojih jedne vrste ima n - 1, a druge r. Ukupan broj takvih permutacija s ponavljanjem ima Pn-1+r(n - 1,r).

PRIMJER 1.34

Zamislimo da imamo n=5 kutija poredanih u niz i da u njih bacamo r=9 kuglica.
Problem možemo razmatrati kao da slažemo kuglice i pregrade medu kutijama. Imamo n-1=4 jednake pregrade i r=9 jednakih kuglica. Dakle, imamo permutacije n+r-1=13 elemenata od kojih su 4 jedne vrste i 9 druge vrste pa je njihov broj: P13(4,9).

PRIMJER 1.35 Razdioba jednakih predmeta

Svaka razdioba r jednakih predmeta na n različitih mjesta je kombinacija s ponavljanjem r -tog razreda od n elemenata.

Broj razdioba je Cn(r).

PRIMJER 1.36 motiv

Na koliko načina možmo rasporediti 3 bagera (jednaki) na 6 gradilišta?

Rješenje: Bagere možemo rasporediti na C6(3) = (n+r-1)
   r = (6+3-1)
   3 = (8)
 3 = 56 načina.

PRIMJER 1.37

3 kuglice iste boje rasporedujemo u 6 kutija. Koliko razdioba možemo dobiti?

Rješenje: C6(3).

PRIMJER 1.38

Uočimo da je izbor r kuglica iz jedne kutije u kojoj je n različitih kuglica s vraćanjem u kutiju ( redoslijed nije važan), analogan rasporedu r jednakih kuglica u n različitih kutija.

PRIMJER 1.39

Iz kutije u kojoj je 6 kuglica različite boje izvlačimo tri kuglice jednu po jednu s vraćanjem. Koliko uzoraka možemo dobiti ako redoslijed nije važan?

Rješenje: C6(3).

PRIMJER 1.40

U prodavaonici se može kupiti 5 vrsta čarapa. Koliko različitih poklona može napraviti prodavač ako je pakirao po 9 pari?

Rješenje: S = {1,2,3,4,5}, n = 5 vrsta čarapa.
Poklon je kombinacija s ponavljanjem 9-razreda (r = 9) od 5 elemenata.
Broj poklona je C5(9) = (      )
 n+rr-1 = (     )
 5+99-1 = (  )
 139 = 715.

PRIMJER 1.41

Iz kutije u kojoj je šest kuglica različitih boja izvlačimo tri odjednom (bez vraćanja). Koliko takvih kombinacija možemo dobiti ako redoslijed nije važan?

Rješenje: C6(3).

PRIMJER 1.42

Iz kutije u kojoj je 6 kuglica različitih boja izvlačimo tri kuglice jednu po jednu s vraćanjem. Koliko uzoraka možemo dobiti ako redoslijed nije važan?

Rješenje: C6(3).

1.6 Ponovimo

IZBOR - s vraćanjem



IZBOR: r-čl. uzorka iz n-čl. skupa različitih elemenata


nije važan poredak Cn(r)


važan poredak V n(r)


IZBOR - bez vraćanja



IZBOR: r-čl. uzoraka iz n-čl. skupa različitih elemenata


nije važan poredak Cn(r)


važan poredak V n(r)


RAZDIOBE - proizvoljno predmeta u kutijama



RAZDIOBE: r predmeta u n različitih kutija


jednakih predmeta Cn(r)


različitih predmeta V n(r)


RAZDIOBE - najviše po jedan predmet u kutiji



RAZDIOBE: r predmeta u n različitih kutija


jednakih predmeta Cn(r)


različitih predmeta V n(r)


UZORCI



UZORCI: veličine r = r1 + r2 + .. + rkiz n = n1 + n2 + .. + nk-čl. skupa


bez vraćanja Cn1(r1) Cn 2(r2) ⋅⋅Cn k(rk)


s vraćanjem Pr(r1,r2,...,rk) (n1)r1(n2)r2 ... (nk)rk


s vraćanjem n r Pr(r1,r2,...,rk)