[ Pobierz całość w formacie PDF ]
//-->Grzegorz BobińskiMatematyka DyskretnaWydział Matematyki i InformatykiUniwersytet Mikołaja Kopernika w Toruniu2014Matematyka DyskretnaSpis treści1 Elementy teorii liczb1.11.21.31.41.51.6Twierdzenie o dzieleniu z resztą . . . . . . . . . . . . . . . . .Największy wspólny dzielnik . . . . . . . . . . . . . . . . . . .116Zasadnicze twierdzenie arytmetyki . . . . . . . . . . . . . . . . 12Kongruencje . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18Funkcja i twierdzenie Eulera . . . . . . . . . . . . . . . . . . . 22Zastosowanie teorii liczb w kryptografii . . . . . . . . . . . . . 25272 Elementy kombinatoryki2.12.22.3Podstawowe obiekty kombinatoryczne . . . . . . . . . . . . . . 27Metoda bijektywna . . . . . . . . . . . . . . . . . . . . . . . . 30Reguła włączania i wyłączania . . . . . . . . . . . . . . . . . . 37403 Funkcje tworzące3.13.23.33.4Szeregi formalne . . . . . . . . . . . . . . . . . . . . . . . . . . 40Funkcje tworzące . . . . . . . . . . . . . . . . . . . . . . . . . 41Rekurencja . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44Wielomiany wieżowe . . . . . . . . . . . . . . . . . . . . . . . 5561664 Systemy reprezentantów i twierdzenie Halla5 Ważne ciągi liczbowe5.15.2Liczby Stirlinga . . . . . . . . . . . . . . . . . . . . . . . . . . 66Liczby Bella . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69726 Elementy teorii grafów6.16.26.3Podstawowe definicje . . . . . . . . . . . . . . . . . . . . . . . 72Grafy planarne . . . . . . . . . . . . . . . . . . . . . . . . . . 79Kolorowanie grafów . . . . . . . . . . . . . . . . . . . . . . . . 81iMatematyka DyskretnaBędziemy korzystać z następujących oznaczeń dla zbiorów liczbowych:•symbolemZoznaczać będziemy zbiór liczb całkowitych,•symbolemNoznaczać będziemy zbiór liczb całkowitych nieujemnych,•symbolemN+oznaczać będziemy zbiór liczb całkowitych dodatnich,•jeślii, j∈Z,to[i,j]:={k ∈Z:i≤k≤j}.•jeślii∈Z,to[i,∞[:= {k ∈Z:i≤k}.Jeślin∈Nix1, . . . , xn∈Z,to dla każdej liczbyk∈[0,n]definiujemywyrażeniai∈[1,k]xiii∈[1,k]xiwzoramixi:=i∈[1,k]i∈[1,k−1]jeślik= 0,xi+xkjeślik >0,ixi:=i∈[1,k]1i∈[1,k−1]jeślik= 0,xi·xkjeślik >0.JeśliIjest zbiorem skończonym orazF:I→Cjest funkcją, to definiujemyF(i) :=i∈Ij∈[1,|I|]F(σ(j))ii∈IF(i) :=j∈[1,|I|]F(σ(j)),gdzieσ: [1,|I|] →Ijest ustaloną bijekcją (powyższe definicje nie zależą odwyboru bijekcjiσ).Ogólniej, jeśliIjest zbiorem iF:I→Cjest funkcją taką, że|I|<∞,gdzieI:={i ∈I:F(i) = 0}(funkcje takie będziemy nazywaćsumowalnymi),to definiujemyF(i) :=i∈Ii∈IF(i).iiMatematyka DyskretnaAnalogicznie, jeśliIjest zbiorem iF:I→Cjest funkcją taką, że|I1|<∞,gdzieI1:={i ∈I:F(i) = 1},(funkcje takie będziemy nazywaćwymnażalnymi),to definiujemyF(i) :=i∈Ii∈I1F(i).Zauważmy, że jeśliF:I→N,gdzieI⊆C,oraz funkcjaG:I→Ndanajest wzoremG(i):=xF(i)(i∈I),to funkcjaFjest sumowalna wtedy i tylko wtedy, gdy funkcjaGjest wymna-żalna.iiiMatematyka Dyskretna1.Elementy teorii liczb1.1. Twierdzenie o dzieleniu z resztąDefinicja.Niechaibbędą liczbami całkowitymi. Mówimy, żeliczbaadzieli liczbęb,jeśli istnieje liczba całkowitaktaka, żeb=k·a.Uwaga.Jeśliaibsą liczbami całkowitymi ia= 0,to liczbaadzieli liczbębwtedy ibtylko wtedy, gdy liczbaajest całkowita.Oznaczenie.Jeśli liczba całkowitaadzieli liczby całkowitąb,to piszemya|b.Przykład.2|4.Oznaczenie.Jeśli liczba całkowitaanie dzieli liczby całkowitejb,to piszemya b.Przykład.2 3.Fakt 1.1.Jeśliajest liczbą całkowitą, toa|a.Dowód.Teza wynika z równościa= 1·a.Fakt 1.2.Jeślia, bicsą liczbami całkowitymi,a|bib|c,toa|c.Dowód.Ustalmy liczby całkowitekiltakie, żeb=k·aic=l·b.Wtedyc=(k·l)·a.Fakt 1.3.Jeśliaibsą liczbami całkowitymi,a|bib|a,tob=±a.Dowód.Jeślia= 0 =b,to teza jest oczywista. Bez straty ogólności możemy zatemzałożyć, żea= 0.Ustalmy liczby całkowitekiltakie, żeb=k·aia=l·b.Wtedya=l·k·a,zateml·k= 1.W szczególnościk=±1,co kończydowód.Fakt 1.4.Jeśliajest liczbą całkowitą, to1|a.W szczególności, jeśliajest liczbą1 [ Pobierz całość w formacie PDF ]