5
$\begingroup$

We were playing a home-made scribblish and were trying to figure out how to exchange papers. During each round, you'll trade k times and each time you need to give your current paper to someone who has never had it, and you need to receive a paper that you've never had. There are n papers. For example, if everyone passes their paper to the left, then you can trade $n-1$ times, and on the $n$th trade everyone gets their papers back. Clearly $k < n$ no matter how you trade.

It is suboptimal for one player to always trade with the same player, so we want to use different permutations each time. When writing a webpage to choose permutations randomly, I ran into a theoretical problem: if we don't know k, can we still generate a good sequence of shuffles? As long as any good sequence of shuffles can be extended to a maximal sequence, we are ok. For n ≤ 6 this is true. Is it true in general?

For n a positive integer, call a sequence of permutations $g_i \in S_n$ deranged if $\prod_{i=a}^b g_i$ has no fixed points on $\{1,\dots,n\}$ for any $1 \leq a\leq b \leq k$, where $k$ is the length of the sequence. Must every maximal deranged sequence have $k=n-1$?

A deranged sequence of length 1 is just called a derangement.

We partial order deranged sequences by $a \leq b$ if $a$ is an initial segment of $b$, so that $(1,2,3,4,5) \leq (1,2,3,4,5), (1,2,3,4,5) \leq (1,2,3,4,5), (1,2,3,4,5), (1,3,5,2,4)$. Hence a deranged sequence $g_1, \dots, g_k\in S_n$ is maximal iff for every $g_{k+1} \in S_n$, the sequence $g_1, \dots, g_k, g_{k+1}$ is not deranged.

Examples:

In order to make the problem more symmetrical, it can be helpful to append $g_{k+1} = (g_1 \cdots g_k)^{-1}$ to the sequence. This corresponds to a final step of "handing everyone back their original paper." Then every consecutive $k-1$ subsequence of every cyclic permutation has the property that it is deranged. Thus these deranged "cycles" of length $k+1$ are acted on both by $S_n$ (relabeling the people) and by $C_{k+1}$ (cyclic permutations). This can help reduce the number of truly distinct examples.

For two players, obviously you just pass it to each other and it is over.

  • (1,2) [ add (1,2) to complete the cycle ]

For three players, you can either pass clockwise twice or counterclockwise twice.

  • (1,2,3), (1,2,3) [ add (1,2,3) to complete the cycle ]
  • (1,3,2), (1,3,2) [ this is the previous one with players 2 and 3 swapped ]

For four players, there are 24 deranged sequences, but after completing them to deranged cycles, there are only 3 distinct orbits under $S_n$ and $C_{k+1}$. Notice that $k+1=n$ in each case:

  • (1,2)(3,4), (1,3)(2,4), (1,2)(3,4), (1,3)(2,4) -- trade within, across, within, across
  • (1,2)(3,4), (1,3,2,4), (1,2)(3,4), (1,4,2,3) -- across, left, across, right
  • (1,2,3,4), (1,2,3,4), (1,2,3,4), (1,2,3,4) -- four lefts

For five players there are 1344 deranged sequences, and once completed they fall into 4 orbits. In each case $n=k+1$.

  • (1,2)(3,4,5), (1,3)(2,4,5), (1,2,3,4,5), (1,2,4,5,3), (1,4,5,2,3)
  • (1,2)(3,4,5), (1,3)(2,4,5), (1,4,3,5,2), (1,3,5,4,2), (1,3,4,2,5)
  • (1,2,3,4,5), (1,2,3,4,5), (1,2,3,4,5), (1,2,3,4,5), (1,2,3,4,5) -- five left
  • (1,2,3,4,5), (1,2,3,4,5), (1,3,5,2,4), (1,5,4,3,2), (1,3,5,2,4) -- left, left, double-left, right, double-left

For six players, the number of possibilities seems to explode (1128960 deranged sequences, 362 orbits of deranged cycles), but in each case $n=k+1$.

The sequence OEIS:A000479 may be relevant.

  • 0
    See also http://math.stackexchange.com/a/63152/583 for a possible algorithm for extending the latin rectangles to latin squares. One just needs an effective form of Hall's marriage theorem.2012-06-18

1 Answers 1

6

Form a $k\times n$ matrix

$A=\left[\matrix{a_{11}&a_{12}&\dots&a_{1n}\\ a_{21}&a_{22}&\dots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{k1}&a_{k2}&\dots&a_{kn}}\right]$

as follows: $a_{ij}$ is the number of the person holding $i$’s paper after $j-1$ rounds. For example, your first deranged sequence for four players produces the matrix

$\left[\matrix{1&2&3&4\\ 2&1&4&3\\ 4&3&2&1\\ 3&4&1&2}\right]\;.$

Each row of $A$ must be a permutation of $1,\dots,n$, and no column of $A$ may contain any number more than once, so $A$ is a $k\times n$ Latin rectangle, which can always be extended to a Latin square. Thus, every maximal deranged sequence has length $n-1$.

Added: Since OEIS A000479 counts the number of such Latin squares with first row $[\matrix{1&\dots&n}]$, it is indeed relevant: it counts the number of unreduced maximal deranged sequences. Dividing by $(n-1)!$ gives the number of reduced Latin squares of order $n$. According to Wikipedia, this number is known only for $n\le 11$, so you’re unlikely to get any nice expression for it.

  • 0
    Thanks, perfect! (I'm actually only interested in the orbit reps, but even those grow too quickly; apparently I'm looking for isomorphism classes of quasi-groups. Hence I'll just extend Latin rectangles for the webpage.)2012-06-18