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;

dla |X| = n :

2

2

n

= liczba wszystkich relacji binarnych;

∑

=













=

n

k

n

k

n

B

0

= liczba wszystkich relacji równoważności w X

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 ;

dla | X |

=

n i | Y |

=

m: | Fun(X, Y) |

=

m

n

, | Inj(X, Y) |

=

m

n

(dla n

≤

m ), | Sur(X, Y) |

=













⋅

=

m

n

m

s

m

n

!

,

, | Bij(X, Y) |

=

n

n

=

n! ,

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! ;

typ permutacji

n

n

λλλλ

λλλλ

λλλλ

...

2

1

2

1

, gdzie

λ

i

oznacza liczbę cykli o długości i ;

inwersją permutacji p

∈

S

n

= para (p(i), p( j)), gdzie p(i)

>

p( j) dla i

<

j

≤

n; I( p) = liczbę inwersji;

)

(

)

(

)

sgn(

p

I

p

1

−

=

;

permutacji jest typu

n

n

λλλλ

λλλλ

λλλλ

...

2

1

2

1

, to jej znak





∑

−

=

=

2

1

2

1

n

j

j

f

λλλλ

)

(

)

sgn(

; 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] ;

i – niezmiennik permutacji, jeśli p(i)

=

i ; Inv(p) = liczba niezmienników; nieporządek, gdy Inv(p)

=

0; | D

n

|

=

∑

=

−

n

i

i

i

n

0

1

!

)

(

!

;

|

(X) |

=

2

n

; | { Y

∈

(X) : | Y |

=

k } |

=

k

k

n

n

n

k

n

k

n

k

n

k

n

k

⋅

⋅

⋅

+

−

−

=

−

=

=













...

)

(

...

)

(

)!

(

!

!

!

2

1

1

1

;













−

−

+













−

=













1

1

1

k

n

k

n

k

n

;

!

...

!

!

!

...

m

m

k

k

k

n

k

k

k

n

⋅

⋅

⋅

=













2

1

2

1

; | A |

=

< k

∗

x

1

, ..., k

∗

x

n

> : liczba podzbiorów k-elementowych =













−

+

=

k

k

n

k

n

k

1

!

;

rozwiązań równania x

1

+

x

2

+

...

+

x

n

=

k jest













−

+

=

k

k

n

k

n

k

1

!

; |

Π

k

(X) |

=













k

n

,













k

n

=













−

−

1

1

k

n

+

k













−

k

n

1

, |

Π

(X)|

=

∑

=













=

n

k

n

k

n

B

0

U

ππππ

ππππ

∈

×

=

A

A

A

E

)

(

; P(n)

=

∑

=

n

k

k

n

P

1

)

,

(

, P(n, k)

=

P(n

−

1, k

−

1)

+

P(n

−

k, k), P(n, k)

=

∑

=

−

k

i

i

k

n

P

0

)

,

(

, P

k

(n)

=

∑

=

k

i

i

n

P

1

)

,

(

;

| A

∪

B |

=

| A |

+

| B |

−

| A

∩

B | , | A

∪

B

∪

C |

=

| A |

+

| B |

+

| C |

−

| A

∩

B |

−

| A

∩

C |

−

| B

∩

C |

+

| A

∩

B

∩

C | ,

∑

∑

⊆

=

−

=

∩

∩

∩

−

=

}

,...,

{

}

,...,

,

{

|

...

|

)

(

n

p

p

p

p

p

p

n

i

i

n

i

i

i

i

A

A

A

A

1

1

1

1

2

1

2

1

1

U

;

∑

∞

=

=

0

i

i

i

z

a

z

A )

(

- funkcja tworząca dla ciągu (a

i

)

=

(a

0

, a

1

, a

2

, ..., a

i

, ... )

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