3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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)$? $\endgroup$
    – durianice
    Commented May 17, 2023 at 17:32

1 Answer 1

2
+100
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ @EdwardH Nice write-up; glad I could help! $\endgroup$
    – JBL
    Commented May 18, 2023 at 22:30
  • $\begingroup$ @EdwardH Also "in slightly more detail" is a very funny (at least to me) understatement of your contribution :) $\endgroup$
    – JBL
    Commented May 20, 2023 at 0:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .