Probability and Counting Theory: Cheat Sheet

Essential Concepts

Counting Principles

  • Addition Principle
    • If one event can occur in [latex]A[/latex] ways and a second event can occur in [latex]B[/latex] ways, and both events cannot occur simultaneously, then there are [latex]A + B[/latex] total ways for the first event OR the second event to occur
  • Multiplication Principle (Fundamental Counting Principle)
    • If one event can occur in [latex]A[/latex] ways and a second event can occur in [latex]B[/latex] ways after the first event has occurred, then the two events can occur in [latex]A \cdot B[/latex] ways

Permutations

  • The number of ways to arrange [latex]n[/latex] distinct objects in a specific order is [latex]n![/latex] (n factorial)
  • Formula for selecting [latex]r[/latex] objects from [latex]n[/latex] distinct objects in order: [latex]_nP_r=P(n,r) = \frac{n!}{(n-r)!}[/latex]

Permutations of Non-Distinct Objects

  • When some objects are identical, many arrangements are duplicates
  • Formula: [latex]\frac{n!}{r_1! \cdot r_2! \cdot \ldots \cdot r_k!}[/latex]
  • [latex]n[/latex] is the total number of objects
  • [latex]r_1, r_2, \ldots, r_k[/latex] represent the number of each type of identical object
  • Divide by factorials of repeated items to eliminate duplicate arrangements

Combinations

  • Formula for selecting [latex]r[/latex] objects from [latex]n[/latex] distinct objects: [latex]_nC_r=\binom{n}{r}=C(n,r) = \frac{n!}{r!(n-r)!}[/latex]
  • Use when order doesn’t matter (e.g., selecting committee members, choosing pizza toppings)

Probability

  • Probability is a number between [latex]0[/latex] and [latex]1[/latex] (or [latex]0%[/latex] and [latex]100%[/latex]) describing the likelihood of an event
  • The sample space [latex]S[/latex] is the set of all possible outcomes
  • An event [latex]E[/latex] is any subset of the sample space
  • A probability model lists all possible outcomes and their associated probabilities
  • The sum of all probabilities in a probability model must equal [latex]1[/latex]

Probability with Equally Likely Outcomes

  • Formula: [latex]P(E) = \frac{\text{number of elements in } E}{\text{number of elements in } S} = \frac{n(E)}{n(S)}[/latex]

Union of Two Events

  • The union [latex]E \cup F[/latex] represents the event that [latex]E[/latex] OR [latex]F[/latex] occurs (or both)
  • Formula: [latex]P(E \cup F) = P(E) + P(F) - P(E \cap F)[/latex]

Mutually Exclusive Events

  • Events that cannot occur at the same time (no outcomes in common)
  • For mutually exclusive events: [latex]P(E \cap F) = 0[/latex]

Complement of an Event

  • The complement [latex]E'[/latex] is the set of all outcomes in the sample space that are not in [latex]E[/latex]
  • Formula: [latex]P(E') = 1 - P(E)[/latex]

Binomial Theorem Applications

Finding a Single Term in a Binomial Expansion

  • The [latex]r+1[/latex]th term of [latex](x+y)^n[/latex] is: [latex]\binom{n}{r}x^{n-r}y^r[/latex]
  • To find a specific term without fully expanding:
    1. Identify [latex]n[/latex] (the exponent)
    2. Determine which term you want: [latex]r+1[/latex]th term
    3. Solve for [latex]r[/latex]
    4. Substitute into the formula
  • The binomial coefficient [latex]\binom{n}{r}[/latex] is the same as [latex]C(n,r)[/latex]

Key Equations

Permutations of [latex]n[/latex] distinct objects taken [latex]r[/latex] at a time [latex]P(n,r) = \frac{n!}{(n-r)!}[/latex]
Permutations of [latex]n[/latex] non-distinct objects [latex]\frac{n!}{r_1! \cdot r_2! \cdot \ldots \cdot r_k!}[/latex]
Combinations of [latex]n[/latex] distinct objects taken [latex]r[/latex] at a time [latex]C(n,r) = \frac{n!}{r!(n-r)!}[/latex]
Probability of the union of two events [latex]P(E \cup F) = P(E) + P(F) - P(E \cap F)[/latex]
Probability of the union of mutually exclusive events [latex]P(E \cup F) = P(E) + P(F)[/latex]
Probability of the complement [latex]P(E') = 1 - P(E)[/latex]
The [latex](r+1)[/latex]th term of a binomial expansion [latex]\binom{n}{r}x^{n-r}y^r[/latex]

Glossary

Addition Principle

States that if one event can occur in [latex]A[/latex] ways and a second event can occur in [latex]B[/latex] ways, and both events cannot occur at the same time, then there are [latex]A + B[/latex] ways for the first event OR the second event to occur.

combination

A selection of objects where the order does not matter; the number of ways to choose objects without regard to arrangement.

complement of an event

The complement [latex]E'[/latex] is the set of all outcomes in the sample space that are not in event [latex]E[/latex].

event

Any subset of the sample space; a collection of outcomes from an experiment.

experiment

An activity with an observable result.

intersection of two events

The event [latex]E \cap F[/latex] that occurs if both event [latex]E[/latex] and event [latex]F[/latex] occur simultaneously. Mathematically represents “and.”

Multiplication Principle

States that if one event can occur in [latex]A[/latex] ways and a second event can occur in [latex]B[/latex] ways after the first event has occurred, then the two events can occur in [latex]A \cdot B[/latex] ways. Also known as the Fundamental Counting Principle.

mutually exclusive events

Events that have no outcomes in common; events that cannot occur at the same time.

permutation

An ordering of objects where the order matters; the number of ways to arrange objects in a specific sequence.

probability

A number between [latex]0[/latex] and [latex]1[/latex] (or [latex]0%[/latex] and [latex]100%[/latex]) that describes the likelihood that an event will occur.

probability model

A mathematical description of an experiment listing all possible outcomes and their associated probabilities. The sum of all probabilities must equal [latex]1[/latex].

sample space

The set of all possible outcomes of an experiment, denoted [latex]S[/latex].

union of two events

The event [latex]E \cup F[/latex] that occurs if either event [latex]E[/latex] or event [latex]F[/latex] (or both) occurs. Mathematically represents “or.”