10.1: Sum and Product Rules

  • Counting: The process of finding the total amount of combinations that something can be

  • The product rule is one way to count sequences (or combinations)
    • Let A1,A2,...,Anbe finite sets. Then, ∣A1∗A2∗...∗An∣=∣A1∣∗∣A2∣∗...∗∣An∣{ \text{Let } A_{1}, A_{2}, ..., A_{n} \text{be finite sets. Then, } |A_{1} * A_{2} * ... * A_{n}| = |A_{1}| * |A_{2}| * ... * |A_{n}| }
    • Example: image
  • A set of characters can be called an alphabet, and in an alphabet Σ, Σn is the set of all strings of length n that contain characters only from Σ
    • Cardinality of Σn:
    • ∣Σn∣=∣Σ∗Σ∗...∗Σ∣=∣Σ∣∗∣Σ∣∗...∗∣Σ∣=∣Σ∣n{|Σ^n| = |Σ * Σ * ... * Σ| = |Σ| * |Σ| * ... * |Σ| = |Σ|^n}
  • The sum rule is used when you can make multiple choices but only one seelection is made
    • Consider n sets,A1,A2,...,An. If the sets are pairwise disjoint, then∣A1∪A2∪...∪An∣=∣A1∣+∣A2∣+...+∣An∣{ \text{Consider n sets,} A_{1}, A_{2}, ..., A_{n} \text{. If the sets are pairwise disjoint, then} |A_{1}\cup A_{2}\cup ...\cup A_{n}| = |A_{1}| + |A_{2}| + ... + |A_{n}|}

10.2: The bijection rule

  • The bijection rule states that if there is a bijection from one set to another, then they have the same cardinality
    • A function that maps one set A to another set B is called a bijection if and only if it has a well defined inverse, where the inverse is a function that maps set B to set A
    • This rule can be applied to map a power set to different strings: image
  • The k-to-1 rule applies for functions that map a set A to another set B such that, for every element in A, there are exactly k different elements in B that it maps to
    • Thus, A = B /k

10.3: The generalized product rule

  • The generalized product rule states that, when selecting an item from a set, if the number of choices at each step does not depend on the previous choices, then the number of combinations is the product of the number of choices in each step
    • Definition: image

10.4: Counting permutations

  • An r-permutation is a sequence of r items with no repetitions, all taken from the same set
    • Order matters in sequences, so {A, B, C} is different than {B, C, A}; both are 3-permutations
    • Formula for number of r-permutations: image
  • A permutation is a sequence that contains every element of a set exactly once
    • Formula for number of permutations of a set with n elements:
    • P(n,n)=n∗(n−1)∗...∗2∗1=n!{P(n, n) = n * (n-1) * ... * 2 * 1 = n!}