Intermediate Counting and Probability

Description

How to Use This Book Acknowledgements Contents 1. Review of Counting & Probability Basics 1.1 Introduction 1.2 Basic Counting Techniques 1.3 Basic Probability Techniques 1.4 Expected Value 1.5 Pascal's Triangle and the Binomial Theorem 1.6 Summation Notation 1.7 Summary 2. Sets and Logic 2.1 Introduction 2.2 Sets 2.3 Operations on Sets 2.4 Truth and Logic 2.5 Quantifiers 2.6 Summary 3. A Piece of PIE 3.1 Introduction 3.2 PIE With 2 Properties 3.3 PIE With 3 Properties 3.4 Counting Problems With PIE 3.5 PIE With Many Properties 3.6 Counting Items With More Than 1 of Something 3.7 Some Harder PIE Problems 3.8 Summary 4. Constructive Counting and 1-1 Correspondences 4.1 Introduction 4.2 Some Basic Problems 4.3 Harder Constructive Counting Problems 4.4 1-1 Correspondence Basics 4.5 More Complicated 1-1 Correspondences 4.6 Clever 1-1 Correspondences 4.7 Summary 5. The Pigeonhole Principle 5.1 Introduction 5.2 It's Just Common Sense! 5.3 Basic Pigeonhole Problems 5.4 More Advanced Pigeonhole Problems 5.5 Summary 6. Constructive Expectation 6.1 Introduction 6.2 Basic Examples 6.3 Summing Expectations Constructively 6.4 A Coat With Many Patches (Reprise) 6.5 Summary 7. Distributions 7.1 Introduction 7.2 Basic Distributions 7.3 Distributions With Extra Conditions 7.4 More Complicated Distribution Problems 7.5 Summary 8. Mathematical Induction 9. Fibonacci Numbers 9.1 Introduction 9.2 A Motivating Problem 9.3 Some Fibonacci Problems 9.4 A Formula for the Fibonacci Numbers 9.5 Summary 10. Recursion 10.1 Introduction 10.2 Examples of Recursions 10.3 Linear Recurrences 10.4 A Hard Recursion Problem 10.5 Problems Involving Catalan Numbers 10.6 Formulas for the Catalan Numbers 10.7 Summary 11. Conditional Probability 11.1 Introduction 11.2 Basic Examples of Conditional Probability 11.3 Some Definitions and Notation 11.4 Harder Examples 11.5 Let's Make a Deal! 11.6 Summary 12. Combinatorial Identities 12.1 Introduction 12.2 Basic Identities 12.3 More Identities 12.4 Summary 13. Events With States 13.1 Introduction 13.2 State Diagrams and Random Walks 13.3 Events With Infinite States 13.4 Two-player Strategy Games 13.5 Summary 14. Generating Functions 14.1 Introduction 14.2 Basic Examples of Generating Functions 14.3 The Binomial Theorem (as a Generating Function) 14.4 Distributions (as Generating Functions) 14.5 The Generating Function for Partitions 14.6 The Generating Function for the Fibonacci Numbers 14.7 Summary 15. Graph Theory 15.1 Introduction 15.2 Definitions 15.3 Basic Properties of Graphs 15.4 Cycles and Paths 15.5 Planar Graphs 15.6 Eulerian and Hamiltonian Paths 15.7 Summary 16. Challenge Problems References Hints to Selected Problems Index