This post is a sequel of Eulerian ordering of the integers modulo n.
Let us recall the definition of an Eulerian ordering:
Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$.
An Eulerian ordering of $C_n$ is an ordering $r_1, \dots, r_n$ of its elements such that:
$$\forall i \le n \ \forall j<i \ \exists k < i \text{ with } \frac{n}{gcd(n,r_k-r_i)} \text{ prime and } \frac{gcd(n,r_k-r_i)}{gcd(n,r_j-r_i)} \text{ integer.}$$
For the motivation of this notion coming from algebraic combinatorics, we refer to the previous post.
Question: How many Eulerian orderings of $C_n$ are there?
Let $a_n$ be the number of Eulerian orderings of $C_n$.
- If $n$ is not square-free then $a_n = 0$ (exercise).
- If $n$ is square-free then $a_n>0$ by this answer, providing an example involving mixed base.
- If $p$ is a prime number, then $a_p = p!$.
- If $n=2p$ with $p>2$ prime, then $a_n = n!/(\frac{p+1}{2})$. See Prop. 2 below, due to @user44191.
Definition: Let $g(n,m)$ be the number of ways for filling a $n \times m$ grid such that each newly filled box (the first excepted) is co-linear (vertically or horizontally) to a previously filled box.
Proposition 1: The number of Eulerian orderings of $C_n$, with $n=pq$ and $p \neq q$ primes is $g(p,q)$.
Proof: The grid corresponds the the decomposition of the cyclic group $C_{pq} \simeq C_p \times C_q$. The fact that two boxes are co-linear (vertically or horizontally) corresponds to $gcd(n,r_k-r_i)$ prime, which is equivalent to $\frac{n}{gcd(n,r_k-r_i)}$ prime (because $n=pq$). So the first condition for an ordering to be Eulerian corresponds exactly to the above way of filling the grid. Finally, $\forall j<i$, if $gcd(n,r_j-r_i)$ is prime then take $k=j$, else $gcd(n,r_j-r_i) = 1$ so the above $r_k$ works. $\square$
Intermediate problem: Find a formula for $g(n,m)$.
The following result is due to @user44191 (see its first comment):
Proposition 2: $g(2,m) = 2 (2m)!/(m+1)$.
Proof: Consider the $2 \times m$ grid. We first count the number of ways for filling $\ell \le m$ horizontally co-linear boxes (below $m=7$ and $\ell = 4$):
$$\substack{ \displaystyle{◻◻◻◻◻◻◻} \cr \displaystyle{◼◻◼◼◼◻◻} } $$
The number is $2 \times \frac{m!}{(m-\ell)!}$. Next we can choose among exactly $\ell$ boxes which are vertically co-linear to a previously filled.
$$\substack{ \displaystyle{◻◻◻◼◻◻◻} \cr \displaystyle{◼◻◼◼◼◻◻} } $$
Finally, any other box is (vertically or horizontally) co-linear to a previous one, so we can finish by any of the $(2m-\ell - 1)!$ ways. It follows that:
$$g(2,m) = 2 \sum_{\ell=1}^m \frac{m!}{(m-\ell)!} \ell (2m-\ell-1)!$$
In fact, as observed by @user44191, this research on WolframAlpha provides the formula: $2\Gamma(2m+1)/(m+1)$ which is equal to $2 (2m)!/(m+1)$. $\square$
Remark: We could try to extend the above approach for a formula of $g(n,m)$, possibly recursive, but it seems already tricky just for $g(3,m)$.
