Apsorpcija binomnih koeficijenata
> Jel bi mi mogao pojasniti Veljanov dokaz svojstva apsorpcije binomnih
> koeficijenata, mislim strana 66. u novoj knjizi. Iako mi je samo
> svojstvo kombinatorno jasno (bar se nadam - od n objekata mozemo
> izabrati r na n povrh r nacina ili prvo mozemo izabrati jednog na n
> nacina, a onda od preostalih n-1 jos na r-1 nacina. Buduci da poredak
> nije vazan, dobit cemo r istih odabira (jer smo prvo mogli izabrati
> prvi, pa drugi, .. pa r-ti), pa jos podijelimo sa r i to je to.
>
> On uspostavlja neku fantomsku bijekciju za koju tvrdi da stima, a ja
> bih htio razumjeti i formalno matematicki dokaz jer ipak treba znati
> na taj nacin razmisljati.
Pa... treba se znati tako izražavati, jer si onda siguran da je ono što intuitivno misliš istina. No naravno da je stvar zapravo ovo što si ti opisao, samo preciznije. :-)
Dakle, prvo što treba razjasniti je da u kombinatornim interpretacijama nema razlomaka -- bar ne onih netrivijalnih. :-) Dakle, da bi dokazao (n#r)=n/r*(n-1#r-1) , ide prvo to pretvoriti u manifestno prirodne brojeve, kako bi znao to interpretirati kao kardinalne brojeve nekih skupova (npr. desna strana bi mogla značiti Kartezijev produkt, ali prvi faktor mu očito ne može imati n/r elemenata, ako r(!|)n ).
So, pomnoži s r i dobije r*(n#r)=n*(n-1#r-1) . Sad može obje strane jednakosti interpretirati kao kardinalnosti konačnih skupova, preciznije Kartezijevih produkata. Što je na lijevoj strani? Uređeni parovi (a, A), gdje je A@([n]#r) te a@A. Drugim riječima, broji r-člane podskupove od [n], svaki skupa s nekim njegovim istaknutim elementom.
> koeficijenata, mislim strana 66. u novoj knjizi. Iako mi je samo
> svojstvo kombinatorno jasno (bar se nadam - od n objekata mozemo
> izabrati r na n povrh r nacina ili prvo mozemo izabrati jednog na n
> nacina, a onda od preostalih n-1 jos na r-1 nacina. Buduci da poredak
> nije vazan, dobit cemo r istih odabira (jer smo prvo mogli izabrati
> prvi, pa drugi, .. pa r-ti), pa jos podijelimo sa r i to je to.
>
> On uspostavlja neku fantomsku bijekciju za koju tvrdi da stima, a ja
> bih htio razumjeti i formalno matematicki dokaz jer ipak treba znati
> na taj nacin razmisljati.
Pa... treba se znati tako izražavati, jer si onda siguran da je ono što intuitivno misliš istina. No naravno da je stvar zapravo ovo što si ti opisao, samo preciznije. :-)
Dakle, prvo što treba razjasniti je da u kombinatornim interpretacijama nema razlomaka -- bar ne onih netrivijalnih. :-) Dakle, da bi dokazao (n#r)=n/r*(n-1#r-1) , ide prvo to pretvoriti u manifestno prirodne brojeve, kako bi znao to interpretirati kao kardinalne brojeve nekih skupova (npr. desna strana bi mogla značiti Kartezijev produkt, ali prvi faktor mu očito ne može imati n/r elemenata, ako r(!|)n ).
So, pomnoži s r i dobije r*(n#r)=n*(n-1#r-1) . Sad može obje strane jednakosti interpretirati kao kardinalnosti konačnih skupova, preciznije Kartezijevih produkata. Što je na lijevoj strani? Uređeni parovi (a, A), gdje je A@([n]#r) te a@A. Drugim riječima, broji r-člane podskupove od [n], svaki skupa s nekim njegovim istaknutim elementom.
Što je na desnoj strani? Uređeni parovi (b, B), gdje je (na prvi pogled) B@([n-1]#r-1) te b@[n]. No ovaj [n-1] je malo šašav... zašto bismo izbacivali baš n iz [n]? Puno je bolje izbaciti neki koji već imamo, konkretno b. (Primijeti da je i na lijevoj strani veza između a i A, samo je tamo pozitivna a@A. Ovdje je negativna b(!@)B.) Dakle, zapravo, na desnoj strani brojimo (b, B) takve da je b@[n] i B@([n]\{b}#r-1).
Sad stvarno nije teško vidjeti bijekciju. Ako ti netko da (a, A), gdje A ima r elemenata među kojima je a, ti vratiš (a, A\{a}) -- to je očito par kojem drugi član ima r-1 elemenata među kojima nije prvi član (a). U suprotnom smjeru, ako ti netko da (b, B) gdje B ima r-1 elemenata među kojima nije b, vratiš (b, BU{b}) -- i to je očito na lijevoj strani.
Ta dva preslikavanja su jedno drugom inverzi (ako ubaciš b pa ga izbaciš, dobit ćeš isto ako b nije bio na početku unutra, a isto tako ako izbaciš a koji jest unutra pa ga vratiš, dobit ćeš isto), pa su bijekcije odnosno broj elemenata lijevog skupa jednak je broju elemenata desnog. Kved.
