Matematyka dyskretna - wykład 1. Relacje Definicja 1.1 Relacją dwuargumentową nazywamy podzbiór produktu kartezjańskiego X Y , którego elementami są pary uporządkowane (x, y), takie, że x " X i y " Y . Uwaga 1.1 Jeśli R jest relacją w zbiorze XX, to mówimy, że R jest relacją w zbiorze X. Rozważmy relację R " X X. Relację R nazywamy zwrotną, gdy:
(x, x) " R x"X symetryczną, gdy:
(x, y) " R ! (y, x) " R x,y"X antyzwrotną, gdy:
(x, x) " R / x"X słabo antysymetryczną, gdy:
((x, y) " R '" (y, x) " R) ! x = y) x,y"X antysymetryczną, gdy:
(x, y) " R (" (y, x) " R x,y"X Niech X = {x1, . . . , xn} oraz R " X X. Wówczas relacji R możemy przy- porządkować macierz n n zdefiniowaną w następujący sposób:
0, gdy (xi, xj) " R / MR = [rij], gdzie rij = 1, gdy (xi, xj) " R Definicja 1.2 Grafem skierowanym prostym nazywamy parę (V, D), gdzie V jest zbiorem skończonym (zbiór wierzchołków), a D jest podzbiorem V V (zbiór krawędzi skierowanych i łuków) Definicja 1.3 Grafem nieskierowanym nazywamy parę (V, E), gdzie V jest zbiorem skoń- czonym (zbiór wierzchołków), a E ą" P2(V ) (zbiór krawędzi nieskierowanych). P2(V ) - rodzina dwuelementowych podzbiorów zbioru V . Niech R, S będą relacjami w zbiorze X X. Wówczas sumą relacji R, S jest zbiór R *" S, iloczynem (przekrójem) relacji R, S jest zbiór R )" S. Dopełnie- niem relacji R jest zbiór X \ R. Relacją odwrotną do relacji R określamy zbiór: R-1 = {(x, y) " X X: (y, x) " R} Uwaga 1.2 Relacja R " X X jest symetryczna, wtedy i tylko wtedy, gdy R = R-1. Lemat 1.1 Jeżeli (Rt)t"T jest rodziną relacji przechodnich w zbiorze X, to przekrój wszystkich relacji z tej rodziny też jest relacją przechodnią. Definicja 1.4 Przechodnim domknięciem relacji R w zbiorze X nazywamy przekrój wszyst- kich relacji przechodnich zawierających relację R. Przechodnie domknięcie oznaczamy symbolem R" Ponadto zdefiniujmy ciąg relacji: R(1) = R, R(2) = R ć% R, R(n+1) = R ć% R(n). Lemat 1.2 "
R" = R(n) n=1 Dowód: Niech Z = {S " X X: S jest przechodnia '" R " S}. Zauważmy, że:
(x, y) " R ! (x, y) " S ! (x, y) " Z ! R " Z S"Z Wówczas: "
(x, y) " R(n) ! (x, y) " R(m) n=1 m"N A więc istnieją w zbiorze X elementy v1, . . . , vm-1 takie, że: (x, v1) " R '" (v1, v2) " R '" . . . '" (vm-1, y) " R Ponieważ R jest zawarte w każdej relacji S ze zbioru Z, to:
(x, v1) " S '" (v1, v2) " S '" . . . '" (vm-1, y) " S S"Z Ponieważ każda relacja S jest przechodnia, to:
(x, y) " S ! (x, y) " Z S"Z Ostatecznie: "
R(n) ą" Z n=1 Zauważmy, że: "
R = R(1) ą" R(n) n=1 Pokażemy, że R" jest relacją przechodnią. Niech (x, y), (y, z) " R". Wówczas:
(x, y) " R(m) '" (y, z) " R(p) m,p"N Więc istnieją w zbiorze X elementy v1, . . . , vm-1, u1, . . . , up-1 takie, że: (x, v1) " R '" . . . '" (vm-1, y) " R '" (y, u1) " R '" . . . '" (up-1, z) " R Niech y = vm. Wtedy powyższa koniunkcja oznacza, że element (x, z) należy do (m + p)-krotnego złożenia relacji R. A więc: "
(x, z) " R(m+p) ! (x, z) " R(n) n=1 co oznacza przechodniość relacji R". Skoro R" jest relacją przechodnią i za-
wiera relację R, to R" "Z oraz Z ą" R", skąd wynika dowodzona równość. Niech MR = [rij] oraz MS = [sij] będą macierzami relacji R, S w zbiorze skończonym X. Wówczas definiujemy następujące macierze: (a) MR*"S = [ rij (" sij ] (b) MR)"S = [ rij '" sij ] (c) MR-1 = [ rji ]
(d) MR = [ <" rij ] (e) MRć%S = [ cij ] gdzie: cij = (ri1 '" s1j) (" (ri2 '" s2j) (" . . . (" (rin '" snj). Definicja 1.5 Relacja R jest porządkiem w zbiorze P , gdy jest zwrotna, słabo antysyme- tryczna i przechodnia. Jeżeli relacja R jest spójna, to mówimy, że porządek R jest liniowy. Zbiór P , w którym określona jest relacja porządkująca R oznaczamy symbo- lem (P, R) lub (P, ). Definicja 1.6 Niech (P, ) będzie zbiorem uporządkowanym. Przedziałem wyznaczonym przez elementy a, b " P nazywamy podzbiór: [a, b] = {x " P : a x b} Zauważmy następujące wynikania:
[a, b] = ! x " [a, b] ! a x b ! a b
x"P <" (a b) ! [a, b] = (a b) ! a, b " [a, b] Ponadto definiujemy jeszcze następujące przedziały: (a, b] = [a, b] \ {a} (!, b] = {x " P : x b} [a, ) = {x " P : a x} Definicja 1.7 Niech a, b " P i a = b. Element a nazywamy poprzednikiem elementu b
(element b nazywamy następnikiem elementu a), jeśli |[a, b]| = 2, czyli gdy [a, b] = {a, b}. Definicja 1.8 Diagramem Hassego zbioru uporządkowanego nazywamy graf relacji następ- nika. Definicja 1.9 Niech (X, ) będzie zbiorem uporządkowanym. Element a " X nazywamy maksymalnym jeśli nie poprzedza on żadnego elementu w zbiorze X:
<" (a x '" a = x)
x"X Element a " X nazywamy największym, jeśli spełniony jest warunek:
x a x"X Element a " X nazywamy minimalnym, jeśli nie poprzedza go żaden element zbioru X:
<" (x a '" x = a)
x"X Element a " X nazywamy najmniejszym, jeśli spełniony jest warunek:
a x x"X Definicja 1.10 Niech A " X, będzie podzbiorem zbioru uporządkowanego (X, ). Element a " X nazywamy ograniczeniem górnym zbioru A, jeśli zachodzi warunek:
x a x"A Element a " X nazywamy ograniczeniem dolnym zbioru A, jeśli zachodzi warunek:
a x x"A Jeśli zbiór wszystkich ograniczeń górnych zbioru A ma element najmniejszy, to nazywamy go kresem górnym zbioru A i oznaczamy sup A. Jeśli zbiór wszystkich ograniczeń dolnych zbioru A ma element największy, to nazywamy go kresem dolnym zbioru A i oznaczamy inf A. Definicja 1.11 Zbiór uporządkowany (P, ) nazywamy kratą, jeśli każdy dwuelementowy podzbiór zbioru P ma kres górny i kres dolny w zbiorze P . Definujemy działania (" oraz '" w następujący sposód: a (" b = c ! sup{a, b} = c oraz a '" b = c ! inf{a, b} = c Uwaga 1.3 Niech (P, ) będzie zbiorem uporządkowanym i niech a, b, c " P . Jeśli c jest kresem dolnym zbioru {a, b}, to zachodzi warunek:
(d a '" d b) ! d c d"P Jeśli c jest kresem górnym zbioru {a, b}, to zachodzi warunek:
(a d '" b d) ! c d d"P Twierdzenie 1.1 W zbiorze uporządkowanym (P. ) działania (" oraz '" są przemienne, łączne i spełniają warunki pochłaniania, tzn.:
(a (" b) '" a = a i (a '" b) (" b = b a,b"P a,b"P Twierdzenie 1.2 Niech (P, ) będzie zbiorem uporządkowanym i niech a, b " P . Wówczas: a b ! ((a (" b = b) '" (a '" b = a)) Twierdzenie 1.3 Każda krata skończona ma element największy i element najmniejszy. Definicja 1.13 Jeśli krata ma element największy i element najmniejszy, to element b nazy- wamy uzupełnieniem elementu a, jeśli a (" b = 1 oraz a '" b = 0 Definicja 1.14 Mówimy, że krata jest rozdzielna jeśli dla każdych elementów a, b, c prawdzi- we są równości: (a) a '" (b (" c) = (a '" b) (" (a '" c) (b) a (" (b '" c) = (a (" b) '" (a (" c) Definicja 1.15 Algebrą Boole a nazywamy kratę rozdzielną zawierającą element największy i element najmniejszy, w której każdy element ma swoje uzupełnienie. Definicja 1.16 Niech (P, 1) i (Q, 2) będą zbiorami uporządkowanymi. Izomorfizmem zbio- rów uporządkowanych nazywamy każde odwzorowanie odwracalne : P Q takie, że:
(a 1 b ! (a) 2 (b)) a,b"P Definicja 1.17 Niech 1 i 2 będą porządkami w zbiorze P . Mówimy, że 2 jest rozszerze- niem 1, gdy:
(a 1 b ! a 2 b a,b"P Przykład 1.1 Zwykły porządek w zbiorze liczb naturalnych jest rozszerzeniem porządku | wyznaczonego przez relację podzielności.
(a|b ! a b) a,b"N Definicja 1.18 Niech (P1, 1), . . . , (Pn, n) będą zbiorami uporządkowanymi. Utwórzmy zbiór P = P1. . .Pn i zdefiniujmy nowy porządek w zbiorze P . Niech (a1, . . . , an), (b1, . . . , bn) " P , wówczas: (a1, . . . , an) (b1, . . . , bn) ! a1 1 b1 '" . . . '" an n bn Tak określony porządek nazywamy produktowym. Definicja 1.19 Niech (P1, 1), . . . , (Pn, n) będą zbiorami liniowo uporządkowanymi. Niech P = P1. . .Pn. Niech (a1, . . . , an), (b1, . . . , bn) " P . Określmy następujący porządek:
(a1, . . . , an) = (b1, . . . , bn) (a1, . . . , an) (b1, . . . , bn) ! ai bi, gdzie: i = min{t: at bt} Tak zdefiniowany porządek nazywamy leksykograficznym. 2. Rozmieszczanie przedmiotów w pudełkach Niech danych będzie n pudełek i k przedmiotów. Załóżmy, że w każdym pudełku mieści się co najwyżej jeden przedmiot. 1ć% Załóżmy, że pudełka są rozróżnialne i przedmioty są rozróżnialne. Wówczas opisem rozmieszczenia jest funkcja różnowartościowa ze zbioru przedmiotów w zbiór pudełek (wariacja bez powtórzeń). Liczba rozmieszczeń wynosi: n! (n - k)! 2ć% Załóżmy, że pudełka są nierozróżnialne a przedmioty są rozróżnialne. Wów- czas istnieje co najwyżej jedno rozwiązanie. 3ć% Załóżmy, że pudełka są rozróżnialne a przedmioty są nierozróżnialne. Wów- czas opisem rozmieszczenia jest k-elementowy podzbiór zbioru pudełek (kom- binacje bez powtórzeń). Liczba rozmieszczeń wynosi: n! k!(n - k)! 4ć% Załóżmy, że pudełka są nierozróżnialne i przedmioty są nierozróżnialne. Wów- czas istnieje co najwyżej jedno rozwiązanie. Niech teraz w każdym pudełku można umieścić dowolną ilość przedmiotów. 1ć% Załóżmy, że pudełka są rozróżnialne i przedmioty są rozróżnialne. Wówczas jest to wariacja z powtórzeniami. Ilość rozmieszczeń wynosi: nk. 2ć% Załóżmy, że pudełka są nierozróżnialne a przedmioty są rozróżnialne. Wów- czas opisem rozmieszczenia jest podział zbioru pudełek. 3ć% Załóżmy, że pudełka są rozróżnialne a przedmioty są nierozróżnialne. Wów- czas opisem rozmieszczenia jest multizbiór pudełek. 4ć% Załóżmy, że pudełka są nierozróżnialne i przedmioty są nierozróżnialne. Wów- czas opisem rozmieszczenia jest podział liczby k na co najwyżej n składników. Takie podziały nazywamy partycjami liczby k. 3. Kombinacje Definicja 3.1 Niech dany będzie zbiór X, taki że |X| = n. Każdy k-elementowy podzbiór zbioru X nazywamy k-elementową kombinacją zbioru X.
n Liczbę k-elementowych kombinacji zbioru n-elementowego oznaczamy: k Twierdzenie 3.1 Prawdziwe są następujące równości:
n
n n n (a) = 2n (b) = k k n - k k=0
n n - 1 n - 1 n n n - 1 (c) = + (d) = k k - 1 k k k k - 1 Dowód: (b) Niech Pk(X) oznacza rodzinę wszystkich k-elementowych podzbiorów zbio- ru X, a Pn-k(X) - rodzinę wszystkich (n - k)-elementowych podzbiorów zbioru X. Zdefinujemy bijekcję Pk(X) ! Pn-k(X) w ten sposób, że jeśli A " Pk(X) to podzbiorowi A przyporządkujemy zbiór X \ A " Pn-k(X). Tak zdefiniowana funkcja jest różnowartościowa i przekształca zbiór Pk(X)
n na zbiór Pn-k(X). A więc |Pk(X)| = |Pn-k(X)|. Ponieważ |Pk(X)| = k
n n n oraz |Pn-k(X)| = , stąd = . n-k k n-k (c) Niech X = {1, . . . , n} i niech Pk(X) będzie rodziną k-elementowych pod- zbiorów zbioru X. Przedstawmy zbiór Pk(X) w postaci sumy rozłącznych zbiorów A i B. Niech A będzie rodziną wszystkich k-elementowych podzbio- rów zawierających element n i niech B = Pk(X) \ A. Utwórzmy bijekcję A ! Pk-1(Y ), gdzie Y = {1, . . . , n - 1}, w ten sposób, że dowolnemu zbiorowi Z " A przyporządkujemy zbiór Z \ {n}. Taka funk- cja jest 1 - 1 i na co oznacza, że rodzina A jest równoliczna ze zbiorem Pk-1(Y ). Rozpatrzmy teraz zbiór B = Pk(Y ) (bo podzbiory zbioru B są k-elementowe i nie zawierają elementu n). Mamy więc:
n n - 1 n - 1 = |Pk(X)| = |A| + |B| = Pk-1(Y ) + Pk(Y ) = + k k - 1 k (d) Rozpatrzmy zbiór par Z = {(A, x): A " Pk(X) '" x " A}. Elementy zbioru Z mogą być dobrane na dwa sposoby. Możemy najpierw wybrać k-elementowy podzbiór A " X i potem ze zbioru A wybrać element x " A.
n Otrzymujemy, że: |Z| = k. k Możemy odwrócić ten proces i najpierw wybrać element x " X i do niego dobrać taki podzbiór A " X, że x " A.
n-1 Otrzymujemy: |Z| = n , gdyż podzbiór A możemy traktować jako k-1 (k - 1)-elementowy podzbiór zbioru (n - 1)-elementowego. Z powyższych rozważań wynika równość (d). Uwaga 3.1
n n! = k k!(n - k)! Definicja 3.2 Silnią dolną nazywamy wielomian: [x]k = x(x - 1) . . . (x - k + 1) Silnią górną nazywamy wielomian: [x]k = x(x + 1) . . . (x + k - 1) 4. Multizbiory (kombinacje z powtórzeniami) 1ć% Niech n(X) będzie rodziną wszystkich n-elementowych ciągów elementów zbioru X. Zdefiniujmy w tym zbiorze relację róznoważności <" w następujący sposób: (x1, . . . , xn) <" (y1, . . . , yn), gdy istnieje permutacja zbioru wszyst- kich wskazników {1, . . . , n}, taka że yi = x(i), i = 1, . . . , n Tak zdefiniowana relacja dzieli zbiór n(X) na klasy abstrakcji. Każdą taką klasę abstrakcji nazywamy multizbiorem. 2ć% Niech dana będzie funkcja charakterystyczna : X N0, taka że jeśli x " X, to (x) oznacza liczbę wystąpień elementu x w multizbiorze wyznaczonym przez funkcję . Liczba wszystkich elementów wyznaczonych przez wynosi:
(x) x"X 3ć% Niech X = {1, . . . , n}. Wówczas każdy k-elementowy podzbiór zbioru X można utożsamiać z ciągiem silnie rosnącym elementów tego zbioru. Każdy k- elementowy multizbiór można utożsamiać z ciągiem niemalejącym o długości k utworzonym z elementów zbioru X. Twierdzenie 4.1 Liczba k-elementowych multizbiorów utworzonych ze zbioru n-elementowego
n+k-1 jest równa k Dowód: Niech X = {1, . . . , n} i niech Mk(X) oznacza rodzinę wszystkich k-elementowych multizbiorów utworzonych ze zbioru X. Załóżmy, że {x1, . . . , xk} " Mk(X), przy czym x1 . . . xk. Utwórzmy z tego ciągu nowy ciąg {x1, x2 + 1 . . . , xk + k - 1} = {y1, . . . , yk}, gdzie yi = xi + i - 1. Zauważmy, że ciąg {y1, . . . , yk} jest ciągiem rosnącym: yi+1 - yi = (xi+1 + i) - (xi + i - 1) = xi+1 - xi + 1 > 0 Ponadto gdyby xk = n, to yk = n+k -1, niech zatem Y = {1, . . . , n+k -1}. Zatem każdy ciąg niemalejący {x1, . . . , xk} można rozszerzyć do ciągu rosną- cego {y1, . . . , yk}, gdzie y1 < . . . < yk. Postępowanie odwrotne jest tak- że możliwe. Z każdego ciągu {y1, . . . , yk} można utworzyć ciąg niemalejący {y1, y2 - 1, . . . , yk - k + 1} = {x1, . . . , xk}, gdzie xi = yi - i + 1. Zdefiniowaliśmy więc bijekcję Mk(X) ! Pk(Y ), a więc oba te zbiory są
n + k - 1 [n]k = k k! 5. Liczby Stirlinga I rodzaju Definicja 5.1 Liczby Stirlinga I rodzaju to współczynniki wielomianu, który powstaje przez rozwinięcie silni dolnej: n
[x]n = x(x-1) . . . (x-n+1) = s(n, 0)+s(n, 1)x+. . .+s(n, n)xn = s(n, k)xk k=0 Twierdzenie 5.1 Liczby Stirlinga I rodzaju spełniają następujące własności: (a) s(n, n) = 1, n 0 (b) s(n, 0) = s(0, k) = 0, n, k > 0 (c) s(n, k) = s(n - 1, k - 1) - (n - 1)s(n - 1, k) Dowód: (c) n
s(n, k)xk = x(x - 1) . . . (x - n + 2)(x - n + 1) = [x]n-1(x - n + 1) = k=0
= s(n, n)xn + (s(n - 1, k - 1) - (n - 1)s(n - 1, k))xk k=1 Ostatecznie otrzymujemy, że: s(n, k) = s(n - 1, k - 1) - (n - 1)s(n - 1, k), 1 k n - 1 (0 < k < n) gdyż równość wielomianów jest równoważna równości ciągów ich współczyn- ników. 6. Podziały zbioru Definicja 6.1 Podziałem zbioru X nazywamy rodzinę podzbiorów Ą = {B1, . . . , Bk} tego zbioru spełniającą warunki: (a) Bi = , i = 1, . . . , k
(b) Bi )" Bj = , gdy i = j
(c) B1 *" . . . *" Bk = X Zbiory Bi, i = 1, . . . , k nazywamy blokami podziału. Definicja 6.2
Jeżeli Ą = {B1, . . . , Bk} oraz Ą = {B1, . . . , Bm} są podziałami zbioru X, to mówimy, że podział Ą jest drobniejszy od podziału Ą (co zapisujemy Ą Ą ), gdy
Bi ą" Bj i"{1,...,k} j"{1,...,m} Relacja zdefiniowana w zbiorze podziałów zbioru X jest relacją porząd- kującą. Zbiór wszystkich podziałów zbioru X oznaczamy symbolem (X). A więc zbiór ( (X), ) jest zbiorem uporządkowanym. Uwaga 6.1 Niech X = {x1, . . . , xn}. Podziałem najdrobniejszym zbioru X jest podział Ą = {{x1}, . . . , {xn}}. Podziałem najgrubszym jest podział Ą = {X}. Niech dana będzie relacja równoważności <". Wówczas zbiór wszystkich klas abstrakcji oznaczamy symbolem X/<". Zauważmy, że dla klas abstrakcji za- chodzą warunki: (a) dla każdego x " X: x " [x] (b) ([x] )" [y] = ) ! ([x] = [y])
a więc zbiór klas abstrakcji relacji <" jest podziałem zbioru X. Uwaga 6.2 Podział Ą = {B1, . . . , Bk} zbioru X wyznacza relację równoważności <". Re- lację tę definiujemy:
x <" y ! x, y " Bi i"{1,...,k} Twierdzenie 6.1 Jeśli R, R są relacjami równoważności wyznaczonymi przez podziały Ą, Ą , to Ą Ą ! R ą" R . Dowód: ( ! ) Załóżmy, że Ą Ą , Ą = {B1, . . . , Bk}, Ą = {B1, . . . , Bm}. Należy pokazać, że R ą" R .
(x, y) " R ! x, y " Bi ! x, y " Bi ą" Bj ! (x, y) " R i"{1,...,k} j"{1,...,m} Dowód implikacji w przeciwną stronę przebiega podobnie. Uwaga 6.3 Niech Ą, Ą będą podziałami zbioru X. Zdefiniujmy podział Ą następująco:
Ą = {Bi )" Bj: Bi " Ą '" Bj " Ą } \ {} Tak zdefiniowany podział jest drobniejszy od podziałów Ą i Ą . Ponadto Ą jest kresem dolnym pary (Ą, Ą ). Niech teraz relacje R, R będą relacjami równoważności wyznaczonymi przez podziały Ą, Ą i niech R" będzie przechodnim domknięciem relacji R *" R . Wówczas kresem górnym pary (Ą, Ą ) jest podział odpowiadający relacji R". 7. Liczby Stirlinga II rodzaju Definicja 7.1 Liczby podziałów zbioru n-elementowego na k bloków nazywamy liczbami Stirlinga II rodzaju i oznaczamy symbole S(n, k) Defincja 7.2 Niech dany będzie zbiór uporządkowany (P, ). Rangą elementu a " P na- zywamy największą długość łańcucha zawartego w zbiorze {x " P : x a} Uwaga 7.1 Niech (X) oznacza zbiór wszystkich podziałów zbioru X. Wówczas S(n, k) jest liczbą elementów rangi n - k w zbiorze (X). Twierdzenie 7.1 Liczby Stirlinga drugiego rodzaju spełniają następujące zależności: (a) S(n, n) = 1, dla n 0 (b) S(n, 0) = S(0, k) = 0, dla n, k > 0 (c) S(n, k) = S(n - 1, k - 1) + kS(n - 1, k), dla 0 < k < n Dowód: Niech X = {x1, . . . , xn}. (a) S(n, n) oznacza podział n-elementowego zbioru X na n bloków. Jest jeden taki podział: Ą = {{x1}, . . . , {xn}}. (b) S(n, 0) oznacza liczbę podziałów zbioru n-elemetowego na 0 bloków, zaś S(0, k) - liczbę podziałów zbioru pustego na k bloków. (c) Niech k(X) będzie rodziną podziałów zbioru X na k bloków oraz niech X = {1, . . . , n} oraz Y = {1, . . . , n - 1}. Przedstawmy zbiór k(X) w postaci sumy zbiorów A *" B. Niech A będzie rodziną wszystkich podziałów na k bloków, takich że liczba n tworzy oddzielny blok i niech B = k(X) \ A. Jeśli podział Ą = {B1, . . . , Bk-1, n} " A to przyporządkujemy mu podział Ą = {B1, . . . , Bk-1} " k-1(Y ). Ten proces jest odwracalny, gdyż jeśli Ą = {B1, . . . , Bk-1} " k-1(Y ), to podziałowi Ą przyporządkujemy podział Ą = {B1, . . . , Bk-1, n} " A. Stąd |A| = | k-1(Y )|. Rozpatrzmy teraz zbiór B. Załóżmy, że Ą " B, a więc Ą = {B1, . . . , Bk}. Załóżmy, że n " Bk. Podziałowi Ą przyporządkujemy podział Ą = {B1, . . . , Bk-1, Bk \ {n}}. A więc Ą jest podziałem na k bloków zbioru (n - 1)-elementowego, czyli Ą " k(Y ). Spróbujmy odrócić to postępowanie. Niech Ą " k(Y ). Podziałowi Ą przypo-
rządkujemy podział postaci Ąi = {B1, . . . , Bi *" {n}, . . . , Bk}. Takiego przy- porządkowania można dokonać na k sposobów. A więc |B| = | k(Y )| k. Ostatecznie S(n, k) = | k(X)| = |A| + |B| = | k-1(Y )| + | k(Y )| k = = S(n - 1, k - 1) + kS(n - 1, k) Twierdzenie 7.2 Niech |X| = n, |Y | = m|, n m. Liczba wszystkich funkcji odwzorowujących zbiór X na zbiór Y jest równa m!S(n, m). Dowód: Rozważmy dowolną funkcję f: X Y . Zdefinujmy zbiory Dy = f-1({y}) = {x " X: f(x) = y}. Ponieważ funkcja f jest na , to każdy zbiór Dy jest niepusty. Ponadto:
(Dy )" Dz = ) ! Dy = Dz czyli Dy = X
y"Y Dochodzimy do wniosku, że zbiory Dy są podziałem zbioru X na m bloków. Niech teraz X = {B1, . . . , Bm} i Y = {y1, . . . , ym}. Zdefiniujmy funkcję g: X Y w następujący sposób: jeśli istnieje takie i " {1, . . . , m}, że x " Bi, to g(x) = yi. Konstrukcja funkcji g pozwala wnioskować, że wszystkich funkcji odwzoro- wujących zbiór X na zbiór Y jest m!S(n, m). Definicja 7.2 Liczbą Bella nazywamy liczbę wszystkich podziałów zbioru n-elementowego: n
B(n) = S(n, k) k=0 8. Podziały liczb Definicja 8.1 Podziałem liczby naturalnej n nazywamy układ n1, . . . , nk, taki że: n = n1 + . . . + nk. Podział liczby nazywamy partycją. Twierdzenie 8.1 Ilość podziałów liczby n na składniki nie przekraczające r jest równa ilości podziałów tej liczby na co najwyżej r składników. Twierdzenie 8.2 Niech P (n) oznacza ilość wszystkich podziałów liczby n. Wówczas:
exp(Ą 2n/3) 1 " P (n) = + Ś(1) n 4 3 gdzie Ś(1) oznacza ciąg zbieżny do zera, gdy n ".