Proof of a conjecture of Kløve on permutation codes under the Chebychev distance

Abstract

Let $d$ be a positive integer and $x$ a real number. Let $A_{d,x}$ be a $d\times 2d$ matrix with its entries $$ a_{i,j}=\left\{ \begin{array}{ll} x\ \ & \mbox{for} \ 1\leqslant j\leqslant d+1-i, 1\ \ & \mbox{for} \ d+2-i\leqslant j\leqslant d+i, 0\ \ & \mbox{for} \ d+1+i\leqslant j\leqslant 2d. \end{array} \right. $$ Further, let $R_d$ be a set of sequences of integers as follows: $$R_d=\{(ρ_1, ρ_2,\ldots, ρ_d)|1\leqslant ρ_i\leqslant d+i, 1\leqslant i \leqslant d,\ \mbox{and}\ ρ_r\neq ρ_s\ \mbox{for}\ r\neq s\}.$$ and define $${\Omega }_d(x)=\sum _{\rho \in R_d}{a}_{1,{\rho }_1}{a}_{2,{\rho }_2}\dots a_{d,{\rho }_d}.$$ In order to give a better bound on the size of spheres of permutation codes under the Chebychev distance, Kløve introduced the above function and conjectured that $${\Omega }_d(x)=\sum _{m=0}^d\left(\genfrac{}{}{0ex}{}{d}{m}\right)(m+1{)}^d(x-1{)}^{d-m}.$$ In this paper, we settle down this conjecture positively.

6 pages