Common themes in counting

  • Break into chunks and then add back together.
  • Break into tasks and then multiply together.
  • Do via the back door – find exactly when you don’t want and what’s left over is what you do want. Combining this with DeMorgan’s Laws can be powerful.
    • Counting: find the total number of ways to accomplish a task and subtract the number of ways that don’t meet your criteria.
    • Probability: take 1 and subtract the probability of what you want not happening.
  • Restrict your viewpoint: if you have 5 pencils in 750 million writing utensils, and you want to know how many ways there are to choose a sample of 3 of the 5 pencils, ignore the rest of the 750 million and compute 5 choose 3.
  • Get rid of overlap: the inclusion-exclusion principle shows up in many different guises.

Leave a Reply

Your email address will not be published. Required fields are marked *