KOMBINATORYKA

OFICJALNA ŚCIĄGAWKA z MATEMATYKI DYSKRETNEJ cz. 1

relacja równoważności jest zwrotna, przechodnia i symetryczna; relacja porządku jest zwrotna, przechodnia i antysymetryczna; n  n

2

dla | X| = n : 2 n = liczba wszystkich relacji binarnych; B

= liczba wszystkich relacji równowa

n = ∑  

żności w X

k

k =0 

relacji równoważności E w zbiorze X wzajemnie jednoznacznie odpowiada podział zbioru X na bloki X| E = { a| E : a ∈ X }; a| E = { b ∈ X : aEb } - klasa abstrakcji elementu a ; ( X, p ) – zbiór uporządkowany: x, y ∈ X są porównywalne, jeśli x p y lub y p x ; x p y ⇔ x p y ∧ x ≠ y ; dla s, t ∈ X zachodzi s p t i nie istnieje taki element u ∈ X , że s p u i u p t , to s jest bezpośrednim poprzednikiem t, a t – bezpośrednim następnikiem s ; x o ∈ X jest elementem maksymalnym w ( X, p ), jeśli w zbiorze X nie istnieje element x ≠ x o, dla którego x o p x ; x o ∈ X jest elementem minimalnym w ( X, p ), jeśli w zbiorze X nie istnieje element x ≠ x o, dla którego x p x o ; x o ∈ X jest elementem największym w ( X, p ), jeśli dla każdego x ∈ X zachodzi zależność x p x o ; x o ∈ X jest elementem najmniejszym w ( X, p ), jeśli dla każdego x ∈ X zachodzi zależność x o p x ; x o ∈ X jest ograniczeniem dolnym zbioru A ⊆ X , jeśli dla każdego x ∈ A zachodzi zależność x o p x ; x o ∈ X jest ograniczeniem górnym zbioru A ⊆ X , jeśli dla każdego x ∈ A zachodzi zależność x p x o ; sup A – kres górny zbioru A = element najmniejszy w zbiorze ograniczeń górnych zbioru A (jeśli istnieje) ; inf A – kresem dolnym zbioru A = element największy w zbiorze ograniczeń dolnych zbioru A (jeśli istnieje) ; podzbiór L ⊆ X , w którym każde dwa elementy x, y ∈ L są porównywalne = łańcuch w ( X, p ) ; podzbiór A ⊆ X , w którym żadne dwa różne elementy x, y ∈ L nie są porównywalne = antyłańcuch w ( 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 ;

 n 

dla | X | = n i | Y | = m: | Fun( X, Y) | = m n, | Inj( X, Y) | = m n (dla n ≤ m ), | Sur( X, Y) | = s

!

, | Bij( X, Y) | = n n = n! , n, m = m ⋅ 



 m

liczba rozmieszczeń uporządkowanych = m n ; Bij( X, Y) ≠ ∅ ⇒| X | = | Y | ; jeżeli zachodzi | X | > r ⋅ | Y | dla r > 0 , to dla f ∈ Fun( X, Y) warunek | f −1({ y}) | > r jest spełniony dla co najmniej jednego y∈ Y ; permutacja zbioru X = bijekcja p : X → X ; | Bij( X, X) | = n! ; λ1 λ2

λ

typ permutacji

n

1 2 .. n

.

, gdzie λ i oznacza liczbę cykli o długości i ; inwersją permutacji p ∈ S

I ( p

=

n = p ara ( p( i), p( j)), gdzie p( i) > p( j) dla i< j≤ n; I( p) = liczbę inwersji;

)

sgn( p)

(

)

1

−

;

 n 2

∑ λ

λ

2 j

1

λ2

λ

permutacji jest typu

n

1 2 .. n

.

, to jej znak sgn( f ) = (−

j =1

1)

; znak cyklu o długości k jest równy (−1) k−1 ; sgn( p s) = sgn( p) ⋅ sgn( s); transpozycja = cykl o długości 2; transpozycja sąsiednia = [ i, i+1] ; n (− i

1)

i – niezmiennik permutacji, jeśli p( i) = i ; Inv( p) = liczba niezmienników; nieporządek, gdy Inv( p) = 0; | Dn | = n! ∑

;

i!

i=0

 n nk

n!

n( n −1 .

) . (

. n − k + )

1

 n  n −1  n −1

|

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

=

=

;   = 

 + 

 ;

 k 

k!

k (

! n − k )!

1⋅ 2 ⋅.. ⋅. k

 k   k   k −1



n



!

n

nk

 n + k −1

=





; | A | = < k∗ x

=

1, ..., k∗ xn > : liczba podzbiorów k-elementowych =



 ;

 k

k

...

k

1

2



k ! k

k!

k

1 ⋅

!

2 ⋅ ... ⋅

!

m

km





nk

 n + k − 

1

 n  n

 n − 

1

 n − 

1

n  n

rozwiązań równania x + +

=

B

n =

1 x 2 ...+ xn = k jest



 ; | Π k( X) | =   ,   = 

 + k 

 , |Π( X)| =

∑ 

k!



k



 k  k

 k − 

1

 k 

k =0 k 

n

k

k

E(π ) = U A× A ; P( n) = ∑

P( n, k ) , P( n, k) = P( n −1, k −1) + P( n − k, k), P( n, k) = ∑

P( n − k, i) , P

P( n, i) ; k =1

i=0

k( n) = ∑ i=1

A π

∈

| A ∪ B | = | A | + | B | − | A ∩ B | , | A ∪ B ∪ C | = | A | + | B | + | C | − | A ∩ B | − | A ∩ C | − | B ∩ C | + | A ∩ B ∩ C | , n

n

∞

U A

1

1

A

A

A

; A( z) = ∑

i

a z - funkcja tworz

i = ∑

i−

(− )

∑| p ∩ p ∩ ... ∩

|

p

i

ąca dla ciągu ( ai) = ( a 0, a 1, a 2, ..., ai, ... ) 1

2

i

i=1

i=1

{ p , p ,..., p 1

i=0

1

2

i ⊆

} { ,..., n}

(jedyna ściągawka, którą wolno mieć na egzaminie, ale nie wolno jej używać na kolokwium poprawkowym)