WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
REPETYTORIUM Z KOMBINATORYKI
Relacja binarna
R ⊆ X × Y
Relacja binarna w zbiorze X:
R ⊆ X × X
Może być określona za pomocą:
zdania logicznego
xRy ⇔ x = y ,
zbioru par uporządkowanych
{( x, y), ( x, x), ...},
grafu relacji
x y z ...
x 1 0 1
tablicy relacji
y 0 1 0
z 1 1 0
...
Cechy relacji binarnej w zbiorze X:
• zwrotna,
jeśli
∀ x ∈ X : xRx
• przechodnia,
jeśli
∀ x, y, z ∈ X : ( xRy ∧ yRz ) ⇒ xRz
• symetryczna,
jeśli
∀ x, y ∈ X : xRy ⇒ yRx
• antysymetryczna, jeśli ∀ x, y ∈ X : ( xRy ∧ yRx ) ⇒ x = y Relacja równoważności jest zwrotna, przechodnia i symetryczna.
Relacja porządku jest zwrotna, przechodnia i antysymetryczna.
REPETYTORIUM (2)
J.Sikorski
Strona 1 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
Dla zbioru skończonego | X | = n :
2
liczba wszystkich relacji binarnych w X wynosi 2 n ,
n n−
liczba wszystkich zwrotnych relacji w X wynosi
(
)
1
2
,
n( n 1
+ )
liczba wszystkich symetrycznych relacji w X wynosi
2
2
,
n( n 1
− )
liczba wszystkich antysymetrycznych relacji w X wynosi n
2
2 ⋅ 3
,
liczba wszystkich relacji równoważności w X wynosi Bn (liczby Bella), n
n
n
n
+1 = ∑
n
B = ∑
; n
B
⋅ i
B
k
i=0 i
k =
0
Każdej relacji równoważności E w zbiorze X można wzajemnie
jednoznacznie przyporządkować podział zbioru X na bloki:
X| E = { a| E : a ∈ X } ,
gdzie pojedynczy blok a| E = { b ∈ X : aEb } nazywany jest klasą abstrakcji elementu a.
Jeżeli G jest grupą permutacji zbioru X, to szczególna rolę odgrywa relacja indukowana w zbiorze X przez grupę G (oznaczana RG ).
Relacja indukowana RG jest relacją równoważności.
Każdą z klas abstrakcji relacji indukowanej RG nazywamy orbitą
działania grupy G. Symbol o( G) oznacza liczbę orbit.
Zbiór orbit działania jest podziałem zbioru X na o( G) bloków.
1
o( G) =
∑ Inv( p) ,
G ∈
p G
gdzie Inv( p) jest liczbą niezmienników permutacji p ∈ G.
REPETYTORIUM (2)
J.Sikorski
Strona 2 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
Relacja porządku p wraz ze zbiorem , w którym została
zdefiniowana tworzy zbiór uporządkowany ( X, p ).
Dwa elementy x, y ∈ X nazywamy porównywalnymi, jeśli x p y lub y p x , w przeciwnym przypadku są one nieporównywalne.
Jeśli każde dwa elementy x, y ∈ X są porównywalne, to parę ( X, p ) nazywamy zbiorem liniowo uporządkowanym.
W zbiorze uporządkowanym ( X, p ) wprowadzamy „ostrą” relację
x p y ⇔ x p y ∧ x ≠ y
Jeżeli dla dwóch elementów s, t ∈ X zachodzi s p t i nie istnieje taki element u ∈ X , że s p u i u p t , to s nazywamy bezpośrednim poprzednikiem t, a t – bezpośrednim następnikiem s.
Wygodnym i czytelnym sposobem
Np.:
70
100
przedstawienia zbioru uporządkowanego ( X, p )
jest tzw. diagram Hassego, na którym łączymy
12
50
odcinkami tylko bezpośrednie poprzedniki z ich
następnikami i następniki umieszczamy
6
10
25
powyżej poprzedników.
3
2
5
Element x o ∈ X nazywamy elementem maksymalnym w zbiorze
częściowo uporządkowanym ( X, p ), jeśli w zbiorze X nie istnieje
element x ≠ x o, dla którego x o p x .
REPETYTORIUM (2)
J.Sikorski
Strona 3 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
Element x o ∈ X nazywamy elementem minimalnym w zbiorze
częściowo uporządkowanym ( X, p ), jeśli w zbiorze X nie istnieje
element x ≠ x o, dla którego x p x o .
Element x o ∈ X nazywamy elementem największym w zbiorze
częściowo uporządkowanym ( X, p ), jeśli dla każdego x ∈ X zachodzi zależność x p x o.
Element x o ∈ X nazywamy elementem najmniejszym w zbiorze
częściowo uporządkowanym ( X, p ), jeśli dla każdego x ∈ X zachodzi zależność x o p x .
W zbiorze częściowo uporządkowanym istnieje co najwyżej jeden
element największy i co najwyżej jeden element najmniejszy.
Przy tym element największy jest elementem maksymalnym, a element
najmniejszy jest elementem minimalnym.
Jeśli ( X, p ) jest zbiorem liniowo uporządkowanym oraz X jest
zbiorem skończonym i niepustym, to w ( X, p ) istnieją elementy
największy i najmniejszy.
Element x o ∈ X nazywamy ograniczeniem dolnym zbioru A ⊆ X , jeśli dla każdego x ∈ A zachodzi zależność x o p x .
Element x o ∈ X nazywamy ograniczeniem górnym zbioru A ⊆ X , jeśli dla każdego x ∈ A zachodzi zależność x p x o .
Jeśli zbiór ograniczeń górnych zbioru A ma element najmniejszy, to
nazywamy go kresem górnym zbioru A i oznaczamy sup A .
REPETYTORIUM (2)
J.Sikorski
Strona 4 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
Jeśli zbiór ograniczeń dolnych zbioru A ma element największy, to
nazywamy go kresem dolnym zbioru A i oznaczamy inf A .
Pokryciem zbioru X nazywamy taką rodzinę jego podzbiorów
{ Y 1, Y 2, ..., Yk } ( Yi ⊆ X), dla której zachodzi X = Y 1 ∪ Y 2 ∪ ... ∪ Yk.
Mówimy, że rodzina { Y 1, Y 2, ..., Yk } pokrywa zbiór X.
Łańcuchem z zbiorze uporządkowanym ( X, p ) nazywamy taki
podzbiór L ⊆ X , w którym każde dwa elementy x, y ∈ L są porównywalne, tzn. zawsze zachodzi x p y lub y p x .
Antyłańcuchem z zbiorze uporządkowanym ( X, p ) nazywamy taki
podzbiór A ⊆ X , w którym żadne dwa różne elementy x, y ∈ L nie są porównywalne, tzn. zawsze zachodzi x p y ⇔ x = y .
W każdym skończonym zbiorze częściowo uporządkowanym ( X, p )
maksymalna liczność antyłańcucha jest równa minimalnej liczbie
łańcuchów pokrywających zbiór X, a maksymalna liczność łańcucha
jest równa minimalnej liczbie antyłańcuchów pokrywających zbiór X.
Funkcja
f : X → Y
jest relacją binarną f ⊆ X × Y taką, że dla każdego x ∈ X istnieje dokładnie jedna para postaci ( x, y = f ( x) ) ∈ f Funkcja f jest injekcją (funkcją różnowartościową, „1−1”), jeśli
∀ x, y ∈ X x ≠ y ⇒ f ( x) ≠ f ( y) Funkcja f jest surjekcją (funkcją „na”), jeśli
∀ y ∈ Y ∃ x ∈ X f ( x) = y
REPETYTORIUM (2)
J.Sikorski
Strona 5 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
Funkcja f jest bijekcją , jeśli jest jednocześnie injekcją i surjekcją.
Fun( X, Y) oznacza zbiór wszystkich funkcji z X w Y, Inj( X, Y) oznacza zbiór wszystkich injekcji z X w Y, Sur( X, Y) oznacza zbiór wszystkich surjakcji z X na Y, Bij( X, Y) oznacza zbiór wszystkich bijekcji z X w Y, Bij( X, Y) = Sur( X, Y) ∩ Inj( X, Y) Dla zbiorów skończonych | X | = n i | Y | = m:
| Fun( X, Y) | = m n
| Inj( X, Y) | = m n (dla n ≤ m )
n m−1
m
| Sur( X, Y) | = s
= ∑(−1 i
n
) ( m −
n m = m!
,
⋅
i)
m
i
i=
0
| Bij( X, Y) | = n n = n!
Zasada równoliczności pozwala rozstrzygać o liczbie elementów
jednego zbioru na podstawie liczby elementów drugiego po
skonstruowaniu bijekcji pomiędzy tymi zbiorami.
Jeżeli Bij( X, Y) ≠ ∅ , to | X | = | Y | = n Rozmieszczeniem uporządkowanym nazywamy wskazanie pewnej
funkcji f : X → Y wraz z określeniem uporządkowań we wszystkich zbiorach f −1({ y}) dla y ∈ Y .
Liczba wszystkich rozmieszczeń uporządkowanych wynosi m n .
Przy zliczaniu funkcji f : X → Y stosujemy często zasadę mnożenia: jeżeli X = X ∪
∪
1
X 2 i Y = Y 1 Y 2
oraz spełnione są warunki X ∩
1
X 2 = ∅, f ( X 1) ⊆ Y 1 i f ( X 2) ⊆ Y 2 , to
| Fun( X, Y) | = | Fun( X 1, Y 1) | ⋅ | Fun( X 2, Y 2) | ; REPETYTORIUM (2)
J.Sikorski
Strona 6 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
jeżeli ponadto Y ∩
1
Y 2 = ∅,
to
| Inj( X, Y) | = | Inj( X 1, Y 1) | ⋅ | Inj( X 2, Y 2) | .
Jeżeli na zbiorze X zdefiniowano funkcję f w zbiór Y , to obowiązuje także zasada szufladkowa:
jeżeli dla zbiorów X i Y zachodzi | X | > r ⋅ | Y | dla r > 0 , to dla każdej funkcji f ∈ Fun( X, Y) warunek | f −1({ y}) | > r jest spełniony dla co najmniej jednego y ∈ Y .
Permutacją zbioru X nazywamy bijekcję p : X → X
| Bij( X, X) | = n!
Sn oznacza zbiór wszystkich permutacji zbioru {1, 2, ..., n}.
Zbiór Sn wraz z operacja składania permutacji tworzy grupę.
Operacja składania permutacji jest łączna, ale nie jest przemienna.
W zbiorze Sn istnieje element neutralny operacji składania e
(permutacja identycznościowa) i dla każdego p ∈ Sn istnieje element odwrotny p−1 ∈ Sn (permutacja odwrotna).
Permutacja p może być określona za pomocą:
1 2 3 4 5
tablicy
p =
,
5 3 2 1 4
1
2
grafu
.
4
5
3
REPETYTORIUM (2)
J.Sikorski
Strona 7 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
Każdą permutację p ∈ Sn można przedstawić w postaci złożenia
rozłącznych cykli:
p = [ 1, 5, 4 ] [ 2, 3 ]
Każdą permutację p ∈ Sn można scharakteryzować przez podanie jej
λ1 λ2
λ
typu:
n
1 2
.. n
.
, gdzie λ i oznacza liczbę cykli o długości i .
Parę ( a i , a j), gdzie p( i ) = a i i p( j ) = a j dla i < j ≤ n, nazywamy inwersją permutacji p ∈ Sn , jeśli a i > a j .
I( p) oznacza liczbę wszystkich inwersji w permutacji p ∈ Sn .
Znakiem permutacji p ∈ S
I ( p
=
n nazywamy liczbę
)
sgn( p)
(
)
1
−
.
n 2
∑λ
λ
2 j
1
λ2
λ
Dla permutacji typu
n
1 2
.. n
.
jej znak sgn( f ) = (−
j =1
1)
.
Znak cyklu o długości k jest równy (−1) k−1.
Dla permutacji p, s ∈ Sn zachodzi równość sgn( p s) = sgn( p) ⋅ sgn( s).
Transpozycją nazywamy cykl o długości 2.
Transpozycją sąsiednią nazywamy cykl postaci [ i, i+1].
Każdą permutację p ∈ Sn można przedstawić w postaci złożenia
I( p) transpozycji sąsiednich, np. p = [2, 3] [3, 4] [4, 5] [1, 2].
Każda transpozycja ma znak równy –1.
Element i ∈ {1, 2, ..., n} nazywamy niezmiennikiem permutacji p ∈ Sn , jeśli p( i) = i.
Inv( p) oznacza liczbę niezmienników permutacji p.
Nieporządkiem nazywamy taką permutację p ∈ Sn ,
dla której Inv( p) = 0.
Dn oznacza zbiór wszystkich nieporządków w zbiorze Sn .
REPETYTORIUM (2)
J.Sikorski
Strona 8 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
n (− i
1)
| Dn | = n! ∑
i!
i=0
Rodzina podzbiorów zbioru X:
( X) = { Y : Y ⊆ X}
Każdy podzbiór Y ∈ ( X) może być jednoznacznie określony przez
swój wektor charakterystyczny ξ( Y ) = ( b 1, b 2, ..., bn ) ∈ {0, 1} n
1 jeśli x ∈ Y
według wzoru:
b
i
=
,
dla X = { x
i
1, ..., xn }.
0 jeśli x ∉ Y
i
|
( X) | = 2 n
Wektory charakterystyczne są wygodnym narzędziem do generowania
wszystkich elementów rodziny ( X) .
Podzbiory k-elementowe zbioru X ( | X | = n ):
n
nk
n!
n( n −1 .
) . (
. n − k + )
1
| { Y ∈ ( X) : | Y | = k } | = =
=
=
k
k!
k (
! n − k )!
1⋅ 2 ⋅.. ⋅. k
n
n n
n −
1
n −
1
n n
n n
=
−
, =
+
,
n
∑ = 2 , ∑ i = n n 1
2
,
k
n − k k k k −
1
i
i
i= 0
i =0
Rozbiciem zbioru X na m podzbiorów o zadanych liczbach
elementów k 1, k 2, ..., km nazywamy taką rodzinę rozłącznych zbiorów
{ X 1, X 2, ..., Xm }, dla której spełnione są warunki:
X = X
X i ∩ X j =
1 ∪ X
∪ ...
2
∪ Xm ,
∅ dla 1 ≤ i < j ≤ m i X =
i
ki .
Liczba wszystkich rozbić zbioru X wynosi:
n
!
n
=
k
k
...
k
1
2
k ! k
1 ⋅
!
2 ⋅ ... ⋅
!
m
km
REPETYTORIUM (2)
J.Sikorski
Strona 9 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
Zbiór z powtórzeniami
A = < k ∗
∗
1 x 1, ..., kn xn >
określony jest przez podanie wektora krotności ( k 1, ..., kn) dla zbioru bazowego X = { x 1, ..., xn }.
Liczba elementów w zbiorze z powtórzeniami A wynosi
| A | = k 1 + ... + kn
Liczba wszystkich podzbiorów zbioru z powtórzeniami A wynosi
( k 1 + 1) ⋅ ( k 2 + 1) ⋅ ... ⋅ ( kn + 1)
Liczba k-elementowych podzbiorów zbioru z powtórzeniami
< k∗ x 1, ..., k∗ xn > (szczególny przypadek ki = k) wynosi nk
n + k − 1
=
k!
k
Funkcja tworząca dla ciągu liczb podzbiorów k-elementowych
zbioru z powtórzeniami A ma postać
A
A( x) = ∑
k
c
=
k
k x
(1 + x + ... + 1
k
x ) ⋅ ... ⋅ (1 + x + ... +
n
x
) ;
k =0
ck jest liczbą podzbiorów k-elementowych zbioru z powtórzeniami A.
Liczba całkowitych nieujemnych rozwiązań liniowego równania
diofantycznego x 1 + x 2 + ... + xn = k dla całkowitego i nieujemnego k wynosi
nk
n + k −
=
1
k!
k
Podziałem zbioru X ( | X | = n ) na k bloków nazywamy taką rodzinę niepustych zbiorów π = { A 1, ..., Ak } , dla której zachodzi X = A 1 ∪ ... ∪ Ak, Ai ∩ Aj = ∅ dla 1 ≤ i < j ≤ k oraz Ai ≠ ∅ .
REPETYTORIUM (2)
J.Sikorski
Strona 10 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
Π k( X) oznacza zbiór wszystkich podziałów zbioru X na k bloków.
Π( X) oznacza zbiór wszystkich podziałów zbioru X.
n
| Π k( X) | = (liczby Stirlinga 2 rodzaju)
k
n
n −
1
n −
1
=
+ k
, dla 0 < k < n
k
k −
1
k
n
n
n
= 1, = 0 dla n ≥ 0;
= 1, dla n > 0
n
0
1
m−1
−
n
1
1
m
n
m
( m i)
=
∑
(−1 i
n
i
) ( m − i) = ∑
−
(−1)
m
m!
i
( m i)! i!
i=
0
i=
− ⋅
0
n
m = ∑ n n
n
n
⋅ k
m =∑
n−
(−
k
1)
⋅ ⋅ k
m zachodzi dla m, n ∈
k =0
k =
k
0
k
n n
|Π( X)| = n
B = ∑ (liczby Bella)
k
k =
0
n
n
+1 = ∑
n
B
⋅ i
B
i=0 i
Każdemu podziałowi π ∈ Π( X) można jednoznacznie przyporząd-
kować relację równoważności E(π) w zbiorze X , definiując ją jako E π
( ) = U A × A
A π
∈
tzn. dwa elementy x, y ∈ X są w relacji E(π), czyli x E(π) y wtedy i tylko wtedy, kiedy x i y należą do tego samego bloku podziału.
Podziałem liczby n na k składników ( n, k ∈ { 1, 2, ... } ) nazywamy taki skończony ciąg całkowity a 1, a 2, ..., ak , dla którego zachodzi REPETYTORIUM (2)
J.Sikorski
Strona 11 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
n = a 1 + ... + ak i a 1 ≥ a 2 ≥ ... ≥ ak > 0
P( n, k) oznacza liczbę podziałów liczby n na k składników.
n
P( n) = ∑
P( n, k ) oznacza liczbę wszystkich podziałów liczby n.
k =1
Pk( n) oznacza liczbę podziałów liczby n o największym składniku równym k.
P( n, k) = Pk( n) ,
dla k ≤ n
P( n, k) = P( n −1, k −1) + P( n − k, k) dla n ≥ k > 0
P(0, 0) = P(0) = 1
k
k
P( n, k) = ∑
P( n − k, i) i P
P( n, i) dla n ≥ k > 0
i=0
k( n) = ∑ i=1
Zasada włączania-wyłączania to sposób wyznaczania liczby
elementów w sumie mnogościowej skończonej liczby zbiorów
(niekoniecznie rozłącznych):
| A ∪ B | = | A | + | B | − | A ∩ B |
| A ∪ B ∪ C | =
= | A | + | B | + | C | − | A ∩ B | − | A ∩ C | − | B ∩ C | + | A ∩ B ∩ C |
n
n
1
U i
A = ∑
i−
(− )
1
∑| Ap ∩ Ap ∩ ... ∩ A |
p
1
2
i
i=1
i=1
{ p , p ,..., p
1
2
i ⊆
} { ,
1 ..., n}
Funkcją tworzącą dla ciągu liczbowego ( ai) = ( a 0, a 1, a 2, ..., ai, ... )
∞
nazywamy szereg pot
i
ęgowy A( z) = ∑ i
a z dla zmiennej zespolonej z.
i=0
REPETYTORIUM (2)
J.Sikorski
Strona 12 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
Funkcje tworzące wybranych ciągów:
Ciąg
Funkcja tworząca
8
(1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 0, ...), ai =
(1 + z)8
i
(0, ..., 0, 1, 0, ...., 0, ... ), an = 1 i ai = 0 dla i ≠ n zn
1
(1, 1, ..., 1, ... ), ai = 1 dla i = 0, 1, ...
1− z
1
( c 0, c 1, c 2, ..., ci, ... ), ai = ci dla i = 0, 1, ...
1 − c ⋅ z
Operacjom na ciągach odpowiadają operacje na funkcjach tworzących:
Operacja na funkcjach
Operacja na ciągu
tworzących
mnożenie przez liczbę:
A( z) → c⋅ A( z)
( ai) → ( c⋅ ai)
dodawanie ciągów:
A( z), B( z) → A( z) + B( z) ( ai), ( bi) → ( ai + bi)
przesunięcie w prawo o m pozycji:
( ai) → (0, ..., 0, a 0, a 1, a 2, ..., ai, ... ) A( z) → zm⋅ A( z)
( ai = 0 dla i = 0, 1, ..., m−1)
Za pomocą funkcji tworzącej można otrzymać nierekurencyjny wzór
na kolejny wyraz ciągu Fibonacciego.
Wzór rekurencyjny:
F
+
+
i = Fi−1 Fi−2 i = 1 dla i = 0, 1, 2, 3, ... ( Fi = 0 dla i < 0) Równanie dla funkcji tworzącej:
REPETYTORIUM (2)
J.Sikorski
Strona 13 / 14
WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT
F( z) = z 2⋅ F( z) + z⋅ F( z) + z Funkcja tworząca:
∞
F ( ) =
z
z
= ∑
i
F
− z − 2
i z
1
z
i=0
Wzór na kolejne wyrazy ciągu:
i
i
1 1+ 5
1 − 5
i
F =
−
dla i = 0, 1, 2, ...
5
2
2
Za pomocą funkcji tworzącej można rozwiązać rekurencyjne równanie
dla złożoności rekurencyjnego algorytmu dla problemu wież Hanoi.
Wzór rekurencyjny:
T =
i 2⋅ Ti−1 + 1 − i = 0 dla i = 0, 1, 2, ... ( Ti = 0 dla i < 0) Równanie dla funkcji tworzącej:
1
T( z) = 2 z⋅ T( z) +
− 1
1− z
Funkcja tworząca:
z
T ( z) =
(1− z)(1− 2 z)
Wzór na zależność liczby ruchów od liczby krążków:
Ti = 2 i – 1 dla i = 0, 1, 2, ...
REPETYTORIUM (2)
J.Sikorski
Strona 14 / 14