Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 145 / 3

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.