Permutations with Restricted Displacement (Q3768908)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4027475
Language Label Description Also known as
default for all languages
No label defined
    English
    Permutations with Restricted Displacement
    scientific article; zbMATH DE number 4027475

      Statements

      Permutations with Restricted Displacement (English)
      0 references
      0 references
      0 references
      1987
      0 references
      permutations with restricted positions
      0 references
      permanents
      0 references
      cryptography
      0 references
      analogue speech scramblers
      0 references
      If \(1\leq k\leq n\), let \(A(n,k)=\{\pi \in S_ n:\overline{\pi (i)}\in \overline{\{i,i+1},...,\overline{i+k-1}\}\) for every i, \(1\leq i\leq n\}\), where \(S_ n\) is the symmetric group of order n and where \(\bar{\j}\) denotes the residue class of j modulo n. It is well-known that the cardinality of A(n,k), \(| A(n,k)|\), is equal to the permanent of a suitable circulant \(n\times n\) (0,1)-matrix [see \textit{H. Minc}, Permanents (1978; Zbl 0401.15005), and Linear Multilinear Algebra 21, 109-148 (1987; Zbl 0621.15006)]. Moreover, \(| A(n,k)|\) is of practical significance since it equals the number of different ``scrambling patterns'' that can be used in a certain type of time element scrambling speech encryption device. This paper gives a new and direct approach to the evaluation of the number \(| A(n,k)|\) in terms of the traces of the n-th powers of [(k-1)/2] (0,1)-matrices. This yields a generalization of the recurrence formulae of \textit{N. Metropolis, M. L. Stein} and \textit{P. R. Stein} [J. Comb. Theory 7, 291-321 (1969; Zbl 0183.298)] and a number of previously well-known results, as well.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references