On the Adjacent Cycle Derangements

A derangement, that is, a permutation without fixed points, of a finite set is said to be an adjacent cycle when all its cycles are formed by a consecutive set of integers. In this paper we determine enumerative properties of these permutations using analytical and bijective proofs. Moreover a combinatorial interpretation in terms of linear species is provided. Finally we define and investigate the case of the adjacent cycle derangements of a multiset. 1. Introduction Let , and let denote the set of permutations of . We will use both the one-line notation of a permutation of and its decomposition as a product of cycles. It will be convenient to write each cycle ending with its smallest element and order cycles by increasing smallest elements. For example . In [1] the authors define an adjacent cycle of a permutation to be a cycle in which the elements form a consecutive set of integers. We generalize the notion defining a permutation of to be adjacent cycle (a.c. for short) when in every cycle the elements form a consecutive set of integers. In other words every cycle of elements, having as the smallest element, is represented by the sequence . In [2] it is proved that the adjacent cycle permutations of turn out to be fixed by the bijection that associates to a permutation of the permutation whose one-line form is obtained from the canonical form of by removing all inner parentheses. For example, let . Notice that we omit commas between the integers in a cycle or in a sequence, unless it leads to ambiguity. We will denote by and the set of adjacent cycle permutations and the set of adjacent cycle derangements of , respectively, and and their cardinalities; moreover, represents the set of adjacent cycle derangements having cycles and its cardinality. We say that an adjacent cycle permutation of is extended to , where , when are inserted in this order in the last cycle of before its last element. Clearly we obtain an adjacent cycle permutation of . For example, the extension of the permutation of to determines the new permutation of . Let denote the th Fibonacci number, with initial conditions , . We now outline the contents of this paper. In Section 2 we determine properties of the adjacent cycle permutations and adjacent cycle derangements of , using analytical and bijective proofs. In Section 3 we prove a relation involving the Fibonacci numbers, which seems new. In Section 4 we present a combinatorial interpretation of the adjacent cycle permutations in terms of linear species; as a consequence we are able to calculate the enumerative results