262080400

10

A. PAWEŁ WOJDA

4.1.3. Liczba podziałów zbioru.

Definicja 2. Rodzinek {Ai}i=jest podziałem zbioru X jeżeli:

(1)    *=U=i.....n^Ai.

(2)    Ai n Aj dla i ^ j.

Definicja 3. Podział zbioru n-elementowego jest typu l^Al2 ^Aa...n^An jeśli zawiera A i zbiorów liczności i (dla i = 1,..., n).

Uwaga: Jeśli istnieje podział n-elementowego zbioru typu l^Al2^A2...n^An, wówczas lAi + 2A2 4"... 4" nA_n = n.

Twierdzenie 14. Jeśli lAi 4- 2A2 4-... 4- n\_n = n wówczas liczba podziałów typu l^Al2^Aa...n^A" dana jest wzorem

n\

P(X_U .... A„) = _AlUj!^_An|(_1!)A₁(2!)A₃...(„|)A„

Dow. ...

4.1.4. Liczby Stirlinga II rodzaju.

Definicja 4. Liczbą Stirlinga II rodzaju nazywamy S(n, k) - liczbę podziałów zbioru n-elementowego na k podzbiorów niepustych.

Twierdzenie 15.

S(n, k)

E

Ai+...+A_n—k; Ai+...+nA„—n

n\

Ai!A₂!...A_n!(l!)^Al(2!)^Az... (n!)^An

Twierdzenie 16. (Zależność rekurencyjna dla liczb Stirlinga II rodzaju)

(1)    S(n,n) = 1 (dla n > Oj,

(2)    S(n, 0) = 0 dla n > 0,

(3)    S(n, k) = S(n — 1, k — 1) 4- kS(n — 1, k) dla 0 < k < n

Dow. ...

4.2. Arytmetyka modularna.

4.2.1. Twierdzenie o dzieleniu liczb całkowitych i jego konsekwencje.

Twierdzenie 17. Dla dowolnych liczb całkowitych a i b, b > 0 istnieją jednoznacznie wyznaczone liczby q,r € Z takie, że a — bq + r, przy czym 0 < r < b.

Liczby q oraz r nazywamy, odpowiednio, ilorazem i resztą dzielenia a przez b. Warto podkreślić, że twierdzenie 17 nie jest tym, które większość studentów pamięta ze szkoły⁶.

Mówimy, że d jest największym wspólnym dzielnikiem liczb całowitych a i b jeżeli

•    d\a i d\b oraz

•    dla każdego cG Z: c|a Ac\b =$■ c\d

^Inaczej: zbiór zbiorów.

^Sprawdź, jaki jest wynik dzielenia liczby —9 przez 7?