Najkrótsze drogi

[Meryjan]

Dzień dobry,
mam problem z zadaniem :
Podaj liczbę wszystkich najkrótszych dróg Z punktu A do punktu B , w tym również przechodzących lub nie przechodzących przez punkt C
Dane :
Punkt A(2,3)
Punkt B(6,7)
Punkt C(3,5)

Z obliczeń wyszło mi 60 czy jest to poprawne ?

[kerajs]

Jest tylko jedna najkrótsza droga między punktami A i B, a jej długość to \(\displaystyle{ 4 \sqrt{2} }\)

Najkrótszych dróg po kolejnych punktach kratowych (idąc tylko w górę lub w prawo) jest \(\displaystyle{ \frac{8!}{4!4!}=70 }\) , w tym \(\displaystyle{ \frac{3!}{2!1!} \cdot \frac{5!}{2!3!} = 30}\) przechodzi przez punkt C.

[FasolkaBernoulliego]

Czy można o tym myśleć w ten sposób, że każda najkrótsza droga po kracie ma długość 8 (4 prawo i 4 w górę) i wybieramy po prostu, w których "krokach" nastąpi przykładowo pójście w górę?

[Janusz Tracz]

Tak. Można o tym myśleć jak o układaniu słów o pewnej długości (tu \(\displaystyle{ 8}\)) z alfabetu składającego się ze znaków \(\displaystyle{ \rightarrow,\uparrow}\). Przy czym zakładamy, że trzeba wykorzystać po \(\displaystyle{ 4}\) znaki. Wszystkich permutacji jest \(\displaystyle{ 8!}\) ale, że \(\displaystyle{ 4}\) znaki się powtarzają to dzielimy przez ich liczbę permutacji i ponownie dla kolejnych \(\displaystyle{ 4}\) permutytowych znaków. A gdy trzeba zahaczyć o punkt pośredni to najpierw idziemy do niego a potem od niego. Przynajmniej tak ja na to patrzę.

Dodano po 3 minutach 55 sekundach:
Można też powiedzieć, że wybieramy \(\displaystyle{ 4}\) miejsca z \(\displaystyle{ 8}\) i wstawimy tam \(\displaystyle{ \rightarrow }\) a potem wybieramy jeszcze \(\displaystyle{ 4}\) z pozostałych \(\displaystyle{ 4}\) i wstawiamy tam \(\displaystyle{ \uparrow}\) czyli możliwości jest \(\displaystyle{ {8 \choose 4} \cdot {4 \choose 4} }\) (wyjdzie na to samo). Take słowo symbolizuje drogę np. \(\displaystyle{ \uparrow\uparrow\uparrow\uparrow\rightarrow\rightarrow\rightarrow\rightarrow}\) to idź do góry "najwyżej" jak się da a potem już cały czas trzeba w prawo.

[Meryjan]

Jest tylko jedna najkrótsza droga między punktami A i B, a jej długość to \(\displaystyle{ 4 \sqrt{2} }\)

Najkrótszych dróg po kolejnych punktach kratowych (idąc tylko w górę lub w prawo) jest \(\displaystyle{ \frac{8!}{4!4!}=70 }\) , w tym \(\displaystyle{ \frac{3!}{2!1!} \cdot \frac{5!}{2!3!} = 30}\) przechodzi przez punkt C.

Dziękuje bardzo ,
nie bardzo rozumiem skąd się wziął zapis\(\displaystyle{ \frac{5!}{2!3!} =30}\)? Mogę poprosić o wyjaśnienie

[kerajs]

Skoro najkrótszych dróg z A do C (3 kroki: 1 w prawo i 2 w górę) jest \(\displaystyle{ \frac{3!}{2!1!} }\) , a dróg z C do B (5 kroków: 3 w prawo i 2 w górę) jest \(\displaystyle{ \frac{5!}{2!3!} }\) , to dróg z A do B przechodzących przez C jest 30.