reguła właczeń i wyłączeń

[leszczu450]

Cześć : )

Zadanie jest takie: Rzucam dziesięć razy kostką i suma ma wyjść \(\displaystyle{ 30}\). Wiem jak zadanie sie robi, ale czy ma znaczenie czy warunek początkowy napisze tak: \(\displaystyle{ 1 \le x_{i} \le 6}\) czy tak: \(\displaystyle{ 0 \le x_{i} \le 5}\).

Z góry dziękuję za pomoc : )

[Malina015]

Wydaje mi się, że tak. Ale to też zależy od tego co dalej napiszesz. Bo w drugim przypadku masz przesunięcie o 1, czyli dla dokładnie dziesięciu rzutów suma wynosi 20, nie 30.

[leszczu450]

Malina015, tak tak, oczywiście, że ta suma się potem odpowiednio zmniejszy. Sęk w tym, że podobno jak się zrobi bez tego przesunięcia o jedno oczko to jest źle. Ale nie wiem czemu dlatego pytam , czy jak zrobie raz tak: \(\displaystyle{ 1 \le x_{i} \le 6}\), a drugi raz tak : \(\displaystyle{ 0 \le x_{i} \le 5}\) to czy oba sposoby są dobre i czy wynik będzie taki sam? : )

[Malina015]

Wzór masz podany dla liczby nieujemnych całkowitoliczbowych rozwiązań
\(\displaystyle{ x_1+\ldots + x_{10}=20}\)
jest to
\(\displaystyle{ {{n+k-1} \choose {k-1}}}\)
Z tego powodu przyjmuje się, że \(\displaystyle{ 0\leq x_i \leq 5}\)
Oczywiście jeśli przyjmiesz \(\displaystyle{ 1\leq x_i \leq 6}\) to nie możesz bezpośrednio skorzystać z tego wzoru tylko trzeba go odpowiednio przekształcić - jest inne n.
Sam warunek nie ma znaczenia, znaczenie ma co z nim dalej zrobisz.
Łatwo zauważyć, że gdybyś zapisał \(\displaystyle{ 1\leq x_i \leq 6}\) to prawdziwy byłby wzór \(\displaystyle{ {{n-1} \choose {k-1}}}\)

[leszczu450]

Malina015, ja to zrobiłem dla \(\displaystyle{ 1 \le x_i \le 6}\). Wtedy wszystkie mozliwe wyniki oznaczylem jako \(\displaystyle{ {30 + 10 -1 \choose 10 -1}}\). I to jest źle zrobione?

[pyzol]

Nie, powinno być \(\displaystyle{ \binom{29}{9}}\), ale to i tak nie będzie prawidłowo, gdyż będzie uwzględniać takie wyniki jak:
\(\displaystyle{ 21,1,1,1,1,1,1,1,1,1}\).

[yorgin]

a drugi raz tak : \(\displaystyle{ 0 \le x_{i} \le 5}\) to czy oba sposoby są dobre i czy wynik będzie taki sam? : )

Dlaczego chcesz tak robić, skoro masz rzucać standardową kością? I wynik raczej taki sam nie będzie.

[Malina015]

Malina015, ja to zrobiłem dla \(\displaystyle{ 1 \le x_i \le 6}\). Wtedy wszystkie mozliwe wyniki oznaczylem jako \(\displaystyle{ {30 + 10 -1 \choose 10 -1}}\). I to jest źle zrobione?

Jest źle, tak jak napisałam, jeśli zrobisz tak, to musisz poprawić wzór. Dlatego zazwyczaj robi się, że \(\displaystyle{ 0 \le x_i \le 5}\) (i wtedy tak samo postępuje się dla wszystkich zadań). \(\displaystyle{ {30 -1 \choose 10 -1}}\) tak powinno być. czyli \(\displaystyle{ {20 + 10 -1 \choose 10 -1}}\).

Nie, powinno być \(\displaystyle{ \binom{29}{9}}\), ale to i tak nie będzie prawidłowo, gdyż będzie uwzględniać takie wyniki jak:
\(\displaystyle{ 21,1,1,1,1,1,1,1,1,1}\).

Uznałam, ze jeśli ktoś twierdzi, ze wie jak rozwiązać to odjęcie zbiorów dla których nie spełniają warunków jest oczywiste.
Odejmujemy \(\displaystyle{ 10{20 + 10-6 -1 \choose 10 -1}- {10 \choose 2} {17 \choose 9} + {10 \choose 3} {11 \choose 9}}\)
Czyli ostatecznie
\(\displaystyle{ {20 + 10 -1 \choose 10 -1}-(10{20 + 10-6 -1 \choose 10 -1}- {10 \choose 2} {17 \choose 9} + {10 \choose 3} {11 \choose 9})}\)

[pyzol]

Dla mnie to jakoś oczywiste nie jest. Możesz wytłumaczyć skąd to:
\(\displaystyle{ 10{20 + 10-6 -1 \choose 10 -1}- {10 \choose 2} {17 \choose 9} + {10 \choose 3} {11 \choose 9}}\)

[leszczu450]

pyzol, potrzebna mi rada kogoś kto się zna : ) Jako zielono-nickowy użytkownik wierze, że dobrze znasz temat. W takim razie proste pytanie . Czy muszę poprawiąc to założenie o \(\displaystyle{ x_i}\) czy nie?

[Malina015]

leszczu450 udzieliłam Ci dość konkretnej odpowiedzi. To zależy od tego co dalej napiszesz. Jak również zamieściłam już całe rozwiązanie zadania. Nie wiem dlaczego uważasz, że to co piszę jest niewiarygodne.

Dla mnie to jakoś oczywiste nie jest. Możesz wytłumaczyć skąd to:
\(\displaystyle{ 10{20 + 10-6 -1 \choose 10 -1}- {10 \choose 2} {17 \choose 9} + {10 \choose 3} {11 \choose 9}}\)

Mogę.
Korzystamy ze wzoru włączeń i wyłączeń, oznaczmy przez \(\displaystyle{ A_i}\) zbiory rozwiązań dla których \(\displaystyle{ x_i\geq 6}\). Wówczas nasze rozwiązanie to \(\displaystyle{ \left| A \right| - \left| \bigcup_{1}^{10} A_i\right|}\)
Gdzie przez A oznaczyłam już policzone wszystkie możliwe rozwiązania. Musimy teraz policzyć:
\(\displaystyle{ \left| \bigcup_{1}^{10} A_i\right|}\).
\(\displaystyle{ \left| A_i \right| = {20 + 10-6 -1 \choose 10 -1}}\). I mamy 10 takich zbiorów.
\(\displaystyle{ \left| A_i \cap A_j \right| = {20 +10 -6 -6 -1 \choose 10-1}}\) i mamy \(\displaystyle{ {10 \choose 2}}\) takich zbiorów.
\(\displaystyle{ \left| A_i \cap A_j \cap A_k \right| = {20 +10 -6 -6 -6 -1 \choose 10-1}}\) i mamy \(\displaystyle{ {10 \choose 3}}\) takich zbiorów.
\(\displaystyle{ \left| A_i \cap A_j \cap A_k \cap A_l \right| = 0}\)
Ostatecznie:
\(\displaystyle{ \left| \bigcup_{1}^{10} A_i\right|=\left| A_i \right|-\left| A_i \cap A_j \right|+\left| A_i \cap A_j \cap A_k \right|=10{20 + 10-6 -1 \choose 10 -1}- {10 \choose 2} {17 \choose 9} + {10 \choose 3} {11 \choose 9}}\)

[leszczu450]

Malina015, nie rozumiem jednej rzeczy. Pozwól, że wyjaśnie Ci jak ja to zrobiłem.

Skoro zakładam, że \(\displaystyle{ 1 \le x_i \le 6}\) to moim zdarzeniem przeciwnym są sytuacje kiedy \(\displaystyle{ x_i \ge 7}\). Tak ja byłem uczony.

W takim razie:

Wszystkich roziązań, bez żadnych specjalnych założeń jest: \(\displaystyle{ {30 + 10 -1 \choose 10-1}}\).


Teraz:
\(\displaystyle{ A_1}\) to taki zbiór rozwiązań, gdzie \(\displaystyle{ x_1 \ge 7}\)
\(\displaystyle{ A_2}\) to taki zbiór rozwiązań, gdzie \(\displaystyle{ x_2 \ge 7}\)
\(\displaystyle{ \ldots}\)

\(\displaystyle{ \ldots}\)

\(\displaystyle{ \ldots}\)

\(\displaystyle{ A_{10}}\) to taki zbiór rozwiązań, gdzie \(\displaystyle{ x_{10} \ge 7}\)

Więc na mocy wzoru włączeń i wyłączeń:
\(\displaystyle{ {30 + 10 -1 \choose 10-1} - 10 {30 - 7 + 10 -1 \choose 10-1} + {10 \choose 2} {30 - 14 + 10-1 \choose 10-1} - {10 \choose 3} {30 -21 + 10-1 \choose 10-1} + {10 \choose 4} {30 - 28 +10-1 \choose 10-1}}\)

Czy tak nie powinno robić się takich zadań ?

Nie mówię, że to co Ty robisz jest źle i nie neguje Twojej wiedzy : ) Chce się tylko upewnić, że mówimy o tym samym i że dojdziemy do dobrych(prawidłowych) wniosków(wyników) )

[pyzol]

Nie, jak masz swoje liczby, to tak jakbyś sobie położył kulki. Masz 30 kul miedzy nimi 29 przerw. Z tych przerw wybierasz 9, które podzielą twoje 30 kul na 10 podzbiorów o łącznej sumie 30. Więc:
\(\displaystyle{ \binom{29}{9}}\).
Mnie tylko zastanawia ten wzór:
\(\displaystyle{ \left| A_i \right| = {20 + 10-6 -1 \choose 10 -1}.}\), którego nie widziałem.

[Malina015]

Wyniki są różne, czyli na pewno ktoś popełnia błąd.
Spójrz zresztą na treść i rozwiązanie zadania 11 tutaj:

Jest dość dokładnie opisane co zostało zrobione.
Po prostu wzór jest prawdziwy dla \(\displaystyle{ x_i \geq 0}\). Stąd przeskalowanie \(\displaystyle{ x_i}\).

Mnie tylko zastanawia ten wzór:
\(\displaystyle{ \left| A_i \right| = {20 + 10-6 -1 \choose 10 -1}.}\), którego nie widziałem.

\(\displaystyle{ A_i}\) to zbiory takie, że \(\displaystyle{ x_i \geq 6}\). Stąd ten wzór.
Ogólnie dla \(\displaystyle{ x_i \geq m_i}\) ilość rozwiązań równania \(\displaystyle{ x_1+\ldots x_n =n}\) jest równa \(\displaystyle{ \left| B \right| = {n+k-1- (m_1+\ldots + m_n) \choose k-1}.}\)

[leszczu450]

pyzol nie rozumiem... Ja byłem uczony, że ilość wszystkich całkwitoliczbowych rozwiązań równania o \(\displaystyle{ r}\) niewiadomych równa jest \(\displaystyle{ {n + r-1 \choose r-1}}\) ,gdzie \(\displaystyle{ n}\) to wysokość prostokątku czyli w naszym przypadku \(\displaystyle{ 30}\). Nie jest tak?