The number of orthogonal permutations (Q1345530)

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\).