= Solution
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\pmod 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. Therefore
$$
\left|\bigcap_{j\in J}A_j\right|=n^{n-k}\qquad(k<n).
$$
This 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 condition
$$
0\equiv\sum_{j=0}^{n-1}j=\frac{n(n-1)}2\pmod n.
$$
It 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 $\binom nk$ <subsets> of size $k$. By the <binomial theorem>,
$$
|X|=\sum_{k=0}^{n-1}(-1)^k\binom nk n^{n-k}+(-1)^nF
=(n-1)^n+(-1)^n(F-1).
$$
Hence \b[the number of admissible <functions> is]
$$
\boxed{|X|=\begin{cases}(n-1)^n+1-n,&n\text{ odd},\\(n-1)^n-1,&n\text{ even}.\end{cases}}
$$
Back to article page
