75 citations · 77 across the 5 of their papers we have counts for
5 papers
On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
Michael H. Albert
We consider the distribution of the length of the longest subsequence avoiding a given pattern in a random permutation of length n. The well-studied case of a longest increasing su…
The enumeration of simple permutations
M. H. Albert, M. D. Atkinson, M. Klazar
A simple permutation is one which maps no proper non-singleton interval onto an interval. We consider the enumeration of simple permutations from several aspects. Our results inclu…
Restricted permutations and queue jumping
M. H. Albert, R. E. L. Aldred, M. D. Atkinson +3
A connection between permutations that avoid 4231 and a certain queueing discipline is established. It is proved that a more restrictive queueing discipline corresponds to avoiding…
Sorting with a forklift
M. H. Albert, M. D. Atkinson
A fork stack is a generalised stack which allows pushes and pops of several items at a time. We consider the problem of determining which input streams can be sorted using a single…
Regular closed classes of permutations
M. Albert, M. D. Atkinson, N. Ruskuc
Machines whose main purpose is to permute and sort data are studied. The sets of permutations that can arise are analysed by means of finite automata and avoided pattern techniques…