Bijections, Homothety & Structured Counting

A bijection is a proof when both the map and its inverse are described and shown to land in the right set; "reflect" must come with "and the reflected path ends at $(n-1, n+1)$, and reflecting again recovers the original". Catalan numbers count triangulations, parenthesizations, and non-crossing matchings by the same recurrence — an answer of $132$ or $429$ is a strong hint that Catalan is behind it.

Inclusion–exclusion over a STRUCTURED family (the edges of a cycle, the diagonal cells) needs the count $m_k$ of $k$ pairwise-compatible forbidden objects — for a cycle that is the number of $k$-matchings, a Lucas-number-like quantity. Write the general term, compute $m_k$ separately, and only then assemble the alternating sum.

Two proofs to know: the diagonal identity $\sum_j\binom{n-j}{j} = F_{n+1}$ by Pascal's rule (both sides satisfy the Fibonacci recurrence), and the tiling bijection (squares and dominoes). When a count comes out Fibonacci, one of these is the intended proof.

Finite sets have the same size exactly when a bijection exists, so a bijective proof is as rigorous as any computation — provided both directions are verified. The inverse map is the part people skip, and it is usually where a wrong “bijection” breaks: the forward map is often obviously defined, but two different objects can go to the same image, or some target is never reached. Writing $\psi$ explicitly forces you to decode, which is exactly the check that the encoding lost no information.

Step 1 — write $n$ as a row of $n$ dots; there are $n - 1$ gaps between neighbours. A composition with $k$ parts is the same thing as a choice of $k - 1$ gaps in which to place bars: $2 + 1 + 3$ is $\bullet\bullet\,|\,\bullet\,|\,\bullet\bullet\bullet$.

Step 2 — the maps: composition $(c_1, \ldots, c_k) \mapsto$ bar positions $\{c_1, c_1 + c_2, \ldots, c_1 + \cdots + c_{k-1}\}$, a $(k-1)$-subset of $\{1, \ldots, n - 1\}$ because the parts are positive; conversely a subset $p_1 < \cdots < p_{k-1}$ gives the parts $p_1, p_2 - p_1, \ldots, n - p_{k-1}$, all positive. The maps undo each other.

Step 3 — so there are $\binom{n-1}{k-1}$ compositions with $k$ parts and $\sum_k\binom{n-1}{k-1} = 2^{n-1}$ in all; for $n = 6$, $32$.

How to find it. Ordered sums of positive integers are cut points on a line. Positivity of the parts is exactly the condition that the cuts are distinct.

Step 1 — the map $\varphi$ from distinct to odd: write each part as $2^j m$ with $m$ odd and replace it by $2^j$ copies of $m$. The result has only odd parts and the same sum.

Step 2 — the map $\psi$ from odd to distinct: if the odd part $m$ occurs $r$ times, write $r$ in binary, $r = 2^{j_1} + 2^{j_2} + \cdots$ with distinct $j$'s, and replace the $r$ copies by the parts $2^{j_1}m, 2^{j_2}m, \ldots$. These are distinct: parts built from the same $m$ have different powers of $2$, and parts built from different odd $m$ have different odd parts.

Step 3 — they are inverse, because binary representation is unique: grouping the parts of a distinct partition by their odd part $m$, the powers of $2$ that occur are distinct, so they are the binary digits of the number of copies of $m$ that $\varphi$ produces. For $n = 8$: $8 \mapsto 1^8$, $\;7 + 1 \mapsto 7 + 1$, $\;6 + 2 \mapsto 3 + 3 + 1 + 1$, $\;5 + 3 \mapsto 5 + 3$, $\;5 + 2 + 1 \mapsto 5 + 1 + 1 + 1$, $\;4 + 3 + 1 \mapsto 3 + 1^5$ — six on each side.

How to find it. “Distinct” and “any multiplicity” are related by binary expansion; “odd” is what is left after removing powers of $2$. Every number is uniquely (power of $2$) $\times$ (odd).

Step 1 — encoding. Given a tree, repeatedly delete the leaf with the smallest label and write down its neighbour; stop when two vertices remain. The result is a sequence of length $n - 2$ with entries in $\{1, \ldots, n\}$: the Prüfer code. For the tree with edges $14, 24, 45, 35, 56$ the leaves removed are $1, 2, 3, 4$ and the code is $(4, 4, 5, 5)$.

Step 2 — what the code remembers: a vertex of degree $d$ appears exactly $d - 1$ times (it is written once for each neighbour deleted before it, and it is itself deleted or survives with one edge left). So the leaves of the tree are exactly the labels absent from the code.

Step 3 — decoding. At step $i$, the leaf deleted was the smallest label that has not been deleted yet and does not occur among the remaining entries $c_i, \ldots, c_{n-2}$ (those are the vertices that still have an edge to lose); it was joined to $c_i$. After $n - 2$ steps join the two labels left. This rebuilds the edges one by one, so decoding inverts encoding.

Step 4 — conversely, every sequence decodes to a tree: each step joins a vertex that will never be used again to one that is still present, so no cycle forms, and $n - 1$ edges on $n$ vertices without a cycle form a tree, whose code is the sequence we started from. Hence trees and sequences are in bijection: $n^{n-2}$ of each. For $n = 6$ that is $1296$.

How to find it. $n^{n-2}$ counts sequences of length $n - 2$ over $n$ symbols; the question is which canonical order of tearing down a tree records it. “Smallest leaf first” makes the order reconstructible.

Expanding the product chooses, for each $j$, either $1$ (leave $s_j$ out) or $x^{s_j}$ (put it in), and multiplies: each subset contributes $x^{\text{its sum}}$. For the filter, $\sum_{j=0}^{m-1}\omega^{jk}$ is $m$ when $m \mid k$ and $0$ otherwise (a geometric series with ratio $\omega^k \ne 1$ sums to $\tfrac{\omega^{km} - 1}{\omega^k - 1} = 0$). So averaging $F(\omega^j)$ over $j$ keeps exactly the coefficients with $m \mid k$. The work in a problem is evaluating $F(\omega^j)$, and the identity $\prod_{r=0}^{m-1}(x - \omega^r) = x^m - 1$ is what usually does it.

Step 1 — the generating function is $\dfrac{1}{(1 - x)(1 - x^2)(1 - x^5)}$: the three geometric series choose how many coins of each value.

Step 2 — extract the coefficient of $x^{10}$ by the number $c$ of $5$s. For $c = 0$, pay $10$ with $1$s and $2$s: the number of $2$s is $0, \ldots, 5$, six ways. For $c = 1$, pay $5$: $0, 1$ or $2$ twos, three ways. For $c = 2$: one way. Total $6 + 3 + 1 = 10$.

How to find it. Unlimited supply of each item is a geometric series; the coefficient is extracted by conditioning on the largest item, which leaves a simpler series.

Step 1 — $F(x) = \prod_{k=1}^{10}(1 + x^k)$, and we want $\tfrac15\sum_{j=0}^4F(\omega^j)$ with $\omega = e^{2\pi i/5}$.

Step 2 — $F(1) = 2^{10} = 1024$. For $j = 1, \ldots, 4$, $\omega^j$ is again a primitive fifth root, and as $k$ runs over $1, \ldots, 10$, $\omega^{jk}$ runs over all five fifth roots twice. So $F(\omega^j) = \left(\prod_{r=0}^4(1 + \omega^r)\right)^2$.

Step 3 — from $\prod_r(x - \omega^r) = x^5 - 1$ at $x = -1$: $\prod_r(-1 - \omega^r) = -2$, so $\prod_r(1 + \omega^r) = (-1)^5(-2) = 2$, and $F(\omega^j) = 4$.

Step 4 — the count is $\tfrac15(1024 + 4\cdot4) = \tfrac{1040}{5} = 208$.

How to find it. “Sum divisible by $m$” is a filter on the coefficients of a subset-sum generating function; the set $\{1, \ldots, 10\}$ is two full cycles of residues mod $5$, which is what makes the product collapse.

Step 1 — track size and sum at once: $G(x, y) = \prod_{k=1}^{2p}(1 + yx^k)$. The answer is the sum of the coefficients of $y^px^s$ over $p \mid s$, i.e. $\tfrac1p\sum_{j=0}^{p-1}[y^p]\,G(\omega^j, y)$ with $\omega = e^{2\pi i/p}$.

Step 2 — $j = 0$: $G(1, y) = (1 + y)^{2p}$, contributing $\binom{2p}{p}$.

Step 3 — $j \ne 0$: $\omega^{jk}$ runs through all $p$-th roots twice, so $G(\omega^j, y) = \left(\prod_{r=0}^{p-1}(1 + y\omega^r)\right)^2$. From $\prod_r(x - \omega^r) = x^p - 1$ with $x = -\tfrac1y$ and $p$ odd, $\prod_r(1 + y\omega^r) = 1 + y^p$. So $G(\omega^j, y) = 1 + 2y^p + y^{2p}$, contributing $2$.

Step 4 — the answer is $\dfrac1p\left(\binom{2p}{p} + 2(p - 1)\right) = \dfrac{\binom{2p}{p} - 2}{p} + 2$. For $p = 3$ this is $8$, for $p = 5$ it is $52$ — both confirmed by listing.

How to find it. Two constraints (size $p$, sum $\equiv 0$) mean two variables. Put the constraint you filter by roots of unity in $x$, and read the other off as a coefficient in $y$.