Counting in Two Ways

In one sentence

The total number of marks in a $0/1$ table (an incidence table) can be added up by rows or by columns:

rows \sum (row sum) = number of marks = columns \sum (column sum)

This sounds too simple to be worth saying, yet it is extremely powerful: choose the “rows” and “columns” well, and one side is easy to compute while the other side is exactly the quantity you want. That is counting in two ways (the Fubini principle).

Predict first

$d (j)$ is the number of positive divisors of $j$ . What is $d (1) + d (2) + \dots + d (12)$ ?

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

Example: Σ d(j) = Σ ⌊n/i⌋

Step 1 / 4

Draw the incidence table
The rows are $i = 1, \dots, 12$ and the columns are $j = 1, \dots, 12$ ; put a dot where $i ∣ j$ . The sum $\sum d (j)$ we want is the number of dots in the table.

$# {(i, j) : i ∣ j, 1 \leq i, j \leq 12}$
Count by columns
Count by rows
The two sides are equal

Stop 1 · Families of subsets (Vol. 1)

Rows = elements, columns = subsets, and a dot where “the element belongs to the subset”. Counting by columns gives $\sum ∣ A ∣$ ; counting by rows gives “how many subsets each element belongs to”.

Example: the total size of all the subsets of {1, 2, 3, 4}

Step 1 / 3

Count by columns
Each column is a subset $A$ , and its column sum is $∣ A ∣$ . Adding up $16$ numbers directly is a bit tiring.

$total = A \sum ∣ A ∣$
Count by rows
In general

Stop 2 · People and groups (Vol. 1)

Rows = people, columns = groups, and a dot where “this person is in this group”. If you know every row sum and every column sum, you can work one out from the other.

Tap cells to put 6 people (P) into 4 groups (G). Try to put everyone in exactly 2 groups: how many people does a group have on average? Can the two counts ever give different totals?

Example: each person is in exactly 3 clubs, each club has exactly 6 people, and there are 40 people. How many clubs are there?

Step 1 / 4

Name the unknown
Say there are $m$ clubs. The incidence table has $40$ rows and $m$ columns.

$40 \times m table$
By rows
By columns
Equate

Stop 3 · Sums and combinatorial identities (Vol. 5)

The most beautiful way to prove an identity is to find a set whose two ways of counting give the two sides.

One problem, several solutions

Prove that $(2 2) + (2 3) + \dots + (2 n) = (3 n + 1)$ .

Count in two ways

Count the $3$ -element subsets of ${1, 2, \dots, n + 1}$ . On one hand there are $(3 n + 1)$ of them. On the other hand, sort them by their largest element $k + 1$ ( $k = 2, \dots, n$ ): the other two elements are chosen from ${1, \dots, k}$ , in $(2 k)$ ways. The two sides are equal.

CostYou have to think of “sorting by the largest element”, but then it takes one line.

Mathematical induction

For $n = 2$ both sides are $1$ . If it holds for $n$ , adding $(2 n + 1)$ to the left side gives $(3 n + 1) + (2 n + 1) = (3 n + 2)$ (Pascal's rule), so it holds for $n + 1$ .

CostMechanical and reliable, but it does not show “why” the identity holds.

Stop 4 · Combinatorial estimates (Vol. 6)

To bound how large a family of sets can be, count some kind of “pair”: one side gives an upper bound from the condition, the other is expressed through the size of the family.

Example: 𝓕 is a family of 3-element subsets of {1, …, 7}, and any two of its sets share at most one element. How large can |𝓕| be?

Step 1 / 4

What to count
Count “(pair of elements ${x, y}$ , set $A$ )” with ${x, y} \subseteq A \in F$ .

$N = # {({x, y}, A) : {x, y} \subseteq A \in F}$
Count by sets
Count by pairs of elements
Bound and construction

Practice

Exercise 1Basic

Find $d (1) + d (2) + \dots + d (10)$ , where $d (j)$ is the number of positive divisors of $j$ .

Exercise 2Basic

A grade has $50$ students. Each student is in exactly $2$ clubs, and each club has exactly $5$ students. How many clubs are there?

Exercise 3Advanced

Find $(2 2) + (2 3) + \dots + (2 8)$ .

Exercise 4Challenge

A family of $3$ -element subsets of ${1, 2, \dots, 9}$ has the property that any two of its sets share at most one element. At most how many sets can such a family have?

In one sentence

Example: Σ d(j) = Σ ⌊n/i⌋

Stop 1 · Families of subsets (Vol. 1)

Example: the total size of all the subsets of {1, 2, 3, 4}

Stop 2 · People and groups (Vol. 1)

Example: each person is in exactly 3 clubs, each club has exactly 6 people, and there are 40 people. How many clubs are there?

Stop 3 · Sums and combinatorial identities (Vol. 5)

Count in two ways

Mathematical induction

Stop 4 · Combinatorial estimates (Vol. 6)

Example: 𝓕 is a family of 3-element subsets of {1, …, 7}, and any two of its sets share at most one element. How large can |𝓕| be?

Practice

Mistake Museum · Exhibits from this stop

Each object is counted twice, but you forget to divide

Taking the bound from double counting as the answer

Stops on this line