przechodzenie po siatce - na ile sposobow

[rivit]

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?

[JHN]

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 ?!?

[Gosda]

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.

[arek1357]

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...