Lecture 4: Counting

What this lecture covers

This lecture introduces counting as a tool for probability problems where every outcome in a finite sample space is equally likely. In that setting, finding a probability reduces to counting the number of outcomes in an event and dividing by the total number of outcomes, so the lecture develops the basic combinatorial techniques needed to do that counting systematically: the multiplication rule for multi-stage experiments, permutations, counting subsets, and the binomial coefficients.

By the end, you should be able to count outcomes of multi-stage experiments using the multiplication rule, compute permutations and combinations of a set of objects, derive and apply the binomial coefficient formula n choose k, use binomial probabilities for sequences of independent coin tosses, and extend counting to partitioning a set into several groups of prescribed sizes, as in dealing a deck of cards.

Key ideas

• Discrete uniform probability law: when a sample space has N equally likely outcomes, the probability of an event with n outcomes is n/N, so counting n and N solves the problem.
• The multiplication (counting) principle: for a multi-stage experiment where the number of choices at each stage does not depend on earlier choices, the total number of outcomes is the product of the number of choices at each stage.
• Permutations: the number of ways to order n distinct objects is n! (n factorial), built by counting the choices available at each position in the sequence.
• Subsets and binomial coefficients: an n-element set has 2^n subsets in total, and the number of k-element subsets is n choose k = n! / (k!(n-k)!).
• Binomial probabilities: for n independent coin tosses with heads probability p, the probability of exactly k heads is (n choose k) * p^k * (1-p)^(n-k), because every sequence with k heads has the same probability and there are n choose k such sequences.
• Conditioning inside a uniform subset: once you condition on an event whose outcomes were originally equally likely, those outcomes remain equally likely within the conditioning event, so counting still applies.
• Partitioning a set into groups: the number of ways to split n objects into groups of prescribed sizes n1, n2, ... that sum to n is n! / (n1! * n2! * ...).

Walkthrough

Counting and the uniform probability law (0:00)

The lecture frames counting as a tool rather than new probability theory: when a sample space has N equally likely outcomes and an event has n of them, the event's probability is n/N. This motivates the need for systematic counting methods.

The multiplication principle (2:04)

Using a tree with stages that each have a fixed number of choices, the lecture shows that the total number of outcomes is the product of the choices at each stage, illustrated with license plate problems both with and without repeated letters or digits.

Permutations (6:08)

Ordering n elements is treated as filling n slots one at a time, with one fewer choice at each subsequent slot, giving n! total orderings, the count of permutations of n objects.

Counting subsets (8:08)

By treating the inclusion of each element as an independent binary decision, the lecture shows an n-element set has 2^n subsets, checked against the small case n=1. This is then applied to compute the probability that six rolls of a fair die all come up different, using permutations of the six face values.

Binomial coefficients (16:24)

To count k-element subsets of an n-element set, the lecture counts ordered lists of k chosen elements two different ways: directly via the multiplication principle, and by first choosing the subset then ordering it. Equating the two gives n choose k = n!/(k!(n-k)!), checked at the extreme cases k=n and k=0, which also motivates defining 0! = 1. A clever combinatorial argument shows the sum of n choose k over all k equals 2^n, since it counts all subsets by size.

Binomial probabilities for coin tosses (27:36)

For n independent tosses of a coin with heads probability p, every sequence with exactly k heads has probability p^k(1-p)^(n-k), and there are n choose k such sequences, giving the binomial probability formula. The lecture confirms that these probabilities sum to 1 over all possible k, again by a counting argument rather than algebra.

Conditional counting example (35:52)

Given 10 coin tosses with exactly 3 heads, the lecture finds the probability the first two tosses were heads. Even though the coin may be biased so outcomes aren't globally equally likely, all sequences with exactly 3 heads are equally likely, so counting works inside that conditioning event: 8 of the 10 choose 3 sequences with 3 heads start with heads-heads.

Partitioning a set into several groups (43:05)

Generalizing n choose k (a split into two groups) to splitting a set into several groups of prescribed sizes, the lecture works through dealing a 52-card deck into four 13-card hands, deriving the formula n! / (n1! n2! n3! n4!), then uses it to set up (without full algebraic simplification) the probability that every player receives exactly one ace.

Before you watch

• Be comfortable with the multiplication rule and independence of events from earlier lectures in this course.
• Review the discrete uniform probability law, since every counting technique here depends on outcomes being equally likely.

Check your understanding

1. Why does the multiplication principle require the number of choices at each stage to not depend on earlier choices?
2. How does deriving n choose k by counting ordered lists two different ways lead to the formula n!/(k!(n-k)!)?
3. Why does every sequence of n coin tosses with exactly k heads have the same probability, even if the coin is biased?
4. In the 10-tosses-with-3-heads example, why can counting be used even though the coin might not be fair?
5. How does the four-group partition formula generalize the two-group n choose k formula?