Wzór włączeń i wyłączeń

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
bukos123
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 23 sty 2014, o 12:55
Płeć: Mężczyzna
Lokalizacja: BDG

Wzór włączeń i wyłączeń

Post autor: bukos123 » 23 sty 2014, o 12:59

Jest ktoś w stanie pomóc mi z jednym (prostym) zadaniem z matematyki dyskretnej?

Treść: Stosując schemat ,,włączeń i wyłączeń" znajdź liczbę wszystkich binarnych słów sześciobitowych zawierających podciąg 01.

A1 = {01****}
A2 = {*01***}
A3 = {**01**}
A4 = {***01*}
A5 = {****01}

Z góry dzięki za pomoc!

bartek118
Gość Specjalny
Gość Specjalny
Posty: 5971
Rejestracja: 28 lut 2010, o 19:45
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 15 razy
Pomógł: 1251 razy

Wzór włączeń i wyłączeń

Post autor: bartek118 » 23 sty 2014, o 13:05

No to ze wzoru włączeń i wyłączeń:
\(\displaystyle{ |A_1 \cup \ldots \cup A_5| = |A_1| + \ldots + |A_5| - |A_1 \cap A_2| - \ldots - |A_4 \cap A_5| + |A_1 \cap A_2 \cap A_3| + \ldots}\)
Musisz policzyć wszystkie wyrażenia występujące po prawej stronie.

bukos123
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 23 sty 2014, o 12:55
Płeć: Mężczyzna
Lokalizacja: BDG

Wzór włączeń i wyłączeń

Post autor: bukos123 » 23 sty 2014, o 13:17

\(\displaystyle{ |A| = |A_1 \cup \ldots \cup A_5|}\)

\(\displaystyle{ |A_1| = ... = |A_5| = 2 ^{4}}\)

\(\displaystyle{ |A_1 \cap A_2|}\) = zb. pusty
\(\displaystyle{ |A_1 \cap A_3| = 2 ^{2}}\)
\(\displaystyle{ |A_1 \cap A_4| = 2 ^{2}}\)
\(\displaystyle{ |A_1 \cap A_5| = 2 ^{2}}\)
\(\displaystyle{ |A_2 \cap A_3|}\) = zb. pusty
\(\displaystyle{ |A_2 \cap A_4| = 2 ^{2}}\)
\(\displaystyle{ |A_2 \cap A_5| = 2 ^{2}}\)
\(\displaystyle{ |A_3 \cap A_4|}\) = zb. pusty
\(\displaystyle{ |A_3 \cap A_5| = 2 ^{2}}\)
\(\displaystyle{ |A_4 \cap A_5|}\) = zb. pusty

\(\displaystyle{ |A_1 \cap A_3 \cap A_5| = 2^{0}}\) , pozostałe "trójki puste"
dla czwórek i piątek też zbiór pusty.

\(\displaystyle{ |A_1 \cup \ldots \cup A_5| = 5 \cdot 2 ^{4} - 6 \cdot 2 ^{2} + 2 ^{0} = 5 \cdot 16 - 6 \cdot 4 + 1 = 80 - 24 + 1 = 57}\)

To jest dobre rozwiązanie?

bartek118
Gość Specjalny
Gość Specjalny
Posty: 5971
Rejestracja: 28 lut 2010, o 19:45
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 15 razy
Pomógł: 1251 razy

Wzór włączeń i wyłączeń

Post autor: bartek118 » 23 sty 2014, o 22:00

Wygląda OK

ODPOWIEDZ