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?
przechodzenie po siatce - na ile sposobow
- JHN
- Użytkownik
- Posty: 668
- Rejestracja: 8 lip 2007, o 18:09
- Płeć: Mężczyzna
- Lokalizacja: Radom
- Podziękował: 7 razy
- Pomógł: 206 razy
Re: przechodzenie po siatce - na ile sposobow
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 ?!?
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
- Użytkownik
- Posty: 340
- Rejestracja: 29 cze 2019, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Oulu
- Podziękował: 42 razy
- Pomógł: 60 razy
Re: przechodzenie po siatce - na ile sposobow
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.
\(\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
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: przechodzenie po siatce - na ile sposobow
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...
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...