STATE 318: Counting, Permutations with Repetition, and Conditional Probability (Notes)

Permutations with repetition (distinguishable permutations / multinomial)

  • When ordering letters with repeats, the number of distinct arrangements is given by the multinomial formula:
    N=n!n<em>1! n</em>2! ⋯ n<em>k!N = \frac{n!}{n<em>1!\,n</em>2!\,\cdots\,n<em>k!} where n is the total number of items and ni is the multiplicity (how many of type i).
  • This is also called distinguishable permutations (order matters, but repeats are indistinguishable within their type).
  • Special case: when there are only two types (with multiplicities n1 and n2 = n - n1), the formula reduces to the binomial coefficient N = \binom{n}{n1} = \frac{n!}{n1!(n-n_1)!}.$n- A real-world familiar example is the word BOOKKEEPER, which has 10 letters with multiplicities:
    • B: 1, O: 2, K: 2, E: 3, P: 1, R: 1.
    • Distinct arrangements:
      N = \frac{10!}{3!\,2!\,2!\,1!\,1!\,1!} = \frac{10!}{3!\,2!\,2!}.
  • A sequential view (product of binomial choices) also yields the same:
    \binom{10}{3}\cdot\binom{7}{2}\cdot\binom{5}{2}\cdot\binom{3}{1}\cdot\binom{2}{1}\cdot\binom{1}{1} = \frac{10!}{3!\,2!\,2!}.
  • Nomenclature and options:
    • Also called multinomial (sometimes people joke calling it “Christmas” due to many parts).
    • Notation varies; common form is \frac{n!}{n1!\,n2!\,\cdots\,ns!} with n = sum of all ni and s the number of distinct types.
  • Practical tip: for computation, cancel factorials to avoid huge numbers (e.g., cancel common factors in numerator and denominator before evaluating).
  • Summary connection:
    • This is a core counting tool, generalizing binomial/multinomial-type counts.
    • It will reappear in probability distributions (multinomial distribution) and algorithms (e.g., counting with repeats).

Complement rule (probability)

  • Complement principle: P(A^c) = 1 - P(A).
  • Sometimes easier to compute the probability of the complement (e.g., “not this” or “none of these”) instead of directly computing P(A).
  • Note: In some problems, complement is not easier; choose the approach that minimizes cases to count.
  • Example idea: to find probability of having at least one success, compute 1 minus the probability of zero successes.

Conditional probability

  • Notation: P(A|B) denotes the probability of A given that B has occurred.
  • Core identity (Bayes/conditional probability):
    • P(A|B) = \frac{P(A \cap B)}{P(B)},\quad \text{provided }P(B) > 0.
    • Equivalently, P(A \cap B) = P(A|B) \;P(B) = P(B|A) \;P(A).
  • General guidance:
    • The conditioning event B changes the sample space to those outcomes in B.
    • The order of conditioning matters: P(A|B) is not generally equal to P(B|A).
  • Worked examples from the transcript: 1) College distribution example (IST or Other vs. Junior):
    • Suppose there are 27 total IST/Other options and 10 juniors within that group.
    • Then P(Junior | IST or Other) = \frac{10}{27}.
    • The converse question (IST/Other | Junior) uses the counts within the junior group instead.
    • Reminder: In a table approach, you can count intersections and totals and form the ratio directly; in algebraic form, you can use P(A|B) = P(A ∩ B)/P(B).
      2) Caffeine example (morning vs afternoon):
    • Let M = caffeine in the morning, A = caffeine in the afternoon.
    • Given: P(M) = 0.52, P(A) = 0.48, P(M ∩ A) = 0.37.
    • Then:
      • P(A|M) = \frac{P(M ∩ A)}{P(M)} = \frac{0.37}{0.52} ≈ 0.712.
      • P(M|A) = \frac{P(M ∩ A)}{P(A)} = \frac{0.37}{0.48} ≈ 0.771.
    • If you have probabilities, you can multiply through directly; if you have counts, you can form the same ratios from counts.
  • Practical notes:
    • The formula scales to any events A, B; always ensure P(B) > 0 before dividing.
    • A table with counts often makes the intersection and conditional probabilities easier to visualize; probabilities can be obtained by normalizing by the relevant row/column totals.
  • Special case: independence (to come later): if A and B are independent, then P(A ∩ B) = P(A)P(B) and P(A|B) = P(A).
  • Preview: Bayes' theorem and broader conditional-probability tools (tree diagrams, joint distributions) will be covered subsequently.

Conditional probability: sampling without replacement (cards)

  • A classic scenario: drawing without replacement from a deck of cards.
  • Example setup: standard 52-card deck with 4 aces.
  • If you draw two cards in order without replacement:
    • Probability of an ace on the second draw given the first draw was not an ace (base card) is:
      P(A2 = \text{ace} \,|\, A1 \neq \text{ace}) = \frac{4}{51}.
    • If the first card was an ace, the second-draw ace probability would be P(A2 = \text{ace} \;|\; A1 = \text{ace}) = \frac{3}{51}.
  • General intersection approach:
    • The probability of two aces in two draws (no replacement) is
      P(A1 = \text{ace} \;\text{and}\; A2 = \text{ace}) = P(A1 = \text{ace}) \cdot P(A2 = \text{ace} \mid A_1 = \text{ace}) = \frac{4}{52} \cdot \frac{3}{51}.
  • Notation: to reflect the order of draws, you may see subscripts (A1, A2) for the first and second draw.
  • The tree diagram approach (optional): you can branch on the first card and then compute probabilities along each branch; this naturally leads to P(A ∩ B) = P(A)P(B|A).

Fake tables (percentages) to reason about probabilities

  • When given probabilities as percentages, a helpful technique is to imagine a population of 100.
  • Example caffeine problem (percent form):
    • Morning caffeine: 52%
    • Afternoon caffeine: 48%
    • Intersection (morning and afternoon): 37%
  • Build a 100-person table:
    • M ∨ A counts consistent with these numbers: M = 52, A = 48, M ∩ A = 37, etc.
    • The remaining counts are determined by intersections/complements to ensure consistency.
  • Conclusion: this method yields the same conditional probabilities as the raw fractions; it’s a visualization aid, not a new method.

How to approach conditional-probability problems (general workflow)

  • Step 1: clearly name the events involved (e.g., M = morning caffeine, A = afternoon caffeine).
  • Step 2: identify P(B) (the conditioning event) and P(A ∩ B) when you can; if you only have a table, count intersections.
  • Step 3: apply the core formula: P(A|B) = \frac{P(A \cap B)}{P(B)}.IfyouknowP(A)andP(B)andP(A∩B),youcanverifyconsistencyviatheidentityIf you know P(A) and P(B) and P(A ∩ B), you can verify consistency via the identityP(A \cap B) = P(A|B)P(B) = P(B|A)P(A).
  • Step 4: check the bottom (denominator) is positive; beware impossible conditioning events (P(B) = 0).
  • Step 5: if numbers come as probabilities, you can work directly with those; if you have counts, form ratios and normalize by the appropriate total.
  • Step 6: recognize that there are many representations (e.g., as a table, as a tree diagram, or as a short algebraic identity) and choose the one that makes the most sense for the problem.

Independent events and Bayes’ theorem (preview)

  • Independent events: a special case where P(A ∩ B) = P(A)P(B) and P(A|B) = P(A) (and P(B|A) = P(B)).
  • Bayes’ theorem (not fully covered yet) links P(A|B) to P(B|A) and the priors: it’s the general tool for updating beliefs given new evidence.
  • The course will return to these topics to formalize their use in probabilistic reasoning.

Quick takeaway

  • Counting with repeats uses the multinomial coefficient and the formula \frac{n!}{n1!n2!\cdots n_s!}.$$
  • Complement and conditional probability are two of the main tools for analyzing events under uncertainty.
  • In many problems you can switch between counting by intersections or using probabilities directly; both paths lead to the same results when done carefully.
  • Always check wording carefully, as English phrasing around conditional events can be tricky and lead to common misreads.