Abstract: A 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.
Publication Year: 1984
Publication Date: 1984-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 22
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot