10.5: Counting subsets

  • A subset of size r is called an r-subset, or an r-combination in the context of counting

Using the k-to-1 rule to count subsets

  • From a set of size 5, if you want to choose 3 elements, there are 5!/2! ways to do so
    • We don’t care about order, so we must divide 5!/2! by 3! in order to get rid of duplicate subsets
    • Thus, the choose notation is created: (nr)=n!r!(n−r)!{ {n \choose r} = { {n!} \over {r!(n-r)!} } }
    • Additionally, (nr)=(nn−r){ {n \choose r} = {n \choose n - r} }
  • Example of using choose notation to count paths on a grid: image

10.6: Subset and permutation examples

  • Typically, we count subsets when the ordering of the elements in the subset do not matter (sometimes marked as indistinguishable, or identical) but permutations when the ordering does matter (sometimes marked as distinguishable)
  • Example showing the difference: image

10.7: Counting by complement

  • To count by complement, we can subtract the number of elements that DO NOT have a desired property from the original set from the number of elements in the original set
    • In other words: $$ { P = S - \overline{P} } $$

10.8: Permutations with repetitions

  • A permutation with repetition is the ordering of a set of items where some elements may be repeated, such as the scrambling of repeated letters in a word
    • Example of counting the number of permutations in MISSISSIPPI: image
  • Formula for counting permutations with repetition: image

10.9: Counting multisets

  • While a set is a collection of unique items, a multiset can have multiple instances of the same instances
    • {1, 2, 3} is a set and a multiset, while {1, 2, 2, 3} is a multiset only
  • Can use a strategy involving code words to count multisets
    • Suppose that we want to count the number of ways to select 12 cookies from 4 types; the following shows a bijection between a multiset and its corresponding code word: image
    • Thus, the number of ways to select cookies is (n+m−1m−1){ {n + m - 1} \choose {m-1} }
    • Table representing the values to what they are in the code word: image
  • In general, the way to select n objects from m varieties can be represented by (n+m−1m−1){ {n + m - 1} \choose {m-1} }
    • This applies to many problems, including ones where indistinguishable objects (such as balls) are distributed amongst distinguishable objects (bins)

10.10: Assignment problems: Balls in bins

  • Table with different ways to organize “balls in bins”, or divide objects amongst distinguishable objects: image

10.11: Inclusion-exclusion principle

  • The principle of inclusion-exclusion is used for finding the cardinality of the union of two sets of known cardinalities
    • Defined as $$ { A \cup B = A + B - A \cap B } $$
    • For three sets, you must add back the intersection of all sets, so:
      • ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣B∩C∣−∣A∩C∣+∣A∩B∩C∣{|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|}
  • Generally, the principle of inclusion-exclusion can be defined as follows: Screen Shot 2023-02-15 at 8 08 27 PM

10.12: Counting problem examples

  • Counting donut varieties with multiple limits: image
  • Counting license plates that match: image