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 ...