Ilość różnych dróg pomiędzy punktami

[41421356]

W zbiorze punktów płaszczyzny o obu współrzędnych całkowitych porusza się pionek według następującej zasady: z punktu \(\displaystyle{ (x,y)}\) może przesunąć się do punktu \(\displaystyle{ (x+1,y+1)}\) lub \(\displaystyle{ (x+1,y-1)}\). Ile jest różnych dróg prowadzących od punktu \(\displaystyle{ (2,3)}\) do punktu \(\displaystyle{ (12,17)}\)?

Zadanie ewidentnie porusza tematykę liczb Catalana, niemniej jednak nie wiem jak do niego podejść.

[kerajs]

Zero. W dziesięciu ruchach dotrze jedynie do (12,13) .

[41421356]

Zakładam w takim razie, że wystąpiła literówka w treści. Zamieńmy zatem punkt \(\displaystyle{ (12,17)}\) na punkt \(\displaystyle{ (17,12)}\).

[kmarciniak1]

Jeśli dobrze myśle to w takiej sytuacji musimy wykonać łącznie \(\displaystyle{ 15}\) ruchów. W \(\displaystyle{ 12}\) z nich musimy się przesunąć w górę a w pozostałych w dół.
A więc\(\displaystyle{ {15 \choose 12} }\)

[41421356]

Dziękuję za odpowiedź, dorzucam zadanko ekstra:

W zbiorze punktów płaszczyzny o obu współrzędnych naturalnych porusza się pionek według następującej zasady: z punktu \(\displaystyle{ (x,y)}\) może przesunąć się do punktu \(\displaystyle{ (x+1,y+1)}\) lub \(\displaystyle{ (x-1,y+1)}\). Ile jest różnych dróg prowadzących z punktu \(\displaystyle{ (0,0)}\) do punktu \(\displaystyle{ (0,6)}\)?

[kerajs]

Po sześciu ruchach rzędna położenia punktu wynosi 6. Aby odciętą było 0 to trzy ruchy piona były w lewo (i w górę), a trzy w prawo (i w górę). Stąd ilość możliwych dróg to: \(\displaystyle{ {6 \choose 3}=20 }\) .

[a4karo]

Dziękuję za odpowiedź, dorzucam zadanko ekstra:

W zbiorze punktów płaszczyzny o obu współrzędnych naturalnych porusza się pionek według następującej zasady: z punktu \(\displaystyle{ (x,y)}\) może przesunąć się do punktu \(\displaystyle{ (x+1,y+1)}\) lub \(\displaystyle{ (x-1,y+1)}\). Ile jest różnych dróg prowadzących z punktu \(\displaystyle{ (0,0)}\) do punktu \(\displaystyle{ (0,6)}\)?

Inna sprawa, że nad tym zadankiem mogłeś sam pomyśleć. Niczym się nie różni od poprzedniego

[41421356]

Prawidłowa odpowiedź to \(\displaystyle{ 5}\), czyli jest to trzecia z kolei liczba Catalana.

[Tmkk]

Może i prawidłowa, ale chyba do innego zadania.

[a4karo]

Prawidłowa odpowiedź to \(\displaystyle{ 5}\), czyli jest to trzecia z kolei liczba Catalana.

A czemu koniecznie Catalana chcesz to wmieszać? Mam 5 palców u rąk: teza: Ilość palców u rąk naczelnych we wszechświecie jest liczbą Catalana

[41421356]

Może i prawidłowa, ale chyba do innego zadania.

W takim razie poproszę o wskazanie błędu.

Dodano po 4 minutach 37 sekundach:

Prawidłowa odpowiedź to \(\displaystyle{ 5}\), czyli jest to trzecia z kolei liczba Catalana.

A czemu koniecznie Catalana chcesz to wmieszać? Mam 5 palców u rąk: teza: Ilość palców u rąk naczelnych we wszechświecie jest liczbą Catalana

Chcę wmieszać, gdyż punkty \(\displaystyle{ (0,0)}\) oraz \(\displaystyle{ (0,6)}\) spełniają warunki dla liczby dróg w zastosowaniu liczb Catalana.

[a4karo]

Ilość dróg musi być parzysta że wzgledu na symetrię obrazka

[41421356]

Tyle, że ciężko tutaj mówić o symetrii, gdy wartości współrzędnych tych punktów muszą być nieujemne. Będę uparty, aby wyliczyć wszystkie takie przypadki wystarczy użyć dwumianu Newtona. Jednak gdy chcemy wydobyć z tych wszystkich przypadków tylko te z pierwszej ćwiartki układu współrzędnych, wówczas z pomocą przychodzi wzór:

\(\displaystyle{ c_n=\frac{1}{1+n}{2n \choose n}}\)

[kmarciniak1]

Nie chcę być niemiły ale najwyraźniej nie rozumiesz tego problemu... Dostałeś rozwiązania dwóch bardzo podobnych do siebie zadań w których wykorzystano tylko wzór na kombinacje bez powtórzeń a ty się upierasz przy tych liczbach Catalana. Niewątpliwie są to przydatne liczby ale raczej do problemów o co najmniej jeden poziom trudniejszych od tych które miałeś rozwiązać. W matematyce a już w szczególności w dziale matematyka dyskretna liczy się myślenie a nie durne podążanie za jakimiś wzorami. Co zresztą bardzo widać na tym forum w tym dziale gdyż bardzo często ktoś koniecznie chce dopasować jakiś wzór zamiast pomyśleć nad daną sytuacją kombinatoryczną. I niestety bardzo często prowadzi to do błędnych rozwiązań.

[41421356]

Nie chcę być niemiły ale najwyraźniej nie rozumiesz tego problemu... Dostałeś rozwiązania dwóch bardzo podobnych do siebie zadań w których wykorzystano tylko wzór na kombinacje bez powtórzeń a ty się upierasz przy tych liczbach Catalana. Niewątpliwie są to przydatne liczby ale raczej do problemów o co najmniej jeden poziom trudniejszych od tych które miałeś rozwiązać. W matematyce a już w szczególności w dziale matematyka dyskretna liczy się myślenie a nie durne podążanie za jakimiś wzorami. Co zresztą bardzo widać na tym forum w tym dziale gdyż bardzo często ktoś koniecznie chce dopasować jakiś wzór zamiast pomyśleć nad daną sytuacją kombinatoryczną. I niestety bardzo często prowadzi to do błędnych rozwiązań.

Nie wiem czy zauważyłeś, ale jedno z rozwiązań było błędne, nikt nie podał poprawnej odpowiedzi do tego drugiego zadania. Może jednak dla poprawności rozwiązania problemu warto już podeprzeć się gotowym wzorem. Pozdrawiam.