Permutations with interval cycles.

We study permutations of the set [n] = {1, 2, . . . , n} written in cycle notation, for which each cycle forms an increasing or decreasing interval of positive integers. More generally, permutations whose cycle elements form arithmetic progressions are considered. We also investigate the class of generalised interval permutations, where each cycle can be rearranged in increasing order to form an interval of consecutive positive integers.. 1 Interval Permutations The partitions of the set [n] = {1, 2, . . . , n} into k nonempty subsets of consecutive integers are enumerated by ( n−1 k−1 ) since this is the number of ways of inserting k − 1 separators between the sequence of numbers 1, 2, . . . , n, 1 ≤ k ≤ n. We will obtain analogous results for permutations of [n], written in the cycle notation. Taking different orderings of the elements of the cycles into account gives several different analogues of the set partition case. Firstly, a permutation p of [n] will be called an interval permutation if every cycle of p consists of one increasing or decreasing sequence of consecutive integers. Even though the standard notation places the least member of a cycle in the first position, we adopt the convention to reckon only with the permutations in which the members of a cycle have been shifted so as to exhibit the maximal number of pairs of consecutive integers. An interval permutation is the unique member of its cycle class in which every v-cycle consists of v increasing or decreasing consecutive integers. Later in Section 5 we will also study the class of generalised interval permutations, where each cycle can be rearranged in increasing order to form an interval of consecutive integers. Denote the set of interval permutations of [n] with k cycles (also kpermutations below) by R(n, k), and let r(n, k) = |R(n, k)|. Also let r(n) = r(n, 1) + r(n, 2) + · · ·+ r(n, n).

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.