Introduction to Counting & Probability (The Art of Problem Solving)

Contents 1 Counting Is Arithmetic 1.1 Introduction 1.2 Counting Lists of Numbers 1.3 Counting with Addition and Subtraction 1.4 Counting Multiple Events 1.5 Permutations 1.6 Summary 2 Basic Counting Techniques 2.1 Introduction 2.2 Casework 2.3 Complementary Counting 2.4 Constructive Counting 2.5 Counting with Restrictions 2.6 Summary 3 Correcting for Overcounting 3.1 Introduction 3.2 Permutations with Repeated Elements 3.3 Counting Pairs of Items 3.4 Counting with Symmetries 3.5 Summary 4 Committees and Combinations 4.1 Introduction 4.2 Committee Forming 4.3 How to Compute Combinations 4.4 Our First Combinatorial Identity 4.5 Summary 5 More With Combinations 5.1 Introduction 5.2 Paths on a Grid 5.3 More Committee-type Problems 5.4 Distinguishability 5.5 Summary 6 Some Harder Counting Problems 6.1 Introduction 6.2 Problems 6.3 Summary 7 Introduction to Probability 7.1 Introduction 7.2 Basic Probability 7.3 Equally Likely Outcomes 7.4 Counting Techniques in Probability Problems 7.5 Summary 8 Basic Probability Techniques 8.1 Introduction 8.2 Probability and Addition 8.3 Complementary Probabilities 8.4 Probability and Multiplication 8.5 Probability with Dependent Events 86* Shooting Stars — a hard problem 8.7 Summary 9 Think About It! 9.1 Introduction 9.2 Problems 9.3 Summary 10 Geometric Probability 10.1 Introduction 10.2 Probability Using Lengths 10.3 Probability Using Areas 10.4 Summary 11 Expected Value 11.1 Introduction 11.2 Definition of Expected Value 11.3 Expected Value Problems 114* A Funky Game 11.5 Summary 12 Pascal’s Triangle 12.1 Introduction 12.2 Constructing Pascal’s Triangle 12.3 Those Numbers Look Familiar! 12.4 An Interesting Combinatorial Identity 12.5 Another Interesting Combinatorial Identity 12.6 Summary 13 The Hockey Stick Identity 13.1 Introduction 13.2 The Problem 13.3 A Step-by-Step Solution 13.4 A Clever Solution 13.5 The Identity 13.6 Summary 14 The Binomial Theorem 14.1 Introduction 14.2 A Little Algebra 14.3 The Theorem 14.4 Applications of the Binomial Theorem 14.5 Using the Binomial Theorem in Identities 14.6 Summary 15 More Challenging Problems 15.1 Introduction 15.2 Problems Hints to Selected Problems Index