Intermediate Counting and Probability

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