Lecture Notes on Discrete Mathematics

Lecture Notes on Discrete Mathematics A. K. Lal September 26, 2012 2 Contents 1 Preliminaries 5 1.1 Basic Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Properties of Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Relations and Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 Counting and Permutations 27 2.1 Principles of Basic Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.1.1 Distinguishable Balls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.1.2 Indistinguishable Balls and Distinguishable Boxes . . . . . . . . . . . . . 36 2.1.3 Indistinguishable Balls and Indistinguishable Boxes . . . . . . . . . . . . . 39 2.1.4 Round Table Configurations . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.2 Lattice Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.2.1 Catalan Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3 Some Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.3.1 Miscellaneous Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3 Advanced Counting 53 3.1 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.2 Principle of Inclusion and Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . 58 4 Polya Theory 63 4.1 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2 Lagrange’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.3 Group Action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.4 The Cycle Index Polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.4.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.4.2 Polya’s Inventory Polynomial . . . . . . . . . . . . . . . . . . . . . . . . . 86 3 4 CONTENTS 5 Generating Functions and Its Applications 93 5.1 Formal Power Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.2 Applications to Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.3 Applications to Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . 106 Chapter 1 Preliminaries We will use the following notation throughout these notes. 1. The empty set, denoted ∅, is a set that has no element. 2. N := {0,1,2,...}, the set of Natural numbers; 3. Z := {...,−2,−1,0,1,2,...}, the set of Integers; 4. Q := {p : p,q ∈ Z, q = 0}, the set of Rational numbers; 5. R := the set of Real numbers; and 6. C := the set of Complex numbers. For the sake of convenience, we have assumed that the integer 0, is also a natural number. This chapter will be devoted to understanding set theory, relations, functions and the principle of mathematical induction. We start with basic set theory. 1.1 Basic Set Theory We have already seen examples of sets, such as N,Z,Q,R and C at the beginning of this chapter. For example, one can also look at the following sets. Example 1.1.1. 1. {1,3,5,7,...}, the set of odd natural numbers. 2. {0,2,4,6,...}, the set of even natural numbers. 3. {...,−5,−3,−1,1,3,5,...}, the set of odd integers. 4. {...,−6,−4,−2,0,2,4,6,...}, the set of even integers. 5. {0,1,2,...,10}. 5 ... - tailieumienphi.vn