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?


1 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.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.