Externally indexed torrent

If you are the original uploader, contact staff to have it moved to your account

Textbook in PDF format

This is a book about discrete mathematics which also discusses mathematical reasoning and logic. Since the publication of the first edition of this book a few years ago, I came to realize that for a significant number of readers, it is their first exposure to the rules of mathematical reasoning and to logic. As a consequence, the version of Chapter 1 from the first edition may be a bit too abstract and too formal for those readers, and they may find this discouraging. To remedy this problem, I have written a new version of the first edition of Chapter 1. This new chapter is more elementary, more intuitive, and less formal. It also contains less material, but as in the first edition, it is still possible to skip Chapter 1 without causing any problem or gap, because the other chapters of this book do not depend on the material of Chapter 1. It appears that enough readers are interested in the first edition of Chapter 1, so in this second edition, I reproduce it (slightly updated) as Chapter 2. Again, this chapter can be skipped without causing any problem or gap. In this second edition, I tried to make the exposition simpler and clearer. I added some Figures, some Examples, clarified certain definitions, and simplified some proofs. A few changes and additions were also made.
In Chapter 3, I moved the material on equivalence relations and partitions that used to be in Chapter 5 of the first edition to Section 3.9, and the material on transitive and reflexive closures to Section 3.10. This makes sense because equivalence relations show up everywhere, in particular in graphs as the connectivity relation, so it is better to introduce equivalence relations as early as possible. I also provided some proofs that were omitted in the first edition. I discuss the pigeonhole principle more extensively. In particular, I discuss the Frobenius coin problem (and its special case, the McNuggets number problem). I also created a new section on finite and infinite sets (Section 3.12). I have added a new section (Section 3.14) which describes the Haar transform on sequences in an elementary fashion as a certain bijection. I also show how the Haar transform can be used to compress audio signals. This is a spectacular and concrete illustration of the abstract notion of a bijection. Because the notion of a tree is so fundamental in computer science (and elsewhere), I added a new section (Section 4.6) on ordered binary trees, rooted ordered trees, and binary search trees. I also introduced the concept of a heap. In Chapter 5, I added some problems on the Stirling numbers of the first and of the second kind. I also added a Section (Section 5.5) on Mobius inversion. I added some problems and supplied some missing proofs here and there. Of course, I corrected a bunch of typos. Finally, I became convinced that a short introduction to discrete probability was needed. For one thing, discrete probability theory illustrates how a lot of fairly dry material from Chapter 5 is used. Also, there no question that probability theory plays a crucial role in computing, for example, in the design of randomized algorithms and in the probabilistic analysis of algorithms. Discrete probability is quite applied in nature and it seems desirable to expose students to this topic early on. I provide a very elementary account of discrete probability in Chapter 6. I emphasize that random variables are more important than their underlying probability spaces. Notions such as expectation and variance help us to analyze the behavior of random variables even if their distributions are not known precisely. I give a number of examples of computations of expectations, including the coupon collector problem and a randomized version of quicksort. The last three sections of this chapter contain more advanced material and are optional. The topics of these optional sections are generating functions (including the moment generating function and the characteristic function), the limit theorems (weak law of large numbers, central limit theorem, and strong law of large numbers), and Chernoff bounds