Elementy kombinatoryki.
Wariacje bez powtórzeń.
Wariacje z powtórzeniami.
Sposób na prawie każde zadanie.
Elementy kombinatoryki.
Wariacje bez powtórzeń.
Wariacje z powtórzeniami.
Sposób na prawie każde zadanie.
Twierdzenie o mnożeniu.
Jeżeli dane są dwa skończone zbiory
A = { x
1
, x
2
, ... x
n
} i B = { y
1
, y
2
, ...
y
m
}, to liczba różnych par ( x, y ), takich, że xA
oraz yB jest równa m•n.
Uwaga
: Twierdzenie to można uogólnić na skończoną
ilość zbiorów.
Przykład:
Niech A = { a
1
, a
2
, a
3
} i B = { b
1
, b
2
}. Liczba par ( x, y )
takich, że xA oraz yB jest równa 3 •2 = 6.
Ilustracja twierdzenia o mnożeniu.
a
1
a
3
a
2
b
1
b
1
b
1
b
2
b
2
b
2
Przykład zastosowania twierdzenia o
mnożeniu
.
Rzucamy sześcienną kostką i symetryczną monetą. Ile
jest wszystkich możliwych wyników?
1
6
5
4
3
2
R
O
R
R
R
R
R
O
O
O
O
O
Permutacja
.
Permutacją zbioru n-elementowego nazywamy
każdy
ciąg
n-elementowy utworzony
z
wszystkich
elementów tego zbioru, czyli jest to pewne
uporządkowanie elementów tego zbioru.
Liczba wszystkich różnych permutacji zbioru n-
elementowego jest równa:
N
n
;
n
1
n
...
2
1
!
n
P
n
Przykład permutacji.
Ile wyrazów mających lub nie sens można ułożyć
przestawiając litery wyrazu KAT?
K A T
A K T
T A K
K T A
A T K
T K A
Są to permutacje zbioru trzyelementowego, a zatem
ich ilość wynosi :
P
3
= 3!
=
1•2•3 = 6
Kombinacja.
Kombinacją k-elementową ze zbioru n-elementowego
nazywamy
każdy
podzbiór
k-elementowy
danego
zbioru.
Liczba wszystkich różnych kombinacji k-
elementowych zbioru n-elementowego jest równa:
k
n
,
N
k
,
n
;
)!
k
n
(
!
k
!
n
k
n
C
k
n
Przykład kombinacji.
1.
Ile jest możliwości wyboru dwóch różnych
kolorów kart z czterech?
Są to kombinacje dwuelementowe ze zbioru czteroelementowego.
Przykład kombinacji.
2.
Ile można narysować na płaszczyźnie prostych
przechodzących przez: a) dwa, b) trzy, c) cztery
punkty
( jeżeli żadne trzy z nich nie są współliniowe ) ?
A
C
D
B
Wariacja bez powtórzeń
.
Wariacją k-elementową bez powtórzeń zbioru
n-elementowego nazywamy
każdy
ciąg różnowartościowy
k-wyrazowy utworzony z
elementów danego zbioru.
Liczba wszystkich różnych k-elementowych wariacji
bez powtórzeń zbioru n-elementowego jest równa:
N
k
,
n
k
n
;
!
k
n
!
n
V
k
n
Przykład wariacji bez powtórzeń.
1.
Ile liczb dwucyfrowych można utworzyć używając
dwóch
różnych
cyfr ze zbioru { 2,5,7,9 }?
2
5
2
7
2
9
7
9
7
2
7
5
5
9
5
7
5
2
9
2
9
7
9
5
Są to dwuwyrazowe wariacje bez powtórzeń ze
zbioru zawierającego cztery elementy.
Przykład wariacji bez powtórzeń..
2.
Na ile sposobów z czteroosobowej reprezentacji
klasy można wybrać kapitana i jego zastępcę :
K Z
K Z
K Z
K Z
K Z
K Z
K Z
K Z
K Z
K Z
K Z
K Z
Są to wariacje dwuelementowe bez powtórzeń ze zbioru
czteroelementowego.
Wariacja z powtórzeniami.
N
k
,
n
;
n
V
k
k
n
Wariacją k-elementową z powtórzeniami
zbioru n-elementowego
nazywamy
każdy
ciąg
k-wyrazowy utworzony
z elementów danego zbioru.
Liczba wszystkich różnych k-elementowych
wariacji z powtórzeniami
zbioru n-elementowego jest równa:
Przykład wariacji z powtórzeniami.
1.
Ile liczb dwucyfrowych można utworzyć używając
cyfr ze zbioru { 2,5,7,9 }?
2
9
7
9
5
9
9
7
2
7
7
5
5
7
9
5
2
5
7
2
5
2
9
2
9
9
7
7
5
5
2
2
Są to dwuwyrazowe wariacje z powtórzeniami ze
zbioru zawierającego cztery elementy.
Przykład wariacji z powtórzeniami.
2.
Na ile sposobów można włożyć trzy różne piłeczki
do dwóch ponumerowanych pudełek ?
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
Przykład wariacji z powtórzeniami.
Są to trzywyrazowe wariacje z powtórzeniami ze
zbioru zawierającego dwa elementy, a zatem ich
ilość wynosi 2
3
= 8.
1
1
1
1
1
2
1
2
1
1
2
2
2
1
1
2
1
2
2
2
1
2
2
2
Sposób na zadanie.
Doświadczenie polega na wylosowaniu k-elementów ze zbioru n-
elementowego
Czy istotna jest kolejność wylosowanych
elementów?
Kombinacja.
Wariacja bez
powtórzeń.
Czy elementy mogą się
powtarzać?
Wariacja
z
powtórzeniami.
nie
tak
tak
nie
Zadania
Ćwiczenie 1
Rozwiąż zadania ze stron 91-95 oraz 99-101 z
podręcznika