Priority queues with binary priorities

We consider a priority queue of unbounded capacity whose input is the sequence 1,2,…,n where each i is given a binary priority. We prove a previously conjectured recurrence for the number of allowable input–output pairs achievable by such a queue with z items of priority 0; the proof provides a new application of inseparable permutations. We then give upper and lower bounds for this and deduce that for fixed z the growth rate is O(n!log^z(n)). We also study the total number of allowable input–output pairs where the number of items of priority 0 is not fixed and provide very tight upper and lower bounds which imply that the growth rate is O(nn!log(n)).