Leniwiec.edu.pl

Podstawowe schematy kombinatoryczne

Oznaczenia i potrzebne definicje

• Silnia
  , symbol czyta się ,,n silnia", umownie przyjmuje się, że .
  Wypiszmy kilka watości silni: 1!=1, 2!=2, 3!=6, 4!=24, 5!=120, .... 
  Często symbol  "trzeba widzieć" w zadaniach jako: 

  

• Współczynniki dwumianu Newtona
  Dla określamy liczbę
              (symbol czytamy ,,n nad k").
  Jest to liczba wyrazowych podzbiorów, jakie można utworzyć ze zbioru -elementowego.
  Z równości

  

  
  wynika, że liczba wszystkich podzbiorów - włączając w to zbiór pusty i cały zbiór - jakie można utworzyć ze zbioru -elementowego jest równa 2ⁿ.
• Ciągi i zbiory elementów
  (a,b) - para uporządkowana (ciąg) dwóch elementów, ważne jest to jakie elementy ją tworzą, ale także ich kolejność,
  {a,b} - para nieuporządkowana (zbiór) dwóch elementów, kolejność nie jest ważna, {a,b} = {b,a}.
  Podobnie dla trójek:
  (a,b,c) - uporządkowana trójka, czyli ciąg z trzech elementów,
  {a,b,c} - zbiór trójelementowy.
• Liczbę elementów zbioru A nazywamy mocą tego zbioru i oznaczamy lub |A|.
• Jeżeli to moc  
  zawsze, dla dowolnych A i B:    

Schematy wyboru
 
Niech A będzie zbiorem skończonym -elementowym
                  
Zajmiemy się losowym wybieraniem elementów spośród elementów tego zbioru.
Przed przystąpieniem do losowania trzeba ustalić:
1. czy istotna jest kolejność w jakiej wybieramy elementy. Inaczej - czy z wylosowanych elementów tworzymy ciąg czy zbiór,
2. czy wybrany element jest zwracany do zbioru A. Inaczej - czy losowanie jest ,,bez zwracania" czy ,,ze zwrotem".

Zasady przeliczania

Tak samo dla większej liczby rozłącznych zbiorów.

Przelicznie zbiorów (liczby wyborów) metodą pymitywną tzn. przez wypisanie wszystkich możliwości, ma sens wówczas, gdy liczba elementów zbioru jest mała. W przeciwnym razie trzeba znać wzór na liczbę wyborów lub metodę przeliczania. Są cztery podstawowe schematy zliczania - schematy kombinatoryczne.
1. Losujemy bez zwracania elementów i ustawiamy je kolejno - tworzymy -wyrazowy ciąg. Każdy z powstałych ciągów nazywa się wariacją bez powtórzeń z elementów po elementów.

2. Losujemy ze zwrotem elementów  i ustawiamy je kolejno - tworzymy -wyrazowy ciąg. Każdy z takich ciągów nazywa się wariacją z powtórzeniami z elementów po elementów.

3. Mamy zbiór elementowy. Elementy tego zbioru ustawiamy w ciąg lub - co na jedno wychodzi - numerujemy je od 1 do Każdy z takich ciągów nazywa się permutacją elementów.

4. Mamy zbiór elementowy. Wybieramy z niego elementów  bez zwrotu i tworzymy z nich zbiór, kolejność nie ma znaczenia. Każdy z takich zbiorów nazywamy kombinacją -elementową ze zbiorów -elementowego.

Dołączamy jeszcze: 
1. Wzór na liczbę podziałów niepustego zbioru. Niech A będzie zbiorem -elementowym, który dzielimy na rozłącznych podzbiorów składających się z elementów Liczba różnych takich podziałów wyraża się wzorem:
                 
Np. Liczba różnych rozdań 52 kart po 13 dla każdego z czterech grających w brydża jest równa
              
2. Wzór na liczbę rozmieszczeń nierozróżnialnych kul w komórkach - czyli kombinacji z powtórzeniami:
                                                
Np. Na ile sposobów pasażerów może wysiąść z windy na piętrach?   
                             

Elementarny rachunek prawdopodobieństwa 

I. Doświadczenia losowe

Rachunek (teoria) prawdopodobieństwa zajmuje się zdarzeniami jakie zachodzą, gdy przeprowadzamy doświadczenia losowe.

Jako przykłady takich doświadczeń podaje się zwykle rzuty monetą lub kostką do gry, kupno losu na loterii, karty jakie można otrzymać w rozdaniu pokera itp.

II. Przestrzeń zdarzeń elementarnych
Wyniku danego doświadczenia losowego nie potrafimy przewidzieć, ale możemy podać (lub opisać) zbiór, do którego należy. Zbiór ten tradycyjnie oznacza się literą .

W szkolnym rachunku prawdopodobieństwa przestrzeń jest zwykle zbiorem o skończonej liczbie elementów:

Przykłady

1. Jednokrotny rzut monetą. Możliwymi wynikami w tym doświadczeniu są dwa zdarzenia elementarne: wyrzucenie orła lub wyrzucenie reszki .
Opisując to doświadczenie przyjmujemy:

2. Jednokrotny rzut kostką. W tym doświadczeniu:

3. Dwukrotny rzut monetą lub równoczesny rzut dwiema różnymi monetami, np. złotówką i dwuzłotówką. Teraz każde  to uporządkowana para:

        (wynik pierwszego rzutu, wynik drugiego rzutu)
lub    (wynik na złotówce, wynik na dwuzłotówce)

 lub krócej

4. Dwukrotny rzut kostką do gry lub równoczesny rzut dwiema kostkami np. czerwoną i zieloną. Teraz każde  to uporządkowana para:

       (liczba oczek w pierwszym rzucie, liczba oczek w drugim rzucie)
lub   (liczba oczek na kostce czerwonej, liczba oczek na kostce zielonej).

W tym doświadczeniu zdarzenia elementarne ustawia się zwykle w tablicy o sześciu wierszach i kolumnach.

5. Rozdania kart w brydżu. Każdy z czterech graczy otrzymuje po 13 kart z talii 52 kart. Przestrzeń zdarzeń elementarnych tworzą podziały zbioru 52 kart na 4 zbiory po 13 kart. Liczba takich podziałów jest olbrzymia,

Zdarzenia oznaczamy początkowymi dużymi literami alfabetu A, B, C, ... i opisujemy je słowami poprzedzając myślnikiem.
Np. gdy
A - wypadła parzysta liczba oczek, A = {2,4,6},
B - wypadła liczba oczek nie mniejsza niż 4, B = {1,2,3,4},
C - wypadła szóstka, C = {6}.

Podzbiorami są też:
- zbiór pusty przedstawiający zdarzenie niemożliwe (np. w jednym rzucie kostką wypadło 7 oczek lub jeden z graczy w brydża otrzymał wśród 13 kart dwie damy kier),
- cała przestrzeń  przedstawiająca zdarzenie pewne (każde ).

Zdarzenie  nazywamy zdarzeniem przeciwnym do A. Jeżeli , to i zachodzi zdarzenie przeciwne do A.
A' to zbiór tych , które nie sprzyjają A.
Zdarzeniem przeciwnym do jest  i odwrotnie.

IV. Działania na zdarzeniach
Gdy dopuszczamy dwa zdarzenia A i B, to możemy interesować się tym, czy te dwa zdarzenia zachodzą równocześnie lub czy zaszło przynajmniej jedno z nich.

O zdarzeniach A i B takich, że mówimy, że wykluczają się.

Jeżeli , to zajście zdarzenia A pociąga za sobą B.

Czasami o zdarzeniach wyrażamy się w terminach teorii zbiorów (iloczyn, suma, dopełnienie), zamiast w terminach rachunku prawdopodobieństwa.

V. Definicja prawdopodobieństwa

•  Model klasyczny (klasyczna definicja prawdopodobieństwa)

Model klasyczny pasuje do wielu zdarzeń, gdzie występują symetryczne monety lub kości do gry, karty, losy na loterii itp.

• Model uogólniony

Model ten stosujemy, gdy nie wszystkie zdarzenia elementarne są jednakowo prawdopodobne.

VI. Podstawowe własności prawdopodobieństwa
1. Prawdopodobieństwo zdarzenia niemożliwego jest równe zero:

VII. Prawdopodobieństwo warunkowe
Jest to podstawowe pojęcie teorii prawdopodobieństwa - chodzi o to, że zajście jakiegoś zdarzenia może zmienić prawdopodobieństwa zajścia innego zdarzenia.

Jeżeli wiemy, że zaszło zdarzenie B, to ograniczamy się do zdarzeń elementarnych sprzyjających B (jest to nowa przestrzeń zdarzeń) oraz tych które należą do części wspólnej (sprzyjają A i B).

Przykłady
1. Rzucono 3 razy monetą i wypadła nieparzysta liczba orłów (zdarzenie B). Jakie jest prawdopodobieństwo, że wypadły 3 orły (zdarzenie A)?

                     . 
Można było też zastosować wzór: ,
, , ,
                                   
2. Rzucono 2 razy kostką do gry i w pierwszym rzucie wypadło 6 oczek (zdarzenie B). Jakie jest prawdopodobieństwo, że w obu rzutach wypadnie co najmniej 10 oczek (zdarzenie A)?
Zastosujmy wzór
Z przykładu 4 w pkt. II (tablica) wiemy, że 



 
                

Teraz prościutko stosując wzór 

Korzystając z tego można pójść dalej

    itd.
Wzory te pojawią się, gdy będziemy opisywali metodę drzew.

VIII. Prawdopodobieństwo całkowite

Mówimy też, że rodzina taka stanowi rozbicie przestrzeni . 

Na diagramie wygląda to np. tak 









Weźmy teraz dowolne zdarzenie A. Umieszczamy je na powyższym diagramie.










Widać, że:
Wszystkie zdarzenia są rozłączne. Z rozdziału II pkt. 5, wynika, że 
 
Stosując wzór na prawdopodobieństwo iloczynu zdarzeń otrzymujemy:
         

Uwaga.
Zdarzenie B i do niego przeciwne B' stanowią rozbicie przestrzeni   
W takim razie
                            

IX. Niezależność zdarzeń

Jeżeli A i B są niezależne to wg tej definicji:
a to oznacza, że zdarzenie B nie ma wpływu na prawdopodobieństwo zdarzenia A.
Uwaga.
Jeżeli zdarzenie A i B są niezależne, to niezależne są też zdarzenia: A i B’, A’ i B, A’ i B’.

X. Schemat Bernoulliego

Jeden z dwóch wyników nazywamy tradycyjnie sukcesem, a drugi porażką. Oznaczamy prawdopodobieństwo sukcesu jako a prawdopodobieństwo porażki Niezależność prób polega na tym, że dowolny wynik jednej próby nie wpływa na prawdopodobieństwo pojawienia się każdego z wyników w następnej próbie.

Przykłady schematu prób Bernolulliego
1. -krotny rzut symetryczną monetą, za sukces możemy przyjąć wypadnięcie orła 
a porażka jest wypadnięcie reszki
2. badanie urządzeń, gdy interesuje nas czy są one sprawne czy wadliwe, sukces  to ,,urządzenie jest sprawne", 
3. -krotny rzut symetryczną kostką, gdy za sukces uważamy wypadnięcie szóstki ,
4. kupno losów na loterii, gdy los jest wygrany (sukces) lub pusty (porażka).

Oznaczmy przez liczbę sukcesów w schemacie prób Bernouliiego.  

Przykłady
1. Rzucamy 6 razy symetryczną kostką do gry. Oblicz prawdopodobieństwo zajścia:
a) zdarzenia A - otrzymano jedną szóstkę,
b) zdarzenia B - otrzymano najwyżej dwie szóstki,
c) zdarzenia C - otrzymano co najmniej jedną szóstkę.

a)
b) , gdzie - otrzymano 0, 1, 2 szóstki. Zdarzenia te wykluczają się. Stąd dalej wynika, że




c) Zdarzeniem przeciwnym do C jest C' - nie wypadła ani jedna szóstka. Stąd
 

2. Oblicz prawdopodobieństwo zdarzenia A - trzeci orzeł wypadł w 10-tym rzucie.
Bezpośrednio nie można zastosować wzoru na . Jak realizuje się zdarzenie A?
, gdzie
B - wypadły 2 orły w 9-ciu rzutach, 
C - w dziesiątym rzucie wypadł orzeł, 


Zdarzenia B i C są niezależne, więc



XI. Drzewa
Teraz będzie o metodzie, która nadaje się do doświadczeń realizowanych w dwóch lub więcej etapach. Takimi są np. - często występujące z zadaniach - losowanie kolejno kul z urny, rzuty monetą lub kostką, ciągnięcie kart z talii itp. oraz złożenie kolejno tych doświadczeń.

Przykład takiego (problemu) doświadczenia.
Mamy dwie urny. W pierwszej są 2 kule białe i 3 czarne, a w drugiej 3 białe i 1 czarna. Rzucamy kostką i jeżeli wypadnie szóstka, to ciągniemy kulę z urny I, w przeciwnym przypadku ciągniemy z urny II. Jakie jest prawdopodobieństwo, że wyciągniemy kulę białą?

W metodzie drzew rysujemy diagram, który daje przejrzystość rozwiązania. Z rysunku widać co trzeba pomnożyć i ewentualnie potem dodać, aby mieć szukane prawdopodobieństwo - to coś dla leniwych!

Diagram nazywamy drzewem. Drzewo zaczyna się początkiem (korzeniem), który zaznacza się kropką lub kółkiem.
Z korzenia wychodzą w dół odcinki zwane krawędziami, w takiej liczbie ile jest różnych wyników w pierwszym etapie (np. trzy). 










Pod krawędziami piszemy wyniki pierwszego etapu, są to węzły drzewa. Obok każdej krawędzi piszemy prawdopodobieństwo otrzymania danego wyniku. W przykładzie etap I może kończyć się wynikami o prawdopodobieństwach  
Przyjmijmy, że w etapie II mogą wystąpić dwa wyniki B i C. Rysujemy drzewo dalej. Z każdego węzła kończącego pierwszy etap wychodzą po dwie krawędzie kończące się zdarzeniami B i C. 

Ciąg krawędzi łączący początek z jakimś węzłem końcowym to gałąź drzewa. Jedna z możliwych gałęzi jest - na rysunku wyżej - oznaczona grubszą linią.
Jakie prawdopodobieństwo przypisać krawędzi łączącej ?
Oczywiście  to prawdopodobieństwo zdarzenia B, gdy w pierwszym etapie zaszło zdarzenie
Pomnóżmy prawdopodobieństwa przypisane krawędziom pogrubionej gałęzi
Jest to - oczywiście, zaszły zdarzenia .

Na koniec spytajmy, jak z drzewa odczytać prawdopodobieństwo, że zaszło zdarzenie B? Jest to suma prawdopodobieństw przypisanych gałęziom kończących się w węzłach B. 

 
.
No i mamy po prostu wzór na prawdopodobieństwo całkowite. Można było nie rysować drzewa, a posłużyć się tym wzorem.

Podsumujmy krótko.

• zaczynamy od korzenia rysując krawędzie w dół,
• krawędzie to odcinki zaczynające się i kończące w węzłach oraz idące zawsze w dół,
• węzły to zdarzenia kończące etapy doświadczenia,
• gałąź to ciąg krawędzi od korzenia do zdarzenia w ostatnim etapie,
• prawdopodobieństwo odpowiadające gałęzi jest iloczynem prawdopodobieństw krawędzi, z których się ona składa.

Rozwiązanie podanego wcześniej przykładu
Oznaczamy zdarzenia:
A - na kostce wypadło 6 oczek,
A' - na kostce nie wypadło 6 oczek,
B - wyciągnięto kulę białą,
B' = C - wyciągnięto kule czarną.

,

lub inaczej

Jeszcze jeden przykład
W urnie jest 7 kul białych i 3 czarne. Losujemy z niej kolejno dwie kule. Jakie jest prawdopodobieństwo, że druga wylosowana kula jest czarna?

Urna przed losowaniem: 

Oznaczamy zdarzenia:
- w pierwszym losowaniu wyciągnięto kulę białą,
- w pierwszym losowaniu wyciągnięto kulę czarną,
- w drugim losowaniu wyciągnięto kulę białą,
- w drugim losowaniu wyciągnięto kulę czarną. 

XII. Wzór Bayesa

Problem polega na tym, że znamy wynik doświadczenia, a pytamy o jego przebieg.

Typowe przykłady
1. Wśród 10 monet jedna ma orły po obu stronach. Wybieramy losowo jedną monetę, rzucamy 5 razy i wypada 5 orłów. Jakie jest prawdopodobieństwo, że jest to moneta z orłami po obu stronach? 
2. Pewne urządzenia są sprowadzane od 3 dostawców A,B,C, w następujących ilościach: 50%, 20% i 30%. Wadliwość urządzeń: od dostawcy A - 1%, B - 2%, C - 3%. Wybrane urządzenie okazało się wadliwe. Jakie jest prawdopodobieństwo, że pochodzi ono od dostawcy A?

Np. na diagramie

Prawdopodobieństwo zdarzenia pod warunkiem, że zaszło zdarzenie A.

Rozwiązanie przykładu 1. 
Oznaczamy i opisujemy zdarzenia:
A - w 5 rzutach wypadło 5 orłów,
B₁ - rzucono monetą prawidłową,
B₂ - rzucono monetą z dwoma orłami. 

B₁ i B₂ tworzą zupełny układ zdarzeń, , bo moneta nie może mieć jednocześnie na obu stronach orła i reszkę oraz dwa orły, a poza B₁ i B₂ innych możliwości nie ma.

gdyż dziewięć z dziesięciu monet jest prawdziwych, a jedna ma dwa orły.

- prawdopodobieństwo, że wypadło 5 orłów w 5 rzutach, gdy rzucano monetą prawidłową. Mamy tu 5 sukcesów w schemacie 5 prób Bernoulliego z prawdopdobieństwem sukcesu więc
 
bo rzucając monetą z dwoma orłami zawsze dostajemy orła.

Drzewo dla tego doświadczenia
















Trzeba policzyć prawdopodobieństwo zdarzenia B₂ (moneta z dwoma orłami) pod warunkiem, że zaszło A

Krótko - trzeba narysować drzewo i iloczyn prawdopodobieństw odpowiadających pogrubionej gałęzi podzielić przez , ...

Tak rozwiążemy przykład 2.
Oznaczamy i opisujemy zdarzenia:
D - urządzenie jest wadliwe,
A - urządzenie kupiono od dostawcy A,
B - urządzenie kupiono od dostawcy B,
C - urządzenie kupiono od dostawcy C.
W języku rachunku prawdopodobieństwa, jeżeli urządzenie jest wybierane losowo,
to
Jeżeli urządzenie pochodzi od dostawcy A, to prawdopodobieństwo, że jest wadliwe i odpowiednio
Drzewo dla tego doświadczenia

Czyli prawdopodobieństwo, że wadliwe urządzenie pochodzi od dostawcy A wynosi 0,28 (28%).