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.