1
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).
2
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
(3) 5! = 120
,
)...
2
)(
1
(
!
!
n
k
k
k
n
+
+
=
gdzie n > k
Symbol Newtona.
Przyjmijmy następującą definicję symbolu
k
n
(czytamy n nad k) gdzie
k
n
N
k
n
>
∈
,
,
zwanego symbolem
Newtona:
n
k
N
n
k
n
k
n
k
n
≤
≤
∈
−
=
0
,
,
)!
(
!
!
Uwaga:
1
0
=
=
n
n
n
n
k
gdzie
k
n
k
n
k
n
≤
≤
+
=
−
+
1
:
,
1
1
−
=
k
n
n
k
n
n
n
n
n
=
−
=
1
1
n
n
k
k
n
2
0
=
∑
=
Przykłady:
(1)
35
3
2
1
!
4
7
6
5
!
4
!
4
!
3
!
7
3
7
=
⋅
⋅
⋅
⋅
=
=
(2)
1
!
3
!
0
!
3
0
3
=
=
(3)
1
!
0
!
6
!
6
6
6
=
=
(4)
4
!
3
!
1
!
4
1
4
=
=
3
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ądź
literami ze wskaźnikami: A
1
, A
2
,...
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:
B
A
∪
A
B
Oczywiście suma dwóch zdarzeń jest równieŜ zdarzeniem, więc uogólniając ją na n składników,
otrzymamy:
i
n
i
n
A
A
A
A
C
U
1
2
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:
4
B
A
∩
A
B
Uogólnienie iloczynu na n zdarzeń:
i
n
i
n
A
A
A
A
C
I
1
2
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:
B
A
−
lub
B
A \
A
B
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:
=
∩
B
A
∅
7. Liczność zbioru A ( moc zdarzenia A ), oznaczamy: Card A lub
A
.
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
A
. Iloczyn zdarzenia i jego
dopełnienia jest zdarzeniem niemoŜliwym. Zdarzenie A i jego dopełnienie
A
są zdarzeniami rozłącznymi,
3.
A
A
A
=
∪
- suma dowolnego zdarzenia z samym sobą jest równowaŜna zajściu tego zdarzenia,
5
4.
A
A
A
=
∩
- iloczyn dowolnego zdarzenia z samym sobą jest równowaŜny temu zdarzeniu,
5.
A
A
=
)
(
- dopełnienie dopełnienia dowolnego zdarzenia jest równowaŜne temu zdarzeniu,
6.
B
A
B
A
∩
=
−
- 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
∩
=
∩
9.
A
A
=
∪
0
10.
0
0
=
∩
A
11.
)
(
)
(
C
B
A
C
B
A
∪
∪
=
∪
∪
12.
)
(
)
(
C
B
A
C
B
A
∩
∩
=
∩
∩
13.
)
(
)
(
)
(
C
B
C
A
C
B
A
∩
∪
∩
=
∩
∪
- prawo rozdzielności mnoŜenia wzgl. dodawania
14.
)
(
)
(
)
(
C
B
C
A
C
B
A
∪
∩
∪
=
∪
∩
- prawo rozdzielności dodawania wzgl. mnoŜenia
15.
B
A
=
- równość zdarzeń
16. Jeśli zbiór A ma n elementów, to ma
n
2
podzbiorów.
Prawa de Morgana:
1.
B
A
B
A
∩
=
∪
- dopełnienie sumy zdarzeń jest równe iloczynowi dopełnień tych zdarzeń,
2.
B
A
B
A
∪
=
∩
- 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.
Są 4 zdarzenia elementarne. Niech:
k
ω
- zdarzenie otrzymania oceny.
Przestrzeń zdarzeń elementarnych: Ω={ 2, 3, 4, 5 }.
Wszystkich moŜliwych zdarzeń losowych jest: 2
4
=16.
Rodzina S
k Zdarzenia losowe k- elementowe
Liczba zdarzeń losowych k- elem.
0
zdarzenie niemoŜliwe
∅
1
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ł,
6
{4,5} - student otrzymał ocenę co najmniej dobrą.
Ogólnie: jeśli: Ω = {
n
ω
ω
ω
,...,
,
2
1
} jest zbiorem n – elementowym, to zdarzeń losowych jest:
n
2
: są to
podzbiory: 0-elementowe, 1- elementowe, ... ,k – elementowe, ... , n- elementowe.
Zdarzeń k- elementowych jest:
n
k
k
n
,...,
1
,
0
,
=
.
B. Zdarzenia losowe w n- wymiarowej przestrzeni euklidesowej
Niech przestrzenią zdarzeń elementarnych Ω będzie n- wymiarowa przestrzeń euklidesowa
n
ℜ
lub jej
podzbiór. Oznaczmy przez S
*
- rodzinę podzbiorów przestrzeni Ω, spełniającą następujące warunki:
1.
*
S
∈
Ω
,
2. Jeśli
*
S
A
∈
, to
*
S
A
∈
−
Ω
,
3. Jeśli
,...,
,
*
2
*
1
S
A
S
A
∈
∈
to
*
1
S
A
i
i
∈
∞
=
U
.
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.
7
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 weź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.
8
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:
9
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:
P
n
=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:
n
1
, n
2
, n
3
, n
4
, ..., n
k
i n
1
+ n
2
+ n
3
+...+ n
k
= n
to liczba permutacji tego zestawienia wynosi:
P
n
n1,n2....nk
=
n !
n
1
!*n
2
!*...*n
k
!
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
!
2
!*
1
!
3
2
,
1
3
=
=
P
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:
10
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:
)!
4
10
(
!
10
!
6
!
10
1
*
2
*
...
*
5
*
6
1
*
2
*
...
*
6
*
7
*
8
*
9
*
10
7
*
8
*
9
*
10
−
=
=
=
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
n
k
≤
≤
1
.
Liczbę wariacji bez powtórzeń k - elementowych wybranych z zestawienia n- elementowego oznaczamy
symbolem
k
n
V
i obliczamy ze wzoru:
)!
(
!
k
n
n
V
k
n
−
=
ZauwaŜmy, Ŝe gdy k = n to wariacja bez powtórzeń staje się permutacją i oczywiście:
n
n
n
P
n
n
n
n
n
V
=
=
=
−
=
!
!
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
odpowiedź. 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 = 10
4
11
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
symbolem
k
n
W
i obliczamy ze wzoru:
k
k
n
n
W
=
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
istotna. MoŜna to oczywiście zrobić na
)!
4
9
(
!
9
4
9
−
=
V
sposobów - jest to liczba wariacji
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 P
4
= 4! , dlatego ostateczna liczba moŜliwych
wyborów będzie równa:
126
!
5
*
1
*
2
*
3
*
4
!
5
*
6
*
7
*
8
*
9
!
5
!*
4
!
9
)!
4
9
!*(
4
!
9
4
4
9
=
=
=
−
=
P
V
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
n
k
≤
≤
0
.
Liczbę kombinacji bez powtórzeń k- elementowych wybranych z zestawienia n- elementowego oznaczamy
symbolem
k
n
C
i obliczamy ze wzoru:
)!
(
!
!
k
n
k
n
k
n
C
k
n
−
=
=
12
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:
( )
)!
1
(
!
)!
1
(
1
−
−
+
=
=
−
+
n
k
k
n
C
k
n
k
k
n
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:
( )
28
!
6
*
2
8
*
7
!*
6
!
6
!
2
!
8
)!
1
7
(
!
2
)!
1
2
7
(
1
2
7
2
2
7
=
=
=
−
−
+
=
=
−
+
C
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
bez powtórzeń
!
n
P
n
=
)!
(
!
k
n
n
V
k
n
−
=
n
k
k
n
k
n
k
n
C
n
k
≤
≤
−
=
=
0
,
)!
(
!
!
z powtórzeniami
!
!...
!
!
2
1
...,
,
,
2
1
k
n
n
n
n
n
n
n
n
P
k
=
k
k
n
n
W
=
)!
1
(
!
)!
1
(
1
1
−
−
+
=
=
−
−
+
n
k
k
n
C
C
n
k
n
k
n
13
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: n
1
to ilość powtórzeń elementu pierwszego, n
2
– elementu drugiego, itd., n
= n
1
+ n
2
+ … + n
k
.
Ilość permutacji z powtórzeniami oznacza się teŜ symbolem P
n
(n
1
,n
2
,…,n
k
). 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 V
n
k
= 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 P
n
= V
n
n
, 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:
C
n
k
= V
n
k
/ P
k
Rozpoznawanie rodzaju zestawień (wersja 2)