Przejdź do treści
Czas Matematyki
0%

Kombinatoryka i rachunek prawdopodobieństwa

Reguły zliczania, wariacje, permutacje, kombinacje, doświadczenia losowe i prawdopodobieństwo; na rozszerzeniu także warunkowe, całkowite i niezależność.

Przejdź do quizuZagraj w dziale Gry

Liczenie etapami

Reguła mnożenia i reguła dodawania

Reguła

Dwa podstawowe narzędzia

  • jeżeli wybór przebiega w kolejnych etapach na n1,n2,…,nkn_1,n_2,\ldots,n_k sposobów, łącznie mamy n1n2⋯nkn_1n_2\cdots n_k możliwości,
  • jeżeli rozłączne przypadki można zrealizować na n1,n2,…,nkn_1,n_2,\ldots,n_k sposobów, łącznie mamy n1+n2+⋯+nkn_1+n_2+\cdots+n_k możliwości.
start3 · 2 = 6 wyników
Każda pełna ścieżka odpowiada jednemu wynikowi doświadczenia lub wyboru.

Przykład

Zestaw obiadowy

Do wyboru są 3 zupy, 5 dań głównych i 2 desery. Liczba zestawów to 3⋅5⋅2=303\cdot5\cdot2=30.

Uporządkowane wybory

Wariacje bez powtórzeń i z powtórzeniami

Definicja

Wariacja k-elementowa

Wybieramy kk elementów z nn i kolejność ma znaczenie.

Vnk=n!(n−k)!V_n^k=\frac{n!}{(n-k)!}

Gdy elementy mogą się powtarzać:

V‾nk=nk\overline V_n^k=n^k

Przykład

Kod z różnych cyfr

Trzycyfrowy kod z 7 cyfr bez powtórzeń można utworzyć na 7⋅6⋅5=2107\cdot6\cdot5=210 sposobów.

Ustawiamy wszystkie

Permutacje bez powtórzeń i z powtórzeniami

Definicja

Permutacja

Pn=n!P_n=n!

Jeżeli wśród nn elementów występują powtórzenia w liczbach n1,…,nsn_1,\ldots,n_s, to:

P=n!n1!n2!⋯ns!P=\frac{n!}{n_1!n_2!\cdots n_s!}

Przykład

Litery słowa ANANAS

Jest 6 liter: A występuje 3 razy, N dwa razy. Liczba napisów wynosi 6!3!2!=60\frac{6!}{3!2!}=60.

Wybór bez kolejności

Kombinacje

Definicja

Kombinacja k-elementowa

(nk)=n!k!(n−k)!{n\choose k}=\frac{n!}{k!(n-k)!}

Kolejność wybranych elementów nie ma znaczenia.

permutacjawariacjakombinacjan!n!/(n−k)!n!/[k!(n−k)!]ustawiamy wszystkokolejność ważnakolejność nieważna
Kluczowe pytanie: czy kolejność ma znaczenie i czy wykorzystujemy wszystkie elementy?

Przykład

Drużyna

Z 10 osób wybieramy 3: (103)=120{10\choose3}=120.

Przykład

Własność symetrii

(nk)=(nn−k){n\choose k}={n\choose n-k}

Wybrać kk osoby znaczy wskazać n−kn-k niewybranych.

Dobór modelu

Kombinatoryka — zadania różne

Reguła

Cztery pytania przed obliczeniem

  1. czy kolejność ma znaczenie?
  2. czy elementy mogą się powtarzać?
  3. czy wybieramy wszystkie elementy?
  4. czy trzeba podzielić zadanie na rozłączne przypadki?

Przykład

Liczby z warunkiem

Tworząc liczby czterocyfrowe, osobno liczymy przypadki zależne od pierwszej cyfry, bo zero nie może stać na początku. Ograniczenia uwzględniamy przed zastosowaniem wzoru.

Warto zapamiętać

W trudniejszych zadaniach diagram drzewa albo rozbicie na przypadki bywa bezpieczniejsze niż próba użycia jednego gotowego wzoru.

Model losowania

Doświadczenie losowe i przestrzeń wyników

Definicja

Przestrzeń zdarzeń elementarnych

Zbiór wszystkich możliwych wyników doświadczenia oznaczamy przez Ω\Omega. Pojedynczy wynik to zdarzenie elementarne.

Przykład

Dwa rzuty monetą

Ω={OO,OR,RO,RR}\Omega=\{OO,OR,RO,RR\}

Przestrzeń ma cztery jednakowo prawdopodobne wyniki.

Zbiory wyników

Zdarzenia i działania na zdarzeniach

ΩABA ∩ B
A i B są podzbiorami przestrzeni wyników Ω. Ciemniejszy obszar A ∩ B oznacza wyniki należące do obu zdarzeń jednocześnie.

Reguła

Suma, iloczyn i dopełnienie

  • A∪BA\cup B — zaszło co najmniej jedno z A lub B,
  • A∩BA\cap B — zaszły jednocześnie A i B,
  • A′A' — zdarzenie A nie zaszło.

Warto zapamiętać

Zdarzenia rozłączne spełniają A∩B=∅A\cap B=\varnothing. Zdarzenie niemożliwe to ∅\varnothing, a pewne to Ω\Omega.

Miara szansy

Określenie prawdopodobieństwa i model klasyczny

Reguła

Aksjomaty i własności

0≤P(A)≤1,P(Ω)=10\le P(A)\le1,\qquad P(\Omega)=1
P(A′)=1−P(A)P(A')=1-P(A)
P(A∪B)=P(A)+P(B)−P(A∩B)P(A\cup B)=P(A)+P(B)-P(A\cap B)

Definicja

Prawdopodobieństwo klasyczne

Gdy wszystkie wyniki elementarne są jednakowo prawdopodobne:

P(A)=∣A∣∣Ω∣P(A)=\frac{|A|}{|\Omega|}

Przykład

Karta z talii

W talii 52 kart jest 13 pików, więc prawdopodobieństwo wylosowania pika wynosi 13/52=1/413/52=1/4.

Quiz · 10 pytań

Sprawdź zakres podstawowy

1. Z 3 koszul i 4 par spodni można utworzyć:

2. Jeżeli dwie rozłączne możliwości można zrealizować odpowiednio na 5 i 7 sposobów, łącznie jest:

3. Liczba permutacji 5 różnych elementów wynosi:

4. Ile dwuliterowych napisów bez powtórzeń utworzymy z 5 różnych liter?

5. Liczba sposobów wyboru 2 osób z grupy 6 osób to:

6. Przy jednym rzucie kostką przestrzeń zdarzeń elementarnych ma:

7. Zdarzenie pewne ma prawdopodobieństwo:

8. Prawdopodobieństwo wyrzucenia liczby parzystej na uczciwej kostce wynosi:

9. Dla dowolnego zdarzenia A zachodzi:

10. Prawdopodobieństwo zdarzenia przeciwnego do A wynosi: