Transforming binary sequences using priority queues

A priority queue transforms an input sequence into an output sequence which is a re-ordering of the sequence . The setR of all such related pairs is studied in the case that is a binary sequence. It is proved thatR is a partial order and that ¦R¦=c_n+1, the (n+1)th Catalan number. An efficient (O(n²)) algorithm is given for computing the number of outputs achievable from a given input.