1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You might list the orderings and see how many begin with each number. That might allow you to develop a recursive or an explicit formula. Gerhard "From Many Small Make Large" Paseman, 2018.04.05. $\endgroup$ – Gerhard Paseman Apr 5 '18 at 22:20
  • 2
    $\begingroup$ For $n = 2p$, there are $2 \sum_{i=1}^p \frac{p!}{(p-i)!} i (2p-i-1)!$ Eulerian orderings. $i$ denotes the number of elements of equal parity to the first before a first "switch" happens. Wolfram Alpha says this is $(2p)!/(\frac{p+1}{2})$, so your pattern does generalize; I don't know my identities enough to check or give reasoning. Also, it may make your program much faster to not check all permutations, but rather to construct "possible" orderings according to the first condition (the one that ignores $j$), and then checking the second condition. $\endgroup$ – user44191 Apr 6 '18 at 0:32
  • 1
    $\begingroup$ I'd suggest that it may be useful to generalize this to a "grid", as in my comment on the earlier problem, but with arbitrary side lengths (so not necessarily prime nor distinct); this will allow us to use small examples that correspond to "many" prime factors. $\endgroup$ – user44191 Apr 6 '18 at 0:45
  • 2
    $\begingroup$ I calculated $g(3,3) = \frac{3}{10} 9!$; given $g(3,i)$ for $i=1,2,3$, I conjecture that $g(3,i)=6(3i)!/((i+1)(i+2))$; more generally, I conjecture $g(m,n)=m!n!(mn)!/(m+n-1)!$ $\endgroup$ – user44191 Apr 6 '18 at 21:31
  • 2
    $\begingroup$ Let $g(m,n,i)$ be the number of ways $i$ "boxes" can be filled in an $m$ by $n$ grid such that every row and every column contains at least one filled box. I think the recursive relation $g(m,n,i+1)=(mn-i) g(m,n,i) + mn g(m-1,n,i) + mn g(m,n-1,i)$ is true; the first term corresponds to "newest element doesn't fill a new row or column", etc. This recursive relation only holds the 2-D grid; its obvious generalization will not hold for higher dimensional grids. With the values $g(1,1,1)=1, g(m,n,0)=0$, there should only be one such function. $\endgroup$ – user44191 Apr 6 '18 at 23:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.