md rep1 id 290150

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 :

liczba wszystkich relacji binarnych w X wynosi 2 n ,

n n−

liczba wszystkich zwrotnych relacji w X wynosi

(

)

n( n 1

+ )

liczba wszystkich symetrycznych relacji w X wynosi

n( n 1

− )

liczba wszystkich antysymetrycznych relacji w X wynosi n

2 ⋅ 3

liczba wszystkich relacji równoważności w X wynosi Bn (liczby Bella), n

 n

+1 = ∑

B = ∑  

  ; n

  ⋅ i

i=0  i 

k =  

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.

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.:

100

przedstawienia zbioru uporządkowanego ( X, p )

jest tzw. diagram Hassego, na którym łączymy

odcinkami tylko bezpośrednie poprzedniki z ich

następnikami i następniki umieszczamy

powyżej poprzedników.

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

)  ( m −

n m = m!

⋅ 

 m

 

| 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 ∪

∪

X 2 i Y = Y 1 Y 2

oraz spełnione są warunki X ∩

X 2 = ∅, f ( X 1) ⊆ Y 1 i f ( X 2) ⊆ Y 2 , to

J.Sikorski

Strona 6 / 14

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

jeżeli ponadto Y ∩

Y 2 = ∅,

| 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

grafu

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:

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)

(

)

−

 n 2

∑λ

2 j

λ2

Dla permutacji typu

1 2

.. n

jej znak sgn( f ) = (−

j =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

| Dn | = n! ∑

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:

= 

dla X = { x

1, ..., xn }.

0 jeśli x ∉ Y

( X) | = 2 n

Wektory charakterystyczne są wygodnym narzędziem do generowania

wszystkich elementów rodziny ( X) .

Podzbiory k-elementowe zbioru X ( | X | = n ):

 n

n( n −1 .

) . (

. n − k + )

| { Y ∈ ( X) : | Y | = k } | =   =

 k 

k (

! n − k )!

1⋅ 2 ⋅.. ⋅. k

 n

 n   n

 n − 

n  n

  = 



−

,   = 

 + 

 ,

∑  = 2 , ∑  i = n n 1

 k

 n − k  k  k   k − 

 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

∪ ...

∪ Xm ,

∅ dla 1 ≤ i < j ≤ m i X =

ki .

Liczba wszystkich rozbić zbioru X wynosi:







 =

 k

...



k ! k

1 ⋅

2 ⋅ ... ⋅

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

= 







Funkcja tworząca dla ciągu liczb podzbiorów k-elementowych

zbioru z powtórzeniami A ma postać

A( x) = ∑

k x

(1 + x + ... + 1

x ) ⋅ ... ⋅ (1 + 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

 n + 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 − 

  = 

 + k 

 , dla 0 < k < n

 k 

 k − 

 k 

 n

  = 1,   = 0 dla n ≥ 0;

  = 1, dla n > 0

 n

0

1

m−1

−

 n 

( m i)

  =

∑

 

(−1 i

)  ( m − i) = ∑

−

(−1)

 m

( m i)! i!

 

− ⋅

m = ∑ n  n

  ⋅ k

m =∑

n−

 

(−

⋅  ⋅ k

m zachodzi dla m, n ∈

k =0

k =

 k 

n  n

|Π( X)| = n

B = ∑   (liczby Bella)

k =  

 n

+1 = ∑

  ⋅ i

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.

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

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 |

U i

A = ∑

i−

(− )

∑| Ap ∩ Ap ∩ ... ∩ A |

i=1

{ p , p ,..., p

i ⊆

} { ,

1 ..., n}

Funkcją tworzącą dla ciągu liczbowego ( ai) = ( a 0, a 1, a 2, ..., ai, ... )

∞

nazywamy szereg pot

ę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, ... ), ai = 1 dla i = 0, 1, ...

1− z

( 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:

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 − 2

i z

i=0

Wzór na kolejne wyrazy ciągu:



i 









1  1+ 5

1 − 5 

F =



 −

dla i = 0, 1, 2, ...

5 











 





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:

T( z) = 2 z⋅ T( z) +

− 1

1− z

Funkcja tworząca:

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