wszystkie najkrótsze trasy

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
NataliaAnna
Użytkownik
Użytkownik
Posty: 72
Rejestracja: 25 sty 2017, o 17:07
Płeć: Kobieta
Lokalizacja: Wrocław
Podziękował: 8 razy

wszystkie najkrótsze trasy

Post autor: NataliaAnna » 28 paź 2017, o 15:09

Na zajęciach przerabialiśmy poniższe zadanie, jednak wszystkie trasy wyznaczaliśmy ręcznie. Jest to jednak bardzo dużo roboty i zastanawiam się, czy istnieje szybszy sposób wyznaczenia takich tras(np jakiś wzór lub metoda)

Rozważmy kratę utworzoną z pięciu poziomych i czterech pionowych odcinków. Wyznacz wszystkie najkrótsze trasy z lewego górnego rogu do dolnego prawego roku tej kraty( ruch odbywa się jedynie w dół i w prawo)

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7895
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 243 razy
Pomógł: 3093 razy

Re: wszystkie najkrótsze trasy

Post autor: kerajs » 28 paź 2017, o 15:32

Każda trasa składa się z piecu odcinków w prawo P,P,P,P,P i czterech w dół D,D,D,D.
Ilość tras to ilość permutacji miedzy elementami P,P,P,P,P,D,D,D,D czyli: \(\displaystyle{ frac{9!}{5!4!}}\)


423490.htm

Awatar użytkownika
pesel
Użytkownik
Użytkownik
Posty: 1632
Rejestracja: 8 cze 2010, o 13:09
Płeć: Mężczyzna
Podziękował: 1 raz
Pomógł: 393 razy

wszystkie najkrótsze trasy

Post autor: pesel » 28 paź 2017, o 23:54

W prawo to będą chyba tylko trzy kroki.

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7895
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 243 razy
Pomógł: 3093 razy

Re: wszystkie najkrótsze trasy

Post autor: kerajs » 29 paź 2017, o 00:26

Ach, czyli chodzi o taką kratę!
\(\displaystyle{ \begin{tikzpicture} \draw[red](0,0)--(3,0); \draw[red](0,1)--(3,1); \draw[red](0,2)--(3,2); \draw[red](0,3)--(3,3); \draw[red](0,4)--(3,4); \draw[blue](0,0)--(0,4); \draw[blue](1,0)--(1,4); \draw[blue](2,0)--(2,4); \draw[blue](3,0)--(3,4); \end{tikzpicture}}\)
I o permutacje między elementami P,P,P,D,D,D,D których jest \(\displaystyle{ \frac{7!}{3!4!}=35}\)

Ja kratę z opisu zinterpretowałem całkowicie inaczej, bo tak:


\(\displaystyle{ \begin{tikzpicture} \foreach \x in{0,1,...,3,4} \foreach \y in{1,2,...,3,4} { \draw[](\x+0.1,\y-1)--(\x+0.9,\y-1); \draw[](\x+1,\y-0.9)--(\x+1,\y-0.1); } \foreach \y in{0,1,...,2,3} { \draw[blue](0,\y+0.1)--(0,\y+0.9); } \foreach \x in{0,1,...,3,4} { \draw[red](\x+0.1,4)--(\x+0.9,4); } \end{tikzpicture}}\)

ODPOWIEDZ