2
$\begingroup$

A friend and I were thinking about this problem today but we were unable to come up with a solution.

Problem:

Consider the the numbers $S=\{1,\ldots,n\}$. Given $2\le d \le n$ what is the maximal number of permutations $p(d)$ of $S$ you can choose such that the following holds: Whenever you compare two chosen permutations, they differ in at least $d$ spots?

Note that we always have $2\le d\le n$ since two permutations cannot differ in exactly one spot.

Note also that $n\le p(d)\le n!$ for all $d:$ $p$ is non-increasing and for $d=n$ one can choose the natural order first and proceed cyclically by writing \begin{matrix} 1 & 2 & \ldots & n-1 & n \\ 2 & 3 & \ldots & n & 1 \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ n & 1 & \ldots & n-2 & n-1 \\ \end{matrix} so that $p(n) \ge n.$ Actually $p(n)=n$ since when writing the $n$ permutations differing in $n$ spots in pairwise comparisons into the rows of a matrix, the first column will contain all $n$ numbers. Thus it is not possible to add a row to the matrix that differs from all previous rows at the first index.

Example: for $n=3$ all possible permutations are: \begin{matrix} 1 & 2 & 3\\ 1 & 3 & 2\\ 2 & 1 & 3\\ 2 & 3 & 1\\ 3 & 1 & 2\\ 3 & 2 & 1 \end{matrix} For $d=3$ we get $p(d) = 3$ since $n=3,$ by the reasoning outlines above, and for $d=2$ we get $p(d) = 6$ since all distinct permutations differ in at least two spots.

$\endgroup$
5
$\begingroup$

You are looking for size of permutation code with Hamming distance. I have found a two years old survey of it - http://www.math.uvic.ca/~dukes/pc-talk.pdf. Most problems are open - for example, even sizes for $n = 7, d = 4$ and $n = 7, d = 5$ are unknown.

$\endgroup$
  • $\begingroup$ Do you understand why slide 44 says "Theorem $M(n,4) = (n-1)!$" when the penultimate slide says $343 \le M(7, 4) \le 535$? $\endgroup$ – Peter Taylor Apr 24 at 13:49
  • 1
    $\begingroup$ I suspect it's a typo and should be $M(n, 4) \leqslant (n - 1)!$, as the "proof idea" speaks about upper bound, and then there is a better bound $\frac{n!}{n+2}$ for square $n$. $\endgroup$ – mihaild Apr 24 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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