Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
See also 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. –  Jack Schmidt Jun 18 '12 at 14:32
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks! If you know an easy way to describe why every Latin rectangle can be extended to a Latin square, I'd love to see it. I don't yet really understand Hall's marriage theorem, but I suspect today is the day I'll learn it. –  Jack Schmidt Jun 18 '12 at 14:25
    
@Jack: I just added a link to Marshall Hall’s proof of the extension result, which does indeed use the marriage theorem. –  Brian M. Scott Jun 18 '12 at 14:28
    
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.) –  Jack Schmidt Jun 18 '12 at 14:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.