Enumerating “Cyclic Double Permutations”

Question

This is a generalization of a question first asked by loopy walt on Puzzling Stack Exchange: https://puzzling.stackexchange.com/q/120243. I asked the following version of the question in the comments, and I couldn't resolve it myself. I will re-phrase this question to make its combinatorics more apparent.

Definition.

The given is an alphabet with $n$ letters $\mathfrak{A}=\{\mathrm{A,B,C,\ldots,N}\}$ and $m$ numbers $\mathfrak{N}=\{1,2,3,\ldots,m\}$. I call a finite sequence $\sigma$ of alternating letters and numbers a “cyclic double permutation” if

1. The consecutive letter-number pairs in $\sigma$ is a permutation of all letter-number pairs in $\mathfrak{A}\times\mathfrak{N}$;
2. If the initial letter of $\sigma$ is moved to the end of $\sigma$ to form a new string $\tau$ of alternating numbers and letters, then the consecutive number-letter pairs in $\tau$ is a permutation of all number-letter pairs in $\mathfrak{N}\times\mathfrak{A}$.

Examples.

0. Take $(n,m)=(3,4)$. The string $$\sigma=\textrm{C3A3C4B1B2B3B4C2C1A2A4A1}$$ is a cyclic double permutation because $\sigma$ is a permutation of $\mathfrak{A}\times\mathfrak{N}=\{\textrm{A1},\textrm{A2},\ldots,\textrm{C4}\}$ and its companion (as in item 2 above) $\tau=\textrm{3A3C}\ldots\textrm{4A1}\underline{\textrm{C}}$ is a permutation of $\mathfrak{N}\times\mathfrak{A}=\{\textrm{1A},\textrm{2A},\ldots,\textrm{4C}\}$. In particular, every cyclic double permutation $\sigma$ should start with a letter, and it should contain precisely $mn$ letters and $mn$ numbers.
1. When $n=1$, there are precisely $m!$ many cyclic double permutations. Namely, those are all the permutations of the set $\{\textrm{A1},\textrm{A2},\ldots,\textrm{A}m\}$.
2. The linked PSE question contains many answers with proofs that when $n=2$, there are precisely $2^{m-1}(m!)^2$ many cyclic double permutations that start with the letter $\textrm{A}$. (See for example xnor's answer.) By a symmetry argument, there are precisely $2^m(m!)^2$ many cyclic double permutations in total.

Question

Is the number of cyclic double permutations always equal to $(n!)^m(m!)^n$?

I have checked using a computer that this holds whenever $n+m\le 7$, and to my best knowledge this sequence has not shown up on OEIS yet.

Answer 1

Nice problem. As you observe in comments, the objects in question are (essentially) Eulerian cycles in a complete bipartite graph. Eulerian cycles can be counted by the BEST theorem, in terms of (essentially) the number of spanning trees of the graph; the spanning trees can be counted by the matrix-tree theorem.