Drogi z punktu A do B

[Iras]

Cześć, Pomógłby mi ktoś rozwiązać to zadanie ?

Ile jest na podanej kracie ulic najkrótszych dróg z A do B, które zawierają przynajmniej jeden z wydzielonych fragmentów dróg?



Wiem że używa się do tego wzoru \(\displaystyle{ {n+k\choose k}}\) ale nie wiem jak to liczyć próbowałem na sume trzech zbiorów ale to coś źle wychodzi?

[Qń]

Użyj zasady włączeń i wyłączeń.

Q.

[Iras]

No właśnie jakoś nie bardzo da się policzyć przejście przez te dwa punkty po prawej stronie

[Straznik Teksasu]

O coś takiego chodzi tutaj ??? , bo robię pierwszy raz tego typu zadanie ?

Górna droga - X
Środkowa - Z
Dolna - Y

Kolejne składniki sumy oznaczają:
- ilość przejść tylko przez Y
- ilość przejść tylko przez X
- ilość przejść tylko przez Z
- ilość przejść tylko przez Y i X
- ilość przejść tylko przez Y i Z

\(\displaystyle{ d=\binom{1+2}{2}\left[ \binom{4+6}{6} -\binom{1+2}{2}\binom{1+3}{3}-\binom{0+1}{1}\binom{2+3}{3}\right]+\left[ \binom{4+4}{4}-\binom{1+2}{2}\binom{1+2}{2}\right]\binom{1+3}{3}+\left[ \binom{2+5}{5}-\binom{1+2}{2}\binom{0+1}{1}\right]\binom{2+3}{3}+\binom{1+2}{2}\binom{1+2}{2}\binom{1+3}{3}+\binom{1+2}{2} \binom{0+1}{1}\binom{2+3}{3}=1054}\)

Odp: Ilość najkrótszych dróg z A do B wynosi \(\displaystyle{ 1054}\).

[a4karo]

Trudno zweryfikować poprawność tych rachunków bez ich uzasadnienia. Generalnie uwielbiam wprost, gdy ktoś w rozwiązaniu zadania kombinatorycznego wypisuje ciąg znaczków składający się z silni i dwumianów Newtona.

[kropka+]

Wyniku nie sprawdzam, ale zapis bardzo by się uprościł, gdybyś liczył

\(\displaystyle{ wszystkie \ najkrotsze \ drogi \ przez \ X \ + \ wszystkie \ przez \ Y\ + \ wszystkie \ przez \ Z \ - \ wszystkie \ przez \ YX \ - \ wszystkie \ przez \ YZ}\)

[arek1357]

Zasada włączeń i wyłączeń w tym zadaniu jest potrzebna ale nie demonizujmy jej.

Bardziej powinniśmy stworzyć sobie koncepcję do tego zadania.

Najpierw może oznaczmy sobie:

\(\displaystyle{ A_{1}B_{1}}\) - początek i koniec lewej dolnej łamanej

\(\displaystyle{ A_{2}B_{2}}\) - początek i koniec prawej dolnej łamanej

\(\displaystyle{ A_{3}B_{3}}\) - początek i koniec górnej łamanej.

I teraz ustalmy:

1). przechodzimy tylko przez \(\displaystyle{ A_{1}B_{1}}\)


Z \(\displaystyle{ A}\) do \(\displaystyle{ B_{1}}\) - jest tyle dróg co z \(\displaystyle{ A do A_{1}}\)

Teraz liczymy drogi z \(\displaystyle{ B_{1}}\) do\(\displaystyle{ B}\)

Z \(\displaystyle{ B_{1} do B}\) (ale bez przejścia przez pozostałe łamane) jest tyle dróg co:

\(\displaystyle{ d(B_{1},B)=w(B_{1},B)-w(B_{1},A_{2}) \cdot w(B_{2},B)-w(B_{1},A_{3}) \cdot w(B_{3},B)}\)

\(\displaystyle{ d}\)- to drogi, które nas interesują

\(\displaystyle{ w}\)- wszystkie drogi

Pokazałem jak obliczyć ilość dróg przechodząc tylko przez pierwszą łamaną.

Podobnie liczymy przez drugą łamaną i trzecią a potem przez:

pierwszą i drugą

oraz:

pierwszą i trzecią.

I stosujemy włączania i wyłączania zasadę.

Zauważmy również, że przejście przez wszystkie łamane jest niemożliwe...

[Straznik Teksasu]

Zapis np. \(\displaystyle{ AX1}\) oznacza ilość wszystkich możliwie najkrótszych dróg przejść od punktu \(\displaystyle{ A}\) do \(\displaystyle{ X1}\).

Teraz zapiszę wyjaśnienie w tej samej kolejności co moje poprzednie obliczenia.

\(\displaystyle{ d=AY1 \cdot \left[ Y2B-Y2X1 \cdot X2B-Y2Z1 \cdot Z2B\right]+\left[ AX1-AY1 \cdot Y2X1\right] \cdot X2B+\left[ AZ1-AY1 \cdot Y2Z1 \right] \cdot Z2B +AY1 \cdot Y2X1 \cdot X2B+AY1 \cdot Y2Z1 \cdot Z2B}\)

[kropka+]

W ten sposób dostajecie tego samego "tasiemca" co kilka postów wyżej. Zamiast zastosować zasadę włączeń i wyłączeń jeden raz, wolicie ją stosować trzykrotnie, a potem dodawać to samo co już dwukrotnie odjęliście.

[Straznik Teksasu]

\(\displaystyle{ d=AY1 \cdot Y2B+ AX1 \cdot X2B+ AZ1 \cdot Z2B -AY1 \cdot Y2X1 \cdot X2B - AY1 \cdot Y2Z1 \cdot Z2B}\)

O to chodziło ?

[kropka+]

tak