Ilość dróg optymalnych

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
fa1thly
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 2 sty 2012, o 12:00
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy

Ilość dróg optymalnych

Post autor: fa1thly »

Ile jest dróg optymalnych z punktu o współrzędnych <1,2,3,4> do punktu <3,3,3,3> na kracie o wymiarach 7x6x5x4?

oraz

Ile jest dróg optymalnych z punktu o współrzędnych <0,0,0,0> do punktu <4,6,3,2> na kracie?

Oba podobne zadania więc proszę o jakąś podpowiedz choć w jednym z nich. Z tego co mi się wydaje bedzie to dwumian Newton'a. Robiłem podobne zadanie ale na kracie z 2 wymiarami gdzie punktem startowym byl (0,0) a końcowym (m,n), w tedy stosowalem dwumian newtona w postaci \(\displaystyle{ {m+n \choose m}}\). Jak będzie w przypadku tych zadań?
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Ilość dróg optymalnych

Post autor: norwimaj »

Zastanów się, jak wyglądają takie drogi. Składają się one z odcinków jednostkowych, które mogą mieć \(\displaystyle{ 4}\) różne kierunki. Ile jest odcinków w poszczególnych kierunkach?
ODPOWIEDZ