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.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-1Correspondence Basics

4.5 More Complicated 1-1 Corespondences

4.6 Clever 1-1 Correspondences

4.7 Summary

5 The Pigeonhole Principle

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

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 ldentities

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 Func ions

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

16 Challenge Problems