Given integers $n > 2$ and $1 \leq k < n$,
I'm interested in the set of permutations $$
\{\pi \in S_n : \pi(i) \neq i \text{ and } \pi(i) – k \not\equiv i \bmod n\}.
$$
When $k = 1$, these are called ménage permutations (OEIS sequence A000179).
I wrote a program to count such permutations, and I have an OEIS sequence (A354408),
but looking at the table of data led me to some natural conjectures that I would love to get additional perspective on.
n\k| 1 2 3 4 5 6 7 8
-----+------------------------------------------------
2 | 0
3 | 1 1
4 | 2 4 2
5 | 13 13 13 13
6 | 80 82 80 82 80
7 | 579 579 579 579 579 579
8 | 4738 4740 4738 4752 4738 4740 4738
9 | 43387 43387 43390 43387 43387 43390 43387 43387
-
In particular, is it true that when $\gcd(n, k) = 1$, the number of restricted
permutations is equal to the number of ménage permutations? (That is, $A354408(n,k) = A000179(n)$.) -
More specifically, does $A354408(p,k) = A000179(p)$ for all primes $p$?
-
With the exception of $A354408(6,3)$, does $\gcd(n,k) \neq 1$ imply that $A354408(n,k) > A000179(n)$?
-
Is the first entry in each row the smallest? That is, is it the case that $A354408(n,k) \geq A354408(n,1)$ for all $1 \leq k < n$?
-
Is there a pattern to which value of $k$ maximizes $A354408(n,k)$?
-
Can we find a decent bound on the difference between the smallest and largest values in each row, $d(n) = \max_k A354408(n,k) – \min_k A354408(n,k)$?
Best Answer
Another way to look at this problem is extensions of $2 \times n$ Latin rectangles to $3 \times n$ Latin rectangles. In particular, the ménage problem asks the number of ways to do it when the first rows are: $$ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \color{blue} 2 & \color{blue} 3 & \color{blue} 4 & \color{blue} 5 & \color{blue} 6 & \color{blue} 7 & \color{blue} 8 & \color{blue} 1 \\ \end{bmatrix} $$ which is the $k=1$ case, and the given generalization allows for different second rows, such as $$ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \color{blue} 4 & \color{blue} 5 & \color{blue} 6 & \color{blue} 7 & \color{blue} 8 & \color{blue} 1 & \color{blue} 2 & \color{blue} 3 \\ \end{bmatrix} $$ which is the $k=3$ case. $2$-row Latin rectangles are defined by their cycle structure, up to isotopism. E.g. if we treat the above two Latin rectangles as permutations (where the elements in row 1 map to the elements in row 2), then we have the permutations $(12345678)$ and $(14725836)$. You can use these permutations to permute the columns and symbols of the first Latin rectangle above, to give the second Latin rectangle above---thus they have the same number of extensions to a $3 \times n$ Latin rectangle, and the same A354408-value. This is one way to show that if $\gcd(k_1,n)=\gcd(k_2,n)$ then $A354408(n,k_1)=A354408(n,k_2)$, and in particular $A354408(n,k)=A000179(n)$ whenever $\gcd(n,k)=1$.
In cases when $\gcd(k,n) \neq 1$, we get a non-isotopic Latin rectangle, such as $$ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \color{blue} 3 & \color{blue} 4 & \color{blue} 5 & \color{blue} 6 & \color{blue} 7 & \color{blue} 8 & \color{blue} 1 & \color{blue} 2 \\ \end{bmatrix} $$ where $k=2$, which corresponds to the permutation $(1357)(2468)$.
Some thoughts:
It's likely (or, as Zeilberger puts it: by general ‘hand-waving’ (that can be easily made rigorous)) for fixed $k$ that these numbers satisfy linear recurrence with polynomial coefficients (i.e. P-recursive). In fact, when $k=1$ (the ménage problem) we have
$$a(n) = n a(n-1) + 2 a(n-2) - (n-4) a(n-3) - a(n-4)$$
where $a(n)=A354408(n,1)$ and $n \geq 6$ (adapted from the recurrence given in Sloane's A000179), and when $k=2$ we have
$$b(n) = n b(n-1) + 3 b(n-2) + (-2n+6) b(n-3) - 3 b(n-4) + (n-6) b(n-5) + b(n-6)$$
where $b(n)=A354408(n,2)$ (Sloane's A354152 reports that this was proved by Doron Zeilberger's computer in Automatic Enumeration of Generalized Menage Numbers (pdf)).
By applying induction on $b(n)-a(n)$ (it's fiddly), we find: $$ b(n) = \begin{cases} a(n) & \text{if $n$ is odd} \\ a(n)+2 & \text{if $n$ is even} \end{cases} $$ which implies that if $\gcd(n,k)=2$ then $A354408(n,k) = b(n) > a(n) = A354408(n,1)$.
By far the best way to compute the number of $k \times n$ Latin rectangles for fixed $k$ (assuming we don't have a recurrence) is Doyle's formula (arXiv) (which I wrote about here). If it could be adapted to this problem, it'd save a considerable amount of computation time. I'm not sure if this is possible.
I'm not 100% sure, but I think this generalization of the ménage problem was studied by Vladimir Shevelev in:
These numbers are also permanents of $(0,1)$-matrices, such as when $n=8$, the numbers are $$ \mathrm{per} \begin{bmatrix} 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ \end{bmatrix} \qquad \mathrm{per} \begin{bmatrix} 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ \end{bmatrix} $$ when $k=1$ and $k=2$. Since permanents are invariant under row and column permutations, it can be easier to view some of the properties in this context.
In this way, we observe that when $n$ is even, then $A354408(n,n/2)=A003471(n)$ (Sloane's A003471).
When $n=10$, the numbers are $A354408(10,1)=439792$, $A354408(10,2)=439794$, and $A354408(10,5)=440192$, and when $n=12$, the numbers are $A354408(12,1)=59216642$, $A354408(12,2)=59216644$, $A354408(12,3)=59216648$, $A354408(12,4)=59216968$, and $A354408(12,6)=59245120$.