ilość kombinacji studia

[aresik88]

Zadanie z kolosa z Matematyki Dyskretnej:
Poruszając się tylko: w prawo lub do góry. Ile jest możliwych dróg do przejścia z lewego dolnego wierzchołka do prawego górnego, poruszając się jedynie w obrębie zamalowanych części (czerwony kolor).
Przepraszam za nierówny rysunek, to jest kwadrat o boku 5 i przekątna przechodzi przez niego, dzieląc dwa pola na trójkąty.


Nie potrafię tego rozwiązać, moim pomysłem było:
\(\displaystyle{ \frac{1}{2} \cdot {6 \choose 3} \cdot \frac{1}{2} \cdot {4 \choose 2}}\) ale to jest niepoprawne rozwiązanie.

[pyzol]

A dojść musisz wykonać 5 ruchów w prawo i tyle samo do góry. Teraz kwestia jak je ułożyć:
\(\displaystyle{ P,P,P,P,P,G,G,G,G,G}\)
Teraz robisz dowolną permutację, możliwości jest \(\displaystyle{ 10!}\), jednak nie rozróżniamy \(\displaystyle{ P}\). Nie rozróżniamy też \(\displaystyle{ G}\). Mamy więc:
\(\displaystyle{ \frac{10!}{5!5!}}\)

-- 24 wrz 2012, o 19:46 --

Oj edit: nie zauważyłem. No ale wskaże co liczysz, a czego nie powinnaś. Taka kombinacja:
\(\displaystyle{ PGGPGP}\) Czyli ta linia raz jest powyżej, a raz poniżej.

[TMac]

Intuicja była dobra, na pewno dobry jest pomysł by policzyć osobno dla każdego trójkąta i potem to wymnożyć (bo po rysunku widać, że poprawna droga musi przejść przez punkt wspólny tych trójkątów). Tyle, że dla każdego trójkąta nie będzie równo po połowie dobrych dróg. Spójrzmy np. na ten \(\displaystyle{ 2}\)x\(\displaystyle{ 2}\). Masz \(\displaystyle{ {4 \choose 2} = 6}\) dróg, a poprawne są tylko \(\displaystyle{ 2}\): \(\displaystyle{ P,P,G,G}\) oraz \(\displaystyle{ P,G,P,G}\). Ich "odpowiedniki" przy symetrii względem przekątnej faktycznie są złe, ale niewłaściwa jest też para \(\displaystyle{ G,P,P,G}\) i \(\displaystyle{ P,G,G,P}\), razem \(\displaystyle{ 4}\) złe drogi.
Moim wstępnym pomysłem byłaby zasada włączania-wyłączania, gdzie \(\displaystyle{ A_{i}}\) to opuszczenie dobrego obszaru na \(\displaystyle{ i}\)-tym skrzyżowaniu leżącym na przekątnej. I teraz policzyć \(\displaystyle{ \left| X/\left( A_{1} \cup A_{2} \cup A_{3}\right) \right|}\) dla dolnego trójkąta i odpowiednio dla górnego (chociaż właściwie już go policzyłem wyżej ).
Ew. \(\displaystyle{ {6 \choose 3}= 20}\) to jeszcze nie jest tak dużo do rozważenia na "siłę"...

[aresik88]

Dużo nie jest, ale jak prowadzący da następnym razem 10x10 to już jest sporo liczenia na prawdę nikt nie wie jak to policzyć? Bo podpowiedź pyzol'a nic mi nie mówi :/ <offtop> pyzol, jestem facetem </offtop>

[pyzol]

A wiem, podpowiedzi nie mam bo najpierw napisałem odpowiedź na cały kwadrat. Potem odpisałem mało zrozumiale, że to tyczyło się tamtego. <offtop>przepraszam<offtop>.
Teraz siedzę i się głowię, tak jak i wczoraj.

[aresik88]

Znalazłem metodę podobną do rozpisywania trójkąta Pascala. Nie jest to piękne, bo polega na zliczaniu ścieżek dochodzących do danego wierzchołka, ale działa i nie ma dużo liczenia. O to przykład liczenia dla trójkąta o boku = 5:

[pyzol]

No fajnie, przysłużyłeś się do poszerzania wiedzy. Zamiast Ci pomóc nauczyłem się czegoś nowego.