The number of orthogonal permutations
type: Item
instance of: scholarly article
title: The number of orthogonal permutations
zbMATH Open document ID: 0828.05004
DOI: 10.1016/0195-6698(95)90091-8
author: Akihiro Nozaki
author: Masahiro Miyakawa
author: Ivo G. Rosenberg
author: Grant R. Pogosyan
published in: European Journal of Combinatorics
publication date: 1995-12-18T00:00:00Z
review text: Denote the set \(\{0, 1, 2,\dots, k- 1\}\) by \({\mathbf k}\). The orthogonality of two permutations \(\pi\), \(\sigma\) of \({\mathbf k}\) is defined; instead of the original definition, we mention the fact that \(\pi\) and \(\sigma\) are not orthogonal exactly if there exist two numbers \(i\), \(j\) (\(1\leq i< k\) and \(1\leq j< k\)) such that \(\pi(i- 1)= \sigma(j- 1)\) and \(\pi(i)= \sigma(j)\). Let \(q(k)\) be the number of permutations of \({\mathbf k}\) which are orthogonal to the identical permutation. Among the numerous results stated in the paper, let two assertions be quoted. A (recursive) formula is obtained for \(q(k)\) in terms of \(q(s)\) and \(g(k, s)\), where \(s\) runs from 2 to \(k- 1\) and \(g(k, s)= \sum n_1! n_2!\dots n_s!\) (the summation is taken over all \(s\)-tuples consisting of positive integers such that \(n_1+ n_2+\cdots+ n_s= k\)) (Corollary 23). The formula \(\lim q(k)/k!= e^{- 2}\) is proved for \(k\to \infty\) (Theorem 37). Some statements of the article concern the natural segmentations of \({\mathbf k}\), i.e., the partitions \(\beta\) of \(\{0, 1, 2,\dots, k- 1\}\) such that \(h\equiv i\pmod\beta\) if \(h< i< j\) and \(h\equiv j\pmod\beta\).
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 731897
zbMATH Keywords: orthogonal permutations
zbMATH Keywords: enumeration
zbMATH Keywords: partitions
reviewed by: A. Ádám
MaRDI profile type: Publication
full work available at URL: 0195-6698(95)90091-8
OpenAlex ID: W2032291542
cites work: Q5809140
cites work: Q3268312
cites work: Relational systems with trivial endomorphisms and polymorphisms
cites work: Q5559270
cites work: Unary polynomials in algebras. I
cites work: Q3208654
cites work: Ramsey properties for classes of relational systems
cites work: Q3338105
Recommended article: Q3769098
Recommended article: On systems of orthogonal permutations
Recommended article: Q5321504
Recommended article: Q3794675
Recommended article: ON THE NUMBER OFA-PERMUTATIONS
Recommended article: Permutative numbers
Recommended article: On the combinatorics of permutations
Recommended article: Combinatorics of permutations
Recommended article: Combinatorics of Permutations
description: scientific article; zbMATH DE number 731897