Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 145 (Topics in Combinatorics)

For edge weights $w_{ij}$, form the out-LaplacianThe directed matrix-tree theorem states that the cofactor $\det L^{(r)}$, obtained by deleting row and column $r$, equals the sum of ${\prod }_{e\in T}{w}_e$ over directed spanning trees oriented towards $r$.

Expand the determinant by permutations, and in each diagonal entry expand the sum of outgoing edge weights. A term chooses one outgoing edge at every vertex other than $r$. If the resulting functional digraph contains a directed cycle, sign-reversing inclusion-exclusion over its cycles cancels the term. The surviving choices are precisely the acyclic ones; every vertex then reaches $r$, so they are rooted directed spanning trees, each with positive sign and its product weight. This proves the theorem.

Solved by gpt-5.6-sol high.

Give every edge weight one and delete the row and column for $v_n$ from the out-Laplacian. Expanding the resulting banded determinant along its last available row givesThe characteristic roots are $2$ and $-1$, and the initial values giveBy the directed matrix-tree theorem, this determinant is exactly the number of directed spanning trees rooted towards $v_n$.

Solved by gpt-5.6-sol high.

The Stirling number of the second kind $\left\{\begin{array}{c}n\\ k\end{array}\right\}$ counts partitions of an $n$-element set into $k$ nonempty unlabeled blocks. Distinguishing the block containing the last element gives

Solved by gpt-5.6-sol high.

For a positive integer $x$, count functions $[n]\to [x]$ by the number $k$ of nonempty fibres. Their fibres form a $k$-block partition in $\left\{\begin{array}{c}n\\ k\end{array}\right\}$ ways, and the blocks receive distinct images in $x^{\underline{k}}$ ways. HenceBoth sides are polynomials of degree $n$ agreeing at every positive integer, so this is a polynomial identity.

Solved by gpt-5.6-sol high.

Partitions of the vertices into independent blocks are the unlabeled colour-class partitions counted by the Graphical Stirling number. ThereforeSince ${\chi }_{P_n}(x)=x(x-1{)}^{n-1}$, the ordinary Stirling identity applied to $x-1$ givesUniqueness in the falling-factorial basis proves the claim.

Solved by gpt-5.6-sol high.

The sum is the chromatic polynomial of the path, so

Solved by gpt-5.6-sol high.

In an independent-block partition of $P_n$, either $v_1,v_n$ lie in different blocks, giving a partition valid for $C_n$, or they lie in the same block. Contracting those endpoints in the second case gives an independent-block partition of $C_{n-1}$. This bijection proves the recurrence. Multiplying by $x^{\underline{k}}$ and summing givesUsing ${\chi }_{P_n}=x(x-1{)}^{n-1}$ and induction from $C_2=P_2$ yields

Solved by gpt-5.6-sol high.

A proper colouring using exactly $k$ colours first partitions the vertices into $k$ nonempty independent colour classes and then injectively assigns $k$ of the $x$ named colours to those classes. These choices numberSumming over $k$ counts every proper colouring exactly once; the expression is the chromatic polynomial ${\chi }_G(x)$.

Solved by gpt-5.6-sol high.

A nonempty Dyck path decomposes uniquely as an up-step, a Dyck path, a down-step, and another Dyck path. Marking each matched outer pair by $x$ givesThe solution with constant term one is

Solved by gpt-5.6-sol high.

Deleting the first up-step and last down-step of a strictly positive walk of semilength $n$ and lowering the remainder by one gives a Dyck path of semilength $n-1$, bijectively. Hence $D_n=C_{n-1}$ and

Solved by gpt-5.6-sol high.

A strictly negative primitive excursion of semilength $n$ has all $2n$ steps negative, so weight ${\sqrt{t}}^{2n}=t^n$. Reflection in the axis identifies it with a strictly positive excursion, givingEvery bridge has a unique decomposition at successive returns to the axis into positive or negative primitive excursions. The sequence construction therefore has generating functionIts exponent of $t$ is half the number of negative steps, proving the asserted interpretation of $f(t,n)$.

Solved by gpt-5.6-sol high.

Since $D(x)=xC(x)=(1-\sqrt{1-4x})/2$,Rationalizing and using the Catalan generating function givesThus the coefficient of every $t^k$, $0\le k\le n$, is $C_n$. The number of bridges with exactly $2k$ negative steps is consequently independent of $k$.

Solved by gpt-5.6-sol high.

Let $v_i\in {\mathbb{F}}_2^n$ be the incidence vector of $S_i$. Thenfor $i\ne j$. If ${\sum }_i{c}_i{v}_i=0$, taking the dot product with $v_j$ gives $c_j=0$. The vectors are linearly independent, so $m\le n$.

Solved by gpt-5.6-sol high.

The required prime-power form of the Frankl-Wilson theorem is: if $A_1,\dots ,A_m\subseteq [n]$, no $|A_i|$ is divisible by $p^r$, and every intersection of $k$ distinct members has size divisible by $p^r$, thenIt follows by associating to each $A_i$ its incidence vector augmented by a constant coordinate and applying the Frankl-Wilson polynomial independence lemma to the $(k-1)$ layers of multilinear intersection polynomials. The hypotheses make the diagonal evaluations nonzero modulo $p^r$ and every $k$-fold off-diagonal evaluation zero; independence leaves at most $(k-1)(n+1)$ polynomials. Applying the theorem gives the desired bound.

When $r=1$, the argument works directly over ${\mathbb{F}}_p$ without the constant-coordinate lift and yields the stronger boundTherefore a family of size $(k-1)(n+1)$ does not exist.

Solved by gpt-5.6-sol high.

The Alon-Tarsi lemma says that if $\mathrm{deg}f\le d_1+\cdots +d_n$ and $A_i$ consists of $d_i+1$ distinct field elements, thenThis follows by applying univariate Lagrange interpolation successively in each variable.

If the displayed coefficient is nonzero, at least one summand has $f(a_1,\dots ,a_n)\ne 0$. This is the coefficient form of the Combinatorial Nullstellensatz.

Solved by gpt-5.6-sol high.

Write each hyperplane as $h_j(x)=0$, normalized so that $h_j(0)=1$, and putThen $P(0)=1$ and $P$ vanishes at every other point of ${\mathbb{F}}_q^n$. Reduce $P$ modulo $x_i^q-x_i$ in every variable. This preserves its function on ${\mathbb{F}}_q^n$, does not increase total degree, and gives the unique representative with each variable degree at most $q-1$.

The unique reduced polynomial for the delta function at zero iswhose total degree is $(q-1)n$. HenceUniqueness follows equally from the Alon-Tarsi lemma on the grids $A_i={\mathbb{F}}_q$.

Solved by gpt-5.6-sol high.