Section 2.1

Bijections and Double Counting

Counting by matching objects to something easier (subsets, compositions, rectangles as pairs of grid lines), counting one quantity two ways, summing over positions (digit sums, sums of all permutations), and combinatorial designs such as secret-sharing locks.

Toolkit

A bijection turns a hard count into an easy one by matching each configuration to a unique combinatorial object (subset, composition, lattice-line pair, word, placement). Double counting evaluates one quantity in two ways — often by summing a local contribution over positions, elements, or classifying by a distinguished part — to force an identity.

Key tools:

Subsets and compositions: compositions of $n$ into positive parts $\leftrightarrow$ subsets of $\{1,\dots,n-1\}$ , giving $2^{n-1}$ .
Grid objects: an axis-aligned rectangle in an $m\times n$ grid $\leftrightarrow$ a pair of vertical and a pair of horizontal lines: $\binom{m+1}{2}\binom{n+1}{2}$ .
Multinomial counting: $\binom{n}{k_1,\dots,k_r}=\frac{n!}{k_1!\cdots k_r!}$ counts words/orderings or placements of distinct items into labelled boxes; $\sum \binom{n}{k_1,\dots,k_r}=r^n$ .
Position-wise summation: total digit sum or total of all permutations equals (contribution per position) $\times$ (number of positions), using uniformity/symmetry of each coordinate.
Subset-parity: $\sum_{k \text{ odd}}\binom{n}{k}=2^{n-1}$ for $n\ge1$ .
Hockey-stick style identities: classify $k$ -subsets by their $j$ -th smallest (or largest) element to collapse weighted sums into a single binomial coefficient.
Double counting incidences (e.g. vertices, boundary cells, coalitions) to derive linear constraints before casework.

Problems