CS285 · Chapter 6 · Annotated SlidesCounting
Original
Overview

Counting

The sum, product and subtraction (inclusion–exclusion) rules, permutations and combinations, the binomial theorem, and Pascal’s triangle.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 49 slides
  1. 1 Slide 1
  2. 2 Chapter Summary
  3. 3 Slide 3
  4. 4 Section Summary
  5. 5 The Basics of Counting
  6. 6 Reminder of Few Definitions Concerning SETS
  7. 7 Warm-Up Questions
  8. 8 Basic Counting Principles The SUM Rule:
  9. 9 SUM The Rule of
  10. 10 Slide 10
  11. 11 Warm- Up Questions
  12. 12 Slide 12
  13. 13 Basic Counting Principles - The PRODUCT Rule:
  14. 14 Product Example
  15. 15 Slide 15
  16. 16 Slide 16
  17. 17 Examples
  18. 18 solution
  19. 19 Solution
  20. 20 Solution
  21. 21 Example
  22. 22 Slide 22
  23. 23 Basic Counting Principles: Subtraction Rule
  24. 24 Inclusion - Exclusion
  25. 25 Inclusion - Exclusion
  26. 26 Example
  27. 27 Solution
  28. 28 Slide 28
  29. 29 Section Summary
  30. 30 Permutations
  31. 31 Cominations
  32. 32 Combinations
  33. 33 Permutation, Combination, Factorial
  34. 34 Example
  35. 35 Solution
  36. 36 Example
  37. 37 Solution
  38. 38 Example
  39. 39 Slide 39
  40. 40 Example
  41. 41 Slide 41
  42. 42 Section Summary
  43. 43 Powers of Binomial Expressions
  44. 44 Binomial Coefficients
  45. 45 Binomial Theorem
  46. 46 The Binomial Theorem
  47. 47 Slide 47
  48. 48 Pascal Triangle
  49. 49 Slide 49
Slide 1 / 49

Slide 1

Slide 1: Slide 1
Slide 2 / 49

Chapter Summary

Slide 2: Chapter Summary
Slide 3 / 49

Slide 3

Slide 3: Slide 3
Slide 4 / 49

Section Summary

Slide 4: Section Summary
Slide 5 / 49

The Basics of Counting

Slide 5: The Basics of Counting
Slide 6 / 49

Reminder of Few Definitions Concerning SETS

Slide 6: Reminder of Few Definitions Concerning SETS
Slide 7 / 49

Warm-Up Questions

Slide 7: Warm-Up Questions
Slide 8 / 49

Basic Counting Principles The SUM Rule:

Slide 8: Basic Counting Principles The SUM Rule:

Exam angle

PredictionQ1

A student picks a project from list A (23) or list B (15), no overlap. Number of choices:

Slide 9 / 49

SUM The Rule of

Slide 9: SUM The Rule of
Slide 10 / 49

Slide 10

Slide 10: Slide 10
Slide 11 / 49

Warm- Up Questions

Slide 11: Warm- Up Questions
Slide 12 / 49

Slide 12

Slide 12: Slide 12
Slide 13 / 49

Basic Counting Principles - The PRODUCT Rule:

Slide 13: Basic Counting Principles - The PRODUCT Rule:

Notes

  1. Memory trick "or" → add, "and then" → multiply.

Exam angle

PredictionQ1

How many bit strings of length 8 are there?

PredictionQ2

License plates of 3 letters followed by 3 digits:

Slide 14 / 49

Product Example

Slide 14: Product Example
Slide 15 / 49

Slide 15

Slide 15: Slide 15
Slide 16 / 49

Slide 16

Slide 16: Slide 16
Slide 17 / 49

Examples

Slide 17: Examples
Slide 18 / 49

solution

Slide 18: solution
Slide 19 / 49

Solution

Slide 19: Solution
Slide 20 / 49

Solution

Slide 20: Solution
Slide 21 / 49

Example

Slide 21: Example
Slide 22 / 49

Slide 22

Slide 22: Slide 22
Slide 23 / 49

Basic Counting Principles: Subtraction Rule

Slide 23: Basic Counting Principles: Subtraction Rule
Slide 24 / 49

Inclusion - Exclusion

Slide 24: Inclusion - Exclusion

Notes

  1. |A ∪ B| = |A| + |B| − |A ∩ B|.

Exam angle

PredictionQ1

How many bit strings of length 8 start with 1 or end with 00?

Slide 25 / 49

Inclusion - Exclusion

Slide 25: Inclusion - Exclusion
Slide 26 / 49

Example

Slide 26: Example
Slide 27 / 49

Solution

Slide 27: Solution
Slide 28 / 49

Slide 28

Slide 28: Slide 28
Slide 29 / 49

Section Summary

Slide 29: Section Summary
Slide 30 / 49

Permutations

Slide 30: Permutations

Exam angle

PredictionQ1

Ways to award gold, silver, bronze among 8 runners:

Slide 31 / 49

Cominations

Slide 31: Cominations

Notes

  1. Combination (order doesn’t matter): C(n, r) = n!/(r!(n − r)!), and C(n, r) = C(n, n − r).

  2. Memory trick Ask: does swapping two chosen items give a new outcome? Yes → permutation; no → combination.

Exam angle

PredictionQ1

Ways to choose a 5-player team from 10 people:

Slide 32 / 49

Combinations

Slide 32: Combinations
Slide 33 / 49

Permutation, Combination, Factorial

Slide 33: Permutation, Combination, Factorial
Slide 34 / 49

Example

Slide 34: Example
Slide 35 / 49

Solution

Slide 35: Solution
Slide 36 / 49

Example

Slide 36: Example
Slide 37 / 49

Solution

Slide 37: Solution
Slide 38 / 49

Example

Slide 38: Example
Slide 39 / 49

Slide 39

Slide 39: Slide 39
Slide 40 / 49

Example

Slide 40: Example
Slide 41 / 49

Slide 41

Slide 41: Slide 41
Slide 42 / 49

Section Summary

Slide 42: Section Summary
Slide 43 / 49

Powers of Binomial Expressions

Slide 43: Powers of Binomial Expressions
Slide 44 / 49

Binomial Coefficients

Slide 44: Binomial Coefficients
Slide 45 / 49

Binomial Theorem

Slide 45: Binomial Theorem

Exam angle

PredictionQ1

The coefficient of x²y³ in (x + y)⁵ is:

PredictionQ2

The coefficient of x³ in (2x + 1)⁴ is:

Slide 46 / 49

The Binomial Theorem

Slide 46: The Binomial Theorem
Slide 47 / 49

Slide 47

Slide 47: Slide 47
Slide 48 / 49

Pascal Triangle

Slide 48: Pascal Triangle

Notes

  1. Pascal’s identity: C(n + 1, k) = C(n, k − 1) + C(n, k); each entry = sum of the two above it.

Slide 49 / 49

Slide 49

Slide 49: Slide 49