Cayley permutations

AbstractA Cayley permutation (C-permutation for short) of length n is a permutation p of n elements with possible repetitions from a set {a1, …, an} of n elements with an order relation, subject to the condition that if an element ai appears in p, then all elements ai < ai also appear in p. An enumeration formula for C-permutations is derived, which exhibits the equivalence to the solution of many other combinatorical enumerative problems. A 1-1 correspondence between C-permutations and a subset of ordered rooted trees called Cayley trees is established, thus providing a simple and elementary proof for the enumeration formula for Cayley trees. Finally, algorithms for generating C-permutations, ranking ordinary permutations with repetitions and ranking C-permutations are given