Zadaci Kombinatorika u1m4d

KOMBINATORIKA Permutacije: a) bez ponavljanja: b) sa ponavljanjem

Kombinacije: a) bez ponavljanja: b) sa ponavljanjem:

Pn= n! P

n k1 , k 2 ,.., k n



n! k1!k 2 !..  k n !

n n! C      k  k!n  k ! k n

 n  k  1 n  k  1!   C   k   k! n  1! k n

Varijacije:

n! a) bez ponavljanja: V  n  k ! k n

b) sa ponavljanjem:

k n

V  nk 1

Zadatak 1. Kako glasi 80-ta permutacija od elemenata: {1, 2, 3, 4, 5} Rješenje:

1 na prvom mjestu……….. 2 na prvom mjestu………. 3 na prvom mjestu………. 41 na prvom mjestu……...

4! = 24 4! = 24 4! = 24 3! = 6

Traženo rješenje

Ukupno………………………... 78 79. permutacija………...

42135

80. permutacija………...

42153 2

Zadatak 2. Koliko ima permutacija elemenata {a, b, c, d, e}, koje na trećem mjestu imaju d :

abdce

acdeb

badce

……..

……..

……..

abdec

aedbc

badec

……..

……..

……..

acdbe

aedcb

bedae

……..

……..

……..

P4= 4! = 4  3  2 1  24

3

Zadatak 3. Na sastanku Saveza studenata treba smjestiti 4 studenta mašinskog, 6 studenata ekonomskog i 2 studenta pravnog fakulteta. Na koliko načina možemo studente razmjestiti ako: a) studenti sa istog fakulteta moraju biti zajedno, b) samo studenti ekonomskog fakulteta moraju biti zajedno.

a)

b)

( P4  P6  P2 )  P3 = ( 4!  6!  2! )  3! = 207.360 P7  P6 = ( 4 + 2 + 1 )!  6! = 3.628.800

4

Zadatak 4.

Koliko se permutacija može napisati od slova riječi: a) BANKA a) P5/

b) BANJA LUKA

c) ANANAS

5! = = 2!

54 3 2 1 = 60 21

8! = = 3!

87654 3 2 1 = 6720 321

2

b) P8/ 3

6! 654 3 2 1 c) P6/3,2 = = 60 = 3! 2! 3  2  1 2 1 5

Zadatak 5.

Koja je po redu u leksikografskom poretku permutacija BEOGRAD sačinjena od elemenata ABGDEOR ? A na prvom mjestu 6!=720 BA……………………... 5!=120 BG…………………...….5!=120 BD……………………… 5!=120 BEA……………….…... 4!= 24 BEG……………………. 4!= 24 BED……………………. 4!= 24 BEOA…………………. 3!= 6 Ukupno…………………....1158

BEOGAD R BEOGARD BEOGDAR BEOGDRA BEOG RAD

1163. permutacija 6

Zadatak 6. Na šahovskom turniru učestvuju 12 šahista. Koliko će se partija odigrati:

a) ako svako treba da igra sa svakim, b) ako pored toga treba da svaki igrač igra i sa bijelim i sa crnim figurama

a)

b)

12

12! 12! = = = 66 partija 2! (12-2)! 2! 10!

C122

=

V122

12! = (12-2)!

2

= 132 partije

(66  2 ) 7

Zadatak 7. Treba obrazovati komisiju od 5 članova birajući između 4 inžinjera i 7 ekonomista. Koliko mogućnosti postoji ako:

a) uzimamo sve u obzir bez razlike, b) isključujemo ekonomiste, v) uzimamo 2 inžinjera i 3 ekonomista g) uzimamo 2 inžinjera i 3 ekonomista tako da među ekonomistima bude 1 određeni član d) da 2 ekonomista izaberemo za predsjednika i potpredsjednika a 3 inžinjera za članove i) isključujući inžinjere

  a) uzimamo sve u obzir bez razlike:

C115

=

11

5

11! = = 462 5! (11-5)!

8

b) isključujemo ekonomiste:

C115

=

11

rješenje ne postoji (prazan skup)

=

5

v) uzimamo 2 inžinjera i 3 ekonomista:

C42

 C37

=

4



2

7 3

4! 7! = = 210  2! (4-2)! 3! (7-3)!

g) uzimamo 2 inžinjera i 3 ekonomista tako da među ekonomistima bude 1 određeni član:

C42

 C26

=

4 2



6 2

4! 6! = = 120  2! (4-2)! 2! (6-2)! 9

d) da 2 ekonomista izaberemo za predsjednika i potpredsjednika a 3 inžinjera za članove:

V72

 C34

4! 7! = = 168  (7-2)! 3! (4-3)!

i) isključujući inžinjere:

C 57

=

7

5

7! = = 21 5! (7-5)!

10

Zadatak 8.

Koliko se trocifrenih brojeva može napisati od cifara { 3, 4, 5, 6, 7 }? 3 V5

= 53 = 125

Zadatak 9.

Jedna trgovina raspolaže sa dvije vrste robe A i B. Na koliko se načina mogu izložiti 4 primjerka robe tako da primjerci stoje jedan pored drugog? 4

4 = 16 2 = V2

Zadatak 10. Koliko se brojeva između 3000 i 5000 može načiniti pomoću cifara { 0, 1, 2, 3, 4, 5, 6, 7 }: a) ako se nijedna cifra ne ponavlja u jednom broju, b) ako se cifre mogu ponavljati? a)

3 012 - najmanji broj

7! V7 = = 210 (osim brojke 3) (7-3)! 3

3 765 - najveći broj

4 012 - najmanji broj

7! V7 = = 210 (7-3)! 3

4 765 - najveći broj Ukupno

420 brojeva 12

b) ako se cifre mogu ponavljati: 3 001 - najmanji broj 3 777 - najveći broj

3 V8

- 1 = 83 - 1 = 511

4 000 - najmanji broj 4 777 - najveći broj Ukupno

3 V8

= 83

= 512 1023 broja

13

Zadatak 11. Na jednom turniru učestvuje 8 fudbalskih klubova koji u prvom danu igraju 4 utakmice. Svaka od utakmica može da ima 3 rezultata označena sa 1, X, 2. Izračunati koliko treba uplatiti za sportsku prognozu da bi dobitak bio siguran, ako za jednu varijantu rezultata na sve 4 utakmice treba platiti 5 KM? množimo sa 5 KM 4 V3

= 34 = 81  5 = 405

14

Zadatak 12. Koliko možemo formirati riječi od 5 slova, od slova riječi SLUČAJEVI ako su: a) slova Č, A, J zajedno, b) slovo E neposredno iza slova L?

a)

V62

6! 3 3! =  3  3! (6-2)!

b)

V73

4 =

= 2  3  3  5  6 = 540

7!  4 = 5  6  7  4 = 840 4! 15

Zadatak 13. Koristeći slova azbuke koliko možemo napisati riječi od 6 slova ako one sadrže: a) 4 različita suglasnika i 2 različita samoglasnika, a počinje slovom M i sadrži slovo I, b) 5 različitih slova i slovo M? 3 a) V24  V 14  5 = 242.880 riječi

5 b) V29  6 = 99.754.200 riječi

16