From veky@student.math.hr Fri Dec 19 09:55:06 2003 Subject: Re: pitanje Lines: 81 Message-ID: <slrnbu3c97.4ft.veky@student.math.hr> References: <brrsis$gqi$1@ls219.htnet.hr> In article <brrsis$gqi$1@ls219.htnet.hr>, black wrote: > pozdrav svima! > >jel bi mi mogao netko dati neku formulu kako izracunati broj mogucih >kombinacija... ono, recimo, imam 15 brojeva i zelim vidjet koliko ima >kombinacija ako kombiniram po tri broja od tih 15 > >npr, brojevi su 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 > >1. kombinacija:1,2,3 >2. kombinacija:1,2,4 >3. kombinacija:1,2,5 >4. kombinacija:1,2,6 > >i tako dalje... kako to izracunati? [lesson title="vrlo blagi uvod u binomne koeficijente"] Stvar se zove "binomni koeficijent". To je opcenito funkcija dva broja, jednog kompleksnog i jednog cijelog, no tebi je ovdje dovoljno da su oba broja prirodni. Ako su n i k prirodni brojevi i k<=n , tad (n choose k) (pise se kao n iznad k u oblim zagradama, nesto poput matrice 2x1 , i cita se " n povrh k ") oznacava broj k-clanih podskupova n-clanog skupa (ili, buduci da se konacni podskupovi jos zovu "kombinacije", broj k-kombinacija n-skupa ). Postoji dosta formula za racunanje binomnih koeficijenata (i jos vise zgodnih jednakosti koje oni zadovoljavaju), no valjda je najjednostavnija za zapisati ova: (n choose k) = n! / ( k! * (n-k)! ) (gdje je s x! oznacen x faktorijela, odnosno produkt svih prirodnih brojeva od 1 do x - npr. 5!=1*2*3*4*5=120 ). No naravno, u toj formuli se obicno punoprevise toga mnozi, pa onda skracuje. Zato postoji druga, koja nije tako simple za zapisati, ali je puno brze racunati s njom: (n choose k) = n\^k / k! (gdje je s n\^k oznacena tzv. padajuca potencija, koju racunas tako da mnozis brojeve kao kod obicne k-te potencije, pocevsi s n , samo ne iste, vec svaki put za jedan manje - npr. 7\^3=7*6*5=210 . BTW, faktorijela je specijalni slucaj padajuce potencije - k!=k\^k :). Ok. Ono sto tebi vjerojatno treba je binomni koeficijent za n=15 i k=3 , odnosno 15 povrh 3 . On je po gornjoj formuli jednak (15 choose 3) = 15\^3 / 3! = (15*14*13)/(3*2*1) = 5*7*13 = 455 . Naravno, mozes i 15!/(3!*(15-3)!)=15!/(3!*12!)=1307674368000/(6*479001600)= =1307674368000/2874009600=455 . :-) A mozes i razmisljati ovako (lakom generalizacijom mozes vidjeti zasto su gornje formule bas takve kakve jesu): za pocetak pretpostavimo da ti je redoslijed bitan, odnosno da npr. 1,2,3 i 1,3,2 smatras razlicitima (mozda to i jest slucaj... tada nastavi citati s vecim zanimanjem:). U tom slucaju trebas odabrati tri broja od njih 15, _redom_, i pritom nikad ne odabiruci neki broj koji si vec odabrao. Prvi mozes odabrati kao bilo koji izmedu njih 15 , dakle na 15 nacina. Drugi mozes odahrati kao bilo koji izmedu njih 15 _osim prvog_, dakle imas 14 mogucnosti. Za treci imas sve mogucnosti osim da ponovo odaberes prvi, illi da ponovo odaberes drugi, dakle 15 osim njih dvije, odnosno 13 . Sve skupa mozes napraviti na 15*14*13=15\^3=2730 nacina. I to je odgovor ako su ti 1,3,2 i 1,2,3 razliciti objekti. No ako nisu, lako se vidi da si zapravo svakog od njih brojao 6 puta: npr. 2,5,6 si brojao kao 2,5,6 , 2,6,5 , 5,2,6 , 5,6,2 , 6,2,5 i 6,5,2 . Dakle, onih koje zelis smatrati razlicitim ima 6 puta manje, odnosno 2730/6=455 . [/lesson] Pitanja? >nadam se da sam bio dovoljno jasan, ... I mi se nadamo. :-) -- Veky ... la poesia ...