Práve som písal riešenie jedného príkladu, v ktorom som použil nasledovnú kombinatorickú identitu:
Hľadím na ňu už asi dvadsať minút a nenapadá ma, ako by som ju dokázal. Vedeli by ste mi pomôcť?
26 septembra 2009
Kombinatorická identita
Už takmer 12 hodín bez väčšej prestávky pracujem na zbierke príkladov z pravdepodobnosti. (Neverili by ste, koľko je s jej napísaním roboty; ale čím ďalej, tým viac sa ma zmocňuje pocit, že keď bude naša zbierka na svete, tak z nej budeme mať radosť.)
Práve som písal riešenie jedného príkladu, v ktorom som použil nasledovnú kombinatorickú identitu:
Hľadím na ňu už asi dvadsať minút a nenapadá ma, ako by som ju dokázal. Vedeli by ste mi pomôcť?
Práve som písal riešenie jedného príkladu, v ktorom som použil nasledovnú kombinatorickú identitu:
Hľadím na ňu už asi dvadsať minút a nenapadá ma, ako by som ju dokázal. Vedeli by ste mi pomôcť?
Prihlásiť na odber:
Zverejniť komentáre (Atom)
7 komentárov:
Napadla mě matematická indukce, první dva kroky jsem zvládla, pro jedničku to platí a pro n předpokládám, že to platí, k odvození pro n+1 jsem se ještě nedostala a tam asi bude zakopaný ten pes, že?
Mne napadlo taketo trochu kombinatoricke riesenie:
Najprv vynasobme obe strany identity 2^(2m) a dostaneme identitu v trochu krajsom tvare (t. j. bez zlomkov :)).
suma od k=0 do m ((k+m) "nad" m).(2^(m-k)) = 2^(2m).
Prava strana identity je pocet (2m)-tic nul a jednotiek. Lava strana tiez, lebo rozhodnut, na ktorych miestach budu jednotky, a na ktorych nuly v (2m)-tici mozme aj tak, ze v prvych k+m miestach vyberieme tie, kde budu jednotky, a ostatne budu nuly (to sa da spravit presne (k+m) "nad" m sposobmi) a ku kazdemu takemu takemutu vyberu mame 2^(m-k) sposobov, ako bude vyzerat zvysnych m-k miest v (2m)-tici. Kedze sticutejeme cez vsetky k od 0 do m, zaratame vsetky mozne (2m)-tice nul a jednotiek prave raz. A preto plati uvedena kombinatoricka identita :).
katka: Ten prvý krok som spravil aj ja, ale na kombinatorickej interpretácii som sa zasekol. A pravdupovediac mi to, čo píšeš (od "Ľavá strana..." ďalej), príliš nedáva zmysel, tú bijekciu tam nevidím. Môžeš to rozpísať podrobnejšie? Ktorému sčítancu napr. zodpovedá vektor 2m núl?
Tu je zatiaľ najlepšia kombinatorická úvaha, ktorá napadla mňa.
Dokazujeme tú istú identitu. Vektory núl a jednotiek dĺžky 2m si môžeme predstaviť ako cesty z bodu (0,0) doprava a dohora.
Predstavme si teraz štvorec s rohmi (0,0) a (m,m). Existuje práve C(2m,m) ciest, ktoré sú celé vnútri. Každá zo zvyšných ho niekedy opustí. To sa pre každú z nich stane buď v bode (k,m) alebo v bode (m,k) pre nejaké k menšie ako m. V každom prípade máme pre nasledujúci krok len jeden možný smer, takže doplniť zvyšok cesty končiacej na (m,k) vieme 2^{m-k-1} spôsobmi. Takže celkový počet ciest vieme vyjadriť ako C(2m,m) + 2 * sum(k=0..m-1) C(m+k,m) * 2^{m-k-1}, čo dokopy dáva našu identitu.
misof: mas pravdu, v mojej uvahe je logicka chyba, niektore vektory sa na lavej strane zaratavaju viackarat, a napr. nulovy vektor tam vobec nie je :)
cisto vypoctovo, bez kombinatoriky.
je to take sikme scitavanie v binomickom trojuholniku.
nech a|b je a "nad" b
najprv (*) sum(k=0..t) (k+m)|m = (k+t+1)|(m+1) to je iba z toho, ze cislo sa rovna suctu dvoch nad nim.
teraz f(m)=sum(k=m..0) 2^(m-k) * (k+m)|m (scitavajme to zdola)
cize pridame koeficienty 1,2,4,8,...
kazdy clen (bez koeficientu) prepiseme ako sucet sikmeho riadku nad nim (podla (*) - treba si to kreslit)
cize (k+m)|m -> (k+m-1)|(m-1) a koeficienty budu 1,3,7,15... (ciastocne sucty predchadzajuceho radu koef)
co je 2-1,4-1,8-1,16-1
pouzijeme este raz (*) na to -1 okrem prveho clenu a dostaneme
teda f(m)=(2m-1)|(m-1)-(2m-1)|(m)+4f(m-1)=4f(m-1)
f(0)=1 => f(m)=2^(2m) a to je co sme chceli
Ďakujem za riešenia!
Keď som túto kominatorickú identitu zadával na blog, trochu so sa obával, či to nie je nejaká úplná trivialita s ktorou si neviem poradiť len preto, že som už veľmi ustatý. Ale ukázalo sa, že to až také triválne nie je a možné riešenia si vyžadujú pekné nápady. Very good.
Zverejnenie komentára