Metoda dróg

[neworder1]

Mamy ciąg \(\displaystyle{ a_{k}=\frac{1}{2k-1} {{2k-1} \choose k}}\). Wykazać, że \(\displaystyle{ a_{n}=a_{1}a_{n-1}+a_{2}a_{n-2}+...+a_{n-2}a_{2}+a_{n-1}a_{1}}\). Kojarzy mi się to z metodą dróg, tylko nie wiem, jak zinterpretować w kategoriach dróg te ułamki plątające się koło współczynników Newtona. Ma ktoś jakiś pomysł, jak zrobić to korzystając z metody dróg (o ile się da)?

[neworder]

Sorry, ten ciąg to miało być \(\displaystyle{ a_{k}=\frac{1}{2k-1} {{2k-1}\choose k}}\)

[półpasiec]

z moich obserwacji wynika ze a_n to liczba drog z pola 0,0 do n,n ale takich ktore nie maja punktow wspolnych z prosta y=x i takich ze mozna isc tylko do gory lub w prawo
ale na razie nie mam na to dowodu

[ Dodano: Nie Wrz 25, 2005 1:11 am ]
a to taka rada do wywalenia tego ulamka
na okregu masz \(\displaystyle{ 2k-1}\) punktow ponumerowanych ktore sa wierzcholkami \(\displaystyle{ 2k-1}\)kata foremnego, chcesz ustalic ile mozna uzyskac figur z tych wierzcholkow ktore maja \(\displaystyle{ k}\) wierzcholkow, jasne ze wtedy wybieramy sposrod \(\displaystyle{ 2k-1}\) punktow \(\displaystyle{ k}\) wierzcholkow nowego, ale kazda figure uzyskujemy \(\displaystyle{ 2k-1}\) razy, wiec musimy ten dwumian podzielic
wydaje mi sie ze mozna by zrobic tak ze mozna utworzyc grupe k chlopcow i k-1 dziewczyn i liczyc te ustawienia wzgledem liczby chlopakow i dziewczyn, ale pewny na razie nie jestem

[neworder]

Masz na myśli to, że z 2k-1 wierzchołków chcemy wybrać k tworzących pewien wielokąt, ale tak, by nie wybrać wielokątów do siebie przystających (wtedy faktycznie dzielimy przez 2k-1, bo dla dowolnego wielokąta mamy jeszcze 2k do niego przystających)?

[półpasiec]

no tak
wybieramy sposrod 2k-1 k wierzcholkow wielokata \(\displaystyle{ A_{2k-1}}\) (indeks to liczba wierzcholkow) tworzacych kolejny wielokat \(\displaystyle{ A_k}\), potrzeba teraz wykazac ze kazdy taki wielokat bedzie uzyskany \(\displaystyle{ 2k-1}\) razy poprzez obroty, bo jak na razie nei stosowalismy
albo na odwrot ze jesli wybierzemy wielokat \(\displaystyle{ A_k}\) to ustalajac pewien w nim wierzcholek i przesuwajac go cyklicznie po kazdym kolejnym wierzcholku \(\displaystyle{ A_{2k-1}}\) dostaniemy \(\displaystyle{ 2k-1}\) wielokatow przystajacych, ale zadne dwa nie beda na siebie nachodzily
trzeba to udowodnic bo przy tym stwierdzeniu w ogole nie korzystalismy z zalozen o liczbach \(\displaystyle{ k,2k-1}\) wiec moglibysmy polozyc dowolne liczby, ale dla par \(\displaystyle{ (6,4)(9,3)}\) to nie zachodzi

[neworder]

Dzięki. Metoda dróg jest tu kłopotliwa, bo: \(\displaystyle{ a_{n}}\) to liczba dróg z punktu (0,0) do punktu (n,n-1) leżących poniżej prostej y=x, a np. przykładowo \(\displaystyle{ a_{1}}\) to liczba dróg z (0,0) do (1,0) i \(\displaystyle{ a_{n-1}}\) to l.d. z (0,0) do (n-1,n-2) (i oczywiście y

[półpasiec]

wykazemy wiec ze jesli wybierzemy pewien wielokat A_k to ustalajac pewien wierzcholek i obracajac wielokat wokol srodka okregu na nim opisanego przechodzac przez kazdy wierzcholek wielokata \(\displaystyle{ A_{2k-1}}\) uzyskamy 2k-1 przystajacych ale inaczej polozonych wielokatow A_k, co znaczy ze nigdy wierzcholki na siebie nie najda
najpierw jednak zauwazmy nastepujaca rzecz - mamy \(\displaystyle{ k}\) bokow, niech \(\displaystyle{ (b_1,b_2,...,b_k)}\) oznacza ile wierzcholkow wielokata \(\displaystyle{ A_{2k-1}}\) znajduje sie odpowiednio miedzy wierzcholkami boku numer \(\displaystyle{ 1,2,...,k}\), mamy oczywiscie \(\displaystyle{ \sum b_i=k-1}\)
zalozmy wiec przeciwnie ze po pewnym obrocie o \(\displaystyle{ d}\) wierzcholkow wielokat A_k najdzie z powrotem na siebie, wtedy pewien bok najdzie na bok oddalony o d, ten z kolei na inny itd, wiec \(\displaystyle{ b_i=b_{i+d}}\), jesli jednak \(\displaystyle{ d}\) bedzie wzglednie pierwsze z k wtedy dostaniemy ze wszystkie liczby \(\displaystyle{ b_i}\) sa rowne (to z algorytmu Euklidesa wynika), zatem nie moze byc d wzglednie pierwsze z k, jednak wtedy kazda wartosc w sumie \(\displaystyle{ \sum b_i}\) pojawia sie \(\displaystyle{ \frac{k}{d}}\) a do tego liczba ta nie jest wzglednie pierwsza z \(\displaystyle{ k}\) i jeszcze dzieli \(\displaystyle{ k-1}\), wiec sprzecznosc
wiec poprzez obroty uzyskamy 2k-1 przystajacych wielokatow ale inaczej polozonych co pozwala nam dwumian przez te liczbe podzielic
przy okazji warto zauwazyc ze korzystalismy tylko z tego ze k,k-1 sa wzglednie pierwsze, zmieniajac te liczby mozna wykazac ze \(\displaystyle{ n| }\) dla n,k wzglednie pierwszych

[ Dodano: Pon Wrz 26, 2005 10:52 pm ]
aha zapomnialem dodac:)
czy moglbys dokladniej wyjasnic to zliczanie z cieciwa??

[neworder]

Eee, to z cięciwami to poroniony pomysł był Natomiast mógłbyś wyjaśnić, jaki pożytek płynie z udowodnionego przez Ciebie przed chwilą twierdzenia?

[półpasiec]

wykazalem ze \(\displaystyle{ a_k}\) to liczba roznych figur z k wierzcholkami wybranymi sposrod 2k-1 wierzcholkow
bo napisalem

na okregu masz 2k-1 punktow ponumerowanych od 1 do 2k-1 ktore sa wierzcholkami 2k-1kata foremnego, chcesz ustalic ile mozna uzyskac figur z tych wierzcholkow ktore maja k wierzcholkow, jasne ze wtedy wybieramy sposrod 2k-1 punktow k wierzcholkow nowego, ale kazda figure uzyskujemy 2k-1 razy, wiec musimy ten dwumian podzielic

ale to
'kazda figure uzyskujemy 2k-1 razy, wiec musimy ten dwumian podzielic'
wcale nie bylo takie oczywiste i trzeba bylo to udowodnic