Discrete Mathematics - Courant Institute of Mathematical ...

1 Discrete MathematicsLecture notes , Yale University, Spring 1999L. Lov asz and K. VesztergombiParts of these lecture notes are based onL. Lov asz J. Pelik an K. Vesztergombi: Kombinatorika(Tank onyvkiad o, Budapest, 1972);Chapter 14 is based on a section inL. Lov asz Plummer: Matching theory(Elsevier, Amsterdam, 1979)12 Contents1 Introduction52 Let us count! A party .. Sets and the like .. The number of subsets .. Sequences .. Permutations .. 173 The sum of odd numbers .. Subset counting revisited.

2 Counting regions .. 244 Counting The number of ordered subsets .. The number of subsets of a given size .. The Binomial Theorem .. Distributing presents .. Anagrams .. Distributing money .. 335 Pascal s Identities in the Pascal Triangle .. A bird s eye view at the Pascal Triangle .. 386 Fibonacci Fibonacci s exercise .. Lots of identities .. A formula for the Fibonacci numbers .. 477 Combinatorial Events and probabilities .. Independent repetition of an experiment .. The Law of Large Numbers.

3 538 Integers, divisors, and Divisibility of integers .. Primes and their history .. Factorization into primes .. On the set of primes .. Fermat s Little Theorem .. The Euclidean Algorithm .. Testing for primality .. 6939 Even and odd degrees .. Paths, cycles, and connectivity .. 7710 How to grow a tree? .. Rooted trees .. How many trees are there? .. How to store a tree? .. 8511 Finding the Finding the best tree .. Traveling Salesman .. 9612 Matchings in A dancing problem.

4 Another matching problem .. The main theorem .. How to find a perfect matching? .. Hamiltonian cycles .. 10713 Graph Coloring regions: an easy case .. 11014 A Connecticut class in King Arthur s court11415 A glimpse of Classical cryptography .. 11716 One-time How to save the last move in chess? .. How to verify a password without learning it? .. How to find these primes? .. Public key cryptography .. 12241 IntroductionFor most students, the first and often only area of Mathematics in college is calculus . Andit is true that calculus is the single most important field of Mathematics , whose emergencein the 17th century signalled the birth of modern Mathematics and was the key to thesuccessful applications of Mathematics in the calculus (or analysis) is also very technical.

5 It takes a lot of work even to introduceits fundamental notions like continuity or derivatives (after all, it took 2 centuries justto define these notions properly). To get a feeling for the power of its methods, say bydescribing one of its important applications in detail, takes years of you want to become a mathematician, computer scientist, or engineer, this investmentis necessary. But if your goal is to develop a feeling for what Mathematics is all about,where is it that Mathematical methods can be helpful, and what kind of questions domathematicians work on, you may want to look for the answer in some other fields are many success stories of applied Mathematics outside calculus .

6 A recent hottopic is Mathematical cryptography, which is based on number theory (the study of positiveintegers 1,2,3,..), and is widely applied, among others, in computer security and electronicbanking. Other important areas in applied Mathematics include linear programming, codingtheory, theory of computing. The Mathematics in these applications is collectively calleddiscrete Mathematics . ( Discrete here is used as the opposite of continuous ; it is alsooften used in the more restrictive sense of finite .)The aim of this book is not to cover Discrete Mathematics in depth (it should be clearfrom the description above that such a task would be ill-defined and impossible anyway).

7 Rather, we discuss a number of selected results and methods, mostly from the areas ofcombinatorics, graph theory, and combinatorial geometry, with a little elementary the same time, it is important to realize that Mathematics cannot be done withoutproofs. Merely stating the facts, without saying something about why these facts are valid,would be terribly far from the spirit of Mathematics and would make it impossible to giveany idea about how it works. Thus, wherever possible, we ll give the proofs of the theoremswe state. Sometimes this is not possible; quite simple, elementary facts can be extremelydifficult to prove, and some such proofs may take advanced courses to go through.

8 In thesecases, we ll state at least that the proof is highly technical and goes beyond the scope ofthis important ingredient of Mathematics isproblem solving. You won t be ableto learn any Mathematics without dirtying your hands and trying out the ideas you learnabout in the solution of problems. To some, this may sound frightening, but in fact mostpeople pursue this type of activity almost every day: everybody who plays a game of chess,or solves a puzzle, is solving Discrete Mathematical problems. The reader is strongly advisedto answer the questions posed in the text and to go through the problems at the end ofeach chapter of this book.

9 Treat it as puzzle solving, and if you find some idea that youcome up with in the solution to play some role later, be satisfied that you are beginning toget the essence of how Mathematics hope that we can illustrate that Mathematics is a building, where results are built5on earlier results, often going back to the great Greek mathematicians; that mathematicsis alive, with more new ideas and more pressing unsolved problems than ever; and thatmathematics is an art, where the beauty of ideas and methods is as important as theirdifficulty or Let us count!

10 A partyAlice invites six guests to her birthday party: Bob, Carl, Diane, Eve, Frank and they arrive, they shake hands with each other (strange European custom). Thisgroup is strange anyway, because one of them asks: How many handshakes does thismean? I shook 6 hands altogether says Bob, and I guess, so did everybody else. Since there are seven of us, this should mean 7 6 = 42 handshakes ventures Carl. This seems too many says Diane. The same logic gives 2 handshakes if two personsmeet, which is clearly wrong. This is exactly the point: every handshake was counted twice.