Enumerating “Cyclic Double Permutations”

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.

1. 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.
2. 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\}$$.
3. 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.

• I don't understand where the "cyclic" part comes from. It seems that you interpret the sequence $\sigma$ as a cyclic permutation, but then how is every permutation of $\{A1,\dots,Am\}$ cyclic? Is $(A1A2)(A3A4)$ considered a cyclic double permutation when $(n,m)=(1,4)$? Commented May 17, 2023 at 17:32