Past exam of the mathematics course of the University of Cambridge / 2014 / ia / Paper 4 / 8E (Numbers and Sets)

For finite sets $A_1,\dots ,A_r$, the inclusion-exclusion principle statesTo prove it, count the contribution of one element. If it belongs to exactly $q\ge 1$ of the sets, it is counted by $\left(\genfrac{}{}{0ex}{}{q}{k}\right)$ intersections of size $k$. Its total weight isusing the binomial theorem. An element belonging to none contributes zero. Summing these weights gives the cardinality of the union and proves the inclusion-exclusion principle. Equivalently, within a finite ambient set $U$, the number avoiding every $A_i$ is the sum over all $J$, with sign $(-1{)}^{|J|}$ and the empty intersection interpreted as $U$.

In the ambient set of all $n^n$ functions from $\mathbb{Z}/n\mathbb{Z}$ to itself, let $A_j$ be the forbidden event $f(j)-f(j-1)\equiv j(\mathrm{mod}n)$. Apply the avoidance form of the inclusion-exclusion principle from part (i).

For a proper subset $J$ of the $n$ cyclic difference constraints, with $|J|=k<n$, the selected edges form disjoint paths around the cycle, including isolated vertices. There are $n-k$ components. On each component, choosing one value of $f$ arbitrarily determines all the other values by the prescribed differences. No consistency condition occurs because the cycle has been broken. ThereforeThis also works for $n=2$, whose two directed constraints use the same pair of vertices: any single constraint leaves one freely chosen value.

If all $n$ constraints hold, summing them around the cycle gives the necessary conditionIt holds when $n$ is odd and fails when $n$ is even, the latter sum being congruent to $n/2$. When it holds, choose $f(0)$ in $n$ ways and determine every other value; the final constraint is then consistent. Thus the full intersection has size $F=n$ for odd $n$ and $F=0$ for even $n$.

There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ subsets of size $k$. By the binomial theorem,Hence the number of admissible functions is