An upper bound on the number of high-dimensional permutations (Q485003): Difference between revisions

A \(d\)-dimensional permutation of order \(n\) is a \(d+1\)-dimensional binary array of size \(n\times n\times \ldots\times n\) that has exactly one entry \(1\) in each line. (A \(1\)-dimensional permutation is just a permutation matrix.) The paper is concerned with the estimation of the number of permutations of dimension \(d\) and order \(n\). The authors prove that \[ | S_{d,n}| \leq\Big((1+o(1))\frac{n}{e^d}\Big)^{n^d} \] and state the conjecture that the equality is true. Their proof adapts methods for determining upper bounds on permanents of binary matrices.