I have a research paper about pseudo-random number generators and I need to answer the following: Given $n \in \mathbb{N}$, let's consider the permutation group of $A=\{{0,1,\dots,n-1}\}$. Since $A$ is finite the series $\{0,p(0),p^2(0),\dots\}$ is eventually periodic with some minimal period. By minimality of the period all elements of the periodic cycle are distinct. Let's denote that period by $R(p)$. Obviously $R(p) \le n$ for all permutations since if $R(p) \gt n$ we would need more than $n$ distinct elements in $A$. Let's define $p$ as maximal if $R(p)=n$. A maximal permutation goes through every element of $A$ exactly once per period. The obvious example of a maximal permutation is the "n++" permutation: $$ 0 \to 1\to 2 \to \dots \to n-2 \to n-1 \to 0 $$ Another example if n is odd is the "$n+=2$" permutation: $$ 0 \to 2\to 4 \to \dots \to n-1 \to 1 \to 3 \to \dots \to n-4 \to n-2 \to 0 $$ My question is how many of them are and if there was a way to calculate them all, mathematically or algorithmically. And what happens if we started at some element $a$ of $A$ instead of $0$? I believe nothing more since we can re-label the elements of $A$ and still have the same problem. I am aware that this depends strongly on $n$ and if needed we can assume that $n$ be prime. This might be simple for experts in the field, but not for me! (yet).
I appreciate, thanks a bunch!
You're actually trying to count the number of n-cycles (or circular permutations) of $S_n$. A $k$-cycle $c$ is a permutation defined by $k$ ordered elements $(a_1,\ldots,a_k)$ in $A$, and its values are : if $x=a_i$ for some $i < k$, then $c(x)=a_{i+1}$, if $x=a_k$ then $c(x)=a_1$ and otherwise $c$ is the identity ($c(x)=x$ if $x \not \in \{a_1,\ldots,a_k\}$). It is just the permutation $a_1 \rightarrow a_2 \rightarrow \ldots \rightarrow a_k \rightarrow a_1$ and $Id$ elsewhere.
As you suggest (when talking about starting from $a$ instead of zero), the first $a_i$ does'nt matter, and $k$-cycle are defined up to a translation meaning that $(a_1,\ldots,a_n)=(a_2,\ldots,a_k,a_1)=\ldots$.
The set $\{a_i,\ldots,a_k\}$ is called the support of $c$. You can check that for any $n$-cycle, since $k=n$ then its support is the entire set $A$ and thus contains zero. Let's assume w.l.o.g that $a_1=0$ (if not, we can always translate the $a_i$s defining the same cycle) and see that $\{0,c(0),c^2(0),\ldots\}=\{a_1,a_2,\ldots,a_n\}=A$. Hence a $n$-cycle is maximal.
Conversely, it is also easy to see that if a permutation $\sigma$ is maximal, then $\sigma$ is actually the $n$-cycle $(0,\sigma(0),\sigma^2(0),\ldots)$
It remains to count how many different $n$-cycle you can build. First, let's pick the $a_i$s : it is actually like picking a permutation of $A$, there are $n!$ possibilites. Of course we are counting some cycles several times (otherwise every permutation would be a $n$-cycle, which is obviously false). You can check that two $n$-cycles $(a_1,\ldots,a_n)$ and $(b_1,\ldots,b_n)$ are equals iff $b_i$s are a "translation" of $a_i$s, id est $\exists r,a_i=b_{i + r \mod n} $, as we said before (but notice that know, we state that it is both necessary and sufficient condition). So each cycle is counted exactly $n$ times, for each $r$ ranging over $A$. Finally the number of n-cycles is $\frac{n!}{n}=(n-1)!$