Matematyka Dyskretna dla informatyków Wojciech Kordecki

background image

Wojciech Kordecki

Matematyka
dyskretna

dla informatyków

Wrocław 2005

background image

Spis treści

1. Relacje, funkcje i rozmieszczenia

1

1.1. Zbiory częściowo uporządkowane

1

1.2. Funkcje i rozmieszczenia

2

1.3. Zadania

4

2. Permutacje

6

2.1. Grupy skończone

6

2.2. Rozkład permutacji na cykle

6

2.3. Liczby Stirlinga pierwszego rodzaju

9

2.4. Zadania

10

3. Kombinacje

12

3.1. Współczynnik dwumianowy

12

3.2. Generowanie podzbiorów

14

3.3. Zbiory z powtórzeniami

15

3.4. Zadania

16

4. Podziały

18

4.1. Zasada włączania – wyłączania

18

4.2. Liczby Stirlinga drugiego rodzaju

21

4.3. Zadania

23

5. Funkcje tworzące

24

5.1. Szeregi formalne

24

5.2. Rozwiązywania rekurencji

25

5.3. Zastosowania funkcji tworzących

26

5.4. Sploty

28

5.5. Zadania

30

6. Ciała skończone i skończone przestrzenie wektorowe

31

6.1. Ciała skończone

31

6.2. Ciała wielomianów

32

6.3. Skończone przestrzenie wektorowe

32

6.4. Zadania

35

7. Geometrie rzutowe i afiniczne

36

7.1. Skończone geometrie rzutowe

36

7.2. Skończone geometrie afiniczne

37

7.3. Zadania

38

8. Matroidy

39

8.1. Definicje

39

8.2. Dualność

41

8.3. Algorytmy zachłanne

41

i

background image

8.4. Zadania

42

9. Transwersale i matroidy

44

9.1. Transwersale

44

9.2. Matroidy transwersalne

45

9.3. Zadania

45

10.Niezmienniki Tutte’a–Gr¨

othendiecka

46

10.1. Operacje na matroidach

46

10.2. Wielomiany Tutte’a

46

10.3. Zadania

48

11.Konfiguracje kombinatoryczne

49

11.1. Podstawowe własności

49

11.2. Konfiguracje kwadratowe

50

11.3. Macierze Hadamarda

51

11.4. Zadania

52

12.Trójki Steinera

54

12.1. Quasigrupy i kwadraty łacińskie

54

12.2. Konstrukcje Bosego i Skolema

55

12.3. Zadania

56

Literatura

57

ii

background image

1

1. Relacje, funkcje i rozmieszczenia

1.1. Zbiory częściowo uporządkowane

Niech X będzie dowolnym zbiorem (skończonym). Relacja binarna 4 na X
nazywa się częściowym porządkiem, jeśli jest zwrotna, przechodnia i antysy-
metryczna, tzn. jeśli

x 4 x,

x 4 y

∧ y 4 z =⇒ x 4 z,

x 4 y

∧ y 4 x =⇒ x = y

Parę (X, 4) nazywa się zbiorem częściowo uporządkowanym, (partially ordered

Posety

set = poset). Jeżeli wiadomo o jaki porządek chodzi, to zbiorem częściowo
uporządkowanym nazywa się też sam zbiór X. Jeżeli dla pewnych elementów
x, y

∈ X zachodzi x 4 y lub y 4 x, to elementy te są porównywalne. Jeżeli

dowolne dwa elementy są porównywalne, to porządek nazywa się liniowym.
Jeżeli x 4 y i x 6= y to pisze się x ≺ y. Element x ∈ X jest

• minimalny, jeśli nie istnieje y ∈ X taki, że y ≺ x,
• maksymalny, jeśli nie istnieje y ∈ X taki, że x ≺ y,
• najmniejszy, jeśli x 4 y dla każdego y ∈ X,
• największy, jeśli y 4 x dla każdego y ∈ X.

Element najmniejszy nazywa się zerem, a największy jedynką zbioru częściowo

Zero i jeden

uporządkowanego, oznaczane są one często przez 0 i 1.
Przykład.

Rodzina R = 2

Z

wszystkich podzbiorów dowolnego zbioru Z z

relacją zawierania ⊆ jest zbiorem częściowo uporządkowanym (R, ⊆). Elemen-

tem największym jest Z, a najmniejszym ∅. Również dowolna rodzina S ⊆ 2

Z

podzbiorów zbioru Z z taką samą relacją ⊆ jest zbiorem częściowo uporząd-

kowanym, choć 0 i 1 mogą być inne lub nie istnieć.
Niech (X, 4) będzie zbiorem częściowo uporządkowanym oraz Y ⊆ X. Jeśli

każde dwa elementy zbioru Y są porównywalne, to Y jest łańcuchem, jeśli

Łańcuchy

zaś żadne dwa różne nie są porównywalne, to Y jest antyłańcuchem. Każdy
łańcuch ma element najmniejszy i największy, czyli początek i koniec łańcucha.
Ograniczeniem dolnym zbioru Y ⊆ X nazywa się dowolny element a ∈ X taki,

że a 4 x dla każdego x ∈ Y , a ograniczeniem górnym zbioru Y ⊆ X nazywa

się dowolny element b ∈ X taki, że x 4 b dla każdego x ∈ Y . Niech A(Y ) i
B

(Y ) będzą zbiorami wszystkich ograniczeń dolnych i górnych odpowiednio.

Własność 0. Zbiory A i B ograniczeń dolnych i górnych są uporządkowane
liniowo.

Dowód.

????

Kresem dolnym zbioru Y nazywa się element największy w A(Y ), kresem

Kresy zbiorów

górnym element najmniejszy w B(Y ). Kresy dolne i górne zbioru Y oznaczane
są odpowiednio przez inf(Y ) i sup(Y ).

background image

1.2. Funkcje i rozmieszczenia

2

Używa się też oznaczeń:

x

∨ y = sup{x, y},

x

∧ y = inf{x, y},

Kratą jest zbiór X częściowo uporządkowany relacją 4 taki, że dla każdej

Kraty

pary x, y ∈ X istnieje kres dolny x ∧ y oraz kres górny x ∨ y. Krata nazywa się

się zupełną, istnieją inf(Y ) i sup(Y ) dla każdego podzbioru Y kraty (X, 4).
Krata nazywa się rozdzielną, gdy dla dowolnych elementów x, y, z kraty (X, 4)
zachodzą równości

x

∨ (y ∧ z) = (x ∨ y) ∧ (z ∨ z),

x

∧ (y ∨ z) = (x ∧ y) ∨ (z ∧ z).

1.2. Funkcje i rozmieszczenia

Niech |X| oznacza moc (liczbę elementów) zbioru skończonego X. Klasycznym

zadaniem kombinatoryki jest następujący problem: dla danych zbiorów X i

Zbiory
w pudełkach

Y

, gdzie |X| = m, |Y | = n znaleźć liczbę wszytkich funkcji f : X → Y

spełniających dane ograniczenia.
Twierdzenie 1.2.1. Jeśli

|X| = m i |Y | = n, to liczba wszystkich funkcji

f

: X → Y jest równa n

m

.

Dowód.

Oznaczmy X = {1, 2, . . . , m}. Funkcje f : X → Y są ciągami długo-

ści m o wyrazach ze zbioru Y . Każdy wyraz można wybrać na n sposobów,
wszystkich więc ciągów jest n

m

.

Zadanie powyższe formułuje się często jako zadanie znalezienia liczby rozmiesz-
czeń m elementów w n pudełkach – element o numerze i znajduje się w pudełku
o numerze j, gdy f (i) = j.
Ograniczając się do funkcji różnowartościowych (wzajemnie jednoznacznych),
otrzymujemy następujące wynik.

Elementy
w pudełkach

Twierdzenie 1.2.2. Jeśli

|X| = m i |Y | = n, to liczba funkcji różnowarto-

ściowych f : X

→ Y jest dla m ¬ n równa

(n)

m

= n(n − 1) . . . (n − m + 1) ,

(1.2.1)

gdzie dodatkowo przyjmuje się (n)

0

= 1. Dla m > n liczba ta jest równa zeru.

Dowód.

Niech X = {1, 2, . . . , m} oraz m ¬ n. Pierwszy wyraz ciągu można

wybrać na n sposobów, drugi na n − 1, a ogólnie i-ty wyraz można wybrać na
m

− (i − 1) = m − i + 1 sposobów, co daje wzór (1.2.1). Dla m > n nie ma

funkcji f : X → Y różnowartościowych.

background image

1.2. Funkcje i rozmieszczenia

3

Jest to zadanie znalezienia liczby rozmieszczeń m elementów w n pudełkach,
gdy w każdym pudełku można umieścić co najwyżej jeden element.
Jeśli m = n, to (n)

m

jest oznaczane przez n! i nazywane silnią liczby n. Jeśli

X

= Y , to różnowartościową funkcję f : X → X nazywa się permutacją zbioru

Permutacje
i silnie

X

. Stąd

Twierdzenie 1.2.3. Jeśli

|X| = |Y | = n, to liczba funkcji różnowartościowych

f

: X → Y jest równa

n

! = n(n − 1) · . . . · 1 .

W szczególności istnieje n! permutacji zbioru n-elementowego.

Ponieważ n! rośnie bardzo szybko, to bardzo użyteczny jest następujący asym-

Wzór Stirlinga

ptotyczny wzór Stirlinga

1

n

! = n

n

2πn (1 + o(1)) .

(1.2.2)

i jego udoskonalenie (wzór Robbinsa

2

)

n

n

e

−n

2πne

1

12

n+1

< n

! < n

n

e

−n

2πne

1

12

n

.

(1.2.3)

(patrz zad. 20).
Zagadnieniem podobnym do zagadnienia rozwiązanego w twierdzeniu 1.2.2
jest zagadnienie rozmieszczenia m elementów w n pudełkach, przy czym każ-
de pudełko zawiera ciąg elementów, (pudełka mogą być też puste). Dwa roz-

Ciągi
w pudełkach

mieszczenia są identyczne, gdy te same pudełka mają te same ciągi elementów.
Rozmieszczenia tego typu nazywa się rozmieszczeniami uporządkowanymi m
elementów w n pudełkach.
Twierdzenie 1.2.4. Liczba rozmieszczeń uporządkowanych m elementów w
n pudełkach jest równa

(n)

m

= n(n + 1) . . . (n + m − 1), ,

(1.2.4)

gdzie dodatkowo przyjmuje się (n)

0

= 1.

Dowód.

Niech X = {x

1

, x

2

, . . . , x

m

}. Element x

1

można rozmieścić na n spo-

sobów, tyle ile jest pudełek. Element x

2

można umieścić na n − 1 sposobów

w n − 1 pustych pudełkach oraz na dwa sposoby w pudełku zawierającym x

1

– otrzymując ciąg (x

1

, x

2

) lub (x

2

, x

1

). Oznaczmy przez s

i

liczbę elementów w

pudełku i-tym po rozmieszczeniu elementów {x

1

, . . . , x

k−1

}. Element x

k

można

teraz rozmieścić w i-tym pudełku na s

i

+ 1 sposobów, czyli w sumie na

n

X

i=1

(s

i

+ 1) = m +

n

X

i=1

s

i

= m + k − 1

sposobów. Stąd otrzymuje się wzór (1.2.4).

background image

1.3. Zadania

4

Na koniec kilka wzorów, których dowody pozostawione są jako zadania.

Potrzebne
wzory

(n)

m

= (n − m + 1) (n)

m−1

,

(1.2.5)

(n)

m

= n!/m! ,

(1.2.6)

(n)

m

= (m + n − 1)

m

.

(1.2.7)

Uwaga.

We wzorach (1.2.1) i (1.2.4) można zamiast n podstawić liczbę rze-

czywistą x, otrzymując definicje symboli (x)

m

i (x)

m

. Wzory (1.2.5) i (1.2.7)

pozostają prawdziwe i przyjmują postać Wtedy

(x)

m

= (x − m + 1) (x)

m−1

,

(1.2.8)

(n)

m

= (m + n − 1)

m

,

(1.2.9)

gdzie (x)

0

= (x)

0

= 1.

1.3. Zadania

1.

Wypisz wszystkie funkcje ze zbioru {a, b} w zbiór {A, B, C}. Ile wśród nich

jest funkcji różnowartościowych?

2.

Ile jest funkcji ściśle rosnących ze zbioru {a,b,c} w zbiór {1,2,3,...,100}?

3.

Ile jest funkcji ściśle rosnących ze zbioru {1,2,3,...,97} w zbiór

{

1,2,3,...,100}?

4.

Na ile sposobów możesz podzielić 20 osób na dwie (niekoniecznie niepu-

ste) grupy? Na ile sposobów możesz podzielić 20 osób na trzy (niekoniecznie
niepuste) grupy?

5.

Wypisz wszystkie możliwe ustawienia dwu osób w kolejkach do dwóch

(trzech) kas. Na ile sposobów można ustawić 20 osób w kolejkach do dwóch
(trzech) kas.

6.

Ile jest funkcji ze zbioru 10-elementowego na zbiór 2-elementowy? Ile na

3-elementowy?

7.

Wyznacz liczbę par (A, B), gdzie A ⊆ B ⊆ {1, 2, . . . , n}.

8.

Pewną pracę należy podzielić pomiędzy 3 kobiety, 4 chłopców oraz 5 męż-

czyzn. Na ile sposobów można to zrobić, przy założeniu, że mamy 3 stanowiska
pracy dla kobiet, 4 dla chłopców oraz 5 dla mężczyzn?

9.

Jak w zadaniu 8, ale dla kobiet i chłopców mamy tylko po 2 stanowiska

pracy.

10.

Mały Arturek ma pięć par butów. Wkładając buty kieruje się dwiema

zasadami:

1

Stirling ???

2

Robbins ???

background image

1.3. Zadania

5

a) nigdy nie wkłada lewego buta na lewą nogę, ani prawego na prawą,
b) nigdy nie wkłada dwu butów z tej samej pary.
Na ile sposobów może włożyć buty na obie nogi?

11.

Pewien bar oferuje 5 zup i 10 drugich dań, drugi – 6 zup i 8 drugich dań.

Ile różnych obiadów dwudaniowych masz do wyboru, jeżeli decydujesz się zjeść
obiad w jednym z tych dwu barów?

12.

Uogólnienie zadania 11. Bar Kombinatoryka oferuje n rodzajów dań:

przystawki, drugie dania, desery etc. Menu i-tego rodzaju dania ma k

i

pozycji.

Na ile sposobów można zjeść posiłek m-daniowy, gdy m ¬ n?

13*.

Na ile sposobów można ustawić na zwykłej szachownicy 8 wież tak, aby

się wzajemnie nie biły?

14.

Oznaczmy [N] = {1, 2, . . . , N}. W zbiorze [N] wprowadzimy relację czę-

ściowego porządku w następujący sposób: n ≺ m wtedy i tylko wtedy, gdy
m

jest podzielne przez n. Wyznaczyć elementy minimalne i maksymalne dla

danego N. Czy zbiorze [N] istnieją elementy najmniejszy i największy?

15**.

Pokazać, że liczba naturalna n ma nieparzystą liczbę dzielników (włą-

czając 1 i n) wtedy i tylko wtedy, gdy

n

jest liczbą całkowitą.

16.

Wyznaczyć wszystkie nieizomorficzne porządki częściowe na zbiorze czte-

roelementowym.

17.

Czy zbiór kół na płaszczyźnie o dowolnym środku i dowolnym promieniu

uporzadkowany przez zawieranie tworzy kratę?

18*.

Udowodnić, że w dowolnej kracie warunki

x

∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)

x

∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

dla wszystkich x, y, z, są równoważne.

19*.

Udowodnić, że

r

!(r + 1)

n−r

¬ n! ¬ r!n

n−r

.

20.

Sprawdzić, (przez napisanie programu), jaką dokładność ma oszacowanie

n

! dane wzorem Robbinsa (1.2.3).

background image

6

2. Permutacje

2.1. Grupy skończone

2.2. Rozkład permutacji na cykle

Permutację zbioru X = {x

1

, x

2

, . . . , x

n

}, czyli funkcję różnowartościową f :

X

→ X, gdzie elementy zbioru X wypisane są w dowolnym, ale ustalonym

porządku ≺, oznacza się zwykle jako tablicę o dwóch wierszach

f

=

x

1

x

2

. . . x

n

y

1

y

2

. . .

y

n

!

,

gdzie y

j

= f (x

j

). Jeżeli w górnym wierszu porządek jest ustalony, a zwłaszcza,

gdy X = {1, 2, . . . , n}, to wystarczy napisać tylko dolny wiersz, a więc zamiast

f

=

1 2 . . .

n

i

1

i

2

. . . i

n

!

,

gdzie i

j

= f (j), piszemy (i

1

, i

2

, . . . , i

n

).

Zbiór wszystkich permutacji zbioru n-elementowego zbioru X, oznacza się
przez S

n

. Jeśli w zbiorze tym wprowadzi jako działanie złożenie permutacji

Złożenie
permutacji

f

◦ g określone wzorem (f ◦ g) (x) = f (g (x)) dla każdego x ∈ X, to (S

n

,

◦)

tworzy grupę.
Niech f : X → X będzie permutacją zbioru X. Załóżmy, że istnieje podział

zbioru X na rozłączne części X

1

, X

2

, . . . , X

k

, tzn. X = X

1

∪ X

2

∪ · · · ∪ X

k

takie, że w każdym X

j

, x ∈ X

j

=⇒ f(x) ∈ X

j

, a żadnego z X

j

nie można

już podzielić na dwie niepuste części o tej własności. Wtedy X można upo-
rządkować w taki sposób, że każde X

j

składa się z kolejnych elemenentów,

X

j

= {x

j

1

, . . . , x

j

mj

} oraz

f

(x

j

1

) = x

j

2

, f

(x

j

2

) = x

j

3

, . . . , f

x

j

mj −1

= x

j+m

j

, f

x

j+m

j

= x

j

1

.

(2.2.1)

Każdy taki podzbiór (uporządkowany) X

j

⊆ X nazywa się cyklem, a przed-

Rozkład
permutacji na
cykle

stawienie X w postaci sumy cykli, nazywa się rozkładem permutacji na cykle.
Moc zbioru X

j

nazywa się długością cyklu X

j

.

Rozkład permutacji (x

1

, x

2

, . . . , x

n

) na cykle oznacza się

[x

1

, . . . , x

m

1

] [x

m

1

+1

, . . . , x

m

1

+m

2

] . . . [x

n−m

k

, . . . , x

n

],

gdzie m

j

jest długością j-tego cyklu. Permutacja f jest typu hλ

1

, . . . , λ

n

i, jeśli w

rozkładzie na cykle ma λ

i

cykli długości i, dla i = 1, 2, . . . , n. Typ ten zapisuje

się symbolicznie 1

λ

1

2

λ

2

. . . n

λ

n

, opuszczając i

λ

i

gdy λ

i

= 0. Permutację typu

n

1

= 1

0

2

0

. . .

(n − 1)

0

n

1

nazywa się cykliczną.

Przykład.

Graficznie rozkład permutacji na cykle można przedstawić jak na

rysunku 1. Przedstawiono na nim rozkład permutacji (7, 3, 4, 5, 6, 5, 1) na cykle
[1, 7][2, 3, 4][5, 6]. Permutacja ta jest typu 2

2

3

1

.

Para (x

i

, x

j

), i < j jest inwersją permutacji (x

1

, . . . , x

n

), jeśli x

j

≺ x

i

. Dla do-

Inwersja

background image

2.2. Rozkład permutacji na cykle

7

1

7

M

N

2

3

4

-

K

5

6

M

N

Rysunek 1. Rozkład permutacji na cykle

wolnej permutacji f przez I (f ) oznacza się liczbę jej inwersji. Znak permutacji
definiuje się wzorem

sgn (f ) = (−1)

I(f )

.

Permutacja jest parzysta, gdy sgn (f ) = 1, a w przeciwnym przypadku jest

Znak
permutacji

nieparzysta

. Permutacja tożsamościowa e jest zawsze parzysta.

Znak permutacji jest wykorzystany w znanej „permutacyjnej” definicji wy-
znacznika det (A) macierzy kwadratowej A = [a

ij

] wymiaru n × n:

det (A) =

X

(i

1

,...,i

n

)

sgn (i

1

, . . . , i

n

)

n

Y

j=1

a

ji

j

,

gdzie sumowanie przebiega po wszystkich permutacjach (i

1

, . . . , i

n

) ciągu

(1, . . . , n).
Lemat 2.2.1. Dowolną permutację f można przedstawić w postaci złożenia
I

(f ) transpozycji sąsiednich elementów.

Dowód.

???

Lemat 2.2.2. Dla dowolnych permutacji f, g

∈ S

n

sgn (f ◦ g) = sgn (f) sgn (g) .

Dowód.

???

Lemat 2.2.3. Jeśli permutacja f jest cyklem długości k, to jej znak wyraża
się wzorem sgn (f ) = (

−1)

k−1

.

Dowód.

???

Lemat 2.2.4. Jeśli permutacja f jest typu 1

λ

1

. . . n

λ

n

, to jej znak wyraża się

wzorem

sgn (f ) = (−1)

P

⌊n/2⌋
j=1

λ

2

j

.

Dowód.

???

background image

2.2. Rozkład permutacji na cykle

8

Poniższy program (w Pascalu) wyznacz znak permutacji.

Porównaj z
programem w
C++

Algorytm 2.2.1. Wejście: dowolna permutacja (f

∈ S

n

) dana w postaci ciągu

P

[1] . . . P [n].

Wyjście: znak permutacji sgn (f ).
function sgn_perm(f:perm):integer;
var i,j:1..max_perm;

s:integer;
new_p:array[1..max_perm] of boolean;

begin

s:=1;
with f do
begin

for j:=1 to n do new_p[j]:=true;
for i:=1 to n do

if new_p[i] then
begin

j:=p[i];
while j<>i do
begin

new_p[j]:=false;
s:=-s;
j:=p[j];

end;

end;

end;
sgn_perm:=s;

end;

Działanie algorytmu 2.2.1 jest proste: ???
Następujące twierdzenie pochodzi od Cauchy’ego

3

.

Twierdzenie 2.2.1. Liczba permutacji typu 1

λ

1

2

λ

2

. . . n

λ

n

zbioru n-ele-

mentowego jest równa

n

!

1

λ

1

2

λ

2

. . . n

λ

n

λ

1

2

! . . . λ

n

!

.

Dowód.

Zapis permutacji f typu 1

λ

1

2

λ

2

. . . n

λ

n

jest znormalizowany, gdy jest

postaci

f

= [a

(1)
0

a

(1)
1

. . . a

(1)
n

1

−1

] . . . [a

(k)
0

a

(k)
1

. . . a

(k)
n

k

−1

],

gdzie występuje kolejno λ

1

cykli długości 1, λ

2

cykli długości 2 itd. Porządek

w jakim występują cykle długości i można zmieniać na λ

i

sposobów. Każdy

taki cykl można przesuwać cyklicznie na i sposobów. Stąd każda permuta-
cja typu 1

λ

1

2

λ

2

. . . n

λ

n

jest określona przez 1

λ

1

2

λ

2

. . . n

λ

n

λ

1

2

! . . . λ

n

! zapisów

znormalizowanych.

3

Cauchy

background image

2.3. Liczby Stirlinga pierwszego rodzaju

9

2.3. Liczby Stirlinga pierwszego rodzaju

Liczby Stirlinga

4

pierwszego rodzaju określa się jako współczynniki s (n, k)

przy kolejnych potęgach x wielomianu (x)

n

, określonego wzorem:

(x)

n

=

n

X

k=0

s

(n, k) x

k

.

(2.3.1)

Twierdzenie 2.3.1. Liczby Stirlinga pierwszego rodzaju spełniają wzór re-
kurencyjny

s

(n, k) = s (n − 1, k − 1) − (n − 1) s (n − 1, k)

(2.3.2)

dla 0 < k < n oraz s (n, n) = 1 dla n

­ 0, s (n, 0) = 0 dla n > 0.

Dowód.

Niech 0 < k < n. Wtedy (x)

n

= (x)

n−1

(x − n + 1), skąd

n

X

k=0

s

(n, k) x

k

= (x − n + 1)

n−1

X

k=1

s

(n − 1, k) x

k

=

n−1

X

k=1

s

(n − 1, k − 1) x

k

− (n − 1)

n−1

X

k=0

s

(n − 1, k) x

k

.

Wzór (2.3.2) otrzymuje się przez porównanie współczynników przy x

k

.

Ze wzorów (2.3.1) i (2.3.2) można otrzymać również wzór

Symetria do
(2.3.1)

x

n

=

n

X

k=0

s

(n, k) (x)

k

.

(2.3.3)

Twierdzenie 2.3.2. Wartość bezwzględna liczby Stirlinga pierwszego rodzaju
jest równa liczbie permutacji zbioru n-elementowego, która ma rozkład na k
cykli.

Dowód.

???

Stąd jako prosty wniosek otrzymujemy

n

X

k=0

|s (n, k) | = n! .

Uwaga.

Liczby Stirlinga definiuje się też wzorem (por. [3])

Inna definicja

c

(n, k) = c (n − 1, k − 1) + (n − 1) c (n − 1, k) .

(2.3.4)

Wtedy liczby obliczone przy pomocy wzoru (2.3.4) są równe wartościom bez-
względnym liczb obliczonych według wzoru (2.3.2), czyli c (n, k) = |s (n, k) |.

4

Stirling

background image

2.4. Zadania

10

Liczby c (n, k) zwane są też nieznakowanymi liczbami Stirlinga pierwszego ro-
dzaju.
Twierdzenie 2.3.3. Dla dowolnych n

­ 0 i k ­ 0

c

(n, k) = (−1)

n+k

s

(n, k) .

Dowód.

???

2.4. Zadania

1.

Na ile sposobów można posadzić n osób przy okrągłym stole, gdy ważne

jest tylko, kto przy kim siedzi?

2.

Na ile sposobów można posadzić n osób przy okrągłym stole o m miejscach?

Zakładamy, że m < n oraz nie jest ważne, gdzie są umieszczone osoby, dla
których zabrakło miejsc przy stole.

3.

Ile jest takich permutacji zbioru n-elementowego w których ustalonych m

elementów nie stoi jeden obok drugiego?

4.

Tworzymy permutację zbioru {1, 2, . . . , n} w następujący sposób:
1. na pierwszym miejscu umieszczamy dowolny, na przykład losowo wybra-

ny element n

1

,

2. jeśli suma n

1

+ · · ·+ n

i−1

jest parzysta, to na miejscu i-tym umieszczamy

największą z dotychczas nie wybranych liczb,

3. jeśli suma n

1

+ · · · + n

i−1

jest nieparzysta, to na miejscu i-tym umiesz-

czamy najmniejszą z dotychczas nie wybranych liczb.

Utworzyć po dwie permutacje zbiorów o 5 i 7 elementach. Rozłożyć je na cykle
i znaleźć ich znak.

5.

Jak wyraża się znak permutacji utworzonej w zadaniu 4 w zależności od

wyboru elementu n

1

?

6

P

.

Napisać procedurę realizującą algorytm z zadania 4 dla dowolnego n.

7

P

.

Niech wybór elementu n

1

w zadaniu 4 będzie miał rozkład równomierny

w zbiorze {1, 2, . . . , n}. Poprze symulację komputerową znaleźć rozkład liczby

cykli dla ustalonych n.

8.

Ile jest możliwych rezultatów, którymi mogą się zakończyć zawody, w któ-

rych startuje 8 osób w trzech konkurencjach, jeśli każda osoba startuje w jed-
nej, dowolnie przez siebie wybranej konkurencji? Przez rezultat zawodów ro-
zumiemy zestawienie kolejności wszystkich zawodników starujących w każdej
konkurencji, przy czym mogą być konkurencje nie obsadzone.

9. Inwolucją

nazywa się permutację f taką, że f ·f = e, gdzie e jest permutacją

tożsamościową. Udowodnić, że f jest inwolucją zbioru n-elementowego wtedy
i tylko wtedy, gdy jest typu 1

λ

1

2

λ

2

oraz λ

1

+ 2λ

2

= n.

background image

2.4. Zadania

11

10.

Udowodnić, że n

n/2

< n

! < n

n

.

11.

Udowodnić, że dla n > 6

n

n/2

< n

! <

n

2

n

.

12.

Udowodnić, że dla dowolnych naturalnych k i n, liczba (k!)

n

jest podziel-

nikiem liczby (kn)! .

13

P

.

Napisać program a) prosty (rekurencyjny), b) efektywny na obliczanie

liczb Stirlinga pierwszego rodzaju.

14.

Pokazać, że

(x)

n

=

n

X

k=1

|s (n, k) |x

k

.

15.

Udowodnić, że średnia liczba cykli dla losowo wybranej permutacji zbioru

n

-elementowego wynosi

n

X

k=1

1

k

,

czyli

1

n

!

n

X

k=1

|s (n, k) | =

n

X

k=1

1
k

.

background image

12

3. Kombinacje

3.1. Współczynnik dwumianowy

Liczba podzbiorów k-elementowych zbioru n-elementowego, oznaczana jest
symbolem

n
k

, zwanym symbolem Newtona

5

lub współczynnikiem dwumia-

nowym

. Podzbiory takie nazywa się również kombinacjami k-wyrazowymi ze

zbioru

n-elementowego bez powtórzeń

. Zamiast symbolu

n
k

używany jest też

symbol C

k

n

. Dla k > n mamy oczywiście

n
k

= 0 oraz

0
0

= 1.

Nazwę „współczynnik dwumianowy” uzasadnia następujące twierdzenie.
Twierdzenie 3.1.1.

(x + y)

n

=

n

X

k=0

n
k

!

x

k

y

n−k

.

(3.1.1)

Dowód.

????

Twierdzenie 3.1.2.

Symbol
Newtona

n
k

!

=

(n)

k

k

!

=

n

!

k

! (n − k)!

.

(3.1.2)

Dowód.

Wiadomo, że (n)

k

jest liczbą ciągów różnowartościowych k-elemen-

towych ze zbioru n-elementowego. Każdy taki ciąg daje zbiór k-elementowy,
przy czym ten sam zbiór powstaje z dokładnie k! ciągów będących wszystkimi
permutacjami tego zbioru.

Symbol Newtona można uogólnić na przypadek

x
k

, gdy x jest dowolną liczbą

rzeczywistą lub zespoloną:

x
k

!

=

(x)

k

k

!

,

gdzie (x)

k

= x(x − 1) . . . (x − k + 1) jest wielomianem stopnia k, określonym

wzorem (1.2.8). Wtedy zgodnie ze wzorem (2.3.1), otrzymujemy

x
k

!

=

k

X

j=0

s

(k, j)

k

!

x

j

.

W szczególności dla k ­ 0

n
k

!

= (−1)

k

k

− n − 1

k

!

.

Do obliczeń

n
k

wygodnie jest stosować następujący wzór rekurencyjny:

n
k

!

=

n

− 1

k

!

+

n

− 1

k

− 1

!

,

(3.1.3)

dla n > 0 i k > 0. Ze wzoru (3.1.3) otrzymuje się trójkąt Pascala:

Trójkąt
Pascala

5

Newton

background image

3.1. Współczynnik dwumianowy

13

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

. . . . . . . . . . . . . . . . . . . . . . . . .

Ze wzoru (3.1.2) wynika wzór

n

0

!

<

n

1

!

<

· · · <

n

⌊n/2⌋

!

=

n

⌈n/2⌉

!

>

n

⌈n/2⌉ + 1

!

· · · >

n
n

!

(3.1.4)

dla n > 1. Zauważyć trzeba, że dla parzystego n mamy ⌊n/2⌋ = ⌈n/2⌉. Znane

są proste oszacowania z góry:

n
k

!

<

n

k

k

!

,

(3.1.5)

n
k

!

¬

n

n

k

k

(n − k)

n−k

.

(3.1.6)

Bardziej skomplikowane jest oszacowanie z dołu:

n

k

!

­

1

n

n+

1
2

k

k+

1
2

(n − k)

n−k+

1
2

exp

1

12n −

1

12k −

1

12(n − k)

!

.

(3.1.7)

Z oszacowań tych wynika, że

n

k

szybko rośnie wraz ze wzrostem n i k rosną-

cym proporcjonalnie do n. Łatwo to zauważyć, pisząc procedurę obliczającą
wartości współczynników dwumianowych.
Twierdzenie 3.1.3.

l

+ r

k

!

=

k

X

t=0

l
t

!

r

k

− t

!

.

(3.1.8)

Równość (3.1.8) jest znana jako tożsamość Cauchy’ego.
Z twierdzenia 3.1.3 wynikają dla nieujemnych l, m, n, q, r, s kolejne wzory:

Jak zmienia
się k?

X

k

r

m

+ k

!

s

n

− k

!

=

r

+ s

m

+ n

!

X

k

l

m

+ k

!

s

n

+ k

!

=

l

+ s

l

− m + n

!

X

k

l

m

+ k

!

s

+ k

n

!

(−1)

k

= (−1)

l+m

s

− m

n

− l

!

Uogólnieniem współczynników dwumianowych są współczynniki wielomiano-
we.

a

1

+ a

2

+ · · · + a

n

a

1

, a

2

, . . . , a

n

!

=

(a

1

+ a

2

+ · · · + a

n

)

a

1

!a

2

! . . . a

n

!

.

(3.1.9)

background image

3.2. Generowanie podzbiorów

14

Nazwa pochodzi stąd, że

(x

1

+ x

2

+ · · · + x

k

)

n

=

X

a1+···+an

0

¬ai¬n

a

1

+ a

2

+ · · · + a

n

a

1

, a

2

, . . . , a

n

!

x

a

1

1

x

a

2

2

. . . x

a

n

k

.

(3.1.10)

Wzory (3.1.9) i (3.1.10) są uogólnieniami wzorów (3.1.1) i (3.1.2) odpowiednio.

3.2. Generowanie podzbiorów

Niech X = {1, 2, . . . , n}. Każdemu podzbiorowi k-elementowemu odpowiada

rosnący podciąg k-elementowy. W zbiorze podciągów k-elementowych wpro-
wadzimy porządek leksykograficzny (słownikowy) w następujący sposób: jeżeli

Porządek lek-
sykograficzny

a

= (a

1

, a

2

, . . . , a

k

) i b = (b

1

, b

2

, . . . , b

k

) oraz dla pewnego j jest a

i

= b

i

dla

i < j

oraz a

j

< b

j

to a ≺ b. Oczywiście, jeśli a

1

< b

1

to również a ≺ b. Tak

określoną relację ≺ można przenieść z ciągów na podzbiory.
Teraz można podać algorytm generujący wszystkie podzbiory k-elementowe
zbioru X w porządku leksykograficznym. Wystarczy zauważyć, że ciągiem na-
stępującym po a = (a

1

, . . . , a

k

) jest ciąg

b

= (b

1

, . . . , b

k

) = (a

1

, . . . , a

p−1

, a

p

+ 1, a

p

+ 2, . . . , a

p

+ k − p + 1)

gdzie p = max{i : a

i

< n

− k + 1}. Po ciągu b następuje ciąg

c

= (c

1

, . . . , c

k

) =

b

1

, . . . , b

p

−1

, b

p

+ 1, b

p

+ 2, . . . , b

p

+ k − p + 1

gdzie

p

=

p

− 1 jeśli b

k

= n,

k

jeśli b

k

< n

.

Zakłada się, że ciągi a i b są różne od ciągu (n − k + 1, . . . , n) – ostatniego

ciągu w tym porządku. Stąd algorytm.
????

procedure gen_k_subset(n,k:integer);
var i,j,p:integer;

a:array[1..max_set] of integer;

begin

for i:=1 to k do a[i]:=i; {pierwszy podzbiór}
p:=k;
while p>=1 do
begin

for j:=1 to k do write(a[j]:8);
writeln;
if a[k]=n then p:=p-1 else p:=k;
if p>=1 then

for i:=k downto p do a[i]:=a[p]+i-p+1;

end;

end;

background image

3.3. Zbiory z powtórzeniami

15

3.3. Zbiory z powtórzeniami

Uogólnieniem pojęcia zbioru (w którym każdy element występuje dokładnie
raz), jest pojęcie zbioru z powtórzeniami. W takim zbiorze, każdy element mo-
że wystąpić kilkakrotnie, a liczba wystąpień nazywa się krotnością elementu.
Istotna jest tu tylko krotność elementu, a nieistotna jest kolejność wystąpień.
Zbiór taki oznacza się albo wypisując element tyle razy, ile wynosi jego krot-
ność, albo gdy dla krotności równej k elementu a, pisząc {. . . , k ∗ a, . . . }.
Przykład.

Jeśli X = {2 ∗ a, 3 ∗ b, 1 ∗ c}, to również X = {a, b, a, b, c, b} =

{a, a, b, b, b, c}, ale X 6= {a, b, c}.
Zbiór A jest podzbiorem zbioru B, A ⊆ B, gdy krotność każdego elementu w
A

jest nie większa od krotności tego samego elementu w B. Liczbę elementów

k

w zbiorze X = {k

1

∗ x

1

, . . . , k

n

∗ x

n

} (liczność zbioru X), definiuje się jako

k

= k

1

+ · · · + k

n

.

Twierdzenie 3.3.1. Liczba k-elementowych zbiorów z powtórzeniami o ele-
mentach ze zbioru n-elementowego (bez powtórzeń) jest równa

n

+ k − 1

k

!

.

(3.3.1)

Twierdzenie 3.3.2. ????

Twierdzenie to można również sformułować w terminach funkcji (patrz roz-
dział 1.2).
Twierdzenie 3.3.3. Istnieje dokładnie

n+k−1

k

funkcji niemalejących f :

{1, . . . , k} → {1, . . . , n}.
Twierdzenie 3.3.4. ????

Przykład.

Niech A = {a, b, c} (czyli n = 3) oraz k = 2. Zgodnie ze wzorem

(3.3.1), z elemntów zbioru A można utworzyć

n

+ k − 1

k

!

=

4
2

!

= 6

dwuelementowych podzbiorów z powtórzeniami:

{a, a} , {a, b} , {a, c} , {b, b} , {b, c} , {c, c} .

Zbiorów czteroelementowych z powtórzeniami można zaś utworzyć

6
4

!

=

6
2

!

= 15.

Zachodzi równość:

n

+ k − 1

k

!

=

(n)

k

k

!

.

background image

3.4. Zadania

16

3.4. Zadania

1.

Oblicz

10

7

.

2.

Co jest większe

100

37

czy

101

55

?

3.

Na ile sposobów można utworzyć koalicję większościową w 459-osobowym

sejmie? A na ile w 460-osobowym? Wynik podaj w możliwie prostej postaci.

4.

Stoisz w lewym dolnym rogu szachownicy. W jednym kroku poruszasz się o

jedno pole w prawo lub o jedno pole do góry. Po 14 krokach będziesz w prawym
górnym rogu. Na ile sposobów możesz odbyć tę wędrówkę?

5.

Na ile sposobów spośród 7 łysych i 8 rudych możesz wybrać pięcioosobową

delegację w której składzie jest dokładnie 2, (0,1,3,4,5) rudych?

6.

Udowodnić tożsamość

n

m

!

m

k

!

=

n

k

!

n

− k

m

− k

!

7.

Pokazać korzystając z tożsamości Cauchy’ego, że

2n

n

!

=

n

X

r=0

n

r

!

2

.

8.

Udowodnić przez indukcję oraz czysto kombinatorycznie, że

n

X

k=0

r

+ k

k

!

=

r

+ n + 1

n

!

oraz

n

X

k=r

k

r

!

=

n

+ 1

r

+ 1

!

.

9.

Pokazać, że

n

X

r=0

(−1)

r

n

r

!

= 0 .

Wskazówka.

Oblicz (1 − 1)

n

na dwa sposoby.

10.

Udowodnić wzór

m

X

k=0

m

k

!

n

+ k

m

!

=

m

X

k=0

n
k

!

m

k

!

2

k

.

11.

Jak wiele istnieje zbiorów k-elementowych zbioru {1, 2, . . . , n}, które nie

zawierają żadnej pary dwóch kolejnych liczb?

background image

3.4. Zadania

17

12.

Udowodnić wzór Leibniza

d

n

(uv)

dx

n

=

n

X

k=0

n
k

!

d

k

u

dx

k

d

(n−k)

v

dx

(n−k)

,

gdzie u i v są funkcjami jednej zmiennej x.

13.

Udowodnić wzór

n

k

1

, k

2

, . . . , k

m

!

=

n

− 1

k

1

− 1, k

2

, . . . , k

m

!

+

n

− 1

k

1

, k

2

− 1, k

3

, . . . , k

m

!

+ · · · +

n

− 1

k

1

, k

2

, . . . , k

m−1

, k

m

!

,

gdzie n ­ 1, k

1

+ k

2

+ · · · + k

m

= n, k

i

>

0.

14.

Udowodnić nierówność

n
k

!

¬

en

k

.

15

P

.

Napisać procedurę wypisującą wszystkie k-elemntowe zbiory z powtó-

rzeniami o elementach ze zbioru n elementowego, o którym mowa w twierdze-
niu 3.3.1.

background image

18

4. Podziały

4.1. Zasada włączania – wyłączania

Obliczmy liczbę elementów sumy zbiorów. Oczywisty jest wzór:

Dwa zbiory

|A ∪ B| = |A| + |B| − |A ∩ B| ¬ |A| + |B| ,

(4.1.1)

prawdziwy dla dowolnych zbiorów A i B. Dla trzech zbiorów A, B i C mamy

Trzy zbiory

|A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ B| ¬

¬ |A ∪ B ∪ C| =

(4.1.2)

= |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ B| + |A ∩ B ∩ C| .

Jak widać ze wzorów (4.1.1) i (4.1.2), dodając do siebie liczby elementów dwóch
zbiorów, dwukrotnie liczymy część wspólną – trzeba ją odjąć. Dla trzech zbio-
rów, odejmując trzykrotnie części wspólne par zbiorów, odejmujemy o jeden
raz za dużo część wspólną wszystkich trzech podzbiorów – trzeba ją więc do-
dać. Powtarzając to rozumowanie, otrzymujemy następujący wynik, znany jako
zasadę włączanie-wyłączania.
Twierdzenie 4.1.1. Jeśli dla dowolnego ciągu (A

1

, . . . , A

n

) niekoniecznie róż-

Zasada
włączania-
wyłączania

nych podzbiorów zbioru X:

A

= A

1

∪ · · · ∪ A

n

,

to

|A| =

n

X

i=1

|A

i

| −

X

1¬i<j¬n

|A

i

∩ A

j

| +

X

1¬i<j<k¬n

|A

i

∩ A

j

∩ A

k

| − · · · +

+ (−1)

n−1

|A

1

∩ · · · ∩ A

n

| .

(4.1.3)

Dowód.

(Przez indukcję). Wzór (4.1.3) jest oczywisty dla n = 1, (także dla

n

= 2 – wzór (4.1.1) i dla n = 3 – wzór (4.1.2)). Przyjmijmy, że wzór (4.1.3)

jest prawdziwy dla n − 1, czyli dla A

= A

1

∪ · · · ∪ A

n−1

prawdziwy jest wzór

|A

| =

n−1

X

i=1

|A

i

| −

X

1¬i<j¬n−1

|A

i

∩ A

j

| +

X

1¬i<j<k¬n

|A

i

∩ A

j

∩ A

k

| − · · · +

+ (−1)

n−2

|A

1

∩ · · · ∩ A

n−1

| .

Ponieważ

A

∩ A

n

=

n−1

[

i=1

(A

i

∩ A

n

) ,

background image

4.1. Zasada włączania – wyłączania

19

to

|A

∩ A

n

| =

n−1

X

i=1

|A

i

∩ A

n

| −

X

1¬i<j¬n−1

|A

i

∩ A

j

∩ A

n

| + · · · +

+ (−1)

n−2

|A

1

∩ · · · ∩ A

n

| ,

skąd

|A| = |A

∪ A

n

| = |A

| + |A

n

| − |A

∩ A

n

| ,

co daje wzór (4.1.3).

Rozważmy problem ogólniejszy. Niech D (r) oznacza liczbę elementów zbioru
tych x ∈ X, które należą do dokładnie r zbiorów A

1

, A

2

, . . . , A

n

, r ¬ n. Niech

1 ¬ i

1

<

· · · < i

r

¬ n będzie dowolnym ciągiem. Przyjmijmy oznaczenia:

N

(i

1

. . . , i

r

) = |A

1

∩ . . . A

i

r

|

(4.1.4)

oraz

W

(r) =

X

N

(i

1

, . . . , i

r

) ,

(4.1.5)

gdzie sumowanie przebiega po wszystkich ciągach 1 ¬ i

1

<

· · · < i

r

¬ n.

Przyjmiemy też W (0) = |X|.
Twierdzenie 4.1.2. Dla dowolnych n > 0 oraz r

¬ n

D

(r) =

n−r

X

j=0

(−1)

−1

r

+ j

r

!

W

(r + j) .

(4.1.6)

Dowód.

Wzór (4.1.2) zapiszmy w postaci

X

x∈X

L

(x) =

X

x∈X

R

(x)

gdzie

L

(x) =

1, gdy x nalezy do dokładnie r zbiorów A

i

,

0

w przeciwnym przypadku.

Podobnie

R

(x) =

n−r

X

j=0

(−1)

j

r

+ j

r

!

R

r+j

(x) ,

(4.1.7)

gdzie R

r+j

(x) jest liczbą ciągów postaci 1 ¬ i

1

<

· · · < i

r+j

¬ n takich,

że x ∈ A

i

∩ · · · ∩ A

i

r

+j

. Trzeba pokazać, że dla każdego x ∈ X zachodzi

L

(x) = R (x).

Niech x ∈ X oraz x należy do dokładnie u zbiorów A

i

. Mamy tu trzy możliwe

przypadki:

background image

4.1. Zasada włączania – wyłączania

20

(i) u < r. Wtedy L (x) = 0 oraz R (x) = 0, bo x /

∈ A

i

1

∩ · · · ∩ A

i

n

.

(ii) u = r. Wtedy l (x) = 1 i R (x) = 1, bo R

r+j

(x) = 0 dla j > 0 oraz

(−1)

0

r+0

r

R

r+0

(x) = R

r

(x) = 1.

(iii) u > r. Wtedy L (x) = 0 oraz R

m

(x) =

u

m

. Podstawiając tę wartość do

(4.1.7) i korzystając z tożsamości

n

m

!

m

k

!

=

n
k

!

n

− k

m

− k

!

(patrz zadanie 6) oraz

n

X

r=0

(−1)

r

n

r

!

= 0 .

(patrz zadanie 9 z rodz. 3.1) otrzymuje się

R

(x) =

n−r

X

j=0

(−1)

j

r

+ j

r

!

u

r

+ j

!

=

u−r

X

j=1

(−1)

j

r

+ j

r

!

u

r

+ j

!

=

u−r

X

j=1

(−1)

j

u

r

!

u

− r

u

− r − j

!

=

u

r

!

u−r

X

j=0

(−1)

j

u

− r

j

!

= 0.

Zasadę włączania-wyłączania można teraz sformułować jako
Twierdzenie 4.1.3.

D

(0) =

n

X

j=0

(−1)

j

W

(j) .

Z twierdzenia 4.1.3 wynikają nastepujące twierdzenia.
Twierdzenie 4.1.4. Jeśli

|X| = n oraz |Y | = m, to liczba s

nm

funkcji z X

na Y jest równa

s

nm

=

m

X

j=0

(−1)

j

m

j

!

(m − j)

n

.

Nieporzadek

na zbiorze X jest permutacją f taka, że f (x) 6= x dla każdego

x

∈ X. Liczba nieporządków D

n

dla |X| = n podana jest w nastepującym

twierdzeniu.
Twierdzenie 4.1.5. Liczba nieporządków D

n

dla

|X| = n dana jest wzorem

D

n

=

n

X

j=0

(−1)

j

n

j

!

(n − j)! = n!

n

X

j=1

(−1)

j

j

!

.

(4.1.8)

Ze wzoru (4.1.8) wynika, że przy n → ∞ nieporządki stanowią e

−1

=

0.36788 . . . wszystkich permutacji.

background image

4.2. Liczby Stirlinga drugiego rodzaju

21

4.2. Liczby Stirlinga drugiego rodzaju

Niech π = {B

1

, B

2

, . . . , B

k

} będzie rodziną podzbiorów zboru X taką, że B

1

B

2

∪ · · · ∪ B

k

= X, B

i

∩ B

j

= ∅ dla i 6= j oraz B

i

6= ∅ dla 1 ¬ i ¬ k. Rodzinę

π

nazywą się podziałem zbioru X na k bloków. Zbiór wszystkich podziałów

zbioru X na k bloków oznacza się przez Π

k

(X), a zbiór wszystkich podziałów

przez Π (X).
Podział Π zbioru n-elementowego zbioru X jest typu λ = (λ

1

, . . . , λ

n

), jeśli

zawiera λ

i

bloków i-elementowych. Typ taki zapisujemy jako 1

λ

1

2

λ

2

. . . n

λ

n

.

Twierdzenie

4.2.1.

Liczba podziałów typu 1

λ

1

2

λ

2

. . . n

λ

n

zbioru n-

elementowego, n = λ

1

+ 2λ

2

+ · · · + nλ

n

= n jest równa

P

1

, . . . , λ

n

) =

n

!

λ

1

2

! . . . λ

n

! (1!)

λ

1

(2!)

λ

2

. . .

(n!)

λ

n

.

Liczby Stirlinga drugiego rodzaju określa się wzorem

x

n

=

n

X

k=0

S

(n, k) (x)

k

(4.2.1)

lub równoważnie

(x)

n

=

n

X

k=0

S

(n, k) x

k

.

(4.2.2)

Twierdzenie 4.2.2. Definicje liczb Stirlinga określone wzorami (4.2.1) i
(4.2.2) są równoważne.

Dowód.

????

Twierdzenie 4.2.3. Liczby Stirlinga drugiego rodzaju spełniają wzór reku-
rencyjny

S

(n, k) = S (n − 1, k − 1) + kS (n − 1, k)

(4.2.3)

dla 0 < k < n oraz S (n, n) = 1 dla n

­ 0, S (n, 0) = 0 dla n > 0.

Twierdzenie 4.2.4.

S

(n, k) = |Π

k

(X) |

(4.2.4)

gdzie

|X| = n.

Z twierdzenia 4.2.1 wynika wzór

S

(n, k) =

X

λ1+···+λn=k

λ1+nλn

n

!

λ

1

2

! . . . λ

n

! (1!)

λ

1

(2!)

λ

2

. . .

(n!)

λ

n

.

background image

4.2. Liczby Stirlinga drugiego rodzaju

22

Liczby Bella

6

definiuje się wzorem

B

n

=

n

X

k=0

S

(n, k) ,

czyli B

n

= |Π (X) |.

Zachodzi równość

B

n+1

=

n

X

i=0

n

i

!

B

i

,

gdzie B

0

= 0.

Twierdzenie 4.2.5.

Jeśli

|X| = n, |Y | = m, to liczba wszystkich funkcji

Przykład
zastosowania
liczb Stirlinga

f

: X

na

→ Y , (f(X) = Y ), jest równa

s

n,m

=

m−1

X

i=0

(−1)

i

m

n

!

(m − i)

n

.

(4.2.5)

Dowód.

Niech Y = {y

1

, . . . , y

m

} oraz niech A

i

= {f : y

i

/

∈ f (X)}. Wtedy

f

(X) = Y ⇐⇒ f ∈

m

[

i=1

A

i

.

Wszystkich funkcji f : X → Y jest m

n

, (twierdzenie 1.2.1). Szukamy więc

|A

1

∪ · · · ∪ A

m

|. Aby skorzystać z twierdzenia 4.1.1, trzeba znać liczebność

iloczynu A

k

1

∩ · · · ∩ A

k

j

dla dowolnego ciągu 1 ¬ k

1

<

· · · < k

j

¬ m. Iloczyn

ten jest zbiorem wszystkich funkcji f : X → Y \

n

y

k

1

, . . . , y

k

j

o

, więc jego

liczebność wynosi (m − j)

n

. Ciąg 1 ¬ k

1

<

· · · < k

j

¬ m można wybrać na

m

j

sposobów, więc

s

n,m

= m

n

m−1

[

j=0

A

j

= m

n

m−1

X

j=1

(−1)

j

m

j

!

(m − j)

n

=

m−1

X

j=0

(−1)

j

m

j

!

(m − j)

n

,

co dowodzi wzoru (4.2.5).

Pokażemy teraz, że

s

n,m

= m!S (n, m) .

Istotnie ????
Stąd otrzymuje się wzór na liczby Stirlinga drugiego rodzaju:

S

(n, k) =

1

k

!

k−1

X

j=0

(−1)

j

k

j

!

(k − j)

n

.

Związek z dzielnikami liczb ????

6

Bell

background image

4.3. Zadania

23

4.3. Zadania

1.

Ile dzielników ma liczba 216000?

2.

Na ile sposobów możesz rozbić zbiór 10-elementowy na zbiory 2-elementowe,

a na ile sposobów możesz rozbić zbiór 2n-elementowy na takie podzbiory?

3.

Wyznaczyć liczbę ciągów długości 2n takich, że każda liczba i ∈ {1 . . . , n}

występuje dokładnie dwa razy, przy czym żadne dwa kolejne wyrazy nie są
równe.

4.

Na pewnej wyspie mieszka 300 dzikusów, z których każdy jest matematy-

kiem, filozofem lub ludożercą. Połowa ludożerców zajmuje się filozofią, połowa
filozofów to matematycy, a połowa matematyków to ludożercy. Wiedząc, że
żaden z ludożerców nie zajmuje się filozofią i matematyką jednocześnie, ustal
z ilu osób składa się każda z tych grup.

5.

Wyznaczyć liczbę podzbiorów 11-elementowych zbioru z powtórzeniami

{4 ∗ a, 3 ∗ b, 7 ∗ c}.

6.

(Wzór Faa di Bruno). Udowodnić, że

d

n

dx

n

f

(g (x)) =

n

X

j=0

X

k1+k2+···+kn=j

k1+2k2+···+nkn=n

k1,k2,...,kn­0

f

(j)

n

!

g

(1)

k

1

. . .

g

(n)

k

n

k

1

! (1!)

k

1

. . . k

n

! (n!)

k

n

.

background image

24

5. Funkcje tworzące

5.1. Szeregi formalne

Definicja.

Niech a

k

będzie ciągiem liczbowym. Funkcją tworzącą nazywa się

szereg formalny

A

(x) =

X

k=0

a

k

x

k

.

(5.1.1)

Nazwa „szereg formalny” oznacza, że wzór (5.1.1) określa takie własności sze-
regów jak ich dodawanie, mnożenie, mnożenie przez liczbę, natomiast nie bada
się ich zbieżności.
Szereg formalny

b

A

(x) =

X

k=0

a

k

x

k

k

!

(5.1.2)

nazywa się wykładniczą funkcją tworzącą.

Dla szeregów A (x) =

X

k=0

a

k

x

k

i B (x) =

X

k=0

b

k

x

k

określa się operacje:

Operacje na
szeregach

dodawanie:

A

(x) + B (x) =

X

k=0

(a

k

+ b

k

) x

k

,

mnożenie przez liczbę:

αA

(x) = αA (x) =

X

k=0

a

k

x

k

,

mnożenia:

A

(x) B (x) =

X

k=0

c

k

x

k

,

gdzie

c

k

=

k

X

i=0

a

i

b

k−i

.

Jeżeli szereg (5.1.1) jest zbieżny do funkcji f (x) = A (x) dla pewnego promie-
nia zbieżności r > 0, to będziemy utożsamiać szereg formalny (5.1.1) z funkcją
f

(x) również dla |x| > r. Wtedy

A

(x) =

X

k=0

(k + 1) a

k+1

x

k

.

background image

5.2. Rozwiązywania rekurencji

25

Przykład.

e

x

=

X

k=0

1

k

!

x

k

dla a

k

= 1/k!,

1

1 − x

=

X

k=0

x

k

dla a

k

= 1,

(1 + x)

n

=

X

k=1

n
k

!

x

k

=

n

X

k=1

n
k

!

x

k

dla a

k

=

n
k

.

Twierdzenie 5.1.1. Szereg (5.1.1) ma szereg odwrotny względem mnożenia
wtedy i tylko wtedy, gdy jego wyraz wolny jest różny od zera.

Przykład.

X

k=0

x

k

!

−1

= 1 − x .

Przykład.

Następującą tożsamość można udowodnić, korzystając z funkcji

tworzących:

m

+ k

k

!

=

k

X

s=0

m

s

!

n

k

− s

!

.

Porównamy współczynniki po obu stronach równości:

m+n

X

k=0

m

+ n

k

!

x

k

= (1 + x)

m+n

= (1 + x)

m

(1 + x)

n

=

m

X

i=0

m

i

!

x

i

n

X

j=0

n

j

!

x

j

=

m+n

X

k=0

k

X

s=0

m

s

!

n

k

− s

!

x

k

.

5.2. Rozwiązywania rekurencji

Problem:

dla danego ciągu {g

n

} spełniającego pewne równanie rekurencyjne,

znaleźć jawny wzór na g

n

jako funkcji n. Rozwiązanie jest następujące.

Algorytm
rozwiązywania

1. Napisać równanie g

n

= f (g

n

, . . . , g

n−k

) dla całkowitych n i pewnego k,

przy czym g

−1

= g

−2

= · · · = 0.

2. Pomnożyć obie strony równania przez x

n

i zsumować. Otrzyma się rów-

nanie

X

n

g

n

x

n

= h (G (x)) ,

background image

5.3. Zastosowania funkcji tworzących

26

3. Rozwiązać równanie ze względu na G (x).
4. Rozwinąć G (x) w szereg potęgowy. Współczynnik przy x

n

jest równy g

n

.

Rozpatrzymy przykład z liczbami Fibonacciego

7

, w oparciu o powyższy sche-

Liczby
Fibonacciego

mat. Liczby Fibonacciego są określone wzorem

1. Równanie rekurencyjne

g

n

=

0,

dla n ¬ 0,

1,

dla n = 1,

g

n−1

+ g

n−2

dla n > 1.

(5.2.1)

Inaczej

g

n

= g

n−1

+ g

n−2

+ [n = 1]

2. Równanie na funkcję tworzącą

G

(x) =

X

n

g

n

x

n

=

X

n

g

n−1

x

n

+

X

n

g

n

2

+

X

n

[n = 1]x

n

=

X

g

n

x

n+1

+

X

n

g

n

x

n+2

+ x

= xG (x) + x

2

G

(x) + x.

(5.2.2)

3. Rozwiązanie równania na funkcję tworzącą

G

(x) =

x

1 − x − x

2

.

(5.2.3)

4. Rozkładamy na G (x) na ułamki proste.

Pierwiastkami równania 1 − x − x

2

= 0 są a =

1 +

5

/

2 oraz b =

1 −

5

/

2. Dla A = a/ (a − b) i B = −b/ (a − b) otrzymujemy

G

(x) =

A

1 − ax

+

B

1 − bx

=

X

k=0

a

k+1

− b

k+1

a

− b

x

k

skąd

Złoty podział

g

k

=

1

5

1 +

5

2

!

k+1

1 −

5

2

!

k+1

.

(5.2.4)

5.3. Zastosowania funkcji tworzących

Funkcja tworząca dla współczynników dwumianowych dla ustalonego n:

X

k=0

n
k

!

x

k

=

n

X

k=0

n
k

!

x

k

= (1 + x)

n

.

7

Leonardo Fibonacci, 1180 – 1250

background image

5.3. Zastosowania funkcji tworzących

27

Interpretacja kombinatoryczna: niech X

=

{e

1

, . . . , e

n

}. W iloczynie

(1 + x)

n

= (1 + x) . . . (1 + x), i-ty czynnik (1 + x) można traktować jako od-

powiednik elementu e

i

i reprezentujący liczby wystąpień elementu e

i

– zero

razy (x

0

= 1) i jeden raz (x

1

= x). Rozumowanie to można uogólnić na przy-

padek zbiorów z powtórzeniami, wtedy i-ty czynnik (1 + x + · · · + x

j

) może

reprezentować liczbę wystąpień elementu.
Przykład.

Niech X = {3∗a, 1∗b, 2∗c} oraz niech c

k

będzie liczbą podzbiorów

k

-elementowych tego zbioru. Wtedy

X

k=0

c

k

x

k

=

1 + x + x

2

+ x

3

(1 + x)

1 + x + x

2

= 1 + 3x + 5x

+

6x

3

+ 5x

4

+ 3x

5

+ x

6

.

Stąd liczba podzbiorów dwuelementowych wynosi 5.

Na liczbę wystąpień e

i

można nakładać ograniczenia.

Twierdzenie 5.3.1. Niech X =

{e

1

, . . . , e

n

} oraz niech c

k

oznacza liczbę k-

elementowych zbiorów A z powtórzeniami, o elementach z X takich, że dla
i

= 1, . . . , n krotność elementu e

i

należy do zbioru

{r

i1

, r

i2

, . . .

}, gdzie 0 ¬

r

i1

¬ r

i2

, . . . . Wtedy funkcja tworząca dla ciągu c

0

, c

1

, . . . jest równa

C

(x) =

X

k=0

c

k

x

k

= (x

r

11

+ x

r

12

+ . . .) (x

r

21

+ x

r

22

+ . . .) . . . (x

r

n1

+ x

r

n2

+ . . .) .

Przykład.

Jeżeli nie nakładamy żadnych ograniczeń, to

1 + x + x

2

+ . . .

n

=

1

(1 − x)

n

.

Rozwijając tę funkcję w szereg MacLaurina otrzymujemy

d

k

dx

k

(1 − x)

−n

= (−n) (−n − 1) . . . (−n − k + 1) (1 − x)

−n−k

(−1)

k

= (n)

k

(1 − x)

−n−k

.

Stąd

(1 − x)

−n

=

X

k=0

(n)

k

k

!

x

k

=

X

k=0

n

+ k − 1

k

!

x

k

,

(porównaj twierdzenie 3.3.1).
Jeżeli liczba wystąpień ma być różna od zera, to funkcja tworząca będzie równa

x

+ x

2

+ . . .

n

=

x

n

(1 − x)

n

.

Twierdzenie 5.3.2. Niech X =

{e

1

, . . . , e

n

} oraz niech c

k

oznacza liczbę

k-elementowych ciągów o elementach z X takich, że dla i = 1, . . . , n liczba

background image

5.4. Sploty

28

wystąpień elementu e

i

należy do zbioru

{r

i1

, r

i2

, . . .

}, gdzie 0 ¬ r

i1

¬ r

i2

, . . . .

Wtedy wykładnicza funkcja tworząca dla ciągu c

0

, c

1

, . . . jest równa

C

(x) =

X

k=0

c

k

x

k

k

!

=

x

r

11

r

11

!

+

x

r

12

r

12

!

+ . . .

x

r

21

r

21

!

+

x

r

22

r

22

!

+ . . .

. . .

x

r

n1

r

n1

!

+

x

r

n2

r

n2

!

+ . . .

.

5.4. Sploty

Sploty Fibonacciego.

Należy znaleźć wzór na

F

n

=

n

X

k=0

f

k

f

n−k

,

gdzie f

k

jest k-tą liczbą Fibonacciego. Ciąg {F

n

} jest splotem ciagu {f

n

} z

sobą. Liczby Fibonacciego mają funkcję tworzącą daną wzorem (5.2.3)

G

(x) =

x

1 − x − x

2

,

Liczby F

n

mają zaś funkcję tworzącą F (x) = (G (x))

2

. Stąd, otrzymujemy

F

(x) =

1
5

X

n=0

(n + 1) (2f

n+1

− f

n

) x

n

2
5

X

n=0

f

n+1

x

n

.

Ostatecznie otrzymujemy

F

n

=

n

X

k=0

f

k

f

n−k

=

2nf

n+1

− (n + 1) f

n

5

.

Sploty harmoniczne.

Efektywność algorytmu „samplesort” zależy od war-

tości sumy

t

m,n

=

n−1

X

k=0

k

m

!

1

m

− k

dla całkowitych m, n > 0. Aby obliczyć t

m,n

zauważmy, że ciąg {t

m,n

} jest

splotem ciągu

0

m

!

,

1

m

!

,

2

m

!

, . . .

z ciągiem 0, 1/1, 1/2, . . . . Ciągi te mają znane funkcje tworzące

X

n=0

n

m

!

x

n

=

x

m

(1 − x)

m+1

;

X

n=0

x

n

n

= ln

1

1 − x

.

background image

5.4. Sploty

29

Stąd funkcja tworząca T

m

(x) dla ciągu {t

m,n

} wyraża się wzorem

Liczby
harmoniczne

T

m

(x) =

x

m

(1 − x)

m+1

ln

1

1 − x

= (H

n

− H

m

)

n

n

− m

!

,

gdzie

H

n

= 1 +

1
2

+ · · · +

1

n

są liczbami harmonicznymi.
Drzewem binarnym T o n wierzchołkach nazywa się drzewo puste T = ∅, gdy
n

= 0 lub trójkę T = (L, r, P ), gdzie r jest wierzchołkiem zwanym korzeniem

drzewa

, L jest drzewem binarnym o l wierzchołkach P jest drzewem binarnym

o p wierzchołkach oraz l + p + 1 = n. Drzewa binarne T

1

i T

2

są izomorficzne,

T

1

≈ T

2

gdy T

1

= T

2

= ∅ lub gdy T

1

= (L

1

, r, P

1

), T

2

= (L

2

, r, P

2

) oraz

L

1

≈ L

2

i P

1

≈ P

2

. Niech c

k

oznacza liczbę nieizomorficznych drzew binarnych

o k wierzchołkach. Oczywiście c

0

= 1 oraz dla 0 ¬ s ¬ k istnieje c

s

c

k−1−s

nieizomorficznych drzew binarnych (L, r, P ) takich, że L ma s wierzchołków.
Wobec tego dla k > 0

c

k

= c

0

c

k−1

+ c

1

c

k−2

+ · · · + c

k−1

c

0

,

(5.4.1)

Niech

C

(x) =

X

k=0

c

k

x

k

będzie funkcją tworzącą dla ciagu określonego wzorem (5.4.1). Ponieważ prawa
strona wzoru (5.4.1) jest splotem ciągu {c

i

} z przesuniętym ciągiem c

i

= c

i−1

,

c

0

= 0, to

C

(x) = xC

2

(x) + 1,

a więc

xC

2

(x) − C (x) + 1 = 0.

Rozwiązując to równanie ze względu na C (x) otrzymujemy dla x 6= 0

C

(x) =

1 ±

1 − 4x

2x

.

(5.4.2)

Rozwijając (1 − 4x)

1/2

w szereg Maclaurina otrzymujemy

1 − 4x = 1 − 2

X

k=1

1
k

2k − 2

k

− 1

!

x

k

.

Aby otrzymać rozwiązanie o dodatnich współczynnikach, należy w (5.4.2) wy-
brać znak minus. Stąd

C

(x) =

1 −

1 − 4x

2x

=

X

k=1

1

k

2k − 2

k

− 1

!

x

k−1

=

X

k=0

1

k

+ 1

2k

k

!

x

k

.

background image

5.5. Zadania

30

Ostatecznie

c

k

=

1
k

2k

k

!

.

Liczby c

k

nazywa się liczbami Catalana

8

.

5.5. Zadania

1.

Znaleźć funkcje tworzące dla ciągów a

k

= k, b

k

= 2

k

oraz c

k

=

m+k

m

dla

k

= 0, 1, . . . .

2.

Znaleźć funkcję tworzącą dla ciągu Fibonacciego, z modyfikacją taką, że

f

0

= 0, f

1

= 1, f

n+1

= f

n

+ f

n−1

.

3.

Niech a

n

będzie liczbą ciągów różnowartościowych o elementach ze zbioru

n

-elementowego. Udowodnić, że

X

n=0

a

n

n

!

x

n

=

e

x

1 − x

.

4.

Na ile sposobów można zbudować kolumnę rozmiaru 2 × 2 × n z cegieł

rozmiaru 2 × 2 × 1?

5.

Liczby Fibonacciego drugiego rodzaju F

n

są określone następująco. F

0

= 0,

F

1

= 1 oraz F

n+1

= F

n

+ F

n−1

+ f

n+1

dla n > 0. Podać F

n

jako funkcję liczb

Fibonacciego f

n

.

6.

Niech c

k

będzie liczbą funkcji różnowartościowych ze zbioru k-elementowego

w zbiór n-elementowy. Znaleźć funkcję tworzącą dla ciągu c

k

i obliczyć c

k

.

7.

Niech p

n

będzie liczbą możliwych rozmieszczeń nawiasów w iloczynie

x

0

. . . x

n

. Udowodnić, że p

n

= c

n

, gdzie c

k

są liczbami Catalana.

8.

Udowodnić, że liczba sposobów, w jaki (n + 2)-kąt wypukły na płaszczyźnie

można podzielić na rozłączne trójkąty za pomocą n − 1 przekątnych nieprze-

cinających się wewnątrz tego (n + 2)-kąta, jest równa liczbie Catalana c

n

.

9.

Niech B

n

będa liczbami Bella. Udowodnić, że

B

n+1

=

n

X

k=0

n
k

!

B

n−k

i korzystając z tej rekurencji znaleźć wykładniczą funkcję tworzącą dla liczb
Bella.

8

Catalan ???

background image

31

6. Ciała skończone i skończone przestrzenie

wektorowe

6.1. Ciała skończone

Zbiór X z działaniami + i · tworzy ciało (X, +, ·), gdy spełnione są warunki:

(w zapisie, zgodnie ze zwyczajem, na ogół nie piszemy kropki)
C1 a + b = b + a,
C2 (a + b) + c = a + (b + c),
C3 ab = ba,
C4 (ab)c = a(bc),
C5 a(b + c) = ab + ac,
C6 Istnieje zero: a + 0 = 0 + a = a,
C7 Istnieje element przeciwny a + (−a) = 0,

C8 Istnieje jedynka a · 1 = 1 · a = a,

C9 Istnieje element odwrotny aa

−1

= a

−1

a

= 1 dla a 6= 0,

C10 0 6= 1.
Jeżeli spełnione są warunki C1, C2, C6, C7, to (X, +) jest grupą addytyw-

Grupa
addytywna

ną przemienną, jeżeli spełnione są warunki C4, C8, C9, to (A, ·) jest grupą

multiplikatywną (niekonieczne przemienną), jeśli dodatkowo jest spełniony

Grupa multi-
plikatywna

warunek C3, to jest grupą multiplikatywną przemienną. Jeżeli spełnione są
warunki C1–C8 i C10, to (X, +, ·) jest pierścieniem.
Twierdzenie 6.1.1. Jeżeli p jest liczbą pierwszą, to działania + i

· określone

jako reszty z dzielenia przez p w zwykłym dodawaniu i dzieleniu w zbiorze
liczb całkowitych, (czyli działania mod p), tworzą ciało skończone na zbiorze
X

= {0, 1, . . . , p − 1}.

Jeżeli p nie jest liczbą pierwszą, to X z działaniami dodawania i mnożenia

Pieścień Z

p

mod p jest pierścieniem Z

p

, ale nie ciałem.

Charakterystyką ciała jest najmniejszą liczbą całkowitą k taką, że

P

k

i=1

1 = 0.

Twierdzenie 6.1.2. Charakterystyka dowolnego ciała skończonego jest liczbą
pierwszą.

Można udowodnić, że każde ciało skończone ma q = p

m

elementów, gdzie p

jest liczbą pierwszą, a m jest liczbą naturalną. Wszystkie ciała skończone o tej
samej liczbie elementów są izomorficzne. Takie q-elementowe ciało oznaczamy

Ciała Galois

przez GF (q) – ciało Galois

9

(Galois field). Dla m > 1 są to ciała wielomianów

(nie wszystkich –. problem ten rozważymy ogólnie w następnym paragrafie).
Gdy q = p

m

, to charakterystyka takiego ciała wynosi p.

Przykład.

Ciało o 2

2

= 4 elementach:

Ciała
wielomianów

0, 1, x, x + 1 .

9

Galois

background image

6.2. Ciała wielomianów

32

Wielomian x

2

+ x + 1 jest nierozkładalny nad GF (2), bo

x

· x = x

2

,

x

(x + 1) = x

2

+ x,

(x + 1)(x + 1) = x

2

+ 2x + 1.

Następnie

x

· x( mod x

2

+ x + 1) = x + 1,

x

(x + 1)( mod x

2

+ x + 1) = 1,

(x + 1)(x + 1)( mod x

2

+ x + 1) = x,

Stąd GF (4):

+

0

1

x

x

+ 1

0

0

1

x

x

+ 1

1

1

0

x

+ 1

x

x

x

x

+ 1

0

1

x

+ 1 x + 1

x

1

0

·

0

1

x

x

+ 1

0

0

0

0

0

1

0

1

x

x

+ 1

x

0

x

x

+ 1

1

x

+ 1 0 x + 1

1

x

Natomiast Z

4

:

+ 0 1 2 3

0

0 1 2 3

1

1 2 3 0

2

2 3 0 1

3

3 0 1 2

· 0 1 2 3

0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1

6.2. Ciała wielomianów

6.3. Skończone przestrzenie wektorowe

Przestrzeń liniowa n-wymiarowa nad ciałem GF (q) jest określona jako zbiór

Przestrzenie
liniowe

wektorów x = (x

1

, . . . , x

n

), gdzie x

i

∈ GF (q). Działaniami są

• Dodawanie x + y = (x

1

+ y

1

, . . . , x

n

+ y

n

),

• Mnożenie przez liczbę λx = (λx

1

, . . . , λx

n

).

Przestrzeń taką oznaczymy przez V (n, q).
Rodzina podprzestrzeni przestrzeni V (n, q) tworzy kratę, gdzie dla podprze-

Kraty
podprzestrzeni

strzeni Z oraz T określamy

Z

∧ T = Z ∩ T,

Z

∨ T = {z + t : z ∈ Z, t ∈ T }.

background image

6.3. Skończone przestrzenie wektorowe

33

Zero kraty 0 to przestrzeń zerowa składająca się z jednego wektora (0, . . . , 0).
Jedynką kraty 1 jest cała przestrzeń V (n, 1).
Atomem a kraty L nazywa się taki jej element, że 0 4 a oraz jeśli 0 4 b 4 a,

Atomy kraty

to albo b = 0 albo b = a. W kracie podprzestrzeni, atomami są podprzestrzenie
jednowymiarowe.

000

100

010

110

001

101

011

111

Rysunek 2. Przestrzeń V (3, 2)

001

010

100

011

110

111

101

H

1

H

3

H

4

H

7

H

6

H

5

H

2

Rysunek 3. Krata podprzestrzeni V (3, 2)

Dla V (3, 2) podprzestrzeniami dwuwymiarowymi są: H

1

, H

2

, H

3

– ściany

zawierające (0, 0, 0), H

4

, H

5

, H

6

– „płaszczyzny” przechodzące przez kra-

wędź zawierającą (0, 0, 0) i krawędź równoległą do niej zawierającą (1, 1, 1),
H

7

= {000, 011, 110, 101}.

background image

6.3. Skończone przestrzenie wektorowe

34

Oznaczmy

[x] =

q

x

− 1

q

− 1

.

(6.3.1)

Własność 0. Jeśli n jest liczba naturalną, to [n] określone wzorem (6.3.1) jest
liczbą atomów w kracie podprzestrzeni, przestrzeni V (n, q) nad ciałem GF (q).

Przyjmijmy oznaczenia:

[x]

k

= [x][x − 1] . . . [x − k + 1], (x)

k

= x(x − 1) . . . (x − k + 1),

[k]! = [k]

k

,

k

! = (k)

k

,

"

x
k

#

=

[x]

k

[k]!

,

x
k

!

=

(x)

k

k

!

.

Twierdzenie 6.3.1.

lim

q→1

[x]

k

= (x)

k

,

lim

q→1

"

x
k

#

=

x
k

!

.

Symbol

h

x
k

i

nazywa się symbolem Gaussa i ma własności podobne do symbolu

Symbol
Gaussa

Newtona.
Twierdzenie 6.3.2.

"

x
k

#

=

"

x

x

− k

#

oraz

"

x

+ 1

k

+ 1

#

=

"

x
k

#

+ q

k+1

"

x

k

+ 1

#

, .

Dowód.

Twierdzenie 6.3.3. Liczba podprzestrzeni wymiaru k przestrzeni V (n, q) czy-
li elementów kraty rzędu k jest równa

"

n
k

#

=

(q

n

− 1)(q

n−1

− 1) . . . (q

n−k+1

− 1)

(q

k

− 1)(q

k−1

− 1) . . . (q − 1)

.

Dowód.

Twierdzenie 6.3.4.

x

n

=

n

X

k=0

"

n
k

#

(x − 1) (x − q) . . .

x

− q

k−1

.

(6.3.2)

Dowód.

background image

6.4. Zadania

35

6.4. Zadania

1.

Sprawdzić, że wielomian x

3

+ x + 1 ∈ Z

2

jest nierozkładalny nad ciałem

Z

2

. Wypisać wszystkie elementy ciała GF (8) rozumianego jako ciało reszt z

dzielenia przez x

3

+ x + 1 w pierścieniu Z

2

.

2.

Sprawdzić, że wielomian x

2

+ x + 2 ∈ Z

3

jest nierozkładalny nad ciałem

Z

3

. Wypisać wszystkie elementy ciała GF (9) rozumianego jako ciało reszt z

dzielenia przez x

2

+ x + 2 w pierścieniu Z

3

.

3.

W ciele GF (8) z zadania 1 obliczyć:

(1 + x) + (x + x

2

), (1 + x)(x + x

2

), x

4

.

4.

W ciele GF (9) z zadania 2 obliczyć:

(1 + x) + (2 + x), (2 + x) − (1 + 2x),
(1 + x)(1 + 2x),

x

3

.

5.

W ciele GF (8) z zadania 1 rozwiązać równania kwadratowe o niewiadomej

t

:

t

2

+ (x

2

+ 1)t + 1 = 0,

t

2

+ t + x = 0,

t

2

+ t + x

2

= 0,

t

2

+ t + (x

2

+ 1) = 0,

t

2

+ (x

2

+ 1)t + (x

2

+ 1) = 0.

6.

Udowodnić, że

"

n

0

#

<

"

n

1

#

<

· · · <

"

n

⌊n/2⌋

#

=

"

n

⌈n/2⌉

#

>

· · · >

"

n
n

#

.

7.

Udowodnić, że dla q > 1

q

k(n−k)

¬

"

n
k

#

¬ q

k(n−k−1)

8.

Udowodnić, że dla q > 1

q

kn−

(

k
2

) ­ (q − 1)

k

[n]

k

­ βq

kn−

(

k
2

),

gdzie

β

=

Y

i=1

1 − q

−i

,

9.

Udowodnić, że dla q > 1

(q − 1)

k

[n]

k

∼ q

kn−

(

k
2

)

o ile kq

−n+k

= o (n).

background image

36

7. Geometrie rzutowe i afiniczne

7.1. Skończone geometrie rzutowe

Geometrią rzutową nazywa się zbiór punktów X i rodzinę podzbiorów zwanych

Geometrie
rzutowe

prostymi, spełniających warunki:

(i) dowolne dwa punkty leżą na dokładnie jednej prostej,

(ii) dla dowolnych czterech punktów x, y, z, t nie leżących na jednej prostej,

jeżeli xy przecina zt, to xz przecina yt,

(iii) każda prosta ma co najmniej trzy punkty.

Jeżeli za punkty przyjmiemy atomy kraty podprzestrzeni V (n, q), to podprze-
strzenie rzędu 2 są prostymi. Taką geometrię oznaczamy symbolem P G(n −

1, q). Geometrię rzutową rzędu P G(2, 2) nazywamy płaszczyzną Fano (rys. 4).
Na rys. 5 przedstawiona jest płaszczyzna P G(2, 3).

1

3

2

6

5

4

7

Rysunek 4. Płaszczyzna Fano P G(2, 2)

Twierdzenie 7.1.1. Liczba podprzestrzeni k-wymiarowych n-wymiarowej
geometrii P G(n

− 1, q) jest równa

h

n

k

i

.

Płaszczyzny rzutowe można określić aksjomatycznie w następujący sposób.

Płaszczyzny
rzutowe

(i) dowolne dwa punkty leżą na dokładnie jednej prostej,

(ii) każde dwie różne proste mają dokładnie jeden punkt wspólny,

(iii) istnieją cztery różne punkty, z których żadne trzy nie leżą na jedej prostej.

Istnieją płaszczyny rzutowe nieizomorficzne z P G(2, q), natomiast geometrie
rzutowe, które nie są płaszczyznami są izomorficzne z P G(n−1, q) dla pewnych
n

i q.

Twierdzenie 7.1.2. Płaszczyna P G(2, q) zawiera q

2

+ q + 1 punktów oraz

q

2

+ q + 1 prostych. Każda prosta zawiera dokładnie q + 1 punktów, a przez

każdy punkt przchodzi q + 1 prostych.

background image

7.2. Skończone geometrie afiniczne

37

Rysunek 5. Płaszczyzna rzutowa P G(2, 3)

7.2. Skończone geometrie afiniczne

Geometrią afiniczną nazywa się zbiór punktów X i rodzinę podzbiorów zwa-

Geometrie
afiniczne

nych prostymi, spełniających warunki:
Geometrię afiniczną AG(n, g) konstruujemy następująco. Niech V (n, q) będzie
n

-wymiarową przestrzenią liniową nad ciałem GF (q), a Z – jej podprzestrzenią.

Relacja ≡ określona wzorem

a

≡ b ⇐⇒ a − b ∈ Z

(7.2.1)

jest relacją równoważności. Atomy w kracie warstw tej relacji są punktami
geometrii afinicznej AG(n, q), podprzestrzenie rzędu 2, są prostymi.
Twierdzenie 7.2.1. Liczba podprzestrzeni k-wymiarowych n-wymiarowej
geometrii AG(n, q) jest równa q

n−k

h

n
k

i

.

Płaszczyzny afiniczne można określić aksjomatycznie w następujący sposób.

Płaszczyzny
afiniczne

(i) dowolne dwa punkty leżą na dokładnie jednej prostej,

(ii) dla każdej prostej L i każdego punktu p /

∈ L istnieje dokładnie jedna

prosta L

równoległa do L (L

k L) taka, że p ∈ L.

(iii) istnieją cztery różne punkty, z których żadne trzy nie leżą na jednej

prostej.

Istnieją płaszczyzny afiniczne nieizomorficzne z AG(2, q), natomiast geome-
trie afiniczne, które nie są płaszczyznami są izomorficzne z AG(n − 1, q) dla

pewnych n i q.
Twierdzenie 7.2.2. Płaszczyna AG(2, q) zawiera q

2

punktów oraz q

2

+ q

prostych. Każda prosta zawiera dokładnie q punktów, a przez każdy punkt

background image

7.3. Zadania

38

przechodzi q + 1 prostych.

7.3. Zadania

1.

Udowodnić, że każda geometria P G(2, q) jest płaszczyzną rzutową, tzn.

spełnia warunki (i) – (iii).

2.

Wyprowadzić wzór na liczbę różnych czworokątów, tzn. czwórek punktów

z których żadne trzy nie leżą na jednej prostej, płaszczyzny P G(2, q).

3.

Udowodnić, że liczba podprzestrzeni rzędu s zawierających ustaloną pod-

przestrzeń rzędu u geometrii P G(n − 1, q), jest równa

"

n

− u

s

− u

#

.

background image

39

8. Matroidy

8.1. Definicje

Niech E będzie zbiorem skończonym. Matroidem (matroidem baz) nazywamy

Bazy matroidu

parę M = (E, B) taką, że niepusta rodzina B podzbiorów zbioru E spełnia

następujące postulaty:
(b

1

) żadna baza nie jest podzbiorem właściwym innej bazy,

(b

2

) jeśli B

1

∈ B, B

2

∈ B, e ∈ B

1

to istnieje f ∈ B

2

takie, że

(B

1

\ {e} ∪ {f}) ∈ B.

Własności takie mają bazy w skończonych przestrzeniach liniowych nad do-
wolnym ciałem, w szczególności GF (q) (własność Steiniza).
Twierdzenie 8.1.1. Wszystkie bazy matroidu M mają tę samą liczbę ele-
mentów r = ρ(M).

Liczbę r = ρ(M) nazywa się rzędem matroidu.
Definicja.

Zbiorem niezależnym nazywa się dowolny podzbiór dowolnej bazy.

Zbiory
niezależne

Rodzinę zbiorów niezależnych oznaczamy przez I. Parę M = (E, I) nazywa

się matroidem zbiorów niezależnych.
Cyklem nazywa się każdy minimalny zbiór zależny (tzn. taki, który nie jest

Cykle

niezależny). Rodzinę cykli oznaczamy przez C . Parę M = (E, C ) nazywa się

matroidem cykli.
Rzędem ρ(A) zbioru A ⊆ E nazywa się liczbę elementów maksymalnego zbioru

Rząd

niezależnego I ⊆ A. Parę M = (E, ρ) nazywa się matroidem z funkcją rzędu.
Rozpięciem σ(A) zbioru A ⊆ E nazywa się maksymalny zbiór B taki, że

Rozpięcie

A

⊂ B i ρ(A) = ρ(B). Parę M = (E, I) nazywa się matroidem rozpięć.

Zbiory niezależne, cykle, rząd i rozpięcie można scharakteryzować również ak-
sjomatycznie, przyjmując warunki konieczne i dostateczne z poniższych twier-
dzeń 8.1.2 – 8.1.5 jako postulaty.
Twierdzenie 8.1.2. Rodzina

I jest rodziną zbiorów niezależnych wtedy i

tylko wtedy, gdy są spełnione warunki:
(i

1

) jeśli I

1

⊆ I

2

∈ I, to I

1

∈ I,

(i

2

) jeśli I

1

, I

2

∈ I, |I

1

| < |I

2

|, to istnieje e ∈ I

2

, e /

∈ I

1

taki, że I

1

∪ {e} ∈ I.

Twierdzenie 8.1.3. Rodzina

C

jest rodziną cykli wtedy i tylko wtedy, gdy są

spełnione warunki:
(c

1

) jeżeli C

1

⊂ C

2

∈ C , to C

1

/

∈ C ,

(c

2

) jeżeli C

1

, C

2

∈ C , C

1

6= C

2

, e

∈ C

1

∩ C

2

, to istnieje C

∈ C

taki, że

C

⊆ C

1

∪ C

2

\ {e}.

Twierdzenie 8.1.4. Funkcja ρ : 2

E

→ R jest funkcją rzędu wtedy i tylko

wtedy, gdy są spełnione warunki:
(r

1

) 0 ¬ ρ(A) ¬ |A|,

(r

2

) jeżeli A ⊆ B ⊆ E, to ρ(A) ¬ ρ(B),

(r

3

) ρ(A ∪ B) + ρ(A ∩ B) ¬ ρ(A) + ρ(B).

background image

8.1. Definicje

40

Twierdzenie 8.1.5. Funkcja σ : 2

E

→ 2

E

jest funkcją rozpięcia wtedy i tylko

wtedy, gdy są spełnione warunki:
(s

1

) A ⊆ σ(A),

(s

2

) jeśli A ⊆ B, to σ(A) ⊆ σ(B),

(s

3

) σ (σ (A)) = σ(A),

(s

4

) jeśli f /

∈ σ(A), f ∈ σ (A ∪ {e}), to e ∈ σ(A ∪ {f}.

Zbiory A ⊆ E takie, że σ (A) = A nazywa się zbiorami domkniętymi.
Określmy własność (s

4

) następująco:

(s

4

) jeśli f /

∈ σ(A), f ∈ σ (A ∪ {e}), f 6= e to e /

∈ σ(A ∪ {f}.

Parę (E, σ) spełniającą warunki (s

1

) – (s

4

) nazywamy antymatroidem.

Pętlą nazywa się cykl jednoelementowy {e}, czyli gdy {e} ∈ C lub ρ ({e}) = 0.
Przykład.

Matroidy trywialne – jedynym zbiorem niezależnym jest ∅. Wtedy

ρ

(M) = 0. Inaczej mówiąc, każdy element tworzy pętlę.

Przykład.

Matroidy wolne – wszystkie podzbiory są niezależne.

Przykład.

Matroidy jednorodne (k-jednorodne) – bazami są wszystkie zbiory

k

-elementowe. Wtedy ρ (M) = k.

Przykład.

Matroidy reprezentowalne nad ciałem F – izomorficzne z matro-

idami, których zbiorami niezależnymi w sensie warunków (i

1

) – (i

2

) są zbiory

wektorów liniowo niezależnych w przestrzeni wektorowej V nad ciałem F . Cia-
ło F nie musi być skończone. Matroidy binarne, to matroidy reprezentowalne
nad ciałem GF (2).

Przykład.

Niech

A

=

a

11

. . .

a

1n

. . . . . . . . . . . . . .

a

m1

. . . a

mn

,

gdzie elementy a

ij

należą do dowolnego ciała F . Niech E będzie zbiorem ko-

Matroid
macierzy

lumn macierzy A. Rodziną zbiorów niezależnych matroidu M (A) = (E, I)

będzie teraz rodzina zbiorów kolumn liniowo niezależnych. Takie matroidy na-
zywane są matroidami macierzowymi. Matroidy macierzowe są oczywiście re-
prezentowalne nad ciałem F .

Przykład.

Niech A będzie podzbiorem punktów skończonej geometrii rzuto-

wej P G(r −1, q) lub afinicznej AG(r, q). Określmy σ(A) jako najmniejszą pod-

przestrzeń zawierającą A. Łatwo sprawdzić, że tak określone σ spełnia warunki
(s

1

) – (s

4

) z twierdzenia 8.1.5, a więc jest rozpięciem. Jeżeli tą podprzestrzenią

jest P G(r

− 1, q) lub AG(r

, q

), to ρ(A) = r

.

Oznacza to, że geometrię można traktować jako matroid, w którym podprze-
strzenie (podgeometrie) są zbiorami domkniętymi. Matroidy te są reprezento-
walne nad GF (q).

background image

8.2. Dualność

41

8.2. Dualność

Matroid dualny M

do matroidu M można określić na różne, choć równoważne

sposoby.
Definicja.

Jeżeli M = (E, B) jest matroidem, to dla rodziny B

określonej

wzorem

B

= {B

: B

= E \ B, B ∈ B} ,

para M

= (E, B

) jest matroidem dualnym do M.

Definicja.

Jeżeli M = (E, ρ) jest matroidem, to dla funkcji ρ

określonej

wzorem

ρ

(A) = |A| + ρ(E \ A) − ρ(E)

dla dowolnego A ⊆ E, para M

= (E, ρ

) jest matroidem dualnym do M.

Można udowodnić, że obie powyższe definicje są równoważne. Oczywista na-
tomiast jest równość M

∗∗

= M.

Mając dane B

lub ρ

można również określić C

jako rodzinę cykli w matro-

Kobazy i
kocykle

idzie dualnym (E, B

) lub (E, ρ

). Zbiory z rodziny B

nazywa się kobazami,

a zbiory z rodziny C

nazywa się kocyklami.

Twierdzenie 8.2.1. Jeżeli C

∈ C , B

∈ B

, to C

∩ B

6= ∅. Jeżeli C

∈ C

,

B

∈ B, to C

∩ B 6= ∅.

Twierdzenie 8.2.2. Rodzina

C

podzbiorów zbioru Ejest rodziną kocykli

wtedy i tylko wtedy, gdy zbiory z

C

są minimalnymi niepustymi podzbiorami

C

⊆ E takimi, że |C ∩ C

| 6= 1 dla każdego C ∈ C .

8.3. Algorytmy zachłanne

Niech E będzie zbiorem skończonym oraz w : E → R

+

. Wartość funkcji w(e)

nazywa się wagą elementu e. Niech S będzie pewną rodziną podzbiorów zbioru
E

. Liczbę

w

(A) =

X

e∈A

w

(e)

nazywa się wagą zbioru A.
Rozważmy problem znalezienia zbioru A ∈ I o największej wadze. W tym

Algorytm
zachłanny

celu sformułujemy następujący algorytm, zwany zachłannym. Algorytm ten
sformułowany został w języku C–podobnym. Załóżmy, że A jest zmienną re-
prezentującą zbiór, a I zmienną reprezentującą rodzinę zbiorów (w rzeczywi-
stości mogą to być odpowiednie listy) oraz że + jest przeciążonym operatorem
dodawania elementu do zbioru. Funkcja in(A,I) sprawdza, czy zbiór A należy
do rodziny I.

background image

8.4. Zadania

42

Algorytm zachłanny

// Sortujemy elementy e wg niemalejących wag
// w ciąg e[0]>=e[1]>=

. . . >=e[n-1]

A=0; // 0 oznacza zbiór pusty
for(i=0;i<n;i++)
{

if(in(A+e[i],I)

{A+=e;}

// wybieramy zachłannie największy możliwy

}
return A;

Twierdzenie 8.3.1. (Rado, Edmonds). Jeżeli M = (E,

I) jest matroidem, to

A znalezione przez algorytm zachłanny jest zbiorem niezależnym o największej
wadze. Jeżeli (E,

I) nie jest matroidem, to istnieje funkcja w : E → R

+

taka,

że A nie jest zbiorem o największej wadze.

8.4. Zadania

1.

Niech E będzie zbiorem skończonym, |E| = n oraz niech m < n. Niech

P = {A : |A| = k, k < m}. Sprawdzić, czy rodzina P jest dla pewnych m

(i) rodziną baz,

(ii) rodziną cykli,

(iii) rodziną zbiorów niezależnych

pewnego matroidu. Jeżeli jest rodziną baz, to wyznaczyć cykle i kocykle, jeżeli
jest rodziną cykli, to wyznaczyć bazy i kocykle.

2.

Dla matroidu P G(2, 2) wyznaczyć bazy i cykle. Wyznaczyć matroid dualny.

3.

Niech rodzinę P tworzą dopełnienia prostych na płaszczyśnie Fano. Spraw-

dzić, czy rodzina P jest dla pewnych m

(i) rodziną baz,

(ii) rodziną cykli,

(iii) rodziną zbiorów domkniętych

pewnego matroidu. Jeżeli jest rodziną baz, to wyznaczyć cykle i kocykle, je-
żeli jest rodziną cykli, to wyznaczyć bazy i kocykle, jeśli jest rodziną zbiorów
domkniętych, to wyznaczyć bazy.

4.

Wykazać, że z dokładnością do izomorfizmu istnieją dokładnie cztery ma-

troidy na zbiorze dwuelementowym i osiem na zbiorze trzyelementowym.

5

P

.

Niech A będzie macierzą o nieujemnych elementach. Niech w matroidzie

macierzowym M (A) wagą kolumny będzie suma jej elementów. Wykorzystując
metodę eliminacji Gaussa, napisać algorytm zachłanny dla matroidu macierzo-
wego.

6

P

.

Niech M = P G(r −1, 2), tzn. niech M będzie matroidem, którego elemen-

tami są punkty P G(r − 1, 2), (niezerowe wektory przestrzeni liniowej V (r, 2) a

background image

8.4. Zadania

43

bazami matroidu bazy V (r, 2). Wagą elementu niech będzie liczba jedynek od-
powiedniego wektora. Napisać algorytm znajdujący bazę o maksymalnej sumie
wag.

background image

44

9. Transwersale i matroidy

9.1. Transwersale

Niech E będzie zbiorem niepustym, a F = (S

1

, . . . , S

m

) rodziną jego niepu-

stych, niekoniecznie różnych podzbiorów. Niech t : {1, . . . , m} → E będzie

funkcją różnowartościową taką, że t (i) ∈ S

i

. Tanswersala T rodziny F, to

zbiór wartości takiej funkcji t. Inaczej mówiąc, do transwersali do transwersali
wybieramy dokładnie m elementów, po jednym z każdego zbioru rodziny F.

Nie dla każdej rodziny F istnieje transwersala.
Transwersala podrodziny F

rodziny F jest transwersalą częściową rodziny F.

Transwersala
częściowa

Rzecz jasna, każdy podzbior transwersali częściowej jest transwersalą częścio-
wą.
Przykład.

Niech E = {1, 2, 3, 4, 5, 6} oraz S

1

= S

2

= {1, 2}, S

3

= S

4

=

{2, 3}, S

5

= {1, 4, 5, 6}. Taka rodzina F nie ma transwersali. Rodzina F

=

{S

1

, S

2

, S

3

, S

5

} ma traswersale, np. T

= {1, 2, 3, 4}, która jest transwersalą

częściową dla F. Transwersalami częściowymi są też na przykład {1, 2, 3, 6},
{2, 3, 6}, {1, 5}, ∅
Warunek konieczny i dostateczny istnienia traswersali podaje następujące
twierdzenie Halla.
Twierdzenie 9.1.1. Niech E będzie niepustym zbiorem skończonym i niech
F = (S

1

, . . . , S

m

) będzie rodziną niepustych podzbiorów zbioru E. Rodzina F

ma transwersalę wtedy i tylko wtedy, gdy suma dowolnych k podzbiorów S

i

ma co najmniej k elementów, 1

¬ k ¬ m.

Dowód.

(Szkic). Konieczność warunku jest oczywista. Dla dowodu dostatecz-

ności wystarczy pokazać, że jeżeli pewien podzbiór ma więcej niż jeden element,
to można usunąć z niego jeden element, nie naruszając przy tym warunku. Po-
wtarzając tę procedurę, otrzymuje w końcu zbiory jednoelementowe. Dowodzi
się tego nie wprost.

Wniosek 9.1.1.

Jeśli E i

F są takie jak w tw. 9.1.1, to rodzina F ma

transwersalę częściową mającą t elementów wtedy i tylko wtedy, gdy suma
dowolnych k podzbiorów ma co najmniej k + t

− m elementów.

Twierdzenie 9.1.2. Niech E będzie niepustym zbiorem skończonym i niech
F = (S

1

, . . . , S

m

) i G = (R

1

, . . . , R

m

) będą dwiema rodzinami niepustych pod-

zbiorów zbioru E. Wówczas rodziny

F i G mają wspólną transwersalę wtedy i

tylko wtedy, gdy dla dowolnych podzbiorów A i B zbioru

{1, 2, . . . , m} zachodzi

nierówność

[

i∈A

S

i

!

[

j∈B

T

j

­ |A| + |B| − m.

background image

9.2. Matroidy transwersalne

45

9.2. Matroidy transwersalne

Twierdzenie 9.2.1. Rodzina

I wszystkich transwersali częściowych rodzi-

ny

F podzbiorów zbioru E jest rodziną zbiorów niezależnych matroidu M =

(E, I).
Dowód tego twierdzenia jest treścią zadania 2.

Matroid
traswersalny

Matroid, w którym zbiorami niezależnymi są transwersale częściowe, nazywa
się matroidem transwersalnym.
Przyjmijmy teraz, że w zbiorze E jest dodatkowo wprowadzona struktura ma-
troidu. Czy istnieje transwersala rodziny G będąca zbiorem niezależnym ma-

troidu? Odpowiedź na to pytanie daje twierdzenie Rado.
Twierdzenie 9.2.2. Niech M = (E,

I) będzie matroidem i niech F będzie

rodziną niepustych podzbiorów zbioru E. Wówczas rodzina

F ma transwersalę

T

∈ I wtedy i tylko wtedy, gdy dla każdego k takiego, że 1 ¬ k ¬ m, suma

dowolnych k podzbiorów S

i

zawiera zbiór niezależny mający co najmniej k

elementów.

Uwaga.

Jeśli M jest matroidem wolnym, to twierdzenie 9.2.2 sprowadza się

do twierdzenia 9.1.1.

9.3. Zadania

1.

Niech E będzie zbiorem liter w słowie MATROIDS. Wykazać, że rodzina

(STAR, ROAD, MOAT, RIOT, RIDS, DAMS, MIST )

podzbiorów zbioru E ma dokładnie osiem transwersal.

2.

Niech T

1

i T

2

będą transwersalami rodziny F. Niech x ∈ T

1

. Wykazać, że

istnieje y ∈ T

2

taki, że T

1

\ {x} ∪ {y} jest również transwersalą rodziny F.

3.

Wykaż prawdziwość twierdzenia Rado w przypadku, gdy M jest matroidem

Fano oraz F = ({1}, {1, 2}, {2, 4, 5}).

background image

46

10. Niezmienniki Tutte’a–Gr¨

othendiecka

10.1. Operacje na matroidach

Niech M = (E, C ) będzie matroidem cykli oraz niech A ⊆ E. Ograniczeniem

Ograniczenie

matroidu M do do zbioru E \ A nazywa się nazywa się matroid M \ A, którego

cyklami są tylko te cykle, które są zawarte w M \ A, czyli M \ A = (E \ A, C

)

gdzie

C

= {C ∈ C : C =⊆ A}.

Redukcją (ściągnięciem) matroidu M do do zbioru E \ A nazywa się nazywa

Redukcja

się matroid M/A, którego cyklami są zbiory minimalne zbioru

C

′′

= {C : C = C

∩ (E \ A) , C

∈ C }.

(10.1.1)

Sumą prostą matroidów M

1

= (E

1

,

C

1

) i M

2

= (E

2

,

C

2

) jest matroid

Suma prosta

M

1

⊕ M

2

= (E

1

∪ E

2

,

C

1

∪ C

2

) .

Rodziną baz matroidu M

1

⊕ M

2

, jest rodzina

B = {B : B = B

1

∪ B

2

, B

1

∈ B

1

, B

2

∈ B

2

},

gdzie B

i

jest rodziną baz matroidu M

i

.

Matroid M

otrzymany matroidu M poprzez kolejne operacje ograniczenia

Minor

lub ściągnięcia, nazywa się minorem matroidu M.
Przykład.

Niech F

3

będzie matroidem Fano, tzn. którego bazami są wszyst-

kie trzyelementowe podzbiory punktów nie będące prostymi płaszczysny Fano
(patrz. rys. 4). Cyklami w F

3

są proste i ich dopełnienia. Niech A = {6, 7}.

Wtedy cyklami w F

3

\ A są {1, 2, 3}, {1, 4, 5} i {2, 3, 4, 5}. Zgodnie ze wzorem

(10.1.1), mamy

C

′′

= {1, 2, 3}, {1, 4, 5}, {2, 3, 4, 5}, {2, 4}, {3, 5}, {1}, },

a więc cyklami w F

3

/A

są {1}, {2, 4}, {3, 5}.

10.2. Wielomiany Tutte’a

Niezmiennikiem

(izomorfizmu) nazywa się każdą funkcję f określoną na klasie

matroidów M = {M

i

} taką, że dla izomorficznych M

i M

′′

, zachodzi równość:

f

(M

) = f (M

′′

).

(10.2.1)

Funkcja tworząca rząd:

R

(M; u, v) =

X

A⊆E

u

ρ(E)−ρ(A)

v

|A|−ρ(A)

.

(10.2.2)

background image

10.2. Wielomiany Tutte’a

47

Wtedy

T

(M; x, y) = R(M; x − 1, y − 1).

(10.2.3)

Wzór (10.2.2) określa funkcję tworzącą rzędu, a wzór (10.2.3) wielomian Tutte,
które dla matroidu M oznaczamy R(M; u, v) i T (M; x, y) odpowiednio.
Własność 0. Dla matroidów M prawdziwy jest wzór

T

(M; x, y) = T (M

; y, x),

(10.2.4)

Dowód.

Ponieważ sumowanie we wzorze (10.2.2) jest po wszystkich podzbio-

rach A ⊆ E to można podstawić A ← A

= E \ A, więc

R

(M

; u, v) =

X

A⊆E

u

r

(E)−r

(A

)

v

|A

|−r

(A

)

.

Ponieważ r

(E) = |E| − ρ(E), to:

r

(E) − r

(A

) = |E| − ρ(E) − |E| + ρ(E) + |A| − ρ(A) = |A| − ρ(A),

oraz

|A| − ρ(A

) = |E \ A| − |E|

|

{z

}

−|A|

+ρ(E) + |A| − ρ(A) = ρ(E) − ρ(A).

Stąd i ze wzoru (10.2.3) otrzymujemy (10.2.4).

Przykład.

Matroid 2-jednorodny na trzech elementach, tzn. składający się z

jednego cyklu. Oznaczmy go przez C

3

.

T

(C

3

; x, y)

|A| = 0 :

= (x − 1)

2

|A| = 1 :

+ 3(x − 1)

|A| = 2 :

+ 3

|A| = 3 :

+ y − 1
= (x − 1)

2

+ 3(x − 1) + 3 + y − 1

= x

2

+ x + y.

Poniższe „twierdzenie – receptę” udowodnili Oxley i Welsh.
Twierdzenie 10.2.1. Niech C będzie klasą matroidów zamkniętych ze wzglę-
du na sumy proste M

1

⊕ M

2

oraz M

\ e i M/e dla e ∈ E(M). Niech f będzie

określone na C spełniając równania

f

(M) = af (M \ e) + bf(M/e),

(10.2.5)

f

(M

1

⊕ M

2

) = f (M

1

)f (M

2

).

(10.2.6)

background image

10.3. Zadania

48

Wtedy f jest dana wzorem

f

(M) = a

|E|−ρ(E)

b

ρ(E)

T

M

;

x

0

b

,

y

o

a

,

gdzie x

0

= f (I) oraz y

0

= f (L).

Każdy niezmiennik f spełniający (10.2.5) – (10.2.6) nazywa się niezmiennikiem
Tutte-Gr¨

othendiecka

, ((T G)-niezmiennikiem).

Niektóre z niezmienników Tutte’a–Gr¨othendiecka.

1. W punkcie (1, 1), T zlicza bazy M.
2. W punkcie (2, 1), T zlicza zbiory niezależne w M.

Szczególną rolę pełnią wartości wielomianów Tutte’a w niektórych punktach
płaszczyzny, a szczególnie wzdłuż hiperboli

H

α

= {(x, y) : (x − 1)(y − 1) = α}

Przykład.

Ponieważ T (C

3

; x, y) = x

2

+ x + y, to liczba baz wynosi

T

(C

3

; 1, 1) = 1 + 1 + 1 = 3, a liczba zbiorów niezależnych wynosi T (C

3

; 2, 1) =

4 + 2 + 1 = 7. Matroidem dualnym do C

3

jest matroid C

3

, którego bazami są

zbiory jednoelementowe, cyklami – zbiory dwuelementowe. Ze wzoru (10.2.4)
wynika, że T (C

3

; x, y) = y

2

+ x + y, a więc liczba baz wynosi T (C

3

; 1, 1) = 3,

a liczba zbiorów niezależnych wynosi T (C

3

; 2, 1) = 1 + 1 + 2 = 4.

10.3. Zadania

1.

Niech M będzie matroidem na zbiorze E oraz A ⊆ B ⊆ E. Pokazać, że

a) (M \ A) \ B = M \ A,
b) (M/A) /B = M/A.

2.

Pokazać, że

(M/A)

= (M

\ A) .

3.

Wyznaczyć wielomian Tutte’a dla matroidów F

3

i F

4

= F

3

. Na tej podsta-

wie obliczyć liczbę baz w tych matroidach.

4.

Skonstruować dowolną funkcję f ∈ C o której mowa w „twierdzeniu –

recepcie” dla matroidu C

3

.

5.

Uogólnić wynik z zadania 4 na matroid F

3

\ A, gdzie A jest dowolnym

dwuelementowym podzbiorem zbioru punktów płaszczyzny Fano.

background image

49

11. Konfiguracje kombinatoryczne

11.1. Podstawowe własności

Niech X będzie zbiorem skończonym oraz niech B = {B

1

, . . . , B

b

} będzie ro-

dziną jego podzbiorów. Podzbiory B

i

mogą się powtarzać. Elementy x ∈ X

Konfiguracje

nazywane są punktami, a zbiory B

i

blokami. Konfiguracją nazywa się parę

(X, B) o parametrach v, k, λ, gdy spełnione są warunki:

(i) |X| = v,

(ii) |B

i

| = k dla 1 ¬ i ¬ b,

(iii) każdy dwuelementowy zbiór {x, y} ⊆ X jest podzbiorem dokładnie λ

bloków należących do B,

(iv) λ > 0 oraz k < v − 1.

Niech x będzie ustalonym punktem oraz niech r będzie liczbą bloków B

i

dla

których x ∈ B

i

. Łatwo pokazać (zadanie), że

λ

(v − 1) = r(k − 1).

(11.1.1)

Wynika stąd, że r jest wyznaczone przez parametry v, k, λ i nie zależy od
wyboru punktu x. Stąd
Własność 0. Każdy punkt konfiguracji należy do dokładnie r bloków, gdzie

r

=

λ

(v − 1)

k

− 1

.

(11.1.2)

Podobnie otrzymuje się (zadanie), że

vr

= bk,

skąd

b

=

λv

(v − 1)

k

(k − 1)

.

(11.1.3)

Konfiguracja taka ma oznaczenie (v, b, r, k, λ)-BIBD, (ang. balanced incomplete
block design

).

Przykład.

Niech k = 3, v ­ 5, λ = 1. Łatwo sprawdzić, że nie istnieje

taka konfiguracja dla v = 5 i v = 6. Wystarczy bowiem sprawdzić, że nie
są spełnione równości (11.1.2) i (11.1.3). Istnieje natomiast taka konfiguracja
dla v = 7. Wystarczy bowiem za X przyjąć punkty płaszczyzny Fano (patrz
rys. 4), a za bloki przyjąć proste z tej płaszczyzny.
Konfiguracje można reprezentować za pomocą macierzy incydencji A = [a

ij

],

Macierze
incydencji

gdzie

a

ij

=

1, gdy x

i

∈ B

j

,

0, gdy x

i

/

∈ B

j

.

Nierówność Fishera.
Twierdzenie 11.1.1. Dla każdego (v, b, r, k, λ)-BIBD jest b

­ v.

background image

11.2. Konfiguracje kwadratowe

50

Dowód.

Niech X = {x

1

, . . . , x

v

}, B = {B

1

, . . . , B

b

}, M – macierz incydencji

oraz niech s

j

będzie j-tym wierszem w M

T

. Wektory s

j

rozpinają podprze-

strzeń S ⊆ R

v

. Wystarczy dowieść, że S = R

v

. W tym celu pokażemy, że

e

i

∈ S, gdzie e

i

= (0, . . . , 1, 0, . . . , 0) (1 na i-tej pozycji).

Ponieważ

b

X

j=1

s

j

= (r, . . . , r) ,

to

1
r

b

X

j=1

s

j

= (1, . . . , 1) ,

(11.1.4)

Dalej, ustalamy i, 1 ¬ i ¬ v. Wtedy

X

j:x

i

∈B

j

s

j

= (r − λ) e

i

+ (λ, . . . , λ) .

(11.1.5)

Porównując (11.1.4) i (11.1.5) otrzymujemy

e

i

=

X

j:x

i

∈B

j

1

r

− λ

s

j

b

X

j=1

λ

r

(r − λ)

s

j

.

(11.1.6)

Wzór (11.1.6) daje e

i

jako liniową kombinację wektorów s

1

, . . . , s

b

.

Przykład.

Nie istnieje konfiguracja dla v = 16, k = 6, λ = 1, bo ze wzoru

(11.1.3) wyliczamy

b

=

1 · 16 · 15

6 · 5

= 8 < 16 = v.

11.2. Konfiguracje kwadratowe

Konfiguracje kwadratowe to takie, w których liczba punktów jest równa liczbie
bloków. Równanie (11.1.1) ma wtedy postać

λ

(v − 1) = k(k − 1).

Konfiguracje kwadratowe są symetryczne, tzn. że nie tylko każdy punkt należy
do λ bloków, ale również każde dwa bloki mają λ wspólnych punktów:
Twierdzenie 11.2.1. Jeśli (X,

B), gdzie B = (B

1

, . . . , B

v

) jest konfiguracją

kwadratową o parametrach v, k, λ, to

|B

i

∩ B

j

| = λ dla dowolnych i 6= j.

Stąd
Wniosek 11.2.1. Jeśli A jest macierzą incydencji kwadratowej, to A

T

jest

macierzą incydencji pewnej konfiguracji kwadratowej o tych samych parame-
trach.

background image

11.3. Macierze Hadamarda

51

Własność 0. Para (X,

B) jest skończoną płaszczyzną rzutową wtedy i tylko

wtedy, gdy jest konfiguracją kwadratową z λ = 1.

Twierdzenie 11.2.2.

(Bruck, Ryser, Chowla). Jeśli istnieje konfiguracja kwa-

dratowa o parametrach v, k, λ oraz n = k

− λ, to

(i) jeśli v jest parzyste, to n jest kwadratem liczby całkowitej,

(ii) Jeśli v jest nieparzyste, to istnieją liczby całkowite x, y, z, nie wszystkie

równe zeru, spełniające równanie

z

2

= nx

2

+ (−1)

(v−1)/2

λy

2

.

(11.2.1)

Wniosek 11.2.2. Nie istnieje płaszczyzna rzutowa rzędu 6.

Twierdzenie 11.2.3.

(Singer). Geometria rzutowa P G(n − 1, q) określa kon-

figurację kwadratową o parametrach

v

=

q

n

− 1

q

− 1

,

k

=

q

n−1

− 1

q

− 1

,

λ

=

q

n−2

− 1

q

− 1

,

gdzie punktami konfiguracji są punkty geometrii rzutowej, a blokami konfigu-
racji są podprzestrzenie rzędu n

− 1 geometrii rzutowej.

11.3. Macierze Hadamarda

Macierz H wymiaru n × n o elementach +1 i −1 nazywa się macierzą Hada-

marda rzędu n, jeśli

HH

T

= nI,

(11.3.1)

gdzie I jest macierzą jednostkową.
Własność 0. Dowolne dwa wiersze macierzy Hadamarda są ortogonalne.

Wniosek 11.3.1. H jest macierzą Hadamarda wtedy i tylko wtedy, gdy H

T

jest macierzą Hadamarda.

Łatwo zauważyć, że permutacja wierszy lub kolumn, a także ich mnożenie przez
−1 nie narusza ortogonalności i prowadzi do macierzy Hadamarda.
Przykład.

"

1

1

1 -1

#

jest macierzą Hadamarda rzędu 2.

Twierdzenie 11.3.1. Macierz Hadamarda rzędu 4t istnieje wtedy i tylko
wtedy, gdy istnieje konfiguracja kwadratowa o parametrach v = 4t

− 1, k =

2t − 1, λ = t − 1.
Konstrukcja.

Normalizujemy macierz Hadamarda, tzn. permutujemy wiersze

i kolumny i mnożymy przez −1 tak, aby w pierwszy wierszu i w pierwszej ko-

lumnie były same +1. Usuwamy z takiej macierzy Hadamarda pierwszy wiersz

background image

11.4. Zadania

52

i pierwszą kolumnę i zamieniamy −1 na 0. Jest macierz incydencji konfiguracji

kwadratowej. Konstrukcja ta jest odwracalna.
Twierdzenie 11.3.2. Jeżeli istnieje macierz Hadamarda rzędu n, to n = 1,
n

= 2 lub n ≡ 0 mod 4.

Hipoteza.

Macierz Hadamarda istnieje wtedy i tylko wtedy, gdy n ≡ 0

mod 4 dla n ­ 4.
Iloczynem Kroneckera macierzy A = a

ij

wymiaru n × m i B wymiaru r × s

nazywa się macierz wymiaru nr × ms:

A

⊕ B =

a

11

B a

12

B . . .

a

1m

B

a

21

B a

22

B . . .

a

2m

B

...

...

...

a

n1

B a

n2

B . . . a

nm

B

Twierdzenie 11.3.3. Jeśli H

1

i H

2

są macierzami Hadamarda rzędów n

1

i

n

2

, to H = H

1

⊗ H

2

jest macierzą Hadamarda rzędu n = n

1

n

2

.

11.4. Zadania

1.

Zbudować konfiguracje o parametrach:

(a) v = b = 7, k = r = 3, λ = 1,
(b) v = b = 13, k = r = 4, λ = 1,
(c) v = 9, b = 12, r = 4, k = 3, λ = 1,
(d) v = 6, b = 10, r = 5, k = 3, λ = 2.

2.

Czy istnieją konfiguracje o parametrach:

(a) v = 15, b = 21, r = 7, k = 4, λ = 2, (b) v = b = 23, r = k = 7, λ = 2, (c)
v

= b = 43, r = k = 7, λ = 1, (d) v = 36, b = 42, r = 7, k = 6, λ = 1.

3.

Sprawdzić, czy spełniony jest warunek konieczny istnienia symetrycznych

(b = v, r = k) konfiguracji:
(a) v = 21, k = 5, λ = 1,
(b) v = 15, k = 7, λ = 3,
(c) v = 19, k = 9, λ = 4,
(d) v = 29, k = 8, λ = 2.

4.

Pokazać, że dla konfiguracji o parametrach v, k, λ zachodzi równość λ(v −

1) = r(k − 1).

5.

Pokazać, że dla konfiguracji o parametrach v, k, λ zachodzi równość vr = bk.

6.

Jaką konfigurację tworzą dopełnienia prostych na płaszczyźnie Fano?

7.

Niech λ = 2. Dla k = 6 i k = 7 znaleźć najmniejsze v ­ 10, dla któ-

rego z twierdzenia Brucka, Rysera i Chowli wynika nieistnienie konfiguracji
kwadratowej rzędu v.

background image

11.4. Zadania

53

8.

Niech

A

=

"

1

1

1 -1

#

.

Napisać macierze Hadamarda B = A ⊗ A oraz C = A ⊗ B. Czy macierz C jest

identyczna z macierzą Hadamarda D otrzymaną z macierzy incydencji konfi-
guracji o parametrach v = 7, k = 3 oraz λ = 1 po ewentualnych permutacjach
wierszy lub kolumn?

background image

54

12. Trójki Steinera

12.1. Quasigrupy i kwadraty łacińskie

System trójek Steinera oznaczany przez STS (v), to (v, 3, 1)-BIBD. Inaczej
mówiąc, STS (v) to rodzina trójek takich, że każda para należy do dokładnie
jednej trójki.
Przykład.

Płaszczyzna Fano, to STS (7), gdzie blokami (trójkami) są proste

na płaszczyźnie.
Płaszczynę AG (2, 3) na 9 elementach, można skonstruować następująco:

A

=

1 2 3
4 5 6
7 8 9

.

Prostymi (blokami) są wszystkie wiersze i kolumny macierzy A oraz takie trój-
ki, że żadne ich dwa elementy nie leżą w jednym wierszu lub kolumnie macierzy
A

. Proste na płaszczyźnie AG (2, 3) to trójki Steinera w STS (9).

Lemat 12.1.1. Jeśli istnieje STS (v), to v

≡ 1 ∨ 3 mod 6, v ­ 7.

Warunek
konieczny

Niech X będzie zbiorem skończonym, a ◦ będzie działaniem takim, że

(i) dla każdych x, y ∈ X, równanie x◦z = y ma dokładnie jedno rozwiązanie,

(ii) dla każdych x, y ∈ X, równanie z◦x = y ma dokładnie jedno rozwiązanie.

Parę (X, ◦) nazywa się quasigrupą. Jeśli x ◦ x = x, to quasigrupa jest idem-

Quasigrupa

potentna

, a jeśli x ◦ y = y ◦ x, to jest symetryczna.

Niech X będzie zbiorem skończonym, |X| = n oraz miech A będzie macierzą
n

× n o elementach a

x,y

taką, że każda kolumna i każdy wiersz jest permutacją

zbioru X. Taką macierz nazywa się kwadratem łacińskim.

Kwadrat
łaciński

Twierdzenie 12.1.1. Niech X będzie zbiorem skończonym,

|X| = n, x, y ∈

X. Jeżeli A = [a

x,y

]

n×n

jest kwadratem łacińskim oraz x

◦ y = a

x,y

, to (X,

◦)

jest quasigrupą.

Przykład.

Niech X = {1, 2}. Istnieją dokładnie dwa kwadraty łacińskie

"

1 2
2 1

#

"

2 1
1 2

#

Oba są symetryczne, ale żaden nie jest idempotentny.

Przykład.

Niech X = {1, 2, 3}. Istnieje 12 kwadratów łacińskich, w tym

cztery symetryczne, a tylko jeden idempotentny:

1 3 2
3 2 1
2 1 3

Lemat 12.1.2.

Idempotentna quasigrupa o n elementach istnieje wtedy i

tylko wtedy, gdy n jest nieparzyste.

background image

12.2. Konstrukcje Bosego i Skolema

55

12.2. Konstrukcje Bosego i Skolema

Konstrukcja Bose daje trójki Steinera w przypadku v ≡ 3 mod 6. Zmodyfi-

kowana konstrukcja Skolema daje trójki Steinera w przypadku v ≡ 1 mod 6.
Załóżmy, że relacja ≺ porządkuje liniowo zbiór X oraz załóżmy, że (X, ◦)

jest symetryczną idempotentną quasigrupą, |X| = 2t + 1, t ­ 1. Niech Y =
X

×Z

3

, gdzie Z

3

jest pierścieniem, z dodawaniem mod 3. Dla każdego x ∈ X

Konstrukcja
Bosego

określamy blok

Λ

x

= {(x, 0), (x, 1), (x, 2)}.

(12.2.1)

Następnie, dla każdej pary x, y ∈ X, ≺ i każdego i ∈ Z

3

określamy blok

B

x,y,i

= {(x, i), (y, i), (x ◦ y, (i + 1) mod 3)}.

(12.2.2)

Niech

B = {Λ

x

: x ∈ X} ∪ {B

x,y,i

: x, y ∈ X, x ≺ y, i ∈ Z

3

}.

(12.2.3)

Twierdzenie 12.2.1. Rodzina

B zdefiniowana wzorami (12.2.1), (12.2.2) i

(12.2.3), tworzy STS (v) dla v ≡ 3 mod 6.
Niech X = Z

n

gdzie n jest parzyste. Określamy permutację π zbioru X wzorem

π

(i) =

x
2

gdy x jest parzyste,

x+n−1

2

gdy x jest nieparzyste.

Działanie quasigrupowe określamy wzorem

x

◦ y = π ((x + y) mod n) .

Niech v = 6t + 1, t ­ 1 oraz niech Y = (Z

2t

× Z

3

) ∪ {∞}. Dla 0 ¬ x ¬ t − 1

Konstrukcja
Skolema

określamy blok

Λ

x

= {(x, 0), (x, 1), (x, 2)}.

(12.2.4)

Następnie, dla każdej pary x, y ∈ Z

2t

i każdego i ∈ Z

3

określamy blok

B

x,y,i

= {(x, i), (y, i), (x ◦ y, (i + 1) mod 3)}.

(12.2.5)

W końcu, dla 0 ¬ x ¬ t − 1 i każdego i ∈ Z

3

określamy blok

C

x,i

= {∞, (x + t, i), (x, (i + 1) mod 3)}.

(12.2.6)

Niech

B = {Λ

x

: 0 ¬ x ¬ t − 1} ∪ {B

x,y,i

: x, y ∈ Z

2t

, x < y, i

∈ Z

3

}

∪ {C

x,i

: 0 ¬ x ¬ t − 1, i ∈ Z

3

}.

(12.2.7)

Twierdzenie 12.2.2. Rodzina

B zdefiniowana wzorami (12.2.4) – (12.2.7),

tworzy STS (v) dla v

≡ 1 mod 6.

Z lematu 12.1.1 oraz twierdzeń 12.2.1 i 12.2.2 wynika
Twierdzenie 12.2.3. ST S

(v) istnieje wtedy i tylko wtedy, gdy v ≡ 1 ∨ 3

mod 6, v ­ 7.

background image

12.3. Zadania

56

12.3. Zadania

1.

Korzystając z konstrukcji Bosego, zbudować ST S(9)

2.

Korzystając z konstrukcji Skolema, zbudować ST S(13)

3.

Podać algorytm i napisać program budujący ST S(n) wg konstrukcji Bosego

i Skolema.

background image

Literatura

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Wprowadzenie do

algorytmów

, WNT 2004.

[2] J. Flachsmeyer, Kombinatoryka, PWN 1977.
[3] R. L. Graham, D. E. Knuth, O. Patashnik, Matematyka konkretna,

PWN 1996.

[4] W. Lipski, Kombinatoryka dla programistów, WNT 2004.
[5] W. Lipski, W. Marek, Analiza kombinatoryczna, PWN 1986.
[6] Z. Palka, A. Ruciński, Niekonstruktywne metody matematyki dyskretnej,

WNT 1996.

[7] Z. Palka, A. Ruciński, Wykłady z kombinatoryki, część 1, WNT 1998.
[8] E. M. Reingold, J. Nievergelt, N. Deo, Algorytmy kombinatoryczne,

PWN 1985.

[9] K. A. Ross, C. R. B. Wright, Matematyka dyskretna, PWN 1996.

[10] K. A. Rybnikow (red.) Analiza kombinatoryczna w zadaniach, PWN 1988.
[11] R. J. Wilson, Wprowadzenie do teorii grafów, PWN 1998.
[12] M. Zakrzewski, T. Żak, Kombinatoryka, prawdopodobieństwo i zdrowy roz-

sądek

, Quadrivium 1998.


Wyszukiwarka

Podobne podstrony:
J Jaworski Z Palka J Szymański Matematyka dyskretna dla informatyków
matematyka dyskretna sciaga, Informatyka - uczelnia, WWSI i WAT, wwsi
Matematyka dyskretna ćwiczenia informacje, Uczelnia, II semestr, Matematyka dyskretna Machnicka ćwic
elementy matematyki dyskretnej dla finansistow
Wojciech Kordecki Matematyka Dyskretna
Wojciech Kordecki Matematyka dyskretna, materiały pomocnicze
PK-I-06, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka dyskretna i TPI, 04-10-2012
Test 2, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka dyskretna i TPI, 04-10-2012
wmd4, 1 STUDIA - Informatyka Politechnika Koszalińska, Labki, Matematyka Dyskretna i logika
Podstawy matematyki dla informatyków
md 3z, wisisz, wydzial informatyki, studia zaoczne inzynierskie, matematyka dyskretna
DEgz2-2011 rozw, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzam
TPI CH 2, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka dyskretna i TPI, 04-10-2012
Mat Dyskr i Log, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka Dyskretna i logika, MD
PK-WE Z E, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka dyskretna i TPI, 04-10-2012
PK-WE Z E 2, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka dyskretna i TPI, 04-10-2012
md 2zb, wisisz, wydzial informatyki, studia zaoczne inzynierskie, matematyka dyskretna, pysiak - pd

więcej podobnych podstron