Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic[1] – do not vary smoothly in this way, but have distinct, separated values. | Discrete Mathematics Lecture Notes Yale University Spring 1999 L. Lovasz and K. Vesztergombi Parts of these lecture notes are based on L. LOVASZ - J. PeLIKAN - K. VeSZTERGOMBI KOMBINATORIKA Tankonyvkiado Budapest 1972 Chapter 14 is based on a section in L. Lovasz - . Plummer Matching theory Elsevier Amsterdam 1979 1 2 Contents 1 Introduction 5 2 Let us count 7 A party. 7 Sets and the like. 9 The number of subsets. 12 Sequences. 16 Permutations. 17 3 Induction 21 The sum of odd numbers . 21 Subset counting revisited . 23 Counting regions . 24 4 Counting subsets 27 The number of ordered subsets. 27 The number of subsets of a given size . 28 The Binomial Theorem . 29 Distributing presents. 30 Anagrams. 32 Distributing money. 33 5 Pascal s Triangle 35 Identities in the Pascal Triangle. 35 A bird s eye view at the Pascal Triangle. 38 6 Fibonacci numbers 45 Fibonacci s exercise. 45 Lots of identities. 46 A formula for the Fibonacci numbers. 47 7 Combinatorial probability 51 Events and probabilities. 51 Independent repetition of an experiment. 52 The Law of Large Numbers. 53 8 Integers divisors and primes 55 Divisibility of integers. 55 Primes and their history. 56 Factorization into primes . 58 On the set of primes. 59 Fermat s Little Theorem . 63 The Euclidean Algorithm. 64 Testing for primality. 69
