Kombinatoryka

Spis treści

Prezentacja wyników za pomocą drzewa

Elementy kombinatoryki

Kombinatoryka
Silnia Permutacja

Wariacja bez powtórzeń Wariacja z powtórzeniami

Kombinacja

Podstawowe zasady kombinatoryki

Linki, literatura

Kombinatoryka a prawdopodobieństwo

W rachunku prawdopodobieństwa nie zawsze można stosować metodę drzew.

Obliczenia kombinatoryczne w uogólniony sposób pozwalają policzyć możliwe zdarzenia elementarne,
a także liczbę zdarzeń elementarnych będących podzbiorami zdarzeń elementarnych.

Kombinatoryka jest działem matematyki, który pomaga odpowiedzieć na pytania typu:
"ile jest możliwych wyników w rzucie monetą?",
"Na ile sposobów możemy wybrać delegację trzyosobową z klasy 20 osobowej?", itp.

Aby rozwiązać tego typu zadania, często stosuje się wzory na permutacje, , wariacje bez powtórzeń,

wariacje z powtórzeniami, kombinacje.

Do rozwiązania większości zadań często wystarcza reguła mnożenia i wzór na kombinację.

Reguła mnożenia

Reguła mnożenia przydaje się podczas rozwiązywania wielu zadań z kombinatoryki i prawdopodobieństwa.

Przykłady

Przykład

W rzucie monetą 2 razy Ile jest wszystkich wyników tego doświadczenia?

Rozwiązanie:
Możliwe są 2 zdarzenia – może wypaść orzeł O lub reszka R.
Jeśli rzucamy 2 razy monetą to możliwe są wyniki:
W I rzucie: {O, R} – 2 możliwości
W II rzucie: {O, R} – 2 możliwości
Łącznie: są 4 możliwości: 2*2 = 4 à { (O, O), (O, R), (R, O), (R, R)

Analogiczne gdy rzucamy 3 razy monetą to są:

W I rzucie 2 możliwości i w II rzucie 2 możliwości i w III rzucie 2 możliwości

Razem 2*2* 2 = 8 możliwości

W regule mnożenia spójnik „i” zamieniamy zawsze na znak mnożenia

Reguła mnożenia
Jeżeli wynik pewnego doświadczenia losowego zależy od kolejno podejmowanych decyzji,
to liczba wszystkich różnych wyników tych decyzji równa się n₁*n₂* …n_k

jeżeli:
n₁ – liczba możliwości wyborów przy podejmowaniu I decyzji

n₂ - liczba możliwości wyborów przy podejmowaniu II decyzji

….
n_k - liczba możliwości wyborów przy podejmowaniu k-tej decyzji, czyli decyzji ostatniej

Przykład:
Ze zbiorów A1 = {3, 5, 7}, A2 = {1, 2}, A3 = {4, 6} wybieramy kolejno po jednej cyfrze i tworzymy
liczbę 3-cyfrową. Pierwszą cyfrę wybieramy ze zbioru A1, drugą z A2, trzecią ze zbioru A3.

Ilość możliwych zdarzeń elementarnych tego doświadczenia: |Ω| = 3*2*2 = 12

Ω = {314, 316, 324, 326, 514, 516, 524, 526, 714, 716, 724, 726}

Ilość liczb, których cyfra setek jest cyfra 3 lub cyfra 7: |A| = 1*2*2 + 1*2**2
Liczby: 314, 316, 324, 326, 714, 716, 724, 726

Reguła mnożenia

Jeżeli zbiór A ma m elementów, a zbiór B ma n elementów, to liczba różnych par (x, y),
takich, że x ∈ A oraz y ∈ B, jest równa m*n

Przykład 1:

Rzucamy 2 monetami: 2-złotówkową i 5-złotówkową:

Oznaczenia:
o – otrzymanie orła na monecie 2-zł, r – reszki na monecie 2 zł

O - otrzymanie orła na monecie 5-zł, R – reszki na monecie 5 zł

Możliwe wyniki doświadczenia: oO, oR, rO, rR

Ilość zderzeń (par) = 2*2 = 4

Przykład 2:

Rzucamy 2 sześciennymi kostkami do gry: niebieską i czarną.

Możliwe wyniki:

1 1 2 1 3 1 4 1 5 1 6 1

1 2 2 2 3 2 4 3 5 2 6 2

…

1 6 2 6 3 6 4 6 5 6 6 6

Liczba zdarzeń: 6 * 6 = 36 (rozróżniamy wyniki takie jak 2 3 i 3 2)

Przykład 3:

Ile jest punktów płaszczyzny, których pierwsza współrzędna x należy do zbioru: A = {1, 2, 3, 4, 5},
a druga do zbioru B = {1, 2, 3}?

|A| = 5, |B| = 3, |A|*|B| = 5*3 = 15

Reguła mnożenia sformułowana bardziej ogólnie

Jeżeli pewien wybór polega na podjęciu n decyzji,
przy czym
decyzję pierwszą można podjąć na k₁ sposobów,
drugą na k₂ sposobów, …,
n-tą na k_n sposobów,
to takiego wyboru można dokonać na
k₁*k₂*…*k_n sposobów

Przykład

Ile może być numerów rejestracyjnych mających na początku 2 litery, a następnie 5 cyfr,
jeśli mogą w nich występować tylko litery WA oraz cyfry 1, 4, 6, 8 (litery i cyfry mogą się powtarzać)?

2 pozycje na litery, na każdej 2 możliwości: 2*2 = 2²,
5 pozycji ma cyfry, na każdej 4 możliwości: 4*4*4*4*4 = 4⁵ =

Ilość numerów: 2*2*4*4*4*4 *4 = 2^2 * 4^5 = 4*1024 = 4096

Zasada mnożenia

Jeśli wybór zależy od podjęcia kolejno n decyzji, przy czym podejmując
pierwszą decyzję, mamy d₁ możliwości,
drugą d₂ możliwości, …
podejmując n-tą decyzję mamy d_nmożliwości,
to wybór ten może być dokonany na
d₁ * d₂ * … d_n sposobów

Przykład:

Mamy 2 długopisy i 3 ołówki.
Na ile sposobów można wybrać zestaw złożony z długopisu i ołówka?
Zasada mnożenia:

Długopis można wybrać na 2 sposoby, ołówek na 3 sposoby.
Zestaw można wybrać na 2*3 = 6 sposobów

Zasada dodawania

Jeżeli wybór polega na podjęciu jednej z n decyzji, przy czym podejmując tę decyzję,
mamy odpowiednio d1, d2, … dn możliwości, to wybór ten może być dokonany na
d₁+ d₂ + … d_n sposobów

Przykład:
Ile różnych wyrazów jednoliterowych lub dwuliterowych można utworzyć z wyrazu „kok”?

Zasada dodawania:

Wyrazy jednoliterowe: k, o – 2 wyrazy

Wyrazy 2-literowe: ko, ok., kk – 3 wyrazy

Liczba wszystkich wyrazów: 2 + 3 = 5

Reguła dodawania

Jeśli zbiory A i B są rozłączne, to liczba elementów zbioru A ∪ B
równa się sumie liczby elementów zbioru A i liczby elementów zbioru B

Jeśli zbiory A i B są rozłączne to |A ∪ B| = |A| + |B|

Przykład

Rzucamy 4 razy kostką i otrzymane liczby oczek zapisujemy jako kolejne cyfry liczby 4-cyfrowej.

Ile można w ten sposób otrzymać liczb, których suma cyfr jest równa 6?

Suma cyfr może być równa 6 w 2 przypadkach:

A. W zapisie liczby występuje trzy razy cyfra 1 oraz jeden raz cyfra 3. Są 4 takie liczby
1113, 1131, 1311, 3111

B. W zapisie występują dwa razy cyfra 2 i dwa razy cyfra 1 Jest 6 takich liczb:
1122, 1212, 2112, 2121, 2211

Razem jest: 4 + 6 = 10

Jeżeli obliczając liczbę możliwych wyników doświadczenia losowego,
w toku rozumowania używamy spójnika:

i - to w obliczeniach wykonujemy mnożenie

lub - to w obliczeniach wykonujemy dodawanie

Prezentacja wyników za pomocą drzewa

Przykład

Rzucono kostką i monetą. Przyjmujemy, że wynikiem doświadczenia jest para (a, b),
gdzie a jest liczbą oczek na kostce, zaś b – orłem lub reszką.
Ile jest możliwych wyników takiego doświadczenia?

Obliczanie liczby oczekiwanych wyników zdarzenia losowego – przykłady

Liczbę oczekiwanych wyników można zliczać różnymi metodami, m. innymi:
- za pomocą grafu

- przez wypisanie wszystkich wyników

- za pomocą tabeli

- poprzez stosowanie reguły mnożenia i reguły dodawania

Przykład

a) Na ile sposobów 3 osoby mogą stanąć w rzędzie lub usiąść na ławce mieszczącej 3 osoby?

Pierwsza osoba ma wybór 3 miejsc, druga ma wybór już tylko 2 miejsc,
a trzecia ma tylko wybór jednego, pozostałego miejsca

|A| = 3*2*1 = 6

b) Na ile sposobów 3 osoby mogą usiąść przy okrągłym stole, z ponumerowanymi krzesłami

Analogicznie jak wyżej. Osobie przyporządkowujemy krzesło.
Są 3 osoby i 3 miejsca. |B| = 3*1*1 = 6

bo
Pierwsza osoba ma wybór 3 miejsc, druga ma wybór już tylko 2 miejsc, a trzecia ma tylko wybór jednego, pozostałego miejsca.

c) Na ile sposobów 3 osoby mogą stanąć w koło i złapać się za ręce?

Osobie przyporządkowujemy sąsiadów. Jest 2 sąsiadów, dlatego liczba możliwości jest 2.

(B –> A –><- C –><- B -><- A), (C-><- A –><- B –><- C -><-A)

-> - prawa ręka, <- lewa ręka danej osoby

|C| = 2

Przykład

a) Na ile sposobów 2 osoby mogą usiąść na ławce mieszczącej 3 osoby?
|A| = 3*2 = 6

b) Na ile sposobów 2 osoby usiąść obok siebie na ławce mieszczącej 3 osoby

|A| = 1 + 2 + 1 = 4

c) Na ile sposobów 2 osoby mogą siedzieć na ławce mieszczącej 4 osoby?

d) Na ile sposobów mogą siedzieć 2 osoby obok siebie, na ławce mieszczącej 4 osoby?

Przykład

Spotkało się 4 przyjaciół. Każdy witał się z każdym. Ile było powitań?

Ogólnie: n osób: Ilość powitań: n*(n-1) / 2

Przykład

Pięciu przyjaciół wysłało SMS ’a, każdy każdemu. Ile wysłano SMS -ów?

Każdy z 5 do pozostałych czterech.

5*4 = 120

Ogólnie: n – osób: n*(n-1) możliwości wysłania SMS -ów każdy do kazdego

Przykład

Oblicz ile jest

a) Ile jest wszystkich liczb naturalnych 4-cyfrowych?

TSDJ - tysiące, setki, dziesiątki, jedności

Na 1 miejscu (tysiące) może być 9 cyfr (bez zera), na następnych 10 – cyfry mogą się powtarzać

N = 9*10*10*10 = 9000

lub

N = 10*10*10*10 – 10*10*10 = 10000 – 1000 = 9000

b) Ile jest liczb naturalnych 3-cyfrowych o różnych cyfrach?

SDJ - setki: 9 możliwości, dziesiątki – 10-1 = 9 możliwości, jedności: 9 -1 = 8 możliwości (o 1 mniej)

N = 9*9*8 = 648

c) Ile jest liczb naturalnych 3-cyfrowych parzystych

SDJ – setki: 9, D – 10, J – 5 (cyfry parzyste, czyli: 0, 2, 4, 6, 8)

9*10*5 = 450

lub

(10*10*10 – 10*10) / 2 = (1000-100) / 2= 900/2 = 450 - co druga liczba jest parzysta

d) Ile jest liczb 3-cyfrowych, takich, ze w zapisie 10-nym występuje jedna cyfra nieparzysta
i 2 cyfry parzyste?

Przykład

Ile jest liczb:

a) Ile jest wszystkich liczb naturalnych 5-cyfrowych?

N = 9*10*10*10*10 = 9*10⁴ = 90000

b) Naturalnych 4-cyfrowych, których cyfry są różne?

N = 9*(10-1)*(9-2)*(9-3) = 9*9*8*7 = 4536

c) Liczb naturalnych 4-cyfrowych nieparzystych?

N = 9*10*10*5 = 4500 (cyfry mogą się powtarzać)

d) Liczb naturalnych 3-cyfrowych, w których zapisie występują tylko liczby nieparzyste lub tylko liczby parzyste

N = 5*5*5 + 4*5*5 = 125 + 100 = 125 (125 nieparzystych i 100 parzystych)

Przykład

a) Na ile sposobów można rozmieścić 3 koszule w 4 szufladach?

Każdą z 4 koszul można włożyć do jednej z 4 szuflad – każda ma 4 możliwości rozmieszczenia.
Możliwości rozmieszczenia jest 4*4*4 = 64

b) Na ile sposobów można rozmieścić 4 koszule w 3 szufladach?
Każdą z 4 koszul można włożyć do jednej z 3 szuflad – (każda ma 3 możliwości rozmieszczenia)

N = 3*3*3*3 = 3⁴ = 81

Przykład

Na ile sposobów można rozmieścić

a) 6 czapek w 4 szufladach?

4*4*4*4*4*4 = 4⁶ = 4096 każda czapka ma 4 możliwości, a jest 6 czapek

b) 4 czapki w 6 szufladach?

6*6*6*6 = 6⁴ = 1296 każda czapka ma 6 możliwości, a są 4 czapki

Przykład

W pudełku jest 7 piłeczek ponumerowanych: 1, 3, 4, 5, 6, 7, 9. Wybieramy kolejno 3 razy po jednej piłeczce i z cyfr tworzymy liczbę trzycyfrową.
Pierwsza z wybranych jest cyfrą setek, druga cyfrą dziesiątek, trzecia cyfrą jedności.

a) Ile liczb mniejszych od 645?

b) Ile liczb parzystych?

c) Ile jest liczb podzielnych przez 3

Warunek podzielności przez 3 spełniają trójki cyfr:

1, 3, 5 1, 4, 7 1, 5, 6 1, 5, 9

3, 4, 5 3, 5, 7 3, 6, 9

4, 5, 6 4, 5, 9

5, 6, 7

Takich trójek jest 10.
Z każdej trójki można utworzyć: 3*2*1 = 6 różnych cyfr

Liczb podzielnych przez 3 jest więc: 10*6 = 60

d) Ile jest wszystkich liczb 3-cyfrowych?

|{1, 3, 4, 5, 6, 7, 9} | = 7

S D J |S| = 7, |D| = 6, |J| = 5

|A| = 7*6*5 = 210

e) Ile jest liczb większych od 456?

1) S=4, D = 5, J = {7, 9} à 1*1*2 = 2 możliwości: 457, 459

2) S = 4, |D| = |{6, 7, 9}| = 3, |J| = 5 à 1*3*5 = 15 możliwości

3) S > 4: |S| = |{5, 6, 7, 9}| = 4, |D| =6, |J| = 5 à 4*6*5 = 120

|A| = 1*1*2 1*3*5 + 4*6*5 = 1*(1*2 + 3*5) + 4*6*5 = 137

f) Ile jest liczb podzielnych przez 9

Suma cyfr dzieli się przez 9

1, 3, 5 4, 5, 9 5, 6, 7 1, 9, 8

Takich trójek jest 4.
Z każdej trójki można utworzyć: 3*2*1 = 6 różnych cyfr

Liczb podzielnych przez 9 jest więc: 4*6 = 24

Przykład

Na ile sposobów można z grupy liczącej 10 osób (n=10) wybrać delegację składającą się z:

a) 2 osób (k=2)

Liczba wszystkich możliwości wyboru 2-osobowej delegacji:
wybór I osoby: 10 możliwości (ile liczy grupa)   Ogólnie:   n      możliwości (ile liczy grupa)
wybór II osoby: (10-1) = 9 możliwości                   Ogólnie:   n-1 możliwości
Liczba kolejności w jakiej 2 osoby zostały wybrane
wybór za I razem:   2 możliwości                             Ogólnie: k możliwości (ile liczy delegacja0
wybór za II razem: 1 możliwość                                              Ogólnie: k-1 możliwości
m = 10*9 / (2*1) = 90/2 = 45

b) 3 osób

m = 10*9*8 / (3*2*1) = 120

Przykład

Na ile sposobów można z grupy liczącej 20 osób (n=20) wybrać delegację składającą się z:
a) 2 osób (k=2)

m = n*(n-1)*…(n-k) / (k*(k-1)*(k-2)..*1

m = 20*19 / (2*1) = 190

b) 3 osób

m = 20*19*18 / (3*2*1) = 6840/6 = 1140

c) 4 osób

m = 20*19*18*17 / (4*3*2*1) = 4845

Elementy kombinatoryki

W kombinatoryce rozważa się zależności miedzy elementami zbiorów i wyrazami ciągów.

Zbiór składa się z elementów nieuporządkowanych – np. jabłka w koszyku.

Ciąg zawiera wyrazy uporządkowane – np. każde kolejne jabłko w ponumerowanym od 1 do n pudełku,
każdy uczeń ma numer w dzienniku, w zawodnik sportowy jest oznaczony numerem itp.

Ustawianie wszystkich elementów zbioru w pewnej kolejności

Tworzenie n -wyrazowych ciągów ze wszystkich elementów zbioru n -elementowego

Kolejność wybierania elementów jest istotna!

Liczba wszystkich możliwych ustawień: n*(n-1)*(n-1)*…*2*1 = n!

Przykład:

Na ile sposobów można rozdzielić 3 czekolady c1, c2, c3 pomiędzy 3 osoby?

I osoba ma 3 możliwości otrzymania czekolady: c1, c2, c3. Załóżmy, że dostała c1.

II osoba ma już tylko 2 możliwości, w tym przypadku : c2 i c3. Załóżmy, że dostała c2.

III osoba – pozostała tylko jedna czekolada – jedna możliwość.

Wszystkich możliwości jest 3*2*1 = 3! = 6

Wybieranie k elementów ze zbioru n –elementowego

1. Wybrane elementy nie mogą się powtarzać i kolejność wybranych elementów jest istotna (k<=n)

Tworzenie k – wyrazowych ciągów utworzonych z różnych elementów n – elementowego zbioru
dla k <= n

Liczba wszystkich możliwości wyboru: n*(n-1)*…[n – (k-1)]

Przykład:
Z cyfr 1, 2, 3, 4, 5 wybieramy dwie cyfry i tworzymy z nich liczbę 2-cyfrową.
Ile można utworzyć takich liczb?
Cyfrę jedności można wybrać spośród 5 cyfr na 5 sposobów. Załóżmy, że wybrano 1.
Cyfrę dziesiątek można wybrać z 4 pozostałych cyfr: 2, 3, 4, 5 – cztery sposoby.

Wszystkich możliwości jest: 5*4 = 20

2. Wybrane elementy mogą się powtarzać i kolejność wybranych elementów jest istotna

Tworzenie k – wyrazowych ciągów utworzonych z elementów n – elementowego zbioru ( k <= n)

Liczba wszystkich możliwości wyboru: n*n*n…*n (k razy) = n^k

Przykład:

Ile różnych liczb 4-cyfrowych można utworzyć z cyfr 6, 7, 8?

Cyfrę jedności można wybrać z cyfr 6, 7, 8 na 3 sposoby – są 3 możliwości,
Cyfrę dziesiątek można wybrać spośród cyfr 6, 7, 8, są więc też 3 możliwości (cyfry mogą się powtarzać)

Cyfrę setek można wybrać spośród cyfr 6, 7, 8, są więc też 3 możliwości

Cyfrę tysięcy można wybrać spośród cyfr 6, 7, 8, są więc też 3 możliwości

Wszystkich możliwości jest 3*3*3*3 = 3⁴ = 81

Przykład:

W sklepie są 3 rodzaje czekolad.

a) Na ile sposobów mogą wybrać te czekolady 2 osoby?

b) Ile jest możliwości wyboru przez te osoby (każda niezależnie) tej samej czekolady?

c) Na ile sposobów, k osób (obiektów) może dokonać wyboru
spośród n czekolad (możliwości)?

Wn^k = n^k - wariacje z powtórzeniami

a) n = 3 (czekolady) k = 2 (osoby) n^k = 3² = 9

b) n = 3 (czekolada) k = 1 (osoba) n^k = 3¹ = 3

c) n - ilość czekolad (możliwości), k – ilość osób (obiektów) Wn^k = n^k

3. Wybrane elementy nie mogą się powtarzać i kolejność wybranych elementów nie jest istotna
(k<= n)

Tworzenie k – elementowych podzbiorów zbioru n – elementowego ( k <= n)

Liczba wszystkich możliwości wyboru:

{ n*(n-1)*…[n – (k-1) ] } / [k*(k-1)*…*2*1] = = { n*(n-1)*…[n – (k-1) ] } / k!

Przykład:

Na ile sposobów można wybrać spośród 6 osób delegację 3-osobową?

Pierwszą osobę można wybrać spośród 6 osób – 6 możliwości.
Drugą osobę można wybrać spośród 5 pozostałych osób – 5 możliwości
Trzecią osobę można wybrać spośród 4 pozostałych osób – 4 możliwości

Osoby można wybrać na: 6*5*4 = 120 sposobów.
Ponieważ kolejność wybieranych osób nie jest istotna, wszystkich możliwości jest:
120/3! = 120/6 = 20

Kombinatoryka

Silnia

Pojęcie silni:

0! = 1 1! = 1 n! = 1*2*…*(n-1)*n dla n > 1

Dla liczby naturalnej n > 1 symbol n! (czyt. n silnia)
oznacza iloczyn kolejnych liczb naturalnych od 1 do n

n! = 1*2*3*…*n

n! = 1, gdy n ∈ {0, 1}

n! = (n-1)!*n, gdy n ∈ N \ {0, 1}

Wzór rekurencyjny: 0! = 1, (n+1)! = (n+1)*n!

Symbol Newtona

Czytamy „n po k” lub „n nad k”

Symbol Newtona oznacza liczbę określoną następująco:

= = gdy n ∈ N, k ∈ N i n >= k

Jeśli n ∈ N, k ∈ N i n >= k, to:

= = 1

= = n

Permutacja

Permutacja bez powtórzeń
n –elementowego zbioru – każdy n –wyrazowy ciąg utworzony ze wszystkich elementów tego zbioru.

Permutacjami, przestawieniami albo przemianami n różnych elementów nazywamy ustawienie
w rząd jeden element za drugim tych n elementów, przy czym w każdej permutacji porządek ustawienia jest inny.

Jeśli mamy np. 2 elementy A i B, to możemy z nich utworzyć 2 permutacje: AB i BA (2! = 1*2 = 2).

Jeśli mamy 3 elementy A, B i C to możemy utworzyć 6 permutacji:
ABC ACB BAC BCA CAB CBA (2! = 1*2*3 = 6)

Jeżeli w doświadczeniu losowym ze zbioru n –elementowego wybieramy elementy w ten sposób, że:

- wybieramy n elementów

- istotna jest kolejność wybierania elementów,
to tworzymy ciąg n – wyrazowy, zwany permutacją tego zbioru

Permutacją zbioru n -elementowego {a1, a2, …, an} nazywamy n –wyrazowy ciąg utworzony ze wszystkich elementów tego zbioru.

Permutacja to ustawienie wszystkich elementów zbioru w pewnej kolejności.

Dwie permutacje tego samego zbioru różnią się między sobą co najwyżej kolejnością elementów.

Z permutacjami mamy do czynienia, gdy określamy liczbę wszystkich ciągów,
jakie możemy utworzyć ze wszystkich elementów danego zbioru, którego liczbę oznaczamy przez n.

Liczba wszytkich permutacji zbioru n -elementowego wyraża się wzorem:
P_n = n! gdzie n ∈ N

n! - czytamy n silnia

Permutacja to ustawienie wszystkich elementów zbioru w pewnej kolejności.

Dwie permutacje tego samego zbioru mogą się różnić między sobą co najwyżej kolejnością elementów.

Na przykład zbiór {a, b} ma 2 permutacje: {a, b} i {b, a}

Zbiór A= {a, b, c} ma 6 permutacji: (a, b, c), (b, c, a), (c, a, b), (a, c, b), (b, a, c), (c, b, a)

Liczba P_n permutacji rośnie bardzo szybko wraz ze wzrostem n.

P₂ = 2, P₃ = 6, P₄ = 24, P₅= 120, P₆ = 720 itd.

Przykład:

Na ile sposobów można ustawić w szereg 6 uczniów?

P₆= 6! = 1*2*3*4*5*6 = 720

Przykład

Na ile sposobów można posadzić przy okrągłym stole 5 osób?
P₅ = 5! = 1*2*3*4*5 = 120

Przykład:
Mamy 8 książek o różnokolorowych okładkach na półce. Ile jest możliwości ustawienia tych książek?

Liczba elementów zbioru, z którego tworzymy ciąg: n = 8
P8 = 8! = 1*2*3*4*5*6*7*8 = 40320

Przykład:

Na ile sposobów można ustawić na półce 3 różne książki?
Oznaczmy książki numerami: 1, 2, 3 i wypiszmy wszystkie możliwe ustawienia:
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1.
Trzy książki można utworzyć na 3! sposobów: P₃= 3! = 1*2*3 = 6

Przykład:
Na ile sposobów można ustawić 8 zawodników na 8 pasach startowych bieżni?

P₈ = 8! = 1*2*3*4*5*6*7*8 = 6!*7*8 = 720*56 = 40320

Przykład

a) Na ile sposobów można ustawić w kolejce 3 dziewcząt i 2 chłopców?

3 + 2 = 5

(3+2)! = 5! = 120 – permutacje

b) Co w sytuacji, gdy dziewczęta mają stać przed chłopcami?

Rozpatrujemy w tej sytuacji 2 kolejki: kolejkę dziewcząt i chłopców.

3! = 6 – sposobów ustawienia w kolejce dziewcząt

2! = 2 - sposoby ustawienia w kolejce chłopców

Na podstawie reguły mnożenia: 3! * 2! = 6*2 = 12 ustawień

Permutacje z powtórzeniami – elementy w zbiorze powtarzają się n₁, n₂, … n_k razy
(n₁ + n₂ + … + n_k= n)

Przykład

Jeżeli spośród elementów: a, b i c, element a weźmiemy 2 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}

Ilość permutacji z powtórzeniami:

Pn’ = P_n ^{n1, n2, ... nk} =

Mając dany zbiór n -elementowy permutacją z powtórzeniami elementów zbioru nazywa się każdy ciąg n -wyrazowy,
którego wyrazy występują odpowiednio n₁, n₂, …, n_k razy.

Definicję permutacji z powtórzeniami można opisać następująco:

1) Kolejność elementów jest istotna

2) Elementy powtarzają się z określoną częstotliwością

Przykład
Dane są elementy x, y i z, z czego elementów x i z użyto jeden raz
natomiast elementu y użyto dwa razy. Ile jest permutacji.

n1 = 1, n2 = 2, n3 = 1

Permutacje:

(x, z, y, y), (z, x, y, y), (z, y, x, y), (x, y, z, y), (y, z, x, y), (y, x, z, y),
(y, z, y, x), (y, x, y, z), (y, y, z, x), (y, y, x, z), (z, y, y, x), (x, y, y, z).

Ilość takich permutacji to:

Pn’ = 4! / (1!*2!*1!) = 24/2 = 12

Przykład

Na ile sposobów można ustawić 3 litery: a, a, b?
A = {a, a, b}

Możliwości – permutacje: (aab), (baa), (aba)

n1 = 2, n2 = 1 n = n1+n2 = 2 + 1 = 3

P’ = n!/ n1!*n2!) = 3!/ (2!*1!) = 6 / 2 = 3

Wariacje

Wariacjami albo rozmieszczeniami po k elementów wybranych z n elementów (k <n)
nazywamy takie ustawienie tych k elementów, przy którym w każdej wariacji porządek ustawienia jest inny.

Przykład

Ilość elementów n = 5. Elementami są litery A, B, C, D, E.
Tworzymy z tych 5 liter zespoły (wariacje) dwuliterowe (k=2):

AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC, ED.

Z 5 liter powstało 20 zespołów (wariacji) 2-literowych.

Ilość tych zespołów jest ilością wariacji z 5-ciu elementów po 2.

Ilość wariacji z n elementów po k oznaczamy V_n^k lub A_n^k

Wariacja bez powtórzeń

Wariacja k –wyrazowa bez powtórzeń zbioru n – elementowego – każdy k –wyrazowy ciąg
o różnych wyrazach ze zbioru n –elementowego.

Z wariacją bez powtórzeń mamy do czynienia, gdy tworzymy ciąg z elementów danego zbioru
i ciąg ten nie musi się składać ze wszystkich elementów zbioru.
Np. w zbiorze jest 20 elementów a ciąg jest 5 elementowy.

„Bez powtórzeń” oznacza, że żaden element tworzonego ciągu nie może się powtarzać.
Np. w przypadku losowania kolejnych elementów ciągu, element wylosowany nie wraca so puli – losowanie bez zwracania.

Liczbę elementów zbioru oznaczamy przez n, a liczbę elementów powstałego ciągu przez k.
Ilość wariacji bez powtórzeń, tworzonej ze zbioru n –elementowego, a ciąg tworzony
ma k elementów - oznaczamy przez V_n^k

Liczba wariacji bez powtórzeń:
V_n^k = n*(n-1)*(n-2)*…*(n-k+1) = n! / (n-k)! gdzie n ∈ N⁺, k ∈ N⁺ i k <=n

Jeżeli w doświadczeniu losowym ze zbioru n -elementowego wybieramy k elementów w ten sposób, że:
- wybrane elementy nie mogą się powtarzać

- kolejność wybranych elementów jest istotna

To tworzymy k -wyrazową wariację bez powtórzeń zbioru n – elementowego, gdzie k <=n

Uwaga: W kalkulatorze oznaczenie: nPr = n! / (n-r)!

Każda n –elementowa wariacja bez powtórzeń zbioru n –elementowego jest jego permutacją

Przykład
Ze zbioru {a, b, c} można utworzyć sześć 2-wyrazowych wariacji bez powtórzeń

(a, b), (a, c), (b, c), (b, a), (c, a), (c, b)

n=3, k = 2

V₃ ²= 3*2*1 = 6

V₃ ² = 3!/(3-2)! = 1*2*3 = 6

Przykład:

Pewien kod tworzymy z 3 liter wybranych spośród następujących: A, B, C, D, E, F, G, H,
przy czym litery nie mogą się powtarzać. Ile jest takich kodów?
Na I miejscu można wpisać jedną z 8 liter, na II miejscu jedną z pozostałych 7 liter,
na trzecim jedną z pozostałych sześciu.
V₈³ = 8*7*6 = 8!/ (8-3)! = 8!/5! = 5!*6*7*8/5! = 6*7*8 = 336

Przykład:

A = {a, b, c} – zbiór wyjściowy – n = 3

Dla k = 2
V₃² = 3!/(3-2)! = 3!/1! = 3! = 1*2*3 = 6 {ab, ba, ac, ca, bc, cb}

Przykład

Spośród 25 zawodników zostanie wybranych 3 medalistów. Jaka jest liczba możliwych wyników?

V₂₅³ = 25*24*..(25-3+1) = 25*24*(25-3+1) = 25*24*23 = 13800

V₂₅³ = 25!/(25-3)! = 22!*23*24*25/22! = 23*24*25= 13800

Przykład

Iloma sposobami można wyciągnąć 2 karty z talii złożonej z 52 kart?

V₅₂² = 52!/ (8-2)! = 50!*51*52 / 50! = 51*52 = 2652

Przykład

Iloma sposobami można posadzić na kanapie 2-osobowej rodzinę złożoną z 8 osób?

V82 = 8!/ *8-2)! = 8!/6! = 6!*7*8 / 6! = 56

Przykład:

Pewien kod jest czterocyfrowy i składa się z cyfr 1 do 9, przy czym żadna cyfra nie może się powtarzać.
Liczba elementów zbioru, z którego losujemy elementy wynosi 9 (cyfry 1, 2, 3, 4, 5, 6, 7, 8, 9 – bez 0)

Liczba elementów ciągu wynosi 4 – kod zawiera 4 cyfry: k = 4

|Ω| = V₉⁴ = 9! / (9-4)! = 9!/5! = 5!*6*7*8*9 / 5! = 6*7*8*9 = 3024

Na kalkulatorze naukowym: 9 SHIFT nPr 4 = 3024

Wariacja z powtórzeniami

Wariacja k – wyrazowa z powtórzeniami zbioru n – elementowego – każdy k – wyrazowy ciąg
o wyrazach ze zbioru n – elementowego.
Wariacje z powtórzeniami stosujemy w takich przypadkach jak wariacje bez powtórzeń
ale z tą różnicą, że poszczególne elementy ciągu mogą się powtarzać.

Liczba wszystkich możliwych wariacji z powtórzeniami:
W_n^k = n^kgdzie n∈ N⁺, k ∈ N⁺

Przykład:

Z elementów zbioru {a, b} można utworzyć:
Cztery 2-wyrazowe wariacje z powtórzeniami:

(a, a), (a, b), (b, a), (b, b)
W₂² = 2²= 4

Osiem 3-wyrazowych wariacji z powtórzeniami:

(a, a, a), (a, a, b), (a, b, a), (b, a, a), (b, b, b), (b, b, a), (b, a, b), (a, b, b)

n =2, k = 3
W₂³ = 2³ = 8

Przykład:

A = {a, b, c}, n-3, k=2
W₃² = 3² = 9 Możliwe podzbiory: {ab, ba, ac, ca, bc, cb, aa, bb, cc}

Przykład:
Ile jest wszystkich liczb 3-cyfrowych, w których zapisie występują tylko cyfry 1 i 2?

Na każdej pozycji mogą być 2 cyfry. |1..2 | 1..2 | 1..2|

Każdą z 3 cyfr można wybrać na 2 sposoby,
zatem jest: 2*2*2 = 8 takich liczb (2 cyfry na każdej z 3 pozycji)

{111, 121, 211, 221, 112, 122, 212, 222}
n=2, k=3

W₂³ = 2³ = 8

Przykład

Ile jest wszystkich liczb 3-cyfrowych, w których zapisie występują tylko cyfry 1, 2, 3, 4, 5?

Na każdej pozycji mogą występować cyfry 1, 2, 3, 4, 5 – pięć cyfr.
n =5, k = 3 [1..5][1..5][1..5]

Jest 5*5*5 = 125 takich liczb

W₅³= 5³ = 125

Przykład

Ile pięcioliterowych kodów można utworzyć z liter: A, B, C, D, E, F, G, H, jeśli litery mogą się powtarzać.

n=8, k = 5; Jest kodów: 8*8*8*8*8 (8 na każdej pozycji)

W₈⁵ = 8⁵= 32768

Kombinacja

Kombinacjami albo połączeniami nazywamy takie zespoły po k elementów wybranych
z n elementów, w których te elementy różnią się między sobą wyłącznie jakością.
W kombinacjach nie bierze się pod uwagę porządku ustawienia.
Np. AB i BA to ta sama kombinacja.

Przykład

Elementami są litery: A, B, C, D, E, F.
Tworzymy z nich zespoły 2-literowe, przy czym zakładamy, że nie interesuje nas porządek liter, a tylko ich jakość.

Ilość utworzonych zespołów 2-literowych z danych sześciu liter wynosi 15.
Są to zespoły:
AB AC AD AE AF

BC BD BE BE BF

CD CE CF

DE DF

Ilość kombinacji po k elementów branych z n elementów oznaczamy przez C_n^k

Można zauważyć, że jeśli w każdej kombinacji złożonej z k elementów poprzestawiamy te elementy na wszystkie sposoby,
to otrzymamy wszystkie możliwe wariacje po k elementów wybranych z n elementów.

Ponieważ jedna kombinacja zawiera k elementów, to ilość możliwych przestawień
– permutacji tych k elementów wynosi k!.

Wszystkich kombinacji jest Cn^k *k, zatem ilość wszystkich wariacji z C_n^k kombinacji będzie Cn^k *k!.
Biorąc pod uwagę, że ilość wariacji z n elementów po k wynosi n!/(n-k)!, otrzymujemy:
Cn^k * k! = n! / (n-k)!, stąd

Cn^k = n! / (k!*(n-k)!

Często piszę się symbol C_n^k w postaci (ⁿ _k)

Przykład

Iloma sposobami można wybrać poczet sztandarowy 3-osobowy z 10-ciu żołnierzy?

C₁₀³ = (¹⁰₃) = 10!/(3!*(10-3)! = 10!/(3!*7!) = 120

Przykład

Iloma sposobami można rozdzielić 3 stypendia w całości między 9 kandydatów o tych samych kwalifikacjach?

C₉³ = 9!/(6!*3!) = 84

Kombinacja bez powtórzeń k elementów spośród n elementów (0 <=k <=n)
- każdy k –elementowy podzbiór zbioru n – elementowego.

Jeżeli w doświadczeniu ze zbioru n –elementowego wybieramy k elementów, w ten sposób, że:

- wybrane elementy nie mogą się powtarzać,

- kolejność wybranych elementów nie jest istotna,

To tworzymy k –elementową kombinację zbioru n -elementowego, gdzie k <=n

Przykład

Zbiór {a, b, c, d}

Dla k = 1 (kombinacje 1-elementowe): {a}, {b}, {c}, {d} à jedna kombinacja

Dla k = 2 (kombinacje 2-elementowe): {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d} à 2 kombinacje

Dla k = 3 (kombinacje 3-elementowe): {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d} à 4 kombinacje

Dla k = 4 (kombinacje 4-elementowe): {a, b, c, d} à jedna kombinacja

Liczba kombinacji bez powtórzeń:

C_n^k = = gdy n ∈ N⁺, k ∈ N⁺ i n >= k

C_n^k = = gdy n ∈ N⁺, k ∈ N⁺ i n >= k

C_n^k= nCk = n! / ( k!*(n-k)! )

k!*C_n^k= V_n^kgdzie V_n^k– wariacja k -wyrazowa bez powtórzeń zbioru n - elementowego

Uwaga: W kalkulatorze oznaczenie: nCr = n! / ( r!*(n-r)! )

Przykład

A = {a, b, c} n = 3

Dla k = 2

C₃² = 3!/(2!*(3-2)! = 3!/(2!*1!) = 1*2*3/2 = 3

Możliwe podzbiory: {ab, ac, bc}

Przykład

Z klasy liczącej 19 dziewcząt i 12 chłopców, wybierana jest delegacja, w skład której wchodzą
3 dziewczyny i 2 chłopców. Na ile sposobów można to uczynić?

3 dziewczyny spośród 19 można wybrać na
C₁₉³sposoby = (¹⁹₃) = 19! / (3!*(19-3)! = 16!*17*18*19/6*16!=969

Dwóch chłopców spośród 12 można wybrać na (¹²₂) sposoby = 12!/ (2!*(12-2)!) = 66

(¹⁹₃) * ¹²₂) = 969*66 = 63954 à delegację można wybrać na sposoby

Przykład

W „Dużym Lotku” skreślamy 6 liczb spośród 1.. 49 liczb.

1. Prawdopodobieństwo zdarzenia A, że trafnie skreślimy 3 liczby

|Ω| = C₄₉⁶ = 49! / (6!*43!) = 13 983 816

Trafnie kreślimy 3 liczby, gdy skreślimy 3 spośród wylosowanych przez maszynę losującą
oraz 3 z 43 (49-6), których nie wylosowała maszyna.

|A| = C₆³* C₄₃³ = 20 * 12341 = 246820

P(A) = |A|/|Ω| = 246820/13983816 ≈ 0,18

2. Prawdopodobieństwo trafienia szóstki

P(B) = 1: C₄₉⁶= 1 / 13983816

3. Prawdopodobieństwo trafienia piątki:

(⁶₅) * (^49-6₁) / (⁴⁹₆) = 6 * 43 / 13983816 = 258/13983816 ≈ 1/54201

4. Prawdopodobieństwo trafienia czwórki

C₆⁴ * C_49-6 ¹ / C₄₉ ⁶ = 15545 / 13983816 = 15*903 / 13983816 = 13545 / 13983816 ≈ 1/1032

4. Prawdopodobieństwo trafienia trójki

C₆³ * C_49-6³ / C₄₉ ⁶ = 246820 / 13983816 ≈ 1/ 57

Podstawowe zasady kombinatoryki

Zasada mnożenia

Jeśli I obiekt daje n możliwości a drugi m możliwości, to przy rozpatrywaniu niezależnym tych obiektów,
mamy: n * m możliwości

Przykład: Ile można utworzyć kodów 2-znakowych, w których
- na miejscu I umieszczamy jedną z 20 liter

- na miejscu II jedną z cyfr 1 do 9
Dane: n = 20, m = 9

n * m = 20*9 = 180 Odp. można utworzyć 180 kodów 2-znakowych, przy zadanych warunkach

Jeśli obiektów jest k,
pierwszy stwarza n₁ możliwości, drugi n₂, … ostatni n_k możliwości

I obiekty te możemy rozpatrywać niezależnie, to jest ogółem:

n₁ * n₂ *… * n_k możliwości

Przykład:
Trzy klasy liczą odpowiednio: 20, 30, 25 uczniów.
Ile 3-osobowych delegacji szkoły można utworzyć, biorąc po jednym uczniu z każdej klasy?
k= 3, n1 = 20, n2 = 30, n3 = 25

20*30*25 = 15000 Odp. Można utworzyć 15000 delegacji trzyosobowych.

Jeśli obiektów jest k i każdy z nich ma tyle samo n możliwości,
to ogółem możliwości jest n^k
Wariacje z powtórzeniami: W_n^k = n^k

Przykład:
Sześciu uczniów ma oceny w skali 2 do 5 (1, 3, 4, 5 – 4 oceny). Ile jest możliwości wystawienia ocen?
n = 4 (oceny), k = 6 (uczniowie)

4⁶ = 4096

Pięcioro uczniów ma oceny w skali 1 do 6. Ile jest możliwości wystawienia ocen?
n=6 (oceny), k = 5 (uczniowie)

6⁵ = 7776

Przykład
Oblicz, ile różnych wyników można otrzymać, rzucając 4 razy monetą.
Wyniki rzutów są wybierane ze zbioru 2-elementowego A = {O, R}, |A| = n = 2.

Rzucając 4 razy monetą tworzymy 4-wyrazowe ciągi, więc k = 4.

Liczba wyników jest równa liczbie V_n^k = n^k = 2⁴ = 16

Odp. Można otrzymać 16 różnych wyników.

Przykład

Obsadzanie wolnych miejsc

Jeśli pierwszy obiekt można umieścić na jednym z n miejsc, drugi na jednym z n-1 miejsc,
trzeci na jednym z n-2 miejsc, a k -ty na jednym z n- (k-1) = n-k+1 miejsc,
to liczba możliwych obsadzeń jest równa:
n*(n-1)*(n-2)*…*(n-k+1) – jest k czynników

Przykład

Na ile sposobów można rozsadzić 5 osób na 6 wolnych miejscach?

n=6, k = 5; 6*5*..(6-5+1) = 6*5*...*2 = 6*5*4*3*2
6*5*4*3*2

Ustawianie się w kolejce

n różnych obiektów można ustawić jeden za drugim na

n! = n*(n-1)*(n-2)*…*2*1 = 1*2*3*…(n-1)*n

Przykład

Na ile sposobów można ustawić w kolejce 4 osoby?

4! = 1*2*3*4 = 24

Przykład

Ile jest możliwych kolejności w jakiej dobiegnie na metę 5 zawodników?
5! = 1*2*3*4*5 = 120

Wykluczenie części możliwości

Czasem łatwiej obliczyć w ilu wypadkach warunek nie jest spełniony.
Spełnienie warunku oblicza się wtedy przez odjęcie od ilości wszystkich możliwych zdarzeń elementarnych,
ilości, w których warunek nie jest spełniony (zdarzeń przeciwnych).

|A| = |Ω| - |A’|

Przykład

Przy wyrzuceniu n razy monetą, ile jest przypadków m, w których orzeł wystąpił choć raz?
Ogółem jest 2ⁿ możliwości (ciągów rzutu monetą).
Wśród nich jest tylko jedna możliwość, w których orła nie ma ani razu.
Zatem takich, w których orzeł wystąpił co najmniej jeden raz jest: |A| = m = 2ⁿ – 1.

Dla n = 3 à m = 2³ – 1 = 8 – 1 = 7 (Orła nie ma ani razu w ciągu {RRR} )

Dla n = 6 à m = 2⁶ -1 = 64 -1 = 63 (Orła nie ma ani razu w ciągu {RRRRRR} )

Dla n = 8 à m = 2⁶ -1 = 256 -1 = 255 (Orła nie ma ani razu w ciągu {RRRRRRRR} )

Drzewa stochastyczne – drzewa zdarzeń

W trudniejszych sytuacjach może się przydać narysowanie drzewa.
W drzewie tym wierzchołki rozgałęziają w zależności od rozwoju sytuacji.

Każdej krawędzi odpowiada liczba wskazująca na ile sposobów dany etap rozwoju sytuacji można
zrealizować.
Mnoży się liczby możliwości rozmieszczone wzdłuż kolejnych krawędzi danej gałęzi by obliczyć
na ile sposobów można zrealizować dany ciąg wydarzeń (tworzący daną gałąź drzewa).

Ilość sumaryczną wszystkich możliwości obliczamy sumując wyniki możliwości dla wszystkich gałęzi drzewa.

Przykład:

Ile można utworzyć haseł trzyznakowych z m liter i n cyfr, jeśli po literze może stać litera lub cyfra,

a po cyfrze zawsze tylko cyfra? Litery i cyfry mogą się powtarzać.

Jeśli hasło 3-znakowe może składać się

z 2 liter i 2 cyfr to jest 32 możliwości.

z 10 liter i 2 cyfr to jest 1248 możliwości.

z 10 liter i 10 cyfr to jest 4000 możliwości.

z 24 liter i 10 cyfr to jest 22984 możliwości.

Z 26 liter i 10 cyfr to jest 27936 możliwości (alfabet łaciński).

Kule w urnach

Jeżeli w k rozróżnialnych (np. ponumerowanych) urnach mamy rozmieścić
n jednakowych, nierozróżnialnych kul
to liczba możliwości rozmieszczenia wyraża się wzorami:

1) Jeśli niektóre urny mogą zostać puste
C ⁿ_n_{+k -1} = ( = (n +k -1)! / (n!*(n+k-1 – n)! = (n+k-1)! / (k-1)!