tailieunhanh - Lecture Notes on Discrete Mathematics

The abuse of technology is evident in some of the examples cited above. Fingers-on-the-buttons has now replaced engagement-of-the-brain with in- creasing frequency. I should also call attention to the insistence in educa- tional documents that students in K-4 be allowed to have access at all times to the calculator ([MAF], ; [N1], ; [N5], ; [UN]). In theory, giving children an extra tool in the form of a calculator can do nothing but “empower” them mathematically, to use a term that is popular these days, but what if the theory is not born out by hard facts? In anecdote after anec- dote, one hears horror stories of the. | Lecture Notes on Discrete Mathematics A. K. Lal September 26 2012 2 Contents 1 Preliminaries 5 Basic Set Theory. 5 Properties of Integers . 8 Relations and Partitions. 16 Functions. 21 2 Counting and Permutations 27 Principles of Basic Counting. 27 Distinguishable Balls. 27 Indistinguishable Balls and Distinguishable Boxes . 36 Indistinguishable Balls and Indistinguishable Boxes. 39 Round Table Configurations. 40 Lattice Paths. 41 Catalan Numbers . 43 Some Generalizations. 46 Miscellaneous Exercises . 50 3 Advanced Counting 53 Pigeonhole Principle. 53 Principle of Inclusion and Exclusion. 58 4 Polya Theory 63 Groups . 63 Lagrange s Theorem. 73 Group Action . 78 The Cycle Index Polynomial . 82 Applications . 84 Polya s Inventory Polynomial. 86