[quote="Nesi"]dakle, imamo...
korolar Vandermondeove formule, tocnije imamo tzv. Vandermondeove konvolucije
[code:1]min {m,n}
suma (m povrh k) * (n povrh k) = (m + n povrh n)
k=0[/code:1]
zanima me specijalni slucaj kad m=n, tj. za to me zanima kombinatorno objasnjenje
[code:1]n
suma (n povrh k) ^ 2 = (2n povrh n)
k=0[/code:1]
hint je bio da su n i 2n parovi cipela
al nije da mi taj hint ista otkriva :([/quote]
Uzmi cipele i slaži... ;-)
No dobro, ne moraš. Dakle, imaš n parova cipelâ, što je naravno 2n cipelâ - n lijevih i n desnih. Gledaš na koliko načina možeš od toga odabrati n cipelâ (parovi su nebitni ovdje). Desna strana kaže zdravorazumski da je to 2n povrh n .
Lijeva strana odgovara ovakvom gledanju: biraš n cipelâ , od kojih su neke lijeve a neke desne. Broj lijevih među njima označimo s k . Budući da lijevih cipelâ ima n , k očito ide do n , a budući da i desnih ima n (that is, dovoljno), k ide od 0 . So, k:0~n .
Za svaki takav k , biraš k (od n) lijevih na n povrh k načina. Među desnima gledaš one koje ostaju - budući da ih biraš n-k , ostat će ti ih k , a odabravši njih odabrala si sve. Dakle to je također n povrh k načina.
Za svaki fiksan k , izbori lijevih i desnih su nazavisni, pa ih oba možeš učiniti na (n povrh k)^2 načina. Sumiravši to po gorenavedenim granicama za k , dobiješ lijevu stranu. Izjednačivši to s gore objašnjenom desnom, dobiješ ono što ti treba.
HTH,
Nesi (napisa): | dakle, imamo...
korolar Vandermondeove formule, tocnije imamo tzv. Vandermondeove konvolucije
Kod: | min {m,n}
suma (m povrh k) * (n povrh k) = (m + n povrh n)
k=0 |
zanima me specijalni slucaj kad m=n, tj. za to me zanima kombinatorno objasnjenje
Kod: | n
suma (n povrh k) ^ 2 = (2n povrh n)
k=0 |
hint je bio da su n i 2n parovi cipela
al nije da mi taj hint ista otkriva |
Uzmi cipele i slaži...
No dobro, ne moraš. Dakle, imaš n parova cipelâ, što je naravno 2n cipelâ - n lijevih i n desnih. Gledaš na koliko načina možeš od toga odabrati n cipelâ (parovi su nebitni ovdje). Desna strana kaže zdravorazumski da je to 2n povrh n .
Lijeva strana odgovara ovakvom gledanju: biraš n cipelâ , od kojih su neke lijeve a neke desne. Broj lijevih među njima označimo s k . Budući da lijevih cipelâ ima n , k očito ide do n , a budući da i desnih ima n (that is, dovoljno), k ide od 0 . So, k:0~n .
Za svaki takav k , biraš k (od n) lijevih na n povrh k načina. Među desnima gledaš one koje ostaju - budući da ih biraš n-k , ostat će ti ih k , a odabravši njih odabrala si sve. Dakle to je također n povrh k načina.
Za svaki fiksan k , izbori lijevih i desnih su nazavisni, pa ih oba možeš učiniti na (n povrh k)^2 načina. Sumiravši to po gorenavedenim granicama za k , dobiješ lijevu stranu. Izjednačivši to s gore objašnjenom desnom, dobiješ ono što ti treba.
HTH,
|