Kombinatorika bez ponavljanja podrazumijeva se kao različiti skupovi koji se mogu oblikovati pomoću «n» elemenata, odabranih između x u x. Svaki skup mora se razlikovati od prethodnog barem u jednom od svojih elemenata (redoslijed nije važan) i ne može se ponoviti.
Kombinatorika bez ponavljanja uobičajena je u statistici i matematici. To odgovara mnogim stvarnim životnim situacijama i njegova je primjena vrlo jednostavna.
Uzmimo za primjer studenta koji ima ispit od 4 pitanja. Od 4 pitanja mora odabrati tri. Koliko bi različitih kombinacija student mogao napraviti? Ako malo razmislimo, vidjeli bismo (bez stvarne primjene formule) da bi student mogao odabrati kako će odgovoriti na 3 pitanja na četiri različita načina.
- Skup / opcija 1: Odgovorite na pitanja 1,2,3.
- Skup / opcija 2: Odgovorite na pitanja 1,2,4.
- Skup / opcija 3: Odgovorite na pitanja 1,3,4.
- Skup / opcija 4: Odgovorite na pitanja 2,3,4.
Kao što vidimo, učenik može oblikovati 4 skupa (n) od 3 elementa (x). Stoga nam kombinatorika bez ponavljanja govori kako oblikovati ili grupirati konačnu količinu podataka / opažanja, u skupinama određene veličine, a da se nijedan element ne može ponoviti u svakoj skupini. To je glavna razlika između kombinacionog s ponavljanjem (elementi u svakoj skupini mogu se ponoviti) i kombinacijskog bez ponavljanja (niti jedan element ne može se ponoviti u svakoj grupi)
Da u ovom primjeru istaknemo da je riječ o kombinatorici bez ponavljanja, budući da učenik ne može postaviti niti jedno pitanje više puta. Stoga se elementi skupova ne mogu ponoviti.
U prethodnom slučaju, s obzirom na to da je ukupan broj elemenata malen, a količina skupa velika, broj opcija je malen i može se lako zaključiti bez primjene formule. U slučaju izravne primjene formule, brojnik bi bio 24 (4 * 3 * 2 * 1), a nazivnik 6 (3 * 2 * 1 * 1) s kojim bismo na isti način došli do izračuna bez razmišljanja o tome kako bismo ta četiri pitanja mogli grupirati u tri.
Kako izračunati kombinatoriku bez ponavljanja?
Formula kombinacije bez ponavljanja je:
Gdje:
- n = Ukupna zapažanja
- x = Broj odabranih stavki
Primjer kombinatorni bez ponavljanja
Zamislimo vojni vod od 12 vojnika. Vojni kapetan želi formirati skupine od po 2 vojnika kako bi se infiltrirali iza neprijateljskih linija na različitim točkama, koliko bi različitih skupina mogao formirati?
Da bismo riješili problem, prvo moramo identificirati ukupan broj elemenata. U ovom slučaju ukupno je 12 vojnika, stoga već imamo svoje n. Budući da kapetan želi skupine od po 2, već znamo koliki je naš x. Znajući to, mogli bismo zamijeniti u formuli i imati broj kombinacija skupina 2.
- n = 12
- x = 2
Prilikom zamjene:
Primjenjujući faktorijel za nazivnik, imali bismo 12 * 11 * 10 * … * 1 = 479,001.600. Za nazivnik imamo 2 * 1 * 10 * 9 * 8 … * 1 = 7.257.600. Naš kombinacijski broj je = 479,001.600 / 7.257.600 = 66.
Kao što vidimo, kapetan može formirati 66 različitih parova vojnika među 12 koliko ih ima.