Discrete Encounters A New Approach Chapman & Hall/CRC Cryptography and Network Security Series

Eschewing the often standard dry and static writing style of traditional textbooks, Discrete Encounters provides a refreshing approach to discrete mathematics. The author blends traditional course topics and applications with historical context, pop culture references, and open problems. This book focuses on the historical development of the subject and provides fascinating details of the people behind the mathematics, along with their motivations, deepening readers? appreciation of mathematics.

This unique book covers many of the same topics found in traditional textbooks, but does so in an alternative, entertaining style that better captures readers? attention. In addition to standard discrete mathematics material, the author shows the interplay between the discrete and the continuous and includes high-interest topics such as fractals, chaos theory, cellular automata, money-saving financial mathematics, and much more. Not only will readers gain a greater understanding of mathematics and its culture, they will also be encouraged to further explore the subject. Long lists of references at the end of each chapter make this easy.

Highlights:

• Features fascinating historical context to motivate readers
• Text includes numerous pop culture references throughout to provide a more engaging reading experience
• Its unique topic structure presents a fresh approach
• The text?s narrative style is that of a popular book, not a dry textbook
• Includes the work of many living mathematicians
• Its multidisciplinary approach makes it ideal for liberal arts mathematics classes, leisure reading, or as a reference for professors looking to supplement traditional courses
• Contains many open problems

Profusely illustrated

Contents

Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix

Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi

Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii

0. Continuous vs. Discrete. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1

1. Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21

2. Proof Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53

3. Practice with Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .85

4. Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .101

5. Venn Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .135

6. The Functional View of Mathematics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .159

7. The Multiplication Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .177

8. Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .197

9. Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .219

10. Pascal and the Arithmetic Triangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .243

11. Stirling and Bell Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .277

12. The Basics of Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .301

13. The Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .327

14. The Tower of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .357

15. Population Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .385

16. Financial Mathematics (and More) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .405

17. More Difference Equations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .427

18. Chaos Theory and Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .453

19. Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .515

20. Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .571

21. Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .641

22. Relations, Partial Orderings, and Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .663

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .691

Craig P. Bauer is a professor of mathematics at York College of Pennsylvania. He’s the

editor-in-chief of Cryptologia and was the 2011–2012 Scholar-in-Residence at the National

Security Agency’s Center for Cryptologic History. He loves to carry out research, write,

and lecture. His previous books areSecret History: The Story of Cryptology and Unsolved!

The History and Mystery of the World’s Greatest Ciphers from Ancient Egypt to Online Secret

Societies. With the present book he stays true to his style, blending mathematics and

history. Craig earned his Ph.D. in mathematics from North Carolina State University

and did his undergraduate work at Franklin & Marshall College.