inclusion-exclusion principle integers modulo n

Question

Consider $\mathbb{Z}_n$ to be the integers modulo $n$ and let $X$ denote the number of functions $f:\mathbb{Z}_n \rightarrow \mathbb{Z}_n$ such that $\forall j \in \mathbb{Z}_n$, $f(j)-f(j-1)\not\equiv j \space (mod \space n)$. Show using inclusion-exlusion that:

$\ X = \left\{ \begin{array}{ll} (n-1)^n+1-n & if \space n \space is \space odd\\ (n-1)^n-1 & \space if \space n \space is \space even.\end{array} \right. $

---

I was thinking of defining $A_i=\{f:\mathbb{Z}_n \rightarrow \mathbb{Z}_n| f(i)-f(i-1)\not\equiv i\}$ $\forall i=1\dots n$

Then we want $|A_1 \cap A_2 \cap \dots \cap A_n|=|A_1 \cup A_2 \cup \dots \cup A_n|-\sum|A_i|+\sum|A_i \cap A_j| - \dots$

For each, $|A_i|=n^{n-1}(n-1)$, but I'm not sure about $|A_1 \cup A_2 \cup \dots \cup A_n|$, or wheater if this is the right approach?

Can anyone please help me?

Answer 1

For all $i \in \left\{0, ..., n -1\right\}$, denote by $E_{i}$ the set of functions $f : \frac{\mathbb{Z}}{n \mathbb{Z}} \rightarrow \frac{\mathbb{Z}}{n \mathbb{Z}}$ such that $f\left(i +p \mathbb{Z}\right) -f\left(i -1 +p \mathbb{Z}\right) = i +p \mathbb{Z}$.

Then, by the inclusion-exclusion principle, we have $$X = n^{n} -\left|\cup_{i = 0}^{n -1} E_{i}\right| = n^{n} -\sum_{k = 1}^{n} (-1)^{k +1} \sum_{0 \leq i_{1} < ... < i_{k} \leq n -1} \left|E_{i_{1}} \cap ... \cap E_{i_{k}}\right|$$

Now, on the one hand, notice that for all $k \in \left\{1, ..., n -1\right\}$ and $0 \leq i_{1} < ... < i_{k} \leq n -1$, $\left|E_{i_{1}} \cap ... \cap E_{i_{k}}\right| = n^{n -k}$ since choosing a function $f : \frac{\mathbb{Z}}{n \mathbb{Z}} \rightarrow \frac{\mathbb{Z}}{n \mathbb{Z}}$ in $E_{i_{1}} \cap ... \cap E_{i_{k}}$ is equivalent to choosing $(n -k)$ elements $f\left(j +p \mathbb{Z}\right) \in \frac{\mathbb{Z}}{n \mathbb{Z}}$ for $j \in \left\{0, ..., n -1\right\} \backslash \left\{i_{1}, ..., i_{k}\right\}$.

On the other hand, notice that $$\sum_{i = 0}^{n -1} i \equiv \left\{ \begin{array}{cl} 0 & \text{if } n \text{ is odd}\\ \frac{n}{2} & \text{if } n \text{ is even} \end{array} \right. \pmod{n}$$ Therefore, we have $$\left|E_{0} \cap ... \cap E_{n -1}\right| = \left\{ \begin{array}{cl} n & \text{if } n \text{ is odd}\\ 0 & \text{if } n \text{ is even} \end{array} \right.$$ Indeed, if $n$ is even and $f : \frac{\mathbb{Z}}{n \mathbb{Z}} \rightarrow \frac{\mathbb{Z}}{n \mathbb{Z}}$ is in $E_{0} \cap ... \cap E_{n -1}$, then $$\frac{n}{2} +p \mathbb{Z} = \sum_{i = 0}^{n -1} f\left(i +p \mathbb{Z}\right) = 0 +p \mathbb{Z}$$ which is a contradiction.
And if $n$ is odd, then choosing a function $f : \frac{\mathbb{Z}}{n \mathbb{Z}} \rightarrow \frac{\mathbb{Z}}{n \mathbb{Z}}$ in $E_{0} \cap ... \cap E_{n -1}$ is equivalent to choosing an element $f\left(0 +p \mathbb{Z}\right) \in \frac{\mathbb{Z}}{n \mathbb{Z}}$.

Thus, we have $$\begin{align*} X & = n^{n} + \sum_{k = 1}^{n -1} \binom{n}{k} (-1)^{k} n^{n -k} + (-1)^{n} \left|E_{0} \cap ... \cap E_{n -1}\right|\\ & = (n -1)^{n} +(-1)^{n +1} + (-1)^{n} \left|E_{0} \cap ... \cap E_{n -1}\right|\end{align*}$$ and finally, $$X = \left\{ \begin{array}{cl} (n -1)^{n} +1 -n & \text{if } n \text{ is odd}\\ (n -1)^{n} -1 & \text{if } n \text{ is even} \end{array} \right.$$