Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI KOMBINATORIKA

Kombinatorika – spisak formula, primeri, izvođenja formula, osobine

[inlmath]{n\choose k}=\frac{n!}{\left(n-k\right)!k!}[/inlmath]

Kombinatorika – spisak formula, primeri, izvođenja formula, osobine

Postod Daniel » Petak, 04. Jul 2014, 10:29

FORMULE U KOMBINATORICI

Permutacije bez ponavljanja od [inlmath]n[/inlmath] elemenata (broj načina na koje možemo [inlmath]n[/inlmath] elemenata rasporediti u niz):
[dispmath]P_n=n\cdot(n-1)\cdots3\cdot2\cdot1=n![/dispmath] Varijacije bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase (broj načina na koje od [inlmath]n[/inlmath] elemenata možemo odabrati [inlmath]k[/inlmath] elemenata pri čemu nema ponavljanja elemenata i redosled je bitan):
[dispmath]V_n^k=\underbrace{n\cdot(n-1)\cdot(n-k+1)}_{k\text{ faktora}}=\frac{n!}{(n-k)!},\qquad0\le k\le n[/dispmath] Kombinacije bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase (broj načina na koje od [inlmath]n[/inlmath] elemenata možemo odabrati [inlmath]k[/inlmath] elemenata pri čemu nema ponavljanja elemenata i redosled nije bitan):
[dispmath]C_n^k=\frac{n!}{(n-k)!\cdot k!}={n\choose k},\qquad0\le k\le n[/dispmath] Permutacije s ponavljanjem od [inlmath]n[/inlmath] elemenata, među kojima ima [inlmath]m[/inlmath] međusobno različitih elemenata [inlmath]a_1,a_2,\ldots,a_m[/inlmath] (broj načina na koje možemo rasporediti elemente [inlmath]a_1,a_2,\ldots,a_m[/inlmath] u niz, pri čemu je [inlmath]n_i[/inlmath] broj pojavljivanja elementa [inlmath]a_i[/inlmath] u svakoj od permutacija):
[dispmath]\overline P_n^{n_1,n_2,\ldots,n_m}=\frac{n!}{n_1!\cdot n_2!\cdots n_m!},\qquad n_1+n_2+\cdots+n_m=n,\qquad0\le m\le n[/dispmath] Varijacije s ponavljanjem od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase (broj načina na koje od [inlmath]n[/inlmath] elemenata možemo [inlmath]k[/inlmath] puta odabrati neki od tih elemenata, pri čemu svaki od elemenata može biti odabran i više puta i redosled izbora elemenata je bitan):
[dispmath]\overline V_n^k=n^k[/dispmath] Kombinacije s ponavljanjem od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase (broj načina na koje od [inlmath]n[/inlmath] elemenata možemo [inlmath]k[/inlmath] puta odabrati neki od tih elemenata, pri čemu svaki od elemenata može biti odabran i više puta i redosled izbora elemenata nije bitan):
[dispmath]\overline C_n^k={n+k-1\choose k}[/dispmath]


PERMUTACIJE BEZ PONAVLJANJA

Permutacije bez ponavljanja od [inlmath]n[/inlmath] elemenata predstavljaju načine na koje možemo [inlmath]n[/inlmath] elemenata rasporediti u niz. Uzmimo, kao primer, skup od [inlmath]4[/inlmath] elementa [inlmath]\{A,B,C,D\}[/inlmath]. Permutacije njegovih elemenata, tj. slova [inlmath]A[/inlmath], [inlmath]B[/inlmath], [inlmath]C[/inlmath] i [inlmath]D[/inlmath], biće:
[dispmath]\begin{array}{llll}
ABCD & BACD & CABD & DABC\\
ABDC & BADC & CADB & DACB\\
ACBD & BCAD & CBAD & DBAC\\
ACDB & BCDA & CBDA & DBCA\\
ADBC & BDAC & CDAB & DCAB\\
ADCB & BDCA & CDBA & DCBA
\end{array}[/dispmath] Na prvu poziciju možemo smestiti bilo koji od [inlmath]n[/inlmath] elemenata, tj. imamo [inlmath]n[/inlmath] mogućnosti. Za drugu poziciju nam ostaje [inlmath](n-1)[/inlmath] mogućnosti, budući da je jedan od tih [inlmath]n[/inlmath] elemenata već iskorišćen (onaj što se već nalazi na prvoj poziciji). Za treću poziciju nam ostaje [inlmath](n-2)[/inlmath] mogućnosti, jer su dva od [inlmath]n[/inlmath] elemenata već iskorišćena, tj. nalaze se na prvom i drugom mestu... Stižemo tako do poslednja dva mesta – za pretposlednje mesto nam preostaju dva elementa, tj. imamo dve mogućnosti, a za poslednje mesto nam, naravno, preostaje samo jedna mogućnost.
Broj mogućih permutacija dobićemo kad pomnožimo sve ove mogućnosti. Dakle,
[dispmath]P_n=n\cdot(n-1)\cdot(n-2)\cdots3\cdot2\cdot1[/dispmath] Kako bi ovo lakše bilo zapisano, uvedena je oznaka faktorijel (piše se kao znak uzvika). Faktorijel nekog broja označava proizvod tog broja i svih prirodnih brojeva manjih od njega:
[dispmath]n!=n\cdot(n-1)\cdot(n-2)\cdots3\cdot2\cdot1[/dispmath] pri čemu se definiše
[dispmath]0!\:\overset{\text{def}}{=\!=}\:1[/dispmath] Prema tome, broj permutacija bez ponavljanja od [inlmath]n[/inlmath] elemenata može se zapisati kao:
[dispmath]\enclose{box}{P_n=n!}[/dispmath] Kod faktorijela, inače, važi osobina koja se često koristi,
[dispmath]n!=n\cdot\underbrace{(n-1)\cdots3\cdot2\cdot1}_{(n-1)!}\qquad\Longrightarrow\qquad n!=n\cdot(n-1)!\qquad(n\in\mathbb{N})[/dispmath] Primenivši formulu za broj permutacija na gornji primer s [inlmath]4[/inlmath] elementa, dobijamo [inlmath]P_4=4!=4\cdot3\cdot2\cdot1=24[/inlmath], što je isti broj koji dobijamo i ako prebrojimo permutacije ispisane u tom primeru.



VARIJACIJE BEZ PONAVLJANJA

Varijacije bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase predstavljaju načine na koje od [inlmath]n[/inlmath] elemenata možemo izabrati [inlmath]k[/inlmath] elemenata ([inlmath]0\le k\le n[/inlmath]), pri čemu je bitan redosled izabranih elemenata i svaki element se može pojaviti najviše jednom, tj. nema ponavljanja elemenata. Primer varijacija bez ponavljanja od [inlmath]5[/inlmath] elemenata [inlmath]3.[/inlmath] klase bio bi odabir [inlmath]3[/inlmath] elementa iz skupa [inlmath]\{A,B,C,D,E\}[/inlmath]:
[dispmath]\begin{array}{llllllllll}
ABC & ADB & BAC & BDA & CAB & CDA & DAB & DCA & EAB & ECA\\
ABD & ADC & BAD & BDC & CAD & CDB & DAC & DCB & EAC & ECB\\
ABE & ADE & BAE & BDE & CAE & CDE & DAE & DCE & EAD & ECD\\
ACB & AEB & BCA & BEA & CBA & CEA & DBA & DEA & EBA & EDA\\
ACD & AEC & BCD & BEC & CBD & CEB & DBC & DEB & EBC & EDB\\
ACE & AED & BCE & BED & CBE & CED & DBE & DEC & EBD & EDC
\end{array}[/dispmath] Slično kao kod permutacija, na prvu poziciju možemo smestiti bilo koji od [inlmath]n[/inlmath] elemenata, znači, imamo [inlmath]n[/inlmath] mogućnosti. Za drugu poziciju je preostalo [inlmath](n-1)[/inlmath] „kandidata“, jer se jedan već nalazi na prvoj poziciji. Po istom rezonu, za treću poziciju nam je preostalo [inlmath](n-2)[/inlmath] elemenata itd. Međutim, dok nam je kod permutacija za poslednju poziciju preostao jedan element, jer smo tada imali broj pozicija koji je jednak broju elemenata, ovde to sada ne mora biti slučaj. Kad dođemo do [inlmath]k[/inlmath]-te pozicije, za nju nam preostaje [inlmath][n-(k-1)][/inlmath], tj. [inlmath](n-k+1)[/inlmath] elemenata. Broj varijacija dobijamo množenjem ovih mogućnosti:
[dispmath]V_n^k=\underbrace{n\cdot(n-1)\cdot(n-2)\cdots(n-k+2)\cdot(n-k+1)}_{k\text{ faktora}}[/dispmath] Da bismo ovo zapisali u lepšem obliku, pomnožićemo izraz sa [inlmath]\frac{(n-k)\cdot(n-k-1)\cdots3\cdot2\cdot1}{(n-k)\cdot(n-k-1)\cdots3\cdot2\cdot1}[/inlmath]:
[dispmath]V_n^k=n\cdot(n-1)\cdot(n-2)\cdots(n-k+2)\cdot(n-k+1)\cdot\frac{(n-k)\cdot(n-k-1)\cdots3\cdot2\cdot1}{(n-k)\cdot(n-k-1)\cdots3\cdot2\cdot1}[/dispmath][dispmath]V_n^k=\frac{\overbrace{n\cdot(n-1)\cdot(n-2)\cdots3\cdot2\cdot1}^{n!}}{\underbrace{(n-k)\cdot(n-k-1)\cdots3\cdot2\cdot1}_{(n-k)!}}[/dispmath][dispmath]\enclose{box}{V_n^k=\frac{n!}{(n-k)!}}[/dispmath] Možemo primetiti to, da se u slučaju [inlmath]k=n[/inlmath] (to jest, kada je broj izabranih elemenata jednak broju elemenata skupa iz kojeg se vrši odabir, što znači da smo izabrali sve elemente skupa), broj varijacija svodi na broj permutacija:
[dispmath]V_n^n=\frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n!=P_n[/dispmath] S druge strane, kada je [inlmath]k=0[/inlmath] (što odgovara slučaju kada izabiramo prazan skup, tj. kada ne izabiramo nijedan od elemenata),
[dispmath]V_n^0=\frac{n!}{(n-0)!}=\frac{\cancel{n!}}{\cancel{n!}}=1[/dispmath] što je i logično, jer prazan skup možemo izabrati na samo jedan način, bez obzira na to koliko elemenata ima skup iz kojeg vršimo (tj. u ovom slučaju ne vršimo) odabir.
Za [inlmath]k=1[/inlmath], tj. kada iz skupa od [inlmath]n[/inlmath] elemenata biramo samo jedan element, intuitivno nam je jasno da to možemo učiniti na [inlmath]n[/inlmath] načina. To se može pokazati i pomoću formule:
[dispmath]V_n^1=\frac{n!}{(n-1)!}=\frac{n\cdot\cancel{(n-1)!}}{\cancel{(n-1)!}}=n[/dispmath] Ako na gornji primer, u kojem smo imali [inlmath]5[/inlmath] elemenata od kojih biramo [inlmath]3[/inlmath] elementa, primenimo odgovarajuću formulu za varijacije, dobijamo [inlmath]V_5^3=\frac{5!}{(5-3)!}=\frac{5\cdot4\cdot3\cdot\cancel{2!}}{\cancel{2!}}=60[/inlmath], što isto dobijamo i ako izbrojimo varijacije napisane u tom primeru.



KOMBINACIJE BEZ PONAVLJANJA

Kombinacije bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase predstavljaju načine na koje od [inlmath]n[/inlmath] elemenata možemo izabrati [inlmath]k[/inlmath] elemenata ([inlmath]0\le k\le n[/inlmath]), pri čemu nije bitan redosled izabranih elemenata i svaki element se može pojaviti najviše jednom, tj. nema ponavljanja elemenata. Primer kombinacija bez ponavljanja od [inlmath]5[/inlmath] elemenata [inlmath]3.[/inlmath] klase bio bi odabir [inlmath]3[/inlmath] elementa iz skupa [inlmath]\{A,B,C,D,E\}[/inlmath]:
[dispmath]\begin{array}{lllll}
ABC & ABE & ACE & BCD & BDE\\
ABD & ACD & ADE & BCE & CDE
\end{array}[/dispmath] Dakle, razlika između varijacija i kombinacija je jedino u tome što je kod varijacija bitan redosled izabranih elemenata, dok kod kombinacija njihov redosled nije bitan.

Sve varijacije u kojima se pojavljuju isti elementi samo s drugačijim redosledom, predstavljaju, zapravo, jednu istu kombinaciju. Primera radi, varijacije [inlmath]BCE[/inlmath], [inlmath]BEC[/inlmath], [inlmath]CBE[/inlmath], [inlmath]CEB[/inlmath], [inlmath]EBC[/inlmath] i [inlmath]ECB[/inlmath], predstavljale bi jednu istu kombinaciju, jer se u svakoj od njih pojavljuju isti elementi – [inlmath]B[/inlmath], [inlmath]C[/inlmath] i [inlmath]E[/inlmath]. Možemo primetiti to, da varijacije s istim elementima predstavljaju, zapravo, permutacije tih elemenata, što znači da bi njihov broj bio [inlmath]P_k=k![/inlmath], gde je [inlmath]k[/inlmath] broj elemenata u odabiru, tj. klasa varijacije. Drugim rečima, [inlmath]k![/inlmath] varijacija se „preslikava“ u jednu kombinaciju, što znači da je ukupan broj kombinacija bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase [inlmath]P_k[/inlmath] puta manji od broja odgovarajućih varijacija bez ponavljanja od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase:
[dispmath]C_n^k=\frac{V_n^k}{P_k}=\frac{\frac{n!}{(n-k)!}}{k!}=\frac{n!}{(n-k)!\cdot k!}[/dispmath][dispmath]\Longrightarrow\qquad\enclose{box}{C_n^k=\frac{n!}{(n-k)!\cdot k!}}[/dispmath] Izraz [inlmath]\frac{n!}{(n-k)!\cdot k!}[/inlmath] definiše se kao binomni koeficijent i obeležava se sa [inlmath]n\choose k[/inlmath]:
[dispmath]{n\choose k}\:\overset{\text{def}}{=\!=}\:\begin{cases}
\frac{n!}{(n-k)!\cdot k!}, & k\in[0,n]\\
\\
0, & k\notin[0,n]
\end{cases}[/dispmath] Prema tome, formula za broj kombinacija bez ponavljanja može se napisati i u sledećem obliku:
[dispmath]\enclose{box}{C_n^k={n\choose k}}[/dispmath] Ako na gornji primer, u kojem smo imali [inlmath]5[/inlmath] elemenata od kojih biramo [inlmath]3[/inlmath] elementa, primenimo odgovarajuću formulu za kombinacije, dobijamo [inlmath]C_5^3={5\choose3}=\frac{5!}{(5-3)!\cdot3!}=\frac{5\cdot4\cdot\cancel{3!}}{2!\cdot\cancel{3!}}=10[/inlmath], što isto dobijamo i ako izbrojimo kombinacije napisane u tom primeru.



OSOBINE BINOMNOG KOEFICIJENTA

[dispmath]{n\choose0}={n\choose n}=1[/dispmath] Dokaz:
[dispmath]{n\choose0}=\frac{n!}{(n-0)!\cdot0!}=\frac{\cancel{n!}}{\cancel{n!}\cdot1}=1\\
{n\choose n}=\frac{n!}{(n-n)!\cdot n!}=\frac{\cancel{n!}}{0!\cdot\cancel{n!}}=1[/dispmath]
[dispmath]{n\choose1}={n\choose n-1}=n[/dispmath] Dokaz:
[dispmath]{n\choose1}=\frac{n!}{(n-1)!\cdot1!}=\frac{n\cdot\cancel{(n-1)!}}{\cancel{(n-1)!}}=n\\
{n\choose n-1}=\frac{n!}{[n-(n-1)]!\cdot(n-1)!}=\frac{n\cdot\cancel{(n-1)!}}{1!\cdot\cancel{(n-1)!}}=n[/dispmath]
Simetričnost:
[dispmath]{n\choose k}={n\choose n-k}[/dispmath] Dokaz:
[dispmath]{n\choose k}=\frac{n!}{(n-k)!\cdot k!}=\frac{n!}{k!\cdot(n-k)!}=\frac{n!}{[n-(n-k)]!\cdot(n-k)!}={n\choose n-k}[/dispmath]
Paskalova formula:
[dispmath]{n\choose k}={n-1\choose k-1}+{n-1\choose k}[/dispmath] Dokaz:
[dispmath]\begin{align}{n-1\choose k-1}+{n-1\choose k}&=\frac{(n-1)!}{[(n-1)-(k-1)]!\cdot(k-1)!}+\frac{(n-1)!}{(n-k-1)!\cdot k!}\\
&=\frac{(n-1)!}{(n-k)!\cdot(k-1)!}+\frac{(n-1)!}{(n-k-1)!\cdot k!}\\
&=\frac{(n-1)!}{(n-k)\cdot(n-k-1)!\cdot(k-1)!}+\frac{(n-1)!}{(n-k-1)!\cdot k\cdot(k-1)!}\\
&=\frac{(n-1)!}{(n-k-1)!\cdot(k-1)!}\cdot\left(\frac{1}{n-k}+\frac{1}{k}\right)\\
&=\frac{(n-1)!}{(n-k-1)!\cdot(k-1)!}\cdot\frac{\cancel k+n-\cancel k}{k(n-k)}\\
&=\frac{n\cdot(n-1)!}{(n-k)\cdot(n-k-1)!\cdot k\cdot(k-1)!}\\
&=\frac{n!}{(n-k)!\cdot k!}\\
&={n\choose k}
\end{align}[/dispmath]
Binomna formula:
[dispmath](a+b)^n={n\choose0}a^n+{n\choose1}a^{n-1}b+{n\choose2}a^{n-2}b^2+\cdots+{n\choose n-1}ab^{n-1}+{n\choose n}b^n=\sum_{k=0}^n{n\choose k}a^{n-k}b^k[/dispmath]
Suma binomnih koeficijenata u razvoju binoma jednaka je [inlmath]2^n[/inlmath]:
[dispmath]{n\choose0}+{n\choose1}+\cdots+{n\choose n}=2^n[/dispmath] Dokaz: u binomnu formulu uvrstimo [inlmath]a=b=1[/inlmath]:
[dispmath](1+1)^n=\sum_{k=0}^n{n\choose k}1^{n-k}1^k\qquad\Longrightarrow\qquad\sum_{k=0}^n{n\choose k}=2^n[/dispmath]
Suma binomnih koeficijenata na neparnim mestima u razvoju binoma jednaka je sumi binomnih koeficijenata na parnim mestima:
[dispmath]{n\choose0}+{n\choose2}+{n\choose4}+\cdots={n\choose1}+{n\choose3}+{n\choose5}+\cdots[/dispmath] Dokaz: u binomnu formulu uvrstimo [inlmath]a=1,\;b=-1[/inlmath]:
[dispmath][1+(-1)]^n={n\choose0}1^n+{n\choose1}1^{n-1}(-1)+{n\choose2}1^{n-2}(-1)^2+{n\choose3}1^{n-3}(-1)^3+{n\choose4}1^{n-4}(-1)^4+\cdots[/dispmath][dispmath]0^n={n\choose0}-{n\choose1}+{n\choose2}-{n\choose3}+{n\choose4}-\cdots[/dispmath][dispmath]{n\choose0}-{n\choose1}+{n\choose2}-{n\choose3}+{n\choose4}-\cdots=0[/dispmath][dispmath]{n\choose0}+{n\choose2}+{n\choose4}+\cdots={n\choose1}+{n\choose3}+\cdots[/dispmath]


PERMUTACIJE S PONAVLJANJEM

Permutacije s ponavljanjem od [inlmath]n[/inlmath] elemenata, među kojima ima [inlmath]m[/inlmath] međusobno različitih elemenata [inlmath]a_1,a_2,\ldots,a_m[/inlmath], predstavljaju načine na koje elemente [inlmath]a_1,a_2,\ldots,a_m[/inlmath] možemo rasporediti u niz, pri čemu se element [inlmath]a_1[/inlmath] u svakoj permutaciji pojavljuje [inlmath]n_1[/inlmath] puta, element [inlmath]a_2[/inlmath] se pojavljuje [inlmath]n_2[/inlmath] puta i tako dalje do elementa [inlmath]a_m[/inlmath] koji se u svakoj permutaciji pojavljuje [inlmath]n_m[/inlmath] puta. Naravno, pri tome je [inlmath]n_1+n_2+\cdots+n_m=n[/inlmath]. Posmatrajmo to na primeru raspoređivanja slova koja čine reč [inlmath]BARABA[/inlmath] (mislio sam prvo da uzmem reč [inlmath]MARAMA[/inlmath], ali ova mi je ipak nekako... „zvučnija“). U toj reči slovo [inlmath]A[/inlmath] se pojavljuje [inlmath]3[/inlmath] puta, slovo [inlmath]B[/inlmath] se pojavljuje [inlmath]2[/inlmath] puta, a slovo [inlmath]R[/inlmath], siromašak, samo jednom. Načini na koje je moguće rasporediti ova slova tako da se u svakom od rasporeda slova [inlmath]A[/inlmath], [inlmath]B[/inlmath] i [inlmath]R[/inlmath] ponavaljaju [inlmath]3[/inlmath], [inlmath]2[/inlmath] i [inlmath]1[/inlmath] put respektivno, biće:
[dispmath]\begin{array}{llllll}
AAABBR & AARBAB & ABBRAA & BAAABR & BARABA & RAAABB\\
AAABRB & AARBBA & ABRAAB & BAAARB & BARBAA & RAABAB\\
AAARBB & ABAABR & ABRABA & BAABAR & BBAAAR & RAABBA\\
AABABR & ABAARB & ABRBAA & BAABRA & BBAARA & RABAAB\\
AABARB & ABABAR & ARAABB & BAARAB & BBARAA & RABABA\\
AABBAR & ABABRA & ARABAB & BAARBA & BBRAAA & RABBAA\\
AABBRA & ABARAB & ARABBA & BABAAR & BRAAAB & RBAAAB\\
AABRAB & ABARBA & ARBAAB & BABARA & BRAABA & RBAABA\\
AABRBA & ABBAAR & ARBABA & BABRAA & BRABAA & RBABAA\\
AARABB & ABBARA & ARBBAA & BARAAB & BRBAAA & RBBAAA
\end{array}[/dispmath] Kada bismo za trenutak pretpostavili da ova tri slova [inlmath]A[/inlmath] nisu ista i obeležili ih sa [inlmath]A_1[/inlmath], [inlmath]A_2[/inlmath] i [inlmath]A_3[/inlmath], tada bismo od jedne permutacije, npr. permutacije [inlmath]RAABAB[/inlmath], dobili sledeće nove permutacije:
[dispmath]\begin{array}{llllll}
RA_1A_2BA_3B & RA_1A_3BA_2B & RA_2A_1BA_3B & RA_2A_3BA_1B & RA_3A_1BA_2B & RA_3A_2BA_1B
\end{array}[/dispmath] Primećujemo da bismo od te jedne permutacije dobili onoliko novih permutacija koliki je broj permutacija od ta tri različita slova [inlmath]A[/inlmath], tj. od [inlmath]A_1[/inlmath], [inlmath]A_2[/inlmath] i [inlmath]A_3[/inlmath]. To jest, dobili bismo [inlmath]3!=6[/inlmath] novih permutacija.
Da smo i dva slova [inlmath]B[/inlmath] označili sa [inlmath]B_1[/inlmath] i [inlmath]B_2[/inlmath] i posmatrali ih kao dva različita slova [inlmath]B[/inlmath], broj novih permutacija koje su nastale od te jedne bio bi uvećan još [inlmath]2![/inlmath] puta.
Uopšteno, kad bismo sve jednake elemente posmatrali kao različite (i time permutacije s ponavljanjem sveli na permutacije bez ponavljanja od [inlmath]n[/inlmath] elemenata), svaka od postojećih permutacija bi dala novih [inlmath]n_1!\cdot n_2!\cdots n_m![/inlmath] permutacija. Sledi da bismo, množenjem broja permutacija s ponavljanjem ([inlmath]\overline P_n^{n_1,n_2,\ldots,n_m}[/inlmath]) sa [inlmath]n_1!\cdot n_2!\cdots n_m![/inlmath], dobili broj permutacija bez ponavljanja od [inlmath]n[/inlmath] elemenata ([inlmath]n=n_1+n_2+\cdots+n_m[/inlmath]), a to je [inlmath]P_n=n![/inlmath]:
[dispmath]\overline P_n^{n_1,n_2,\ldots,n_m}\cdot n_1!\cdot n_2!\cdots n_m!=P_n=n![/dispmath] Odatle možemo, deljenjem obe strane sa [inlmath]n_1!\cdot n_2!\cdots n_m![/inlmath], odrediti broj permutacija s ponavljanjem:
[dispmath]\enclose{box}{\overline P_n^{n_1,n_2,\ldots,n_m}=\frac{n!}{n_1!\cdot n_2!\cdots n_m!}}[/dispmath] Ako ovu formulu primenimo na prikazani primer sa slovima reči [inlmath]BARABA[/inlmath], imaćemo da je [inlmath]n=6[/inlmath], [inlmath]n_1=3[/inlmath], [inlmath]n_2=2[/inlmath], [inlmath]n_3=1[/inlmath], pa je broj permutacija s ponavljanjem:
[dispmath]\overline P_6^{3,2,1}=\frac{6!}{3!\cdot2!\cdot1!}=\frac{6\cdot5\cdot4\cdot\cancel{3!}}{\cancel{3!}\cdot2}=60[/dispmath] što ćemo isto dobiti i ako jednostavno izbrojimo sve napisane permutacije s ponavljanjem koje čine slova reči [inlmath]BARABA[/inlmath].

Primetimo da se za slučaj kada se svaki element u permutacijama pojavljuje tačno jedanput ([inlmath]n_1=n_2=\cdots=n_m=1[/inlmath]), permutacije s ponavljanjem svode na permutacije bez ponavljanja (što je i logično):
[dispmath]\overline P_n^{1,1,\ldots,1}=\frac{n!}{1!\cdot1!\cdots1!}=n!=P_n[/dispmath] U tom slučaju i samo u tom slučaju, biće i [inlmath]m=n[/inlmath], tj. broj međusobno različitih elemenata biće jednak ukupnom broju elemenata.



VARIJACIJE S PONAVLJANJEM

Varijacije s ponavljanjem od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase predstavljaju načine na koje iz skupa od [inlmath]n[/inlmath] elemenata možemo [inlmath]k[/inlmath] puta birati po jedan element, pri čemu je moguće da neki elementi budu izabrani i više puta i pri čemu je bitan redosled odabira.
Jedan čest primer varijacija s ponavljanjem bio bi, ako bismo iz vreće u kojoj se nalazi [inlmath]n[/inlmath] različitih kuglica, [inlmath]k[/inlmath] puta izvlačili po jednu kuglicu a zatim je vraćali u vreću, prethodno zabeleživši koja je kuglica izvučena i vodeći računa o redosledu kuglica koje su izvučene.
Takođe, bacanje kockice čija je svaka strana numerisana brojem od [inlmath]1[/inlmath] do [inlmath]6[/inlmath], pri čemu beležimo dobijene brojeve vodeći računa o njihovom redosledu – predstavlja varijacije s ponavljanjem od [inlmath]6[/inlmath] elemenata [inlmath]k[/inlmath]-te klase, pri čemu [inlmath]k[/inlmath] označava ukupan broj bacanja kockice.
Još jedan primer, poznat iz informatike, bio bi formiranje osmobitnog binarnog broja od nula i jedinica (izvin'te zbog pleonazma – čim je osmobitni jasno je da je binarni, a čim je binarni jasno je da se sastoji od nula i jedinica, al' ja to zato da bi bilo što jasnije). Broj elemenata je [inlmath]n=2[/inlmath] (jedan element je nula, drugi element je jedinica), a klasa varijacija je [inlmath]8[/inlmath] (jer te nule i jedinice treba rasporediti na [inlmath]8[/inlmath] pozicija, tj. odabiramo ih [inlmath]8[/inlmath] puta). Broj binarnih brojeva koji se na taj način mogu formirati predstavlja broj varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa [inlmath]8.[/inlmath] klase.
Naravno, to isto važi i za formiranje brojeva i od cifara ostalih brojnih sistema – oktalnog, dekadnog, heksadekadnog itd...

Primer varijacija s ponavljanjem od [inlmath]3[/inlmath] elementa [inlmath]\{A,B,C\}[/inlmath] [inlmath]4.[/inlmath] klase (što znači da biramo [inlmath]4[/inlmath] elementa s ponavljanjem, vodeći pri tome računa o njihovom poretku) izgledao bi ovako:
[dispmath]\begin{array}{lllllllll}
AAAA & ABAA & ACAA & BAAA & BBAA & BCAA & CAAA & CBAA & CCAA\\
AAAB & ABAB & ACAB & BAAB & BBAB & BCAB & CAAB & CBAB & CCAB\\
AAAC & ABAC & ACAC & BAAC & BBAC & BCAC & CAAC & CBAC & CCAC\\
AABA & ABBA & ACBA & BABA & BBBA & BCBA & CABA & CBBA & CCBA\\
AABB & ABBB & ACBB & BABB & BBBB & BCBB & CABB & CBBB & CCBB\\
AABC & ABBC & ACBC & BABC & BBBC & BCBC & CABC & CBBC & CCBC\\
AACA & ABCA & ACCA & BACA & BBCA & BCCA & CACA & CBCA & CCCA\\
AACB & ABCB & ACCB & BACB & BBCB & BCCB & CACB & CBCB & CCCB\\
AACC & ABCC & ACCC & BACC & BBCC & BCCC & CACC & CBCC & CCCC
\end{array}[/dispmath] Radi izvođenja formule za broj varijacija s ponavljanjem, primetimo da je svako od izvlačenja nezavisno od ostalih, što znači da ishod bilo kog izvlačenja neće ni na koji način zavisiti od ishoda prethodnih i budućih izvlačenja. Broj načina na koji iz skupa od [inlmath]n[/inlmath] elemenata možemo u prvom izvlačenju izvući neki element je, naravno, [inlmath]n[/inlmath]. Pošto time što smo taj element već izvukli, ne znači da ga ne možemo izvući i sledeći put (varijacije su s ponavljanjem), broj načina na koji u drugom izvlačenju možemo izvući neki element takođe će biti [inlmath]n[/inlmath]. Isto važi i za treće izvlačenje, i za četvrto... i za [inlmath]k[/inlmath]-to izvlačenje. Dakle, množimo sve ove načine i dobijamo broj varijacija s ponavljanjem od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase:
[dispmath]\overline V_n^k=\underbrace{n\cdot n\cdots n}_{k\text{ činilaca}}[/dispmath][dispmath]\enclose{box}{\overline V_n^k=n^k}[/dispmath] Dok smo kod varijacija bez ponavljanja imali uslov da je [inlmath]k\le n[/inlmath], kod varijacija s ponavljanjem to uopšte ne mora biti uslov. Kod njih može biti [inlmath]k<n[/inlmath], može biti [inlmath]k=n[/inlmath], ali može biti i [inlmath]k>n[/inlmath]. Upravo smo takav slučaj i imali u gornjem primeru, u kojem je bilo [inlmath]n=3[/inlmath], a [inlmath]k=4[/inlmath].

U tom primeru broj napisanih varijacija s ponavljanjem je [inlmath]81[/inlmath]. Isto ćemo dobiti i ako primenimo formulu za broj varijacija s ponavljanjem od [inlmath]3[/inlmath] elementa [inlmath]4.[/inlmath] klase ([inlmath]n=3,\;k=4[/inlmath]):
[dispmath]\overline V_3^4=3^4=81[/dispmath]


KOMBINACIJE S PONAVLJANJEM

Kombinacije s ponavljanjem od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase predstavljaju načine na koje iz skupa od [inlmath]n[/inlmath] elemenata možemo [inlmath]k[/inlmath] puta birati po jedan element, pri čemu je moguće da neki elementi budu izabrani i više puta i pri čemu nije bitan redosled odabira. Znači, razlika u odnosu na varijacije s ponavljanjem je samo u tome, što kod kombinacija s ponavljanjem, isto kao i kod kombinacija bez ponavljanja, redosled izabranih elemenata nije bitan.
Primeri kombinacija s ponavljanjem vrlo su slični primerima varijacija s ponavljanjem. Jedan primer je izvlačenje kuglica iz vreće, pri čemu se u vreći nalazi [inlmath]n[/inlmath] kuglica – svaki put izvučemo po jednu kuglicu, zabeležimo koja kuglica je izvučena i vratimo je, zatim vršimo novi odabir i tako [inlmath]k[/inlmath] puta. Nakon [inlmath]k[/inlmath] puta izbrojimo koliko smo puta izvukli koju kuglicu, s tim što sada, za razliku od varijacija s ponavljanjem, ne vodimo računa o redosledu njihovog izvlačenja.
Isti slučaj i s bacanjem kockice [inlmath]k[/inlmath] puta, pri čemu nam nije od važnosti kojim su redosledom ispadali brojevi, već samo koji su brojevi dobijeni i koliko je puta dobijen koji broj, što predstavlja kombinacije s ponavljanjem od [inlmath]6[/inlmath] elemenata [inlmath]k[/inlmath]-te klase.

Primer kombinacija s ponavljenjem od [inlmath]3[/inlmath] elementa [inlmath]\{A,B,C\}[/inlmath] [inlmath]4.[/inlmath] klase (što znači da biramo [inlmath]4[/inlmath] elementa s ponavljanjem, ne vodeći pri tome računa o njihovom poretku) izgledao bi ovako:
[dispmath]\begin{array}{lllll}
AAAA & AABB & ABBB & ACCC & BBCC\\
AAAB & AABC & ABBC & BBBB & BCCC\\
AAAC & AACC & ABCC & BBBC & CCCC
\end{array}[/dispmath] Iako smo formulu za kombinacije bez ponavljanja izveli vrlo jednostavno, tako što smo broj odgovarajućih varijacija bez ponavljanja samo podelili brojem permutacija bez ponavljanja od onoliko elemenata kolika je klasa tih varijacija ([inlmath]C_n^k=\frac{V_n^k}{P_k}[/inlmath]), kod kombinacija s ponavljanjem ne možemo primeniti taj rezon, budući da kod varijacija s ponavljanjem možemo imati po više istih elemenata, pa se neće uvek isti broj varijacija preslikavati u jednu kombinaciju. Izvođenje formule za kombinacije s ponavljanjem je složenije i potrebno je da koristimo analogiju s raspoređivanjem kuglica u kutije.

Ta analogija bi izgledala ovako: neka iz skupa od [inlmath]n[/inlmath] elemenata vršimo odabir [inlmath]k[/inlmath] puta, pri čemu isti element možemo izabrati i više puta. Zamislimo da imamo [inlmath]n[/inlmath] praznih kutija (znači, onoliko kutija koliko ima elemenata skupa iz kojeg vršimo odabir), poređanih u niz i priljubljenih jedna uz drugu, tako da su granice između njih pregradni zidovi. Zamislimo, zatim, i da imamo [inlmath]k[/inlmath] kuglilca, znači, onoliko kuglica koliko puta vršimo odabir. I, na kraju, zamislimo da svaki put kad odaberemo [inlmath]i[/inlmath]-ti element tog skupa, ubacujemo jednu kuglicu u [inlmath]i[/inlmath]-tu kutiju. Znači, ako smo izabrali [inlmath]3.[/inlmath] element, ubacujemo kuglicu u [inlmath]3.[/inlmath] kutiju. Ako smo zatim izabrali [inlmath]5.[/inlmath] element, ubacujemo sledeću kuglicu u [inlmath]5.[/inlmath] kutiju. Ako smo nakon toga opet izabrali [inlmath]3.[/inlmath] element, ubacujemo još jednu kuglicu u [inlmath]3.[/inlmath] kutiju, tako da će u [inlmath]3.[/inlmath] kutiji sada biti dve kuglice itd... Koliko kuglica imamo u nekoj kutiji, to znači da smo toliko puta izvukli odgovarajući element. Nakon [inlmath]k[/inlmath] izvlačenja, u svim kutijama će ukupno biti [inlmath]k[/inlmath] kuglica, a njihov broj u svakoj od kutija pokazivaće koliko smo puta izvukli odgovarajući element.

Recimo da smo [inlmath]1.[/inlmath] element izvukli [inlmath]4[/inlmath] puta, [inlmath]2.[/inlmath] element jednom, [inlmath]3.[/inlmath] element [inlmath]2[/inlmath] puta, [inlmath]4.[/inlmath] element [inlmath]5[/inlmath] puta, [inlmath]5.[/inlmath] element nijednom, [inlmath]6.[/inlmath] element [inlmath]3[/inlmath] puta... i [inlmath]n[/inlmath]-ti element [inlmath]2[/inlmath] puta. Situacija s kuglicama u kutijama izgledala bi ovako:

[dispmath]\begin{array}{|c|c|c|c|c|c|c|c|}
\hspace{2em} & \hspace{2em} & \hspace{2em} & \hspace{2em} & \hspace{2em} & \hspace{2em} & \hspace{7em} & \hspace{2em}\\
\circ & & & \circ\circ & & & \ldots & \\
\circ\circ\circ & \circ & \circ\circ & \circ\circ\circ & & \circ\circ\circ & & \circ\circ\\ \hline
\end{array}\\ \begin{array}{cccccccc}
\hspace{2em} & \hspace{2em} & \hspace{2em} & \hspace{2em} & \hspace{2em} & \hspace{2em} & \hspace{7em} & \hspace{2em}\\
1 & 2 & 3 & 4 & 5 & 6 & \cdots & n
\end{array}[/dispmath] Sada se traženje formule za kombinacije s ponavljanjem od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase svodi na traženje formule za broj načina na koje možemo [inlmath]k[/inlmath] kuglica rasporediti u [inlmath]n[/inlmath] kutija. Na gornjoj slici vidimo jedan od takvih načina, a potrebno je, dakle, odgovoriti na pitanje, koliko ukupno ima različitih načina da se tih [inlmath]k[/inlmath] kuglica rasporede u tih [inlmath]n[/inlmath] kutija.
Sada te kuglice u kutijama predstavimo na sledeći način. Napravimo niz od simbola [inlmath]\circ[/inlmath] i [inlmath]|[/inlmath], pri čemu simbol [inlmath]\circ[/inlmath] predstavlja kuglicu, a simbol [inlmath]|[/inlmath] predstavlja pregradni zid između dve kutije. Pri tome, levi zid prve i desni zid poslednje kutije ignorišemo. Gornja situacija s kutijama i kuglicama, predstavljena na ovaj način, izgledala bi, dakle, ovako:
[dispmath]\circ\circ\circ\circ|\circ|\circ\circ|\circ\circ\circ\circ\circ||\circ\circ\circ|\cdots |\circ\circ[/dispmath] Naravno, tamo gde imamo dva simbola [inlmath]|[/inlmath] jedan do drugog, znači da je kutija između njih prazna (što odgovara slučaju da element koji ta kutija predstavlja nije izvučen nijednom). Može se desiti i da bude više simbola [inlmath]|[/inlmath] jedan uz drugi, što znači da su sve kutije unutar tih simbola prazne.
Pošto kutija ukupno imamo [inlmath]n[/inlmath], znači da ćemo pregradnih zidova ukupno imati [inlmath]n-1[/inlmath]. Kuglica imamo [inlmath]k[/inlmath]. Znači, kuglica i pregradnih zidova (tj. simbola [inlmath]\circ[/inlmath] i simbola [inlmath]|[/inlmath]) ukupno imamo [inlmath]n+k-1[/inlmath].
Traženi broj kombinacija s ponavljanjem od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase ovime smo sveli na broj načina na koje možemo [inlmath]k[/inlmath] kuglica rasporediti na [inlmath]n+k-1[/inlmath] pozicija. Drugim rečima, od [inlmath]n+k-1[/inlmath] pozicija, biramo onih [inlmath]k[/inlmath] pozicija na koje ćemo smestiti kuglice – broj načina na koje to možemo učiniti je broj kombinacija bez ponavljanja od [inlmath]n+k-1[/inlmath] elemenata [inlmath]k[/inlmath]-te klase, tj. [inlmath]n+k-1\choose k[/inlmath]. Prema tome, dobili smo formulu za broj kombinacija s ponavljanjem od [inlmath]n[/inlmath] elemenata [inlmath]k[/inlmath]-te klase:
[dispmath]\enclose{box}{\overline C_n^k={n+k-1\choose k}}[/dispmath] Naravno, umesto posmatranja [inlmath]k[/inlmath] kuglica, mogli smo posmatrati i na koliko načina možemo [inlmath]n-1[/inlmath] pregradnih zidova, tj. [inlmath]n-1[/inlmath] simbola [inlmath]|[/inlmath], postaviti na [inlmath]n+k-1[/inlmath] pozicija. Dobili bismo da to možemo učiniti na [inlmath]n+k-1\choose n-1[/inlmath] načina, što je, zbog ranije pomenute osobine simetričnosti binomnog koeficijenta, jednako rezultatu [inlmath]n+k-1\choose k[/inlmath].

Treći način određivanja broja mogućnosti na koje [inlmath]k[/inlmath] kuglica i [inlmath]n-1[/inlmath] pregradnih zidova možemo rasporediti na [inlmath]n+k-1[/inlmath] pozicija je preko permutacija s ponavljanjem od [inlmath]n+k-1[/inlmath] elemenata, pri čemu se kuglice pojavljuju [inlmath]k[/inlmath] puta, a pregradni zidovi [inlmath]n-1[/inlmath] puta, pa je broj tih permutacija jednak [inlmath]\overline P_{n+k-1}^{k,n-1}=\frac{(n+k-1)!}{k!\cdot(n-1)!}={n+k-1\choose k}[/inlmath].

Možemo primetiti da, kao ni kod varijacija s ponavljanjem, tako ni kod kombinacija s ponavljanjem ne postoji uslov da je [inlmath]k\le n[/inlmath]. Bez obzira na to da li je [inlmath]k[/inlmath] veće, jednako ili manje od [inlmath]n[/inlmath], u binomnom koeficijentu [inlmath]n+k-1\choose k[/inlmath] donji broj, [inlmath]k[/inlmath], nikad ne može biti veći od gornjeg broja, [inlmath]n+k-1[/inlmath].

Sada kad znamo formulu za broj kombinacija s ponavljanjem, možemo je proveriti i na gorepomenutom primeru izbora [inlmath]4[/inlmath] slova iz skupa [inlmath]\{A,B,C\}[/inlmath]. Kad se izbroje sve napisane kombinacije, vidi se da ih ima [inlmath]15[/inlmath]. A evo i računski:
[dispmath]n=3,\;k=4\quad\Longrightarrow\quad\overline C_3^4={3+4-1\choose4}={6\choose4}=\frac{6!}{(6-4)!\cdot4!}=\frac{6\cdot5\cdot\cancel{4!}}{2!\cdot\cancel{4!}}=\frac{6\cdot5}{2}=15[/dispmath]
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Kombinatorika – spisak formula, primeri, izvođenja formula, osobine

Postod Miladin Jovic » Petak, 22. Januar 2016, 21:51

Ovaj dokaz za kombinacije bez ponavljanja mi se veoma dopao.

Neka je [inlmath]A_n[/inlmath] konačan skup od [inlmath]n[/inlmath] elemenata.
Označimo sa [inlmath]A[/inlmath] skup svih permutacija skupa [inlmath]A_n[/inlmath], a sa [inlmath]B[/inlmath] skup svih kombinacija [inlmath]k[/inlmath]-te klase skupa [inlmath]A_n[/inlmath]. Tada je [inlmath]|A|=n![/inlmath] , [inlmath]|B|=C^k_n[/inlmath]. Neka je [inlmath]f:\:A\to B[/inlmath] preslikavanje definisano na sledeći način: svaka permutacija skupa [inlmath]A[/inlmath] preslikava se u onu kombinaciju [inlmath]k[/inlmath]-te klase skupa [inlmath]B[/inlmath], koja se dobija tako što se uzme prvih [inlmath]k[/inlmath] elemenata te permutacije. Permutovanje prvih [inlmath]k[/inlmath] elemenata jedne permutacije skupa [inlmath]A_n[/inlmath] ne dovodi do promene kombinacije, a isto važi i za permutovanje poslednjih [inlmath]n-k[/inlmath] elemenata. Na osnovu principa proizvoda, zaključujemo da se ukupno [inlmath]k!(n-k)![/inlmath] permutacija skupa [inlmath]A[/inlmath] preslikava u jednu kombinaciju skupa [inlmath]B[/inlmath]. Sada na osnovu principa većeg broja zaključujemo da je
[dispmath]|A|=k!(n-k)!|B|[/dispmath]
tj.
[dispmath]C^k_n=\frac{n!}{k!(n-k)!}[/dispmath]
Zaslužni forumaš
 
Postovi: 378
Zahvalio se: 243 puta
Pohvaljen: 138 puta

Re: Kombinatorika – spisak formula, primeri, izvođenja formula, osobine

Postod Miladin Jovic » Subota, 23. Januar 2016, 00:20

Evo još jednog dokaza za permutacije sa ponavljanjem.

Neka je data familija od [inlmath]n[/inlmath] objekata.
[dispmath]\{\underbrace{a_1,\ldots,a_1}_{n_1},\underbrace{a_2,\ldots,a_2}_{n_2},\ldots,\underbrace{a_k,\ldots,a_k}_{n_k}\}[/dispmath]
Od ukupnog broja [inlmath]n_1+n_2+\cdots+n_k=n[/inlmath] pozicija izdvojimo [inlmath]n_1[/inlmath] i u njih stavimo elemenat [inlmath]a_1[/inlmath]; zatim od preostalog broja [inlmath]n_2+\cdots+n_k[/inlmath] pozicija izdvojimo [inlmath]n_2[/inlmath] i u njih stavimo [inlmath]a_2[/inlmath] itd. redom. Na kraju ostaje [inlmath]n_k[/inlmath] pozicija u koje stavljamo elemenat [inlmath]a_k[/inlmath]. Kako pojedina izdvajanja predstavljaju kombinacije bez ponavljanja, te je prema principu proizvoda broj svih izdvajanja jednak:
[dispmath]C_n^{n_1}\cdot C_{n_2+\cdots+n_k}^{n_2}\cdots C^{n_{k - 1}}_{n_{k-1}+n_k}\cdot C_{n_k}^{n_k}[/dispmath]
Posle sređivanja, dobija se
[dispmath]\frac{n!}{n_1!\cdot n_2!\cdots n_k!}[/dispmath]
Zaslužni forumaš
 
Postovi: 378
Zahvalio se: 243 puta
Pohvaljen: 138 puta


Povratak na KOMBINATORIKA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 39 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 15:05 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs