Lecture notes · Math for Computer Science · Lecture 16

Counting Rules I

MIT 6.042J Mathematics for Computer Science, lecture 16, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part introduces counting with sets, sequences, and permutations, and shows how to count the ways to arrange things in order.

Key ideas

A key counting trick is to count a hard set of objects by mapping them to something easier to count. This idea runs through the whole week. 1:13
A set is an unordered collection of distinct elements, meaning no repeats and order does not matter. Its size is called its cardinality. 1:33
A sequence is an ordered collection, where order matters and the same element may appear more than once. 3:37
A permutation of a set is a sequence that uses every element exactly once. For a set of n elements, the number of permutations is n times n minus 1, and so on down to 1. 5:13
You can count permutations by multiplying the number of choices for each position. The first position has n choices, the second has n minus 1, and so on. This product is called n factorial. 9:21

Words to know

Set: A group of different things where the order does not matter. Repeats are not allowed.
Sequence: A list of things in a fixed order. The same thing can appear more than once.
Permutation: One way to arrange every item in a group in a line, using each item exactly once.
Factorial: Multiplying a whole number by every whole number below it, down to 1. For example, 3 factorial is 3 times 2 times 1, which is 6.

Example

Imagine three friends, Ann, Ben, and Cy, lining up for a photo. Each different line-up is one permutation, and there are six possible line-ups. You can count them by noting there are 3 choices for the first spot, 2 for the second, and 1 for the last, which gives 3 times 2 times 1.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part explains what a function is, the three special kinds of functions (surjective, injective, and bijective), and why a permutation counts as a bijection.

Key ideas

A function pairs every element of the starting set X with exactly one element of the set Y. No element of X can be left out or paired with two outputs. 11:06
The lecturer shows that a pairing is not a function if some element has two outputs or no output at all. 13:07
A function is surjective when every element of Y is hit at least once. Nothing in Y is left empty. 14:21
A function is injective when every element of Y is hit at most once. No element of Y gets hit twice. 15:30
A function is bijective when every element of Y is hit exactly once. This happens only when it is both surjective and injective, and a permutation is an example of this. 15:50

Words to know

function: A rule that sends every item in one set to exactly one item in another set.
surjective: Every item in the target set gets hit at least once, so none are left out.
injective: Every item in the target set gets hit at most once, so no two inputs share a target.
bijective: Every item in the target set gets hit exactly once, so it is both surjective and injective.

Example

Think of guests and chairs at a dinner. If each guest sits in exactly one chair, and every chair has exactly one guest, the seating is bijective. If one guest sits in two chairs, it is not a function, because each guest must have exactly one seat.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part explains how comparing set sizes lets you count hard things by matching them up with easier things, and shows how to count subsets with bit sequences.

Key ideas

If a function is surjective (every element in the range gets hit by at least one element in the domain), the domain has at least as many elements as the range. 20:48
If a function is injective (no two domain elements land on the same range element), the domain has at most as many elements as the range. 21:30
A bijection is both one-to-one and onto, so the two sets have exactly the same size. This is the bijection rule: if you can build a bijection, you can count one set by counting the other. 22:34
To count doughnut selections, the lecturer maps each selection to a string of 0s and 1s, where each doughnut is a 0 and each divider between baskets is a 1. Because this mapping can be reversed, it is a bijection, so counting the strings counts the selections. 25:08
To count subsets of a set, map each subset to a bit sequence where bit i is 1 if i is in the subset and 0 if not. Each bit has 2 choices, so there are 2 to the power n sequences for n items. 28:58

Words to know

cardinality: The number of elements in a set. It is how big the set is.
surjective: A function where every element in the target set gets hit by at least one element from the starting set. Nothing is left out.
injective: A function where each target element is hit by at most one starting element. No two starting elements share the same result.
bijection: A pairing where every element on one side matches exactly one element on the other side, with nothing left over on either side.

Example

Think of handing out name tags to guests at a party so that each guest gets exactly one tag and each tag goes to exactly one guest. If every guest gets a tag and every tag is used, the number of guests equals the number of tags. That is the bijection idea: a perfect one-to-one matching means the two groups have the same count.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part shows how to count hard things by matching them to easier things, and how the pigeonhole principle proves that some items must share a property even when you cannot find them.

Key ideas

A bijection is a perfect one-to-one matching between two groups. If you can show one, you can count the easier group and know the count of the harder one. 30:18
The number of subsets of an n-element set equals the number of n-bit sequences, which is 2 to the power of n. Each bit in a sequence says whether one item is in the subset. 30:00
The generalized pigeonhole principle says that if set X is more than k times the size of set Y, then any function from X to Y must send at least k plus 1 elements of X to the same element of Y. 32:24
The pigeonhole principle is the special case where k is 1: if you have more pigeons than holes, at least two pigeons must share a hole. 33:21
The speaker proves the general rule by contradiction. He assumes the opposite, then counts and shows that the total number of elements in X would be too small, which breaks the assumption. 35:03

Words to know

bijection: A perfect matching where every item in one group pairs with exactly one item in the other group, and no item is left out or used twice.
cardinality: The size of a set, meaning how many items it has.
pigeonhole principle: If you put more items into boxes than there are boxes, at least one box must hold two or more items.
non-constructive proof: A proof that shows something must be true without finding or showing the specific example.

Example

Imagine 5 pigeons flying into 4 holes. The pigeons cannot all have their own hole, so at least two must share one. You do not need to see which pigeons they are to know this must happen.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part shows how counting can prove that two groups of numbers must match in some way, even when you never find the matching pair.

Key ideas

A non-constructive proof shows that something is true without giving a specific example. The lecturer contrasts this with the constructive proofs, which build or point to an example, mostly done with induction so far. 40:00
Take 10 two-digit numbers. Some group of them (a subset) must have the same sum as another group. Checking by hand is very hard, so the lecturer uses counting instead. 41:37
There are 2 to the power 10, or 1,024, possible subsets. The possible sums only range up to about 990, which is fewer than 1,024. So by the pigeonhole principle, at least two different subsets must have the same sum. 44:37
A k-to-1 function maps exactly k elements of the domain to each element of the range. Then the domain's size is k times the range's size. This is the division rule. 47:02
The division rule generalizes the bijection rule. A bijection is a 1-to-1 function, so when k equals 1, the domain and range have the same size. 48:41

Words to know

non-constructive proof: A way of showing that something is true without giving a specific example of it. The proof uses reasoning, such as counting, instead.
pigeonhole principle: If you have more items than containers, at least one container must hold two or more items. Here, more subsets than possible sums means two subsets share a sum.
cardinality: The size of a set, or how many elements it has.
bijection: A matching between two sets where every element of one set pairs with exactly one element of the other, with nothing left over on either side.

Example

Imagine you have 1,024 letters and only 991 mailboxes. You cannot put each letter in its own box, so at least one box must get two letters. You know a box has two letters without ever opening the boxes, which is the same kind of reasoning the lecturer used with the subsets.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–1:00:00

This part shows how to count the ways to place 2 identical rooks on a chessboard so that no two share a row or column, by counting sequences and then correcting for double counting.

Key ideas

The goal is to count the ways to place 2 identical rooks on a chessboard so that no row or column is shared. The rooks cannot attack each other, so they must be on different rows and different columns. 50:32
Each placement can be written as a sequence of four numbers, r1, c1, r2, c2, which gives the row and column of each rook. A function f turns each sequence into a valid board configuration. 51:40
The function f is 2 to 1. Swapping the two identical rooks gives a different sequence but the same board, so every valid configuration is reached by exactly two sequences. 55:06
Because f is 2 to 1, the division rule says to count all the valid sequences and then divide by 2. The lesson's counting is 8 × 8 × 7 × 7 sequences, which gives 8 × 8 × 7 × 7 ÷ 2 configurations. (The lesson writes the total as 8 × 7 squared, which looks like a slip; the full product is the correct count.) 57:36
The lesson then starts to state the generalized product rule: for a sequence of length k, multiply the number of choices at each step. The explanation is cut off in this part, so the full rule is not covered here. 58:21

Words to know

sequence: a list of items in a fixed order, like r1, c1, r2, c2, where the order matters.
cardinality: the number of items in a set, or how many things there are to count.
bijective: a matching where every item on one side is paired with exactly one item on the other side. The lesson checks this by asking whether each valid configuration is hit exactly once.
division rule: a counting shortcut: if every outcome is produced by the same number of sequences, count the sequences and divide by that number.

Example

Imagine you have two identical red cups and you want to count the ways to put them on two different shelves. If you list the choices as (shelf for cup 1, shelf for cup 2), then picking shelf A then shelf B and picking shelf B then shelf A describe the same setup, because the cups look the same. Each real arrangement is counted twice, so you divide your total list by 2.

3 checked practice questions for this part are in the app.

Part 7 · 1:00:00–1:10:00

This part shows how to count the number of possible outcomes by multiplying the choices at each step, and it uses that idea to show that a strange-looking property is actually common.

Key ideas

If each step has a fixed number of choices that does not depend on earlier picks, you multiply the choice counts together: n1 times n2 times and so on, up to nk. 1:00:49
When you arrange items in a row with no repeats, the first spot has n choices, the next has one fewer, and so on. Multiplying these gives n factorial. 1:01:54
To count committees with a leader, a secretary, and a consultant from n people, you multiply n, then n minus 1, then n minus 2. 1:04:27
A 'defective' dollar bill has a repeated digit in its 8-digit serial number. It is easier to count the non-defective bills, where all digits differ. Only about 1.8 percent are non-defective, so defective bills are very common. 1:09:18

Words to know

permutation: an ordered arrangement of items, where the order matters and no item is used twice.
factorial: a number written with an exclamation mark, such as n!, equal to n times each smaller whole number down to 1.
fraction: a part of a whole, shown as one number divided by another, such as the share of bills that are non-defective.
counterintuitive: surprising, because it goes against what your first guess would be.

Example

Imagine a club of 10 people choosing a leader, then a secretary, then a consultant, with no one holding two jobs. The leader has 10 choices, the secretary has 9, and the consultant has 8, so there are 10 times 9 times 8 ways to fill the roles. Multiplying the choices at each step gives the total.

3 checked practice questions for this part are in the app.

Part 8 · 1:10:00–1:19:56

This part teaches two basic counting rules, the product rule and the sum rule, and shows how to use them together to count passwords.

Key ideas

A product of sets is the set of all sequences where the first entry comes from the first set, the second from the second set, and so on. To count it, you multiply the sizes of the sets. 1:10:18
When you build a sequence of bits, each bit has 2 choices (0 or 1). So an n-bit sequence has 2 multiplied by itself n times, which is 2 to the power n possibilities. 1:11:50
If sets do not overlap at all (they are disjoint), the number of items in their combined set is just the sum of each set's size. The sum rule adds the counts. 1:12:33
Real counting problems often need both rules at once. The password example first splits passwords into groups by length, adds those groups, and then multiplies the choices within each group. 1:19:27
The lesson says that the full password count comes out to about 1.8 times 10 to the power 14. 1:19:01

Words to know

cardinality: The number of items in a set. If a set has 52 items, its cardinality is 52.
disjoint: Two or more sets that share no items at all. Their overlap is empty.
union: All the items you get when you put several sets together into one combined set.
sequence: An ordered list of items, where the order matters. For example, 0 then 1 is different from 1 then 0.

Example

Suppose you pick an outfit with one shirt from 3 choices and one pair of pants from 2 choices. Each shirt can go with each pair of pants, so you multiply 3 by 2 to get 6 outfits, which is the product rule. If you then choose between two separate lists of shoes that share no pairs, you add the two counts together, which is the sum rule.

3 checked practice questions for this part are in the app.

← Lecture 13: Sums and Asymptotics · Lecture 18: Probability Introduction →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York