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
1987
0 references
permutations with restricted positions
0 references
permanents
0 references
cryptography
0 references
analogue speech scramblers
0 references
0.7513009905815125
0 references
0.7460260987281799
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