Rachunek prawdopodobieństwa
1. Pojęcie prawdopodobieństwa.
2. Prawdopodobieństwo warunkowe. Niezale\
ność zdarzeń. Schemat Bernoulli ego. Prawdopodobieństwo
całkowite.
Literatura podstawowa
1. Z. Hellwig Elementy rachunku prawdopodobieństwa i statystyki matematycznej. Warszawa 1977.
2. W. Kordecki Rachunek prawdopodobieństwa i statystyka matematyczna. Definicje, twierdzenia,
wzory. Wrocław 2002.
3. H. Jasiulewicz, W. Kordecki Rachunek prawdopodobieństwa i statystyka matematyczna. Przykłady i
zadania. Wrocław 2002.
4. W. Krysicki, J. Bartos, W. Dyczka, K. Królikowska. M. Wasilewski Rachunek prawdopodobieństwa i
statystyka matematyczna w zadaniach. Część 1 i część 2. Warszawa 1986.
Zdarzenia i prawdopodobieństwa zdarzeń
Rachunek prawdopodobieństwa to dział matematyki zajmujący się badaniem zjawisk losowych. Ze
zjawiskami takimi mamy do czynienia, gdy wykonujemy np. doświadczenie, którego wyniku z góry nie znamy,
ale mo\
emy je wielokrotnie powtarzać w tych samych warunkach. Dzięki temu jesteśmy w stanie przewidzieć
ró\
ne zakończenia tego doświadczenia i określić ich szanse.
Je\
eli np. wykonujemy doświadczenie polegające na rzucie monetą, to z góry nie wiemy, czy wypadnie orzeł
czy reszka. Jednak po wielu powtórzeniach tego doświadczenia mo\
emy nabrać podejrzeń, \
e szanse
wypadnięcia orła są takie same jak wypadnięcia reszki, czyli mówimy, \
e ka\
de z tych zjawisk zachodzi z
prawdopodobieÅ„stwem ½. Inne przykÅ‚ady doÅ›wiadczeÅ„ losowych: rzut kostkÄ… do gry, rozdanie kart, losowanie
toto-lotka, strzelanie do tarczy itp.
Rachunek prawdopodobieństwa zajmuje się te\
zjawiskami masowymi.
Np. interesuje nas, kto wygra wybory prezydenckie. Oczywiście wyniku z góry nie znamy, ale na podstawie
sonda\
y przedwyborczych mo\
emy przewidzieć jakie są szanse ka\
dego z kandydatów.
Widzimy więc, \
e z określaniem prawdopodobieństw ró\
nych zdarzeń mamy do czynienia na co dzień.
Przestrzeń zdarzeń elementarnych
W ka\
dej teorii istnieją pewne pojęcia pierwotne, czyli te, których się nie definiuje, np.
w arytmetyce  liczba, w geometrii  punkt, prosta, płaszczyzna.
Pojęciem pierwotnym w rachunku prawdopodobieństwa jest pojęcie:
przestrzeń zdarzeń elementarnych (zbiór zdarzeń elementarnych).
Oznaczamy jÄ… literÄ… &!, a jej elementy zwane zdarzeniami elementarnymi oznaczać bÄ™dziemy maÅ‚Ä… literÄ… É.
Przestrzeń zdarzeń elementarnych &!  jest to kompletna i rozłączna lista mo\
liwych wyników rozwa\
anego
doświadczenia losowego.
Przestrzeń zdarzeń elementarnych &! mo\
e być zbiorem skończonym lub nieskończonym, przeliczalnym albo
nieprzeliczalnym.
W praktyce zainteresowani jesteśmy nie tyle pojedynczymi zdarzeniami elementarnymi, ale ich zbiorami, a
więc podzbiorami zbioru &!.
Taką rodzinę podzbiorów &!, którą wyró\
niamy, nazywamy rodziną S podzbiorów przestrzeni zdarzeń
elementarnych ( tzw. zbiór zbiorów).
1
Zdarzeniami będziemy nazywać jedynie elementy rodziny S.
Przykłady:
- rzucając jednokrotnie monetą: zdarzenia elementarne O i R, przestrzeń {O,R}
- rzucając dwukrotnie monetą zdarzenia np.: (O,R), (O,O), przestrzeń to: {(O,O); (O,R);
(R,O); (R,R)},
- losowanie totolotka zdarzenia to szóstki: (1,2,3,4,5,6), (1,3,23,21,43,5) ... ,
przestrzeń to 13 983 816 mo\
liwych szóstek.
Silnia.
Symbol n! ( czytaj n  silnia) określamy rekurencyjnie:
1! = 1, n! = n · (n-1)!,
wiÄ™c: n!= n· n· (n-1)· (n-2)· ..... 3· 2· 1 i przyjmujemy: 0! = 1.
·
Przykłady:
(1) 2! = 1· 2 = 2
(2) 3! = 1· 2· 3 = 6
n!
(3) 5! = 120 = (k +1)(k + 2)...n, gdzie n > k
k!
Symbol Newtona.
Przyjmijmy nastÄ™pujÄ…cÄ… definicjÄ™ symbolu ëÅ‚ n öÅ‚ (czytamy n nad k) gdzie zwanego symbolem
n, k " N , n > k
ìÅ‚ ÷Å‚
ìÅ‚ ÷Å‚
k
íÅ‚ Å‚Å‚
Newtona:
n
ëÅ‚ öÅ‚ n!
ìÅ‚ ÷Å‚ = , n " N ,0 d" k d" n
ìÅ‚ ÷Å‚
k k!(n - k )!
íÅ‚ Å‚Å‚
Uwaga:
n n n n n + 1
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚ = ìÅ‚ ÷Å‚ = 1 ìÅ‚ ÷Å‚ + ìÅ‚ ÷Å‚ = ìÅ‚ ÷Å‚, gdzie : 1 d" k d" n
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
0 n k k - 1÷Å‚ ìÅ‚ k
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
n
n
ëÅ‚ öÅ‚
n n n n
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ n
ìÅ‚ ÷Å‚ = 2
ìÅ‚ ÷Å‚ = ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ = ìÅ‚ ÷Å‚ = n
"
ìÅ‚ ÷Å‚
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚
k
k n - k 1 n - 1÷Å‚
k = 0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
Przykłady:
7
ëÅ‚ öÅ‚ 7! 4!5 Å" 6 Å" 7
(1)
ìÅ‚ ÷Å‚ = = = 35
ìÅ‚ ÷Å‚
3 3!4! 4!1 Å" 2 Å" 3
íÅ‚ Å‚Å‚
3
ëÅ‚ öÅ‚ 3!
(2)
ìÅ‚ ÷Å‚ = = 1
ìÅ‚ ÷Å‚
0 0!3!
íÅ‚ Å‚Å‚
6
ëÅ‚ öÅ‚ 6!
(3) ìÅ‚ = = 1
ìÅ‚6÷Å‚ 6!0!
÷Å‚
íÅ‚ Å‚Å‚
4
ëÅ‚ öÅ‚ 4!
(4) ìÅ‚ = = 4
ìÅ‚1÷Å‚ 1!3!
÷Å‚
íÅ‚ Å‚Å‚
2
 Algebra zdarzeń. Działania na zdarzeniach
Zdarzenie pewne  jest to podzbiór przestrzeni zdarzeń elementarnych &!, zawierający wszystkie elementy tej
przestrzeni. Zdarzenie pewne oznaczamy tÄ… samÄ… literÄ… &!.
Zdarzenie niemo\
liwe  jest to podzbiór pusty przestrzeni zdarzeń elementarnych &!. Zdarzenie to będziemy
oznaczać symbolem ".
Przykład:
RzucajÄ…c raz kostkÄ… do gry : zdarzenia elementarne: 1,2,3,4,5,6 ,
przestrzeń zdarzeń{1,2,3,4,5,6}
Przykłady zdarzeń:
A - wyrzucenie parzystej liczby oczek, A = { 2, 4, 6}
B - wyrzucenie co najwy\
ej 4 oczek, B = { 1, 2, 3, 4 }
C - wyrzucenie dokładnie 4 oczek, C = { 4 }
D - wyrzucenie co najmniej jednego oczka, D = { 1, 2, 3, 4, 5, 6} - zdarzenie pewne
F - wyrzucenie więcej ni\
6 oczek, F = " - zdarzenie niemo\
liwe
Zdarzenia losowe jako podzbiory przestrzeni &! są zbiorami i będziemy je oznaczać literami A, B, C,... bądz

literami ze wskaz
nikami: A1, A2,...
Relacje i działania na zdarzeniach są więc po prostu relacjami i działaniami na zbiorach.
1. Mówimy, \
e zdarzenie losowe A jest zawarte w zdarzeniu losowym B, jeśli ka\
de zdarzenie
elementarne nale\
Ä…ce do A nale\
y te\
do B (relacja implikacji). Oznaczamy to jako:
B
A
A ‚" B
2. Sumą (alternatywą) dwu zdarzeń losowych A i B nazywamy zbiór zło\
ony z tych i tylko tych zdarzeń
elementarnych, które nale\
ą co najmniej do jednego ze zdarzeń losowych A oraz B. Oznaczamy jako:
A B
A *" B
Oczywiście suma dwóch zdarzeń jest równie\
zdarzeniem, więc uogólniając ją na n składników,
otrzymamy:
n
C = A1 *" A2 *"... *" An =
UAi
i =1
3. Iloczynem (koniunkcją) dwu zdarzeń losowych A oraz B nazywamy zbiór zło\
ony z tych i tylko tych
zdarzeń elementarnych, które nale\
ą zarówno do A, jak i do B. Oznaczamy to:
3
A B
A )" B
Uogólnienie iloczynu na n zdarzeń:
n
C = A1 )" A2 )"... )" An =
IAi
i =1
Przykład:
Rzut kostkÄ…:
{2,4,6} - zdarzenie polegajÄ…ce na wyrzuceniu parzystej liczby oczek,
{4,5,6} - zdarzenie polegające na wyrzuceniu więcej ni\
3-ch oczek.
Iloczyn tych dwóch zdarzeń, to: {4,6}.
4. Ró\
nicą dwóch zdarzeń losowych A oraz B nazywamy zbiór zło\
ony z tych i tylko tych zdarzeń
elementarnych, które nale\
Ä… do zdarzenia A i nie nale\
Ä… do zdarzenia B. Oznaczamy:
A B
A \ B
A - B lub
5. Zdarzenie przeciwne do zdarzenia A ( dopełnienie zdarzenia A )  nazywamy zdarzenie obejmujące te
wszystkie zdarzenia elementarne, które nie nale\
Ä… do zdarzenia A. Oznaczamy:
A A
A = &! - A
Przykład:
Dopełnieniem zdarzenia polegającego na wyrzuceniu parzystej liczby oczek: {2,4,6} jest zdarzenie
polegajÄ…ce na wyrzuceniu nieparzystej liczby oczek: {1,3,5}.
6. Zdarzenia rozłączne (wykluczające się) A i B je\
eli ich iloczyn jest zdarzeniem niemo\
liwym, czyli:
A )" B = "
A
7. Liczność zbioru A ( moc zdarzenia A ), oznaczamy: Card A lub .
Związki między wprowadzonymi działaniami na zdarzeniach
1. A *" A = &! - suma zdarzenia i jego dopełnienia jest zdarzeniem pewnym,
2. A )" A = - zajście zdarzenia A wyklucza zajście zdarzenia . Iloczyn zdarzenia i jego
" A
A
dopełnienia jest zdarzeniem niemo\
liwym. Zdarzenie A i jego dopełnienie są zdarzeniami rozłącznymi,
3. A *" A = A - suma dowolnego zdarzenia z samym sobą jest równowa\
na zajściu tego zdarzenia,
4
4. A )" A = A - iloczyn dowolnego zdarzenia z samym sobą jest równowa\
ny temu zdarzeniu,
(A) = A - dopełnienie dopełnienia dowolnego zdarzenia jest równowa\
ne temu zdarzeniu,
5.
A
6. - B = A )" B - ró\
nica dwóch zdarzeń jest równa iloczynowi jednego ze zdarzeń i dopełnienia
drugiego zdarzenia.
7. A *" B = B *" A
8. A )" B = B )" A
A *" 0 = A
9.
A )" 0 = 0
10.
(A *" B) *" C = A *" (B *" C)
11.
(A )" B) )" C = A )" (B )" C)
12.
(A *" B) )" C = (A )" C) *" (B )" C)
13. - prawo rozdzielności mno\
enia wzgl. dodawania
(A )" B) *" C = (A *" C) )" (B *" C)
14. - prawo rozdzielności dodawania wzgl. mno\
enia
15. A = B - równość zdarzeń
2n
16. Jeśli zbiór A ma n elementów, to ma podzbiorów.
Prawa de Morgana:
1. A *" B = A )" B - dopełnienie sumy zdarzeń jest równe iloczynowi dopełnień tych zdarzeń,
2. A )" B = A *" B - dopełnienie iloczynu zdarzeń jest równe sumie dopełnień tych zdarzeń.
Po omówieniu relacji i działań na zdarzeniach losowych powróćmy do problemu, jakie podzbiory
przestrzeni &! będziemy nazywać zdarzeniami losowymi.
Rozwa\
my 2 przypadki:
A. Zdarzenia losowe w skończonej przestrzeni zdarzeń elementarnych &!
Jeśli &!  zawiera skończoną liczbę elementów, to jako rodzinę S przyjmujemy rodzinę wszystkich
podzbiorów przestrzeni zdarzeń elementarnych &!, czyli dowolny podzbiór jest zdarzeniem losowym.
Przykład:
Na egzaminie student uzyskuje jedną z 4-ch ocen: 2, 3, 4, 5. Określić przestrzeń zdarzeń elementarnych
i wypisać wszystkie zdarzenia losowe występujące przy zdawaniu egzaminu.
Ék
SÄ… 4 zdarzenia elementarne. Niech: - zdarzenie otrzymania oceny.
Przestrzeń zdarzeń elementarnych: &!={ 2, 3, 4, 5 }.
Wszystkich mo\
liwych zdarzeń losowych jest: 24 =16.
Rodzina S
k Zdarzenia losowe k- elementowe Liczba zdarzeń losowych k- elem.
0 1
zdarzenie niemo\
liwe "
1 {2}, {3}, {4}, {5} 4
2 {2,3},{2,4},{2,5},{3,4},{3,5},{4,5} 6
3 {2,3,4},{2,3,5},{2,4,5},{3,4,5} 4
4 {2,3,4,5}  zdarzenie pewne &! 1
Suma zdarzeń: 16
Zdarzenie niemo\
liwe - student nie otrzymał \
adnej oceny ( k=0 ),
{3,4,5} - student zdał,
5
{4,5} - student otrzymał ocenę co najmniej dobrą.
É1,É2,...,Én
2n
Ogólnie: jeśli: &! = { } jest zbiorem n  elementowym, to zdarzeń losowych jest: : są to
podzbiory: 0-elementowe, 1- elementowe, ... ,k  elementowe, ... , n- elementowe.
n
ëÅ‚ öÅ‚
Zdarzeń k- elementowych jest: .
ìÅ‚ ÷Å‚, k = 0,1,..., n
ìÅ‚ ÷Å‚
k
íÅ‚ Å‚Å‚
B. Zdarzenia losowe w n- wymiarowej przestrzeni euklidesowej
!n
Niech przestrzenią zdarzeń elementarnych &! będzie n- wymiarowa przestrzeń euklidesowa lub jej
podzbiór. Oznaczmy przez S* - rodzinę podzbiorów przestrzeni &!, spełniającą następujące warunki:
&! " S*
1. ,
A" S* &! - A" S*
2. Jeśli , to ,
"
" S* .
A1 " S*, A2 " S*,...,
3. Jeśli to UAi
i=1
Rodzinę zbiorów S* nazywamy przeliczalnie addytywnym ciałem zdarzeń.
Niech S  oznacza najmniejsze przeliczalnie addytywne ciało zdarzeń, zawierające wszystkie zbiory
otwarte; takie ciało nazywamy ciałem zbiorów borelowskich, a jego elementy zbiorami borelowskimi.
Czyli zdarzenia losowe sÄ… to zbiory borelowskie.
ReasumujÄ…c:
- jeśli &! jest zbiorem przeliczalnym, to S składa się ze wszystkich podzbiorów &!,
- jeÅ›li &! jest zbiorem nieprzeliczalnym, to S jest pewnÄ… rodzinÄ… podzbiorów &!, zwanÄ… Ã- ciaÅ‚em
zdarzeń, spełniającą powy\
sze 3 warunki.
Elementy kombinatoryki
Kombinatoryka jest działem matematyki, który zajmuje się ró\
norodnymi zestawieniami elementów.
Termin ten pochodzi z pracy G. W. Leibniza (1646-1716) "Dissertatio de arte combinatoria" (Rozprawa o
sztuce kombinacji), która została wydana w 1666 roku.
Początki kombinatoryki spotykamy w pracach arabskich matematyków z przełomu X i XI wieku, natomiast ju\

Arystoteles rozwa\
ał ustawienia liter alfabetu.
Wzory na liczbę permutacji oraz wariacji zostały podane w XIII wieku.
Prace "De ludo aleae" (O grze w kości) G. Cardano (1564-1643) oraz "Consideratione sopra il guioco dei
dadi" (Rozwa\
ania nad grą w kości) Galileusza (1564-1642) zapoczątkowały rozwój kombinatoryki.
Kombinatoryka jest gałęzią wiedzy, zajmującą się zestawieniami, czyli grupami utworzonymi z danej grupy
przedmiotów zwanych elementami. Mówiąc dokładniej, kombinatoryka odpowiada na pytanie, ile da się
zbudować zestawień określonego rodzaju z dostępnych elementów.
Pojęcie zestawienia nie jest formalnie definiowane; nie nale\
y go te\
uto\
samiać z pojęciem zbioru, znanym z
innych dziedzin matematyki. W literaturze polskiej rozró\
nia się na ogół 3 rodzaje zestawień: permutacje,
wariacje i kombinacje. Tak oto przedstawiają się te pojęcia w klasycznym rozumieniu ( zob. np. J. Królikowski,
C. Steckiewicz: Matematyka. Wzory, definicje i tablice ).
Permutacje to zestawienia spełniające dwa następujące warunki:
" ka\
da permutacja obejmuje wszystkie dane elementy,
" istotna jest tylko kolejność elementów permutacji.
6
Z trzech danych elementów: a, b, c, mo\
na utworzyć następujące permutacje: {a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a}.
Wariacje to zestawienia spełniające dwa następujące warunki:
" obejmują jedynie określoną liczbę k spośród danych n elementów (mniejszą ni\
liczba elementów
danych, k < n, zob. jednak ni\
ej),
" istotna jest kolejność elementów wariacji.
Z trzech danych elementów: a, b, c, mo\
na utworzyć następujące dwuelementowe wariacje: {a, b}, {a, c}, {b, a}, {b, c}, {c, a}, {c, b}.
Kombinacje to zestawienia spełniające dwa następujące warunki:
" obejmują jedynie określoną liczbę k spośród danych n elementów (mniejszą ni\
liczba elementów
danych, k < n),
" nie jest istotna kolejność elementów kombinacji.
Z trzech danych elementów: a, b, c, mo\
na utworzyć następujące dwuelementowe kombinacje: {a, b}, {a, c}, {b, c}.
Zdefiniowane powy\
ej pojęcia mo\
na równie\
rozszerzyć na przypadki, gdy brane są pod uwagę powtórzenia
elementów. W przypadku permutacji rozpatrujemy przypadki, gdy ilość powtórzeń danego elementu jest ściśle
określona. A zatem, je\
eli spośród elementów: a, b i c, element a wez
miemy dwa razy, element b jeden raz i
element c jeden raz, mo\
emy utworzyć następujące permutacje z powtórzeniami:
{a, a, b, c}, {a, a, c, b}, {a, b, a, c}, {a, b, c, a}, {a, c, a, b}, {a, c, b, a}, {b, a, a, c}, {b, a, c, a}, {b, c, a, a}, {c,
a, a, b}, {c, a, b, a}, {c, b, a, a}.
Z trzech danych elementów: a, b, c, mo\
na utworzyć następujące dwuelementowe wariacje z powtórzeniami:
{a, a}, {a, b}, {a, c}, {b, a}, {b, b}, {b, c}, {c, a}, {c, b}, {c, c}. Zwróćmy uwagę, \
e ilość elementów wariacji
z powtórzeniami mo\
e być równa całkowitej ilości elementów, a nawet od niej większa.
Z podanych trzech elementów mo\
emy więc tworzyć wariacje z powtórzeniami trójelementowe: {a, a, a}, {a, a,
b}, & , a tak\
e np. czteroelementowe: {a, a, a, a}, {a, a, a, b}, itd.
Z trzech danych elementów: a, b, c, mo\
na utworzyć następujące dwuelementowe kombinacje z
powtórzeniami: {a, a}, {a, b}, {a, c}, {b, b}, {b, c}, {c, c}.
Równie\
i w wypadku kombinacji z powtórzeniami odpada warunek, \
e ilość elementów tworzących
kombinację musi być mniejsza ni\
całkowita dostępna ilość elementów (np. z trzech elementów mo\
emy
tworzyć kombinacje dziesięcioelementowe).
Współczesne podręczniki często definiują powy\
sze pojęcia kombinatoryki przy pomocy pojęć  zbiór i
 ciąg , jednak takie podejście nie wydaje się najlepsze, z co najmniej dwóch powodów, o czym ni\
ej. Najpierw
jednak zastanówmy się, czym są zbiory i ciągi.
Zbiór i element to pojęcia pierwotne. Nie mo\
emy podać tu definicji zbioru, mimo to mo\
emy podać dwie cechy zbioru:
" w zbiorze kolejność elementów nie jest istotna,
" zbiór nie zawiera dwóch identycznych elementów,
to znaczy ka\
dy element traktujemy tak, jakby występował tylko jeden raz. Zauwa\
my, \
e kombinacje bez powtórzeń są zbiorami.
Multizbiór ró\
ni siÄ™ z kolei tym od zbioru, \
e mo\
e zawierać elementy identyczne, a więc innymi słowy, ka\
dy
z ró\
nych elementów multizbioru mo\
e występować więcej ni\
jeden raz. Zauwa\
my, \
e kombinacje z
powtórzeniami są multizbiorami. Skoro kombinacje z powtórzeniami nie są zbiorami, lecz multizbiorami,
rezygnowanie w definicji kombinacji z pojęcia  zestawienie i zastępowanie go pojęciem  zbiór nie jest
najszczęśliwszym rozwiązaniem.
7
CiÄ…g definiuje siÄ™ formalnie jako funkcjÄ™ na danym zborze, mo\
na te\
określić ciąg jako  zbiór
uporządkowany (takie określenie jest jednak nieścisłe, bo ciąg nie jest zbiorem, por. jednak  a sequence is an
ordered set of mathematical objects  tutaj). Intuicyjnie przez ciÄ…g nale\
y rozumieć obiekt podobny do zbioru,
w którym  elementy (zwane tu wyrazami) uło\
one sÄ… po kolei. CiÄ…g mo\
e zawierać wyrazy identyczne lub
nie.
Zauwa\
my, \
e permutacje i wariacje są ciągami. Permutacje i wariacje bez powtórzeń są ciągami nie
zawierającymi wyrazów identycznych. Permutacje i wariacje z powtórzeniami są ciągami zawierającymi
wyrazy identyczne.
Zauwa\
my, \
e elementy, z których tworzyć będziemy zestawienia (permutacje, wariacje, kombinacje) bez
powtórzeń, pobieramy zawsze (bez zwracania) z jakiegoś zbioru.
Elementy, z których tworzyć będziemy zestawienia z powtórzeniami, pobieramy z jakiegoś multizbioru (w
przypadku wariacji i kombinacji mo\
emy pobierać ze zbioru, zwracając pobrane elementy; w przypadku
permutacji z powtórzeniami nie jest to mo\
liwe). Jest to drugi powód, dla którego opieranie definicji
poszczególnych rodzajów zestawień na pojęciu zbioru, nie jest najszczęśliwsze.
Permutacje określane są te\
jako przestawienia, wariacje jako przemiany albo rozmieszczenia,
kombinacje jako połączenia.
Najbardziej elementarną metodą kombinatoryki, często stosowaną intuicyjnie jest reguła mno\
enia i
dodawania. Mo\
emy ją sformułować w następujący sposób.
Je\
eli mamy k mo\
liwości wykonania jednej operacji oraz l mo\
liwości wykonania drugiej, to wykonując:
- jednÄ… operacjÄ™ i drugÄ… mamy k * l mo\
liwości;
- jednÄ… operacjÄ™ albo drugÄ… mamy k + l mo\
liwości.
Oczywiście w przypadku większej liczby operacji wykorzystujemy regułę mno\
enia i dodawania wielokrotnie.
Zastosowanie reguły dodawania i mno\
enia ilustruje następujący przykład:
Przykład
Dziewczyna wybierajÄ…c siÄ™ na dyskotekÄ™ mo\
e wybrać bluzkę spośród czterech oraz spódnicę, których
ma trzy albo spodnie, których ma pięć. Ile wariantów ubioru ma do dyspozycji ?
RozwiÄ…zanie
W przykładzie wykonujemy trzy operacje: wybór bluzki (operacja 1 ), wybór spódnicy (operacja 2 )
oraz wybór spodni (operacja 3 ). Nietrudno zauwa\
yć, \
e operacje te mo\
na połączyć następująco:
operacja 1 i (operacja 2 albo operacja 3)
Stosując regułę mno\
enia i dodawania, otrzymamy, \
e liczba wariantów ubioru będzie wynosić:
4 * ( 3 + 5 ) = 4 * 8 = 32
Stosując w odpowiedni sposób regułę mno\
enia i dodawania bez trudności mo\
na określić inne podstawowe
pojęcia kombinatoryki.
Permutacje bez powtórzeń
Często spotykamy się z sytuacją, gdy musimy elementy pewnego zbioru ustawić w określonej kolejności.
Rozwa\
my prosty przykład:
8
Przykład
Trzy osoby wybierają nagrody (ró\
ne) w konkursie w kolejności według zajętych miejsc. Na ile
sposobów mogą to zrobić?
RozwiÄ…zanie
Pierwsza osoba ma trzy mo\
liwości, druga ju\
tylko dwie (jedną z nagród wybrała ju\
pierwsza osoba),
a trzecia tylko jednÄ…. Poniewa\
nagrodÄ™ wybiera pierwsza osoba i druga, jak i trzecia, to do obliczenia
liczby mo\
liwych wariantów stosujemy regułę mno\
enia i otrzymujemy, \
e nagrody mogą być wybrane
na: 3 * 2 * 1 sposobów.
RozumujÄ…c analogicznie dochodzimy do wniosku, \
e gdy mamy ustawić w określonej kolejności elementy
-elementowego zestawienia, to liczba mo\
liwych wariantów będzie wynosić:
n * (n-1)*...* 2* 1 = n!
Definicja
Permutacją bez powtórzeń zestawienia skończonego nazywamy ka\
de ustawienie wszystkich jego
elementów w określonej kolejności. Dwie permutacje uwa\
amy za ró\
ne, gdy przynajmniej dwa
elementy występują w nich na ró\
nych miejscach.
Liczbę permutacji zestawienia n- elementowego obliczamy według wzoru:
Pn =n!
Permutacje z powtórzeniami
Jeśli zestawienie X składa się z n elementów podzielonych na k grup, gdzie liczby elementów w
poszczególnych grupach wynoszą odpowiednio:
n1, n2, n3, n4, ..., nk i n1 + n2 + n3 +...+ nk = n
to liczba permutacji tego zestawienia wynosi:
n !
Pnn1,n2....nk = n !*n2 !*...*n k !
1
Przykład
Ile jest 3- elementowych permutacji elementów a i b , w których element a powtarza się 2 razy?
RozwiÄ…zanie
3 - elementowe permutacje tych elementów, to: ( a, a, b ) , ( b, a, a ), ( a, b, a )
Ilość tych permutacji, to:
3!
P31,2 = = 3
1!*2!
Wariacje bez powtórzeń
Następnym problemem kombinatorycznym, które pojawia się w naturalny sposób jest ustawianie w określonej
kolejności elementów zestawienia, ale niekoniecznie wszystkich. Przykładem mo\
e być losowanie, w którym
elementy zestawienia losujemy bez zwracania (bez powtórzeń) i kolejność wylosowanych elementów jest
istotna. Rozwa\
my następujący przykład:
9
Przykład
Pan X ma wybrać kod PIN zło\
ony z czterech nie powtarzajÄ…cych siÄ™ cyfr. Ile ma mo\
liwości?
RozwiÄ…zanie
PierwszÄ… cyfrÄ™ mo\
e wybrać na dziesięć sposobów, drugą ju\
tylko na dziewięć (cyfry nie mogą się
powtarzać), trzecią na osiem i czwartą na siedem. Poniewa\
wybiera pierwszÄ… i drugÄ… i trzeciÄ… i czwartÄ…
cyfrę, to stosując regułę mno\
enia otrzymujemy, \
e pan X ma 10 * 9 * 8 * 7 mo\
liwości.
Ten iloczyn mo\
na uzupełnić do następującej postaci:
10 * 9 * 8 * 7 * 6 * ... * 2 * 1 10! 10!
10 * 9 * 8 * 7 = = =
6 * 5 * ... * 2 * 1 6! (10 - 4)!
Widzimy więc, \
e liczbÄ™ wszystkich permutacji zbioru 10-elementowego nale\
y podzielić przez liczbę
permutacji zbioru ( 10  4 )-elementowego.
Definicja
Wariacją bez powtórzeń k- elementów z zestawienia n- elementowego nazywamy ka\
de ustawienie w
określonej kolejności k nie powtarzających się elementów wybranych z zestawienia n- elementowego,
przy czym 1 d" k d" n .
Liczbę wariacji bez powtórzeń k - elementowych wybranych z zestawienia n- elementowego oznaczamy
symbolem i obliczamy ze wzoru:
Vnk
n!
Vnk =
(n - k )!
Zauwa\
my, \
e gdy k = n to wariacja bez powtórzeń staje się permutacją i oczywiście:
n! n!
Vnn = = = n! = Pn
(n - n )! 0!
Wariacje z powtórzeniami
W tym momencie pojawia siÄ™ pytanie, jak mo\
na wyrazić liczbę wariantów gdy elementy zestawienia
ustawiane w określonej kolejności mogą się powtarzać. Proste zastosowanie reguły mno\
enia daje natychmiast
odpowiedz
. Rozwa\
my przykład:
Przykład
Pan X wybierajÄ…c kod PIN mo\
e powtarzać cyfry. Ile ma mo\
liwości?
RozwiÄ…zanie
WybierajÄ…c pierwszÄ… cyfrÄ™ ma 10 mo\
liwości, wybierając drugą nadal ma 10 mo\
liwości, podobnie jest
z trzecią i czwartą cyfrą. Stosując regułę mno\
enia Å‚atwo obliczymy, \
e liczba mo\
liwych wariantów
wynosi:
10 * 10 * 10 * 10 = 104
10
Definicja
Wariacją z powtórzeniami k- elementów z zestawienia n- elementowego nazywamy ka\
de ustawienie
w określonej kolejności k elementów mogących się powtarzać wybranych z zestawienia
n- elementowego.
Liczbę wariacji z powtórzeniami k- elementowych wybranych z zestawienia n - elementowego oznaczamy
k
W
symbolem i obliczamy ze wzoru:
n
k k
W = n
n
Kombinacje bez powtórzeń
We wszystkich dotychczasowych rozwa\
aniach zakładaliśmy, \
e kolejność elementów jest istotna. W wielu
przypadkach jednak tak nie jest, wystarczy rozwa\
yć choćby losowanie Du\
ego Lotka. Nie interesuje nas czy
skreślona na kuponie liczba zostanie wylosowana jako pierwsza, czwarta czy te\
szósta. Wa\
ne jest jedynie to,
czy wybrana przez nas liczba znajdzie siÄ™ w zbiorze wylosowanych liczb. StÄ…d w kombinatoryce pojawia siÄ™
kolejne pojęcie, które zilustrujemy następującym przykładem:
Przykład
Z grupy dziewięciu osób mamy wybrać czteroosobową delegację. Na ile sposobów mo\
emy to zrobić?
RozwiÄ…zanie
Na początek obliczmy na ile sposobów mo\
na wybrać delegacje w sytuacji gdy kolejność wyboru jest
9!
istotna. Mo\
na to oczywiście zrobić na sposobów - jest to liczba wariacji
V94 =
(9 - 4 )!
czteroelementowych z zestawienia dziewięcioelementowego. Jednak nas kolejność wyboru tych
czterech osób nie interesuje, zatem niepotrzebnie uwzględniliśmy liczbę ustawień czterech osób w
określonej kolejności. Liczba takich ustawień wynosi P4 = 4! , dlatego ostateczna liczba mo\
liwych
wyborów będzie równa:
V94 9! 9! 9 * 8 * 7 * 6 * 5!
= = = = 126
P4 4!*( 9 - 4)! 4!* 5! 4 * 3 * 2 * 1 * 5!
Definicja
Kombinacją bez powtórzeń k- elementową z zestawienia n- elementowego nazywamy ka\
dy wybór
podzbioru k- elementowego spośród elementów zestawienia n- elementowego, przy czym 0 d" k d" n .
Liczbę kombinacji bez powtórzeń k- elementowych wybranych z zestawienia n- elementowego oznaczamy
k
symbolem C i obliczamy ze wzoru:
n
n
ëÅ‚ öÅ‚ n!
k
C = ìÅ‚ ÷Å‚ =
n
ìÅ‚ ÷Å‚
k k!(n - k )!
íÅ‚ Å‚Å‚
11
Kombinacje z powtórzeniami
Definicja
Kombinacją z powtórzeniami k- elementową z zestawienia n- elementowego A nazywamy
zestawienia zło\
one z ró\
nych lub nie ró\
niących się elementów zestawienia A . Ich liczba wynosi:
(n + k -1)!
n +k -1
Cnk = ( )=
k
k!(n -1)!
Przykład
Kości do gry w domino są oznaczone dwoma liczbami. Ile ró\
nych kości mo\
na utworzyć z liczb 0, 1,
2, 3, 4, 5, 6 ?
RozwiÄ…zanie:
Z 7- elementowego zestawienia liczb nale\
y wybierać 2- elementowe podzbiory, w których elementy
mogą się powtarzać a uporządkowanie nie odgrywa roli. Kości jest więc:
(7 + 2 -1)! 8! 6!*7*8
7+2-1
C72 = ( )= = = = 28
2
2!(7 -1)! 2!6! 2*6!
Rozpoznawanie rodzaju zestawień
Właściwości poszczególnych typów zestawień obrazuje tabela:
spośród wyciągamy czy zwracamy? czy notujemy kolejność?
permutacje bez powtórzeń n ró\
nych elementów wszystkie nie tak
permutacje z powtórzeniami n elementów, w tym identyczne wszystkie nie tak
wariacje bez powtórzeń n ró\
nych elementów k elementów, k < n nie tak
wariacje z powtórzeniami n ró\
nych elementów k elementów tak tak
kombinacje bez powtórzeń n ró\
nych elementów k elementów, k < n nie nie
kombinacje z powtórzeniami n ró\
nych elementów k elementów tak nie
Aby ustalić rodzaj zestawień, które będziemy analizować, nale\
y postępować według następującego algorytmu:
a. Ustalamy, czy kolejność elementów w zestawieniach jest istotna, czy te\
nie. Je\
eli nie jest istotna, a zestawienia ró\
nią się tylko składem, mamy
do czynienia z kombinacjami i omijamy punkt b.
b. Ustalamy, czy zestawienia ró\
nią się tylko kolejnością elementów. Je\
eli tak, mamy do czynienia z permutacjami. Je\
eli ró\
niÄ… siÄ™ nie tylko
kolejnością elementów, ale tak\
e składem, nasze zestawienia to wariacje.
c. Ustalamy, czy w zestawieniach elementy powtarzajÄ… siÄ™, czy te\
nie.
Obliczanie ilości zestawień
Ilość zestawień danego typu obliczamy według następujących wzorów:
permutacje wariacje kombinacje
n! n
ëÅ‚ öÅ‚ n!
n
bez powtórzeÅ„ Vnk = C = ìÅ‚ ÷Å‚ = ,0 d" k d" n
Pn = n!
k
ìÅ‚ ÷Å‚
k k!(n - k )!
(n - k)!
íÅ‚ Å‚Å‚
n!
(n + k - 1)!
1
k n -1
z powtórzeniami Pnn ,n2, ...,nk = C = C =
Wnk = nk
n n + k -1
k!(n - 1)!
n1!n2!...nk!
12
Uwagi do wzorów:
" n oznacza ilość elementów, z których tworzymy zestawienie,
" k oznacza ilość elementów w zestawieniu ,
" dla permutacji z powtórzeniami: n1 to ilość powtórzeń elementu pierwszego, n2  elementu drugiego, itd., n
= n1 + n2 + & + nk.
Ilość permutacji z powtórzeniami oznacza się te\
symbolem Pn(n1,n2,& ,nk). W mianowniku mo\
na pominąć
elementy, które występują tylko jeden raz, gdy\
1! = 1, a dzielenie przez 1 nie zmienia wyniku.
Ilość wariacji bez powtórzeń wyra\
a równowa\
ny wzór Vnk = n (n  1) (n  2) & (n  r + 1). W dobie
kalkulatorów z wbudowaną funkcją silnia (n!) wygodniej jest jednak posługiwać się wzorem podanym w
tabeli. Zauwa\
my, \
e istotnie Pn = Vnn, a więc permutacje bez powtórzeń mo\
na uznać za rodzaj wariacji bez
powtórzeń. Jednak ilość permutacji z powtórzeniami wcale nie jest równa ilości wariacji z powtórzeniami.
Dlatego lepiej przyjąć określenie klasyczne, w myśl którego permutacje i wariacje to jednak pojęcia
rozłączne.
Zauwa\
my równie\
, \
e ilość k- elementowych kombinacji bez powtórzeń z n elementów równa jest
stosunkowi liczby k- elementowych wariacji bez powtórzeń z n elementów do liczby permutacji z k:
Cnk = Vnk / Pk
Rozpoznawanie rodzaju zestawień (wersja 2)
13