Is is just something like $n!(1-\frac{1}{n^n})$ because at each of the $a_i$ there is a $\frac{1}{n}$ chance it isn't satisfied

so is the answer some silly formula like that approximately equal for large n to mine?

kunterbunt, I checked your solution for b) and I think you messed up your calculations, more precisely in the second sum and the last part of the reasoning.

Could you either point out an error in my argument or give your reasoning?

In the first part, the second sum isn't $-(n-2)^{n-1}$ you are missing one of the terms of the sum, $2^{n-1}$. On the last part of your solution, you are only considering the possible diferences between the terms of the sequence but you need to multiply by $n$ because there are $n$ diferent $a_{0}$. My doubt about your solution arrised because the final formula should always be divisible by $n$ and at least for n=7 your formula doesn't give a multiple of 7.

You are absolutely right, thank you for your correction. I don't know why I didn't check the result. For completeness, I include the fixed version below.

This can certainly be proved directly, too. I specifically didn't look for a simpler proof because my result didn't look promising...

Here's a different approach: (a) Let $ c_{i} = a_{i+1} - a_{i}$ for $ i=1,2 ... n$ (where $ a_{n+1} = a_{1}$). We have $ c_{1} + ... + c_{n} \equiv 0 (mod n)$, and $ c_{i} \neq i (mod n)$. Consider the sequence $ b_{i} = c_{i} - i$: we require $ b_{1} + ... + b_{n} \equiv c_{1} + ... + c_{n} - [1+2+ ... +n] \equiv 0 (mod n)$, since $ n$ is odd so $ 1+2+ ... + n \equiv n* \frac{n+1}{2} \equiv 0 (mod n)$. Also, $ b_{i} \neq 0 (mod n)$, since $ c_{i} \neq i (mod n)$. We can see easily see that each such set $ b_{i}$ corresponds to exactly $ n$ choices for a set $ a_{i}$ [since there are $ n$ choices for $ a_{1}$, and after all $ a_{i}$ are determined by the $ b_{i}$ sequence]. Thus we need to count the number of sets $ b_{i}$, with $ b_{i} \neq 0 (mod n)$ and $ b_{1} + ... + b_{n} \equiv 0 (mod n)$, and multiply this number by $ n$. Using recurrences, we can quickly do this: Define $ c_{k,l}$ to be the number of sets $ b_{1}, b_{2} ... b_{k}$ such that $ b_{1} + ... + b_{k} \equiv l (mod n)$, and $ b_{j} \neq 0 (mod n)$ for $ 1 \leq j \leq k$. We seek to find $ c_{n,0}$. We have $ c_{1,0} = 0, c_{1,t}=1$ for $ t=2,3...n$. Since $ b_{k} = 1$ or $ 2$ or ... $ n$. If $ b_{k} = p$, the number of such sets is equal to the number sets where $ b_{1} + ... + b_{k-1} = l-p$, which is $ c_{k-1, l-p}$. Thus we have $ c_{k,l} = \sum_{t: 0 \leq t \leq n-1, t \neq l} c_{k-1,t} = [\sum_{t} c_{k-1,t}] - c_{k-1,l} = (n-1)^{k-1} - c_{k-1,l}$, since in our summation $ t \neq l (mod n)$ since $ b_{l} = 0$ is not possible, and $ \sum_{t} c_{k-1,t} = (n-1)^{k-1}$, since the number of sequences $ b_{1} ... b_{k-1}$ together is equal to $ (n-1)^{k-1}$ ($ n-1$ choices for each of the $ k-1$ possible variables). Using this recurrence, we can prove by induction the following: $ c_{k,0} = \frac {(n-1)^k + 1}{n} - 1$ when $ k$ is odd, and $ c_{k,0} = \frac {(n-1)^k - 1}{n} + 1$ when $ k$ is even. To finish off, since $ n$ is odd, we have $ c_{n,0} = \frac {(n-1)^n+1}{n} - 1$. Recalling that our answer is this number multiplied by $ n$, the number of satisfactory sets $ a_{i}$ is: $ (n-1)^n + 1-n$. (b) This is harder since our recurrence method will not work to completion. As in (a), define the sequence $ c_{i}$, and define the sequence $ b_{i} \equiv c_{i} - i (mod n)$. This time we require $ b_{i} \neq 0, i (mod n)$, and we must count how many sequences $ b_{i}$ such that $ b_{1} + ... + b_{n} \equiv 0 (mod n)$. Since $ n$ is prime, denote $ n=p$. As in (a), define the sequence $ c_{k,l}$. Using the same method we used to obtain the recurrence for $ c_{k,l}$ in part (a), we shall do so again now. We obtain, that for $ k \leq p-1$, that $ c_{k,l} = (p-2)^{k-1} - c_{k-1,l} - c_{k-1,l-k}$. Note that we require $ k \leq p-1$, since for $ k=p$, $ c_{k} \neq 0, k (mod n)$, but $ 0 \equiv p (mod p)$, so instead we have that $ c_{p,l} = (p-2)^{p-1} - c_{p-1, l}$. We seek to compute $ c_{p,0}$. Thus we have: $ c_{p,0} = (p-2)^{p-1} - c_{p-1, 0}$. But we have $ c_{p-1, 0} = (p-2)^{p-2} - c_{p-2, 0} - c_{p-2, 1}$, so substituting back in: ${ c_{p, 0} = (p-2)^{p-1} - (p-2}^{p-2} + c_{p-2, 0} + c_{p-2, 1}$. But we can break down $ c_{p-2, 0}$ and $ c_{p-2, 1}$ further, and doing so we obtain $ c_{p, 0} = (p-2)^{p-1} - (p-2)^{p-2} + 2^1* (p-2)^(p-3) - c_{p-3, 0} - c_{p-3, 1} - c_{p-3, 2} - c_{p-3, 3}$. Now, a pattern emerges, and we can utilise it to break down $ c_{p, 0}$ in terms of $ c_{1, 0}, c_{1,1} ... c_{1, p-1}$, all of which we know (since $ c_{1,0} = c_{1,1} = 0$, and the rest are equal to $ 1$). We define the following set recursively: $ S_{1} = {0}$, and if $ S_{k} = {a_{1} ... a_{t}}$, then $ S_{k+1} = {a_{1}, ... a_{t}, a_{1} + k, a_{2} + k, ... a_{t} + k}$ (with repeated elements included. From the pattern that emerges when we keep breaking down $ c_{p,0}$ using the recurrence, we obtain the following: $ c_{p,0} = (p-2)^{p-1} - (p-2)^{p-2} + 2^1 * (p-2)^{p-3} - 2^2* (p-2)^{p-4} ... - 2^{p-3}*(p-2)^{1} + \sum_{t \in \{S_{p-1}\}} c_{1,t}$. Now we note that in this sum, by a trivial induction, $ {S_{p-1}}$ consists of $ 2^{p-2}$ elements; and thus since $ c_{1,t} = 1$ for all $ t$, except when $ t \equiv 0, 1 (mod p)$, $ \sum_{t \in \{S_{p-1}\}} c_{1,t} = 2^{p-2} - X$, where $ X$ is equal to how many elements in $ S_{p-1}$ are equivalant to $ 0, 1 (mod p)$. Next, we can easily see, by induction, that $ S_{n}$ consists of the sum of all subsets of $ {1,2 ... n-1}$ (including the empty subset); thus we need to find how many subsets of $ (1,2 ... p-2)$ have sum equivalant to $ 0$ or $ 1$ in $ Z_{p}$. However, we can see that a subset of $ (1,2 ... p-1)$ has sum equal to $ 0$ in $ Z_{p}$ either when: [1] it doesn't have $ p-1$, and the remaining elements sum to $ 0 (mod p)$ or [2] it does have $ p-1$, and the remaining elements, a subset of $ (1,2 .. p-2)$ sum to $ 1 (mod p)$. Thus, effectively, our number $ X$ is equal to the number of subsets of $ (1,2 ... p-1)$ which have sum divisible by $ p$. But we can see, that this number is equal to half the number of subsets of $ (1,2 ... p)$ which have sum divisible by $ p$ since, a subset of $ (1,2 ... p)$ has sum divisible by $ p$ [1] when it doesn't contain $ p$, and the remaining elements have sum divisible by $ p$ [2] it does have $ p$, and the remaining elements have sum divisible by $ p$. So now we must count how many subsets of $ {1,2 .. p}$ have sum divisible by $ p$, half that to find $ X$, and then compute $ c_{p,0}$ from the above formula. My way of counting such subsets of $ (1,2 .. p)$ is complete overkill: it's a slight variant of the method used in Special Prize solution to IMO 95/6. For $ k \neq 1, p$, we shall prove that the number of subsets of $ (1,2 ... p)$, of size $ k$, whose sum is divisible by $ p$, is equal to $ \frac {\binom pk}{p}$. Let $ a_{m}$ be the number of subsets, size $ k$, whose sum is equivalant to $ k (mod p)$. Consider a $ p$-th root of unity, $ w$. Consider polynomial $ P(x) = x^{p} - 1 = \prod_{1 \leq j \leq p} (x - w^j)$. Consider the sum of products of roots, taken $ k$ at a time. Since coefficient of $ x^{p-k}$ in $ P(x)$ is $ 0$, we have: $ 0 = \sum_{1 \leq j_{1} < j_{2} ... <j_{k} \leq p} w^{j_{1}}*w^{j_{2}} ... w^{j_{k}}$ But the RHS is equal to $ w^{s}$, whenever $ j_{1} + ... + j_{k} \equiv s (mod p)$. There are $ a_{s}$ such sets. So we have the following: $ 0 = a_{0} + a_{1} * w^{1} + a_{2} * w^{2} ... + a_{p-1}*w^{p-1}$. Since the minimal polynomial of $ w$ in $ Q[x]$ is $ 1+x+x^2... + x^{p-1} = 0$, we thus have $ a_{0} = a_{1} ... = a_{p-1}$. But since $ a_{0} + .. + a_{p-1} = \binom pk$, we have $ a_{0} = \frac {\binom pk}{p}$. Thus the number of subsets, of size $ k$ which have sum $ 0 (mod p)$ is $ \frac {\binom pk}{p}$: so the total number of such subsets is $ 2 + \frac {\sum_{1 \leq k \leq p-1} \binom pk }{p} = \frac {2^p + 2p - 2}{p}$ (using Binomial Theorem, and the fact that we have two extra sets, $ 1$ for each $ k=1$, $ k=p$). Thus $ X = \frac {2^{p-1}-1}{p} + 1$. Finishing off now is just computations. We have: $ \sum_{t \in \{S_{p-1}\}} c_{1,t} = 2^{p-2} - X = 2^{p-2} - [\frac {2^{p-1}-1}{p} + 1]$, so then, from above, $ c_{p,0} = (p-2)^{p-1} - (p-2)^{p-2} + 2^1 * (p-2)^{p-3} - 2^2* (p-2)^{p-4} ... - 2^{p-3}*(p-2)^{1} + \sum_{t \in \{S_{p-1}\}} c_{1,t} = (p-2)^{p-1} - (p-2)^{p-2} [ 1 + Y + Y^2 ... + Y^{p-3} ] + 2^{p-2} - [\frac {2^{p-1}-1}{p} + 1] = \frac {(p-1)((p-2)^{p-1}-1)}{p}$, where $ Y = \frac {-2}{p-2}$, since we can use sum of geometric series. Here I've skipped all of the computations, they're very simple. The answer is $ p$ times $ c_{p,0}$ (going back to the very beginning), i.e. $ (p-1)[ (p-2)^{p-1} - 1]$.

Part a.) It is equivalent to find the number of tuples $(x_1, x_2, \dots , x_n)$ where $n \nmid x_i-i$ and $n \mid \sum x_i$. Let $T(X)=X+X^2+\dots+X^n$ and $\epsilon$ be a primitive $n$ th root of unity. Define the polynomial $$h(X) \overset{\text{def}}{:=} \prod^n_{j=1} \left(T(X)-X^j\right)=\sum_{k \ge 0} a_kX^k.$$Note that the desired answer is $n \cdot \left(\sum_{j \ge 0} a_{jn}\right)$. This evaluates to $\sum^n_{j=1} h(\epsilon^j)$. Note that $h(1)=(n-1)^n$ and $h(\epsilon^j)=-1$ for all other indices, so $\boxed{(n-1)^{n}-(n-1)}$ is the answer. Part b.) Following the notations of Part a.) define $$h(X) \overset{\text{def}}{:=} \prod^n_{j=1} \left(T(X)-X^j-X^{2j \bmod n}\right),$$and note that we require $\sum^n_{j=1} h(\epsilon^j)$ as the answer. Clearly $h(1)=(n-1)(n-2)^{n-2}$ and all other summands are $-1$ so we obtain the $\boxed{(n-1)(n-2)^{n-1}-(n-1)}$ as the answer.