Elementy kombinatoryki
• zasada golebnika,
• zasada wlaczania i wylaczania,
• permutacje, kombinacje, podzialy liczb,
• algorytmy generowania obiektów kombinatorycznych,
Zasada Golebnika (Zasada szufladkowa DIRICHLET’A)
Niech:
m obiektów oraz n pudelek
jezeli n < m, to przynajmniej dwa obiekty sa w jednym pudelku
Niech |A| - moc zbioru A ;
np. A = {a,b,c,d,e} ; |A| = 5
Jezeli skonczony zbiór S jest podzielony na k zbiorów, to co najmniej jeden z tych zbiorów ma |S|/k lub wiecej elementów.
Zastosowania:
W kazdej grupie n osób sa przynajmniej 2 osoby, które znaja te sama liczbe osób.
„Znajomosc” jest relacja symetryczna i antyzwrotna (nikt tak naprawde nie zna siebie).
Niech f(x) - liczba znajomych osoby x
Zatem f(x) ∈ {0, 1, 2, ..., n-1}, czyli liczba wszystkich mozliwych wartosci funkcji f(x) równa sie liczbie wszystkich osób n.
Jezeli zatem ∃y f(y) = n-1 i ∀x ≠ y f(x) ∈ {0, 1, 2, ..., n-2}, to
∃ y1 f(y1) = n-2 i ∀x ≠ y1 f(x) ∈ {0, 1, 2, ..., n-3} , a zatem
∃ yn-1 f(yn-1) = 1 i ∀x ≠ yn-1 f(x) ∈ {0} , tak wiec jezeli
∃ yn f(yn) = 0 ∈ {0, 1, 2, ...,n – 2, n-1}
Ilustracja
Dany zbiór A = {a1, a2,...,a9} taki, ze suma jego elementów = 90.
a)
∃ trzy takie elementy zbioru A, ze ich suma ≥ 30.
b)
∃ cztery takie elementy zbioru A, ze ich suma ≥ 40.
a)
(a1 + a2 + a3)
+
(a4 + a5 + a6) +
(a7 + a8 + a9) = 90
α < 30
β < 30
γ > 30
α < 30
β = 30
γ > 30
b)
a1
a2
a3
a4
a5
a6
a7
a8
a9
a2
a3
a4
a5
a6
a7
a8
a9
a1
a3
a4
a5
a6
a7
a8
a9
a1
a2
a4
a5
a6
a7
a8
a9
a1
a2
a3
4 x 90 = 360
zatem 360/9 = 40
a1 + a2 + a3 + a4 lub a2 + a3 + a4 + a5 lub ....... ≥ 40
Zasada wlaczania i wylaczania
Nalezy „wlaczyc” (dodac do siebie licznosci poszczególnych zbiorów), nastepnie „wylaczyc” (odjac licznosc przeciec po dwa zbiory), potem „wlaczyc” (dodac licznosci wszystkich przeciec po trzy zbiory), itd.
A
B |A ∪ B ∪ C | =
= |A| + |B| + |C| - |A ∩ B| -
- |A ∩ C| - |B ∩ C| + |A ∩ B ∩ B|
C
Ilustracja
A = {a,b} ;
B = {1,2} ;
C = {x,y}
|A ∪ B ∪ C | = 6 = 2 + 2 + 2 – 0 – 0 – 0 + 0 = 6
Ile jest liczb miedzy 1 a 999 nie podzielnych, ani przez 5, ani przez 7?
1, 2, ... , 999
/7
/5
999 - „/5” - „/7” + „/5 7” = 999 - 999/5 - 999/7 + 999/35 =
= 999 - 199 - 142 + 28 = 686
Ile liczb naturalnych ze zbioru S = {1,2,3,...,1000} dzieli sie przez 3
lub 5 lub przez obie te liczby jednoczesnie?
Niech D3 = {n∈S : n dzieli sie przez 3}
D5 = {n∈S : n dzieli sie przez 5}
D ∩
3
D5 = {n∈ S : n dzieli sie przez 15}
D3 = {3m∈S : 1≤ m ≤ 333}
| D3 | = 1000/3 = 333
D5 = {5m∈S : 1≤ m ≤ 200}
| D5 | = 1000/5 = 200
| D ∩
3
D5 | = 1000/15 = 66
Zatem
| D
∩
3 ∪ D5| = | D3 | + | D5 | - | D3
D5 | = 333 + 200 – 66 = 467
Permutacje
• funkcje na zbiorze liczb naturalnych {a1,a2, ...,an}
Liczba permutacji
Pn = n! = n (n-1) (n-2) ...1 = 1 2 3 ...n
0! = 1
{A , B , C}
A B
C
B
C
A
C
A
B
C
B
C
A
B
A
Urzednik zapomnial hasla do swoje aktówki. Haslo jest liczba 7
cyfrowa zlozona z cyfr od 1 do 7. Cyfry w hasle nie powtarzaja sie.
(Ostatnie 3 cyfry wybierane sa ze zbioru {3,4,7}) Ile mozliwosci w najgorszym przypadku trzeba sprawdzic aby otworzyc zamek?
{3,4,7})
(3,4,7) , (4,7,3) , (7,4,3) , (3,7,4) , (4,3,7) , (7,3,4)
Wariacje
• bez powtórzen
Dany zbiór A = {a1,a2, ...,an}. Wariacja – k-elementowy ciag nie powtarzajacych sie obiektów zbioru A.
Liczba k-elementowych wariacji zbioru A, n = |A| .
V k
n = n (n-1) (n-2) ... (n – k+1))
n!
V k
n =
(n-k)!
n!
n (n-1) (n-2) ...(n-k+1) (n- k) (n-k-1)..2 1
V k
n =
=
=n(n-1)..(n-k+1)
(n-k)!
(n-k) (n-k-1) ...2 1
A = {a,b,c} ; k = 2
;
(a,b) , (a,c) , (b,c) , (b,a) , (c,a) , (c,b)
W urnie jest 10 kul ponumerowanych od 1 do 10. Losujemy kolejno i bez zwrotu 5 kul. Po kazdym losowaniu zapisujemy jej numer. Ile jest wszystkich mozliwych wyników losowania?
V k
5
n = n (n-1) (n-2) ... (n – (k-1))
; V10 = 10 9 8 7 6
• z powtórzeniami
Rzucamy 10 razy moneta. Ile jest mozliwych wyników tego doswiadczenia?
Liczba k-elementowych wariacji z powtórzeniami
W k
n = n n n n ...n = nk
k
Na ile sposobów mozna rozmiescic 2 kule (czarna i biala) w 3
szufladach?
I
II
III
0
b
c
{O,R} , {O,R},..., {O,R}
2n
0
c
b
0
c-b 0
0
0
c-b
{c,b,c-b} , {c,b,c-b} , {c,b,c-b} 33
b
c
0
c
b
0
c-b 0
0
b
0
c
c
0
b
Kombinacje
Dany zbiór A = {a1,a2, ...,an}. Kombinacja – k-elementowy podzbiór zbioru A.
Liczba k-elementowych kombinacji ze zbioru A, n = |A| .
n!
n
C k
n = =
k!(n-k)! k
n!
n
C k
n = =
k!(n-k)! k
3
3!
= = 3 {3,2,1} , k = 2
; (1,2) , (1,3) , (2,3)
2 2! 1!
Latwo zauwazyc, ze:
n!
V k
k
n = = k! Cn
(n-k)!
Na ile sposobów mozna wybrac 8 kart z talii 24 kart jezeli kolejnosc nie jest wazna?
Ile z tych ukladów 8-kartowych zawiera 2 asy.
C 6
2
20 C4
Na ile sposobów mozna rozmiescic 6 osób w 3 róznych pokojach 2 osobowych?
C 6
4
2
2 C2 C2
Wlasnosci kombinacji
a)
n
n
=
k
n - k
b)
n
n
=
= 1
0
n
c)
n
n
=
= 1
1
n-1
Trójkat Pascal’a
1
1
1
1
2
1
1
3
3
1
1
4
6
4
1
Dwumian Newton’a
n
n
n
n
(a – b)n = an + an-1 b + ... + a bn-1 + bn
0
1
n-1
n
n
n
(a – b)n = Σ an-i bi
i=0 i
Ciag Fibonacciego
1
1
2
3
5
8
13 21 34 55 89 144 ...
F1 = 1
;
F2 = 1
;
Fn = Fn-1 + Fn-2 dla n > 2
1
2
3
5
8
13 21 34 55 89 144 ...
pary 1
1
2
3
5
8
okresy
1
2
3
4
5
6
M
R
R
R
R
R
M
M
R
M
R
R
M
M
R
R
R
M
M
R
Zlota proporcja
a
x
a-x
a
x
a2
a
=
;
a2 – a x = x2
;
- - 1 = 0
x
a – x
x2
x
a
√5 + 1
=
= 1,618033989.... liczba niewymierna
x
2
a
x
a – x
np. front Partenonu
Fn+1 √5 + 1
φ =
=
= 1,618033989.....
Fn
2
1
1 + √5 n
1 - √5 n
Fn = -
√5
2
2
Fn+1/ Fn
2/1 = 2
3/2 = 1.5 5/3 = 1.667
8/5 = 1.6
13/8 = 1.625
21/13 = 1.615
34/21 = 1.619
55/34 = 1.618
. . .