przechodzenie po siatce - na ile sposobow

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
rivit
Użytkownik
Użytkownik
Posty: 151
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 65 razy
Pomógł: 1 raz

przechodzenie po siatce - na ile sposobow

Post autor: rivit » 11 gru 2019, o 22:49

startujemy od punktu (0,0) i chcemy dojsc do (14,9)
mozemy isc tylko w prawo i w gore oraz na ukos(w prawo i w górę w jednym kroku)

na ile sposobow mozna dojsc do celu?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
JHN
Użytkownik
Użytkownik
Posty: 345
Rejestracja: 8 lip 2007, o 18:09
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 5 razy
Pomógł: 96 razy

Re: przechodzenie po siatce - na ile sposobow

Post autor: JHN » 11 gru 2019, o 23:59

Problemem jest s - skos, łączący dwa ruchy: w prawo (p) i w górę (g)
Możliwości mamy:
14 p i 9 g (w dowolnej kolejności) :\(\displaystyle{ \frac{23!}{14!\cdot 9!}}\)
albo
13 p, 1 s i 8 g :\(\displaystyle{ \frac{22!}{13!\cdot 1!\cdot 8!}}\)
albo
12 p, 2 s i 7 g :\(\displaystyle{ \frac{22!}{13!\cdot 2!\cdot 7!}}\)
albo
.....
albo
5 p i 9 s :\(\displaystyle{ \frac{14!}{5!\cdot 9!}}\)
i trzeba dodać...

Pozdrawiam
PS. Można krócej ?!?

Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 248
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu
Podziękował: 34 razy
Pomógł: 43 razy

Re: przechodzenie po siatce - na ile sposobow

Post autor: Gosda » 12 gru 2019, o 03:39

Jak się zna teorię funkcji tworzących, to trochę można. Rozpatrzmy ciąg \(\displaystyle{ a_n}\) opisujący liczbę dróg z punktu zerowego do \(\displaystyle{ (n, k)}\), gdzie \(\displaystyle{ k}\) jest ustaloną liczbą naturalną. Zauważyłem, że funkcja tworząca wyraża się wzorem

\(\displaystyle{ A(z) = \frac{(1 + z)^k}{(1-z)^{k-1}}}\)

co dla \(\displaystyle{ k = 9}\) daje

\(\displaystyle{ A(z) = 1 + 19 z + 181 z^2 + \ldots + 50250765 z^{14} + \ldots}\),

więc odpowiedź to 50250765.

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3836
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 89 razy
Pomógł: 378 razy

Re: przechodzenie po siatce - na ile sposobow

Post autor: arek1357 » 28 gru 2019, o 12:41

Nie chcę tworzyć nowego wątku ale chciałbym podkręcić to zadanie a mianowicie wyznaczyć liczbę dróg z lewego dolnego wierzchołka prostokąta do prawego górnego , ale dopuszczamy jeszcze ścieżki nie tylko północ , wschód i północny wschód, ale również południe, zachód północny zachód i południowy zachód, południowy wschód, warunek że nie można przechodzić dwa razy po tej samej ścieżce, ale jak dojdziemy do punktu docelowego to możemy oczywiście jeszcze się cofać i wracać z powrotem, wierzchołki możemy przecinać wiele razy byle nie przechodzić jak już mówiłem przez te same ścieżki...

Myślałem o tworzeniu macierzy sąsiedztwa i potęgowaniu , ale trzeba by było tworzyć wiele skierowanych grafów i mogłyby się w tej metodzie powtarzać niektóre ścieżki...

Problem można jeszcze inaczej postawić: "Ile jest łamanych między tymi punktami o bokach równych bokom kwadratów jednostkowych lub ich sumom i równych przekątnym tychże kwadratów jednostkowych...

ODPOWIEDZ