CS285 · Annotated SlidesChapter 6 — Counting
Chapter 6 · Annotated slides

Counting

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

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: Slide 1
Exam weight Low

    Chapter Summary

    The Basics of Counting

    Permutations and Combinations

    Binomial Coefficients and Identities

    2
    Exam weight Low

      The Basics of Counting

      6 1

      Section.

      3
      Exam weight Low

        Section Summary

        The Product Rule

        The Sum Rule

        The Subtraction Rule

        The Division Rule

        Examples, Examples, and Examples

        4
        Exam weight Low
          Slide 5: Slide 5
          Exam weight Low
            Slide 6: Reminder of Few Definitions Concerning SETS
            Exam weight Low
              Slide 7: Warm-Up Questions
              Exam weight Low
                Slide 8: Basic Counting Principles The SUM Rule:
                Exam weight High
                1. Sum rule: a task done EITHER one of n₁ ways OR one of n₂ ways (no overlap) → n₁ + n₂ ways.
                🎯 How this can come up · 1 question
                MCQ

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

                Slide 9: SUM The Rule of
                Exam weight Low
                  Slide 10: Slide 10
                  Exam weight Low
                    Slide 11: Warm- Up Questions
                    Exam weight Low
                      Slide 12: Slide 12
                      Exam weight Low
                        Slide 13: Basic Counting Principles - The PRODUCT Rule:
                        Exam weight High
                        1. Product rule: a task done in stages, n₁ ways THEN n₂ ways → n₁·n₂ ways.
                        Memory trick"or" → add, "and then" → multiply.
                        🎯 How this can come up · 2 questions
                        MCQ

                        How many bit strings of length 8 are there?

                        MCQ

                        License plates of 3 letters followed by 3 digits:

                        Slide 14: Product Example
                        Exam weight Low
                          Slide 15: Slide 15
                          Exam weight Low
                            Slide 16: Slide 16
                            Exam weight Low
                              Slide 17: Examples
                              Exam weight Low
                                Slide 18: Slide 18
                                Exam weight Low
                                  Slide 19: Slide 19
                                  Exam weight Low
                                    Slide 20: Slide 20
                                    Exam weight Low
                                      Slide 21: Example
                                      Exam weight Low
                                        Slide 22: Slide 22
                                        Exam weight Low

                                          Basic Counting Principles: Subtraction Rule

                                          Subtraction Rule: If a task can be done either in one of n ways

                                          or in one of n ways, then the total number of ways to do the

                                          +

                                          task is n n minus the number of ways to do the task that are

                                          common to the two different ways.

                                          • Also known as, the principle of inclusion-exclusion:
                                          Basic Counting Principles: Subtraction Rule
                                          23
                                          Exam weight Low
                                          1. Subtraction rule: n₁ + n₂ − (ways counted twice).
                                          Slide 24: Inclusion - Exclusion
                                          Exam weight High
                                          1. |A ∪ B| = |A| + |B| − |A ∩ B|.
                                          🎯 How this can come up · 1 question
                                          MCQ

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

                                          Slide 25: Inclusion - Exclusion
                                          Exam weight Low
                                            Slide 26: Slide 26
                                            Exam weight Low
                                              Slide 27: Solution
                                              Exam weight Low
                                                Slide 28: Slide 28
                                                Exam weight Low

                                                  Section Summary

                                                  Permutations

                                                  Combinations

                                                  Combinatorial Proofs

                                                  29
                                                  Exam weight Low
                                                    Slide 30: Permutations
                                                    Exam weight High
                                                    1. Permutation (order matters): P(n, r) = n!/(n − r)!.
                                                    🎯 How this can come up · 1 question
                                                    MCQ

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

                                                    Slide 31: Cominations
                                                    Exam weight High
                                                    1. Combination (order doesn’t matter): C(n, r) = n!/(r!(n − r)!), and C(n, r) = C(n, n − r).
                                                    Memory trickAsk: does swapping two chosen items give a new outcome? Yes → permutation; no → combination.
                                                    🎯 How this can come up · 1 question
                                                    MCQ

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

                                                    Slide 32: Combinations
                                                    Exam weight Low
                                                      Slide 33: Permutation, Combination, Factorial
                                                      Exam weight Low

                                                        Example

                                                        Example
                                                        34
                                                        Exam weight Low
                                                          Slide 35: Slide 35
                                                          Exam weight Low

                                                            Example

                                                            Example
                                                            36
                                                            Exam weight Low
                                                              Slide 37: Solution
                                                              Exam weight Low
                                                                Slide 38: Slide 38
                                                                Exam weight Low

                                                                  Solution

                                                                  Slide 39
                                                                  39
                                                                  Exam weight Low
                                                                    Slide 40: Slide 40
                                                                    Exam weight Low

                                                                      Binomial Coefficients and Identities

                                                                      Section

                                                                      41
                                                                      Exam weight Low

                                                                        Section Summary

                                                                        The Binomial Theorem

                                                                        and Triangle

                                                                        Pascal’s Identity

                                                                        42
                                                                        Exam weight Low

                                                                          Powers of Binomial Expressions

                                                                          • Definition: A binomial expression is the sum of two terms, such as x + y. (More generally, these terms can be products of constants and variables.)
                                                                          • We can use counting principles to find the coefficients in the n expansion of (x + y) where n is a positive integer.
                                                                          • To illustrate this idea, we first look at the process of expanding (x 3 . + y)
                                                                          • (x + y) (x + y) (x + y) expands into a sum of terms that are the product of a term from each of the three sums.
                                                                          43
                                                                          Exam weight Low
                                                                            Slide 44: Slide 44
                                                                            Exam weight Low

                                                                              Binomial Theorem

                                                                              Binomial Theorem: Let x and y be variables, and n a nonnegative

                                                                              integer. Then:

                                                                              45
                                                                              Exam weight High
                                                                              1. Binomial theorem: (x + y)ⁿ = Σ C(n, j)·xⁿ⁻ʲ·yʲ.
                                                                              🎯 How this can come up · 2 questions
                                                                              MCQ

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

                                                                              MCQ

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

                                                                              Slide 46: The Binomial Theorem
                                                                              Exam weight Low
                                                                                Slide 47: Slide 47
                                                                                Exam weight Low
                                                                                  Slide 48: Pascal Triangle
                                                                                  Exam weight Medium
                                                                                  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: Slide 49
                                                                                  Exam weight Low