Kombinatorika
Iz mementa
Niz duljine k ili uređena k-torka izgrađena od različitih elemenata skupa [latex] \{ {a_1,\enspace a_2,\ldots,a_n} \}[/latex] u kombinatorici se zove varijacija k-tog reda u tom skupu ([latex]k\le n[/latex]).
Ukupni broj takvih nizova nad skupom veličine [latex]n[/latex] jest:
[latex]n(n-1)(n-2)\ldots(n-k+1)[/latex].
Ukoliko se elementi skupa [latex]\{ {a_1,\enspace a_2,\ldots,a_n} \}[/latex] mogu ponavljati radi se o varijaciji k-tog reda s ponavljanjem.
Njihov je ukupan broj nad skupom veličine [latex]n[/latex] jednak [latex]n^k[/latex].
Primjer 1
a) Bacamo igraću kockicu tri puta. Odredimo ukupan broj mogućih ishoda.
a) Prilikom prvog bacanja kocke mogućih je 6 ishoda. Isto toliko je ishoda mogućih i prilikom drugom odnosno trećeg bacanja kocke pa je ukupan broj različitih načina [latex]6\cdot6\cdot6=6^3=216[/latex].
b) Odredimo koliko različitih četveroznamenkastih pinova možemo kreirati od znamenki i slova engleske abecede uz uvjet da prva dva znaka budu znamenke, a druga dva znaka slova engleske abecede.
b) Na prvu poziciju možemo postaviti 10 znamenki. Isto toliko možemo postaviti i na drugu poziciju. Na treću i četvrtu poziciju postavljamo slova engleske abecede, a njih je 26. Ukupan broj načina je: [latex]10\cdot10\cdot26\cdot26=67600[/latex]
c) Koliko nizova duljine [latex]3[/latex] (uređenih trojki) možemo izgraditi od elemenata skupa [latex]\{ {1,2,3,4} \}[/latex]?
c) Za prvo mjesto niza imamo [latex]4[/latex] mogućnosti.
Za drugo mjesto niza opet imamo [latex]4[/latex] mogućnosti koje, kombinirane s [latex]4[/latex] mogućnosti za prvo mjesto, daju ukupno [latex]4\cdot4[/latex] mogućnosti za prva dva mjesta.
Za treće mjesto niza opet imamo [latex]4[/latex] mogućnosti koje, kombinirane s [latex]4\cdot4[/latex] mogućnosti za prva dva mjesta, daju ukupno [latex]4\cdot4\cdot4[/latex] mogućnosti za sva tri mjesta.
Dakle, nizova duljine [latex]3[/latex] nad skupom veličine [latex]4[/latex] ima ukupno [latex]4^3[/latex].
d) Koliko nizova duljine [latex]3[/latex] (uređenih trojki) s različitim elementima možemo izgraditi nad skupom [latex]\{ {1,2,3,4} \}[/latex]?
d) Za prvo mjesto niza imamo [latex]4[/latex] mogućnosti.
Za drugo mjesto niza imamo [latex]3[/latex] mogućnosti koje, kombinirane s [latex]4[/latex] mogućnosti za prvo mjesto, daju ukupno [latex]4\cdot3[/latex] mogućnosti za prva dva mjesta.
Za treće mjesto uređenoga skupa imamo [latex]2[/latex] mogućnosti koje, kombinirane s [latex]4\cdot3[/latex] mogućnosti za prva dva mjesta, daju ukupno [latex]4\cdot3\cdot2[/latex] mogućnosti za sva tri mjesta.
Dakle, uređenih skupova duljine [latex]3[/latex] nad skupom veličine [latex]4[/latex] ima ukupno [latex]4\cdot3\cdot2=24[/latex].
Zadatak 1
Iz mementa
Varijacija n-tog reda zove se permutacija.
Ukupan broj permutacija nad skupom veličine [latex]n[/latex] jest [latex]n![/latex]
[latex]n![/latex] označava umnožak prvih [latex]n[/latex] prirodnih brojeva.
Primjer 2
Zadatak 2