Ilość różnych dróg pomiędzy punktami
-
- Użytkownik
- Posty: 541
- Rejestracja: 11 maja 2016, o 13:36
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 497 razy
- Pomógł: 5 razy
Ilość różnych dróg pomiędzy punktami
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ść.
Zadanie ewidentnie porusza tematykę liczb Catalana, niemniej jednak nie wiem jak do niego podejść.
-
- Użytkownik
- Posty: 541
- Rejestracja: 11 maja 2016, o 13:36
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 497 razy
- Pomógł: 5 razy
Re: Ilość różnych dróg pomiędzy punktami
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
- Użytkownik
- Posty: 809
- Rejestracja: 14 lis 2014, o 19:37
- Płeć: Mężczyzna
- Podziękował: 48 razy
- Pomógł: 183 razy
Re: Ilość różnych dróg pomiędzy punktami
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} }\)
A więc\(\displaystyle{ {15 \choose 12} }\)
-
- Użytkownik
- Posty: 541
- Rejestracja: 11 maja 2016, o 13:36
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 497 razy
- Pomógł: 5 razy
Re: Ilość różnych dróg pomiędzy punktami
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)}\)?
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
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Ilość różnych dróg pomiędzy punktami
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 }\) .
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Re: Ilość różnych dróg pomiędzy punktami
Inna sprawa, że nad tym zadankiem mogłeś sam pomyśleć. Niczym się nie różni od poprzedniego41421356 pisze: ↑7 kwie 2020, o 22:02 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)}\)?
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Re: Ilość różnych dróg pomiędzy punktami
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
-
- Użytkownik
- Posty: 541
- Rejestracja: 11 maja 2016, o 13:36
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 497 razy
- Pomógł: 5 razy
Re: Ilość różnych dróg pomiędzy punktami
W takim razie poproszę o wskazanie błędu.
Dodano po 4 minutach 37 sekundach:
Chcę wmieszać, gdyż punkty \(\displaystyle{ (0,0)}\) oraz \(\displaystyle{ (0,6)}\) spełniają warunki dla liczby dróg w zastosowaniu liczb Catalana.
Ostatnio zmieniony 9 kwie 2020, o 23:52 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 541
- Rejestracja: 11 maja 2016, o 13:36
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 497 razy
- Pomógł: 5 razy
Re: Ilość różnych dróg pomiędzy punktami
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}}\)
\(\displaystyle{ c_n=\frac{1}{1+n}{2n \choose n}}\)
- kmarciniak1
- Użytkownik
- Posty: 809
- Rejestracja: 14 lis 2014, o 19:37
- Płeć: Mężczyzna
- Podziękował: 48 razy
- Pomógł: 183 razy
Re: Ilość różnych dróg pomiędzy punktami
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ń.
-
- Użytkownik
- Posty: 541
- Rejestracja: 11 maja 2016, o 13:36
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 497 razy
- Pomógł: 5 razy
Re: Ilość różnych dróg pomiędzy punktami
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.kmarciniak1 pisze: ↑10 kwie 2020, o 11:08 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ń.