Counting the Elements of a Finite Set

In the Chinese book: 有限集元素的数目

Too hard to count? Count 0-1 strings, or split by the last element.

What this move does

The number of elements of a finite set $A$ is written $∣ A ∣$ . If you can list them, just count. If you can't, use one of these three moves:

Listing: write out every small case to see the structure.
Correspondence: build a one-to-one correspondence that swaps what you want to count for something easier to count. Subsets $⟷$ 0-1 strings: a $1$ in position $i$ means $i$ is in the subset.
Recursion: split the objects into two classes by whether they contain the last element $n$ . Each class becomes a smaller copy of the same problem.

Move 2 immediately gives the most basic formula: each digit is independently $0$ or $1$ , so

{A ∣ A \subseteq {1, 2, \dots, n}} = 2^{n} .

Grouping by the number of elements, group $k$ has $C_{n}^{k}$ members, so $C_{n}^{0} + C_{n}^{1} + \dots + C_{n}^{n} = 2^{n}$ . The groups by size on the workbench above are exactly one row of Pascal's triangle.

Predict first

How many subsets of ${1, 2, \dots, 8}$ contain $1$ but not $2$ ?

subsets

Choose an answer first; then you can see the result.

Work through one

Problem: how many subsets of ${1, 2, \dots, n}$ contain no two consecutive numbers? Call this number $a_{n}$ .

Recursion: subsets with no two consecutive numbers

Step 1 / 6

Count a small case first
$n = 4$ : of the $16$ subsets, the ones marked ✗ contain two consecutive numbers. Count the ones without ✗: $a_{4} = 8$ .

$a_{4} = 8$
Split by whether 4 is in
The class without 4
The class with 4
The recurrence
Keep going

When it fails

Break it

Counterexample lab: remove one condition

Conclusion: The two sides have the same size

Subsets $\leftrightarrow$ 0-1 strings: different subsets give different strings, and every string can be read back as a subset. So ${1, 2, 3, 4}$ has exactly as many subsets as there are 0-1 strings of length $4$ , namely $16$ .

Practice

Exercise 1Basic

How many subsets of ${1, 2, \dots, 10}$ contain both $3$ and $7$ ?

Exercise 2Basic

How many subsets of ${1, 2, \dots, 10}$ contain no two consecutive numbers? (The empty set counts.)

Exercise 3Advanced

How many subsets of ${1, 2, \dots, 6}$ have an even number of elements? Rule: don't compute $C_{6}^{0} + C_{6}^{2} + \dots$ ; build a one-to-one correspondence instead.

Exercise 4Challenge

How many subsets of ${1, 2, \dots, 10}$ contain no three consecutive integers?

Mistake Museum · Exhibits from this stop

Before you leave, look at the traps other people fell into here.See every exhibit in the museum →

Exhibit

Non-empty proper subsets, but only one thing subtracted

{1, 2, \dots, n}

has

2^{n} - 1

non-empty proper subsets.

What went wrong? Think first, then open

Diagnosis Out of the $2^{n}$ subsets, two have to go: the empty set (not non-empty) and the whole set itself (not proper).

There are

2^{n} - 2

non-empty proper subsets. Before counting, name each object you are excluding, one by one.

“Exclude as many as you name, and name every one you exclude”

Exhibit

Counting through a correspondence that is not one-to-one

Match each subset of

{1, 2, 3, 4}

with the sum of its elements. The sum can only be

0, 1, \dots, 10

, so there are

11

subsets.

What went wrong? Think first, then open

Diagnosis Different subsets can have the same sum: ${1, 4}$ and ${2, 3}$ both sum to $5$ . This correspondence is “many-to-one”, so the two sides do not have the same size (there are actually $16$ subsets).

Before counting through a correspondence, check two things: different objects go to different images (injective), and every image is hit by some object (surjective). Subsets ↔ 0-1 strings passes both checks.

“Only a one-to-one correspondence lets you count the other side instead”