Priority Queues and Multisets

M.D. Atkinson S.A. Linton L.A. Walker

Department of Mathematical and Computational Sciences University of St. Andrews North Haugh, St. Andrews KY16 9SS, Scotland

           {sal,mda,louise}@dcs.st-and.ac.uk

Submitted: February 14 1995; Accepted November 10 1995.

Abstract

A priority queue, a container data structure equipped with the operations insert and delete-minimum, can re-order its input in various ways, depending both on the input and on the sequence of operations used. If a given input σ can produce a particular output τ then (σ, τ) is said to be an allowable pair. It is shown that allowable pairs on a fixed multiset are in one-to-one correspondence with certain k-way trees and, consequently, the allowable pairs can be enumerated. Algorithms are presented for determining the number of allowable pairs with a fixed input component, or with a fixed output component. Finally, generating functions are used to study the maximum number of output components with a fixed input component, and a symmetry result is derived.

Mathematical Reviews Subject Classifications: 68R05,05A15,68P05

1 Introduction

Abstract data types (ADTs) are a fundamental design tool in modern software systems. They are setting the direction of programming in the 1980’s and 1990’s as firmly as Structured Programming set it in the 1960’s and 1970’s. In principle there is an infinity of possible ADTs since an ADT is defined once its permitted set of operations has been specified, and there is no restriction on this set except for common sense. In practice, a small number of ADTs occur over and over again (stacks, arrays, queues, dictionaries etc.) suggesting that some ADTs are more “natural” than others.

the electronic journal of combinatorics 2 (1995), #R24 2

Exactly the same phenomenon occurs in algebra and, significantly, the natural algebraic systems (groups, rings, modules etc.) have very rich theories. Many of the commonly occurring ADTs are container data types: they are holders for collections of data items and support an Insert operation and a Delete operation (often restricted in some way).

Normally, a container data type is used in the following way. First it is initialised as empty. Then some input sequence of data items is inserted into it one by one (the Insert operation) and these items are removed (the Delete operation) in some order and placed in an output sequence. The insertions and deletions may be interleaved in any way (provided that the Delete operation is never used on the empty container). Thus, a container data type is a mechanism for transforming an input sequence into an output sequence. The functional behaviour of a container data type is essentially characterised by the relationship between the input sequences and the output sequences. An understanding of this relationship allows us to judge the capabilities of a data type and to assess its potential applications. In general, if σ is an input sequence that gives rise to an output sequence τ then we shall say that (σ, τ) is allowable (with respect to the data type). The statistics of the allowability relation associated with a given data type are measures of the transformational capability of that data type.

In the case of a queue (where the Delete operation always removes the element which has been in the queue the longest) the allowability relation is trivial since the output sequence is always the same as the input sequence; in other words, the only allowable pairs are of the form (σ, σ). In the case of stacks (where the Delete operation always removes the element which was placed in the stack most recently) the relation is more complicated and there are significant connections with a number of other combinatorial objects such as trees [9] 2.3.4.4, ballot sequences [10] p531, Young tableaux [10] pp63,64, and triangulations of polygons [6] pp320–324. For dictionaries (which have an unrestricted Delete operation) the output can be any permutation of the input.

The allowability relation has also been considered for various types of deques. For a general deque (where insertions and deletions are permitted at both ends) Pratt [12] has characterised the allowable pairs in terms of forbidden subsequences. For input restricted deques (where insertion is permitted at one end only) and output restricted deques, Knuth [9] 2.2.1 has given generating functions and recurrence relations for computing the number of allowable pairs of a given length.

In this paper we shall consider the case of priority queues. Priority queues are characterised by two main operations, Insert and Delete-Minimum. Several efficient implementations of them are known in which O(log n) operations suffice for each of Insert and Delete-Minimum, where n is the number of items currently in the priority queue. A priority queue algorithm is defined to be a sequence of Insert and Delete-Minimum operations which is well-formed in the same sense as bracket sequences. In other words there are equal numbers of each operation and (in order that a Delete-Minimum is only executed when the priority queue is non-empty) the tth Delete-Minimum operation must be preceded by at least t Insert operations. A priority queue algorithm with n Insert and n Delete-Minimum operations transforms an input sequence of length n into an output sequence of length n. In the terminology introduced above, the pair (σ, τ) is allowable if and only if there is a priority queue algorithm which transforms σ into τ.

Our focus here is on the allowability relation for priority queues. The case of input and output sequences which are permutations of 1, 2, …, n was considered in [1, 2, 7] whilst binary sequences were considered in [3]. As was shown in [2, 7] allowable pairs of permutations are in one-to-one correspondence with labelled trees for which there is an extensive enumeration theory [11] beginning with Cayley’s famous enumeration formula. Labelled trees are in one-to-one correspondence with other combinatorial objects; for example, with the number of ways of expressing an n-cycle as a product of n−1 transpositions [5] p86. We shall consider the general case in which the input and output sequences are elements of a finite multiset S. From now on S will denote a fixed multiset of size n whose elements are 1, 2, …, k with element i having multiplicity a_{i}. Our results unify those in [1, 2, 3, 7] and lead to some combinatorial results which are peculiar to the general case.

In the next section we give a one-to-one correspondence between the set of allowable pairs and a set of k-way trees. This correspondence permits us to enumerate the set of allowable pairs. In section 3 we give polynomial time algorithms for computing the number of outputs that can arise from a fixed input, and for the number of inputs that can give rise to a fixed output. Finally, in section 4, we consider the maximal number of outputs that a given input can generate as a function of a_{1}, …, a_{k}. We derive recurrences and a multi-variate generating function, and conclude with an unexpected symmetry result.

2 Allowable pairs

The main theorem in this section concerns the number of allowable pairs of sequences in which the elements of the input (and output) sequences are permutations of the fixed multiset S. Although in reality equal symbols of a multiset cannot be distinguished we shall find it convenient, as an expositional device only, to pretend that each symbol has a unique identity. The symbols all equal to some fixed i will be distinguished from each other by their order of occurrence in the input sequence σ. We further suppose, again as an expositional device only, that occurrences of multiple copies of the same symbol are deleted from the priority queue in the same order as they are inserted; so the order of occurrence of equal symbols in the output sequence τ is the same as their order in σ.

We occasionally make this convention explicit by subscripting each symbol of a given value with the order of its occurrence among the symbols of this value. For example, the allowable pair of Figure 1 below would be written:

(3_{1}2_{1}3_{2}1_{1}1_{2}2_{2}2_{3}3_{3}1_{3}2_{4}1_{4}, 1_{1}2_{1}3_{1}1_{2}2_{2}3_{2}2_{3}1_{3}3_{3}1_{4}2_{4})

These two devices allow us to associate each input symbol with a unique output symbol. This allows us to track a symbol’s progress as it goes into the priority queue and eventually emerges as a member of the output sequence. In practice, of course, when there are several equal minimal elements in the priority queue, any one of them might be deleted by a Delete-Minimum operation. But each of them will produce the same value in the output sequence, so it does no harm to suppose that it is the minimal value of longest residence in the priority queue that is deleted.

Theorem 1 The number of allowable pairs (σ, τ) where σ (and τ) are permutations of the multiset S is

\frac{1}{n + 1} ∏_{i=1}^{k} \binom{n + 1}{a_{i}}

Corollary 1 The number of allowable pairs (σ, τ) where σ ranges over all the k^{n} sequences of length n with at most k distinct members is

\frac{1}{n + 1}\binom{kn + k}{n}

Proof of Corollary. The number in question is

∑ \frac{1}{n + 1} ∏_{i=1}^{k} \binom{n + 1}{a_{i}}

where the summation is over all integer vectors (a_{1}, a_{2}, …, a_{k}) with non-negative components such that ∑ a_{i} = n. This is clearly the coefficient of x^{n} in

\frac{1}{n + 1}(1 + x)^{n+1}(1 + x)^{n+1} … (1 + x)^{n+1} = \frac{1}{n + 1}(1 + x)^{kn+k}

from which the result follows.

In the case that all a_{i} = 1 and k = n, Theorem 1 corresponds to sequences which are permutations of {1, 2, …, n} and gives the main theorem of [1] while the case k = 2 of the Corollary corresponds to binary sequences and gives one of the results of [3].

Theorem 1 is proved by establishing a one-to-one correspondence between allowable pairs and certain trees. We recall the definition of a k-way tree: a k-way tree is either empty or it consists of a root node and a sequence of k k-way subtrees. It is common to represent a k-way tree by a diagram in which the root node is connected to its non-empty subtrees by edges which point in one of k fixed directions.

[figure: ∞; 1; 3; 2; 3; 2; 1; 2; 1; 3; 1; 2]
(3_{1}2_{1}3_{2}1_{1}1_{2}2_{2}2_{3}3_{2}1_{3}2_{4}1_{4}, 1_{1}2_{1}3_{1}1_{2}2_{3}3_{3}2_{3}1_{3}3_{3}1_{4}2_{4})

Figure 1: a 3-way tree, its corresponding unambiguous tree and allowable pair

We also define an unambiguous tree. Such a tree is rooted, unordered, and labelled; the root is labelled ∞ and the non-root nodes are labelled with the elements of a multiset of integers subject to the condition that the children of every node have distinct labels.

There is an obvious one-to-one correspondence between k-way trees and unambiguous trees on multisets on {1, 2, …, k}. Given the diagram of a k-way tree we can label the root node ∞, and label the lower node of any edge in the ith direction with the label i; this gives an unambiguous tree. Conversely, from any unambiguous tree we can use the labels to direct the edges in the appropriate directions thereby obtaining a k-way tree. In this correspondence the number of labels equal to i in an unambiguous tree is equal to the number of edges pointing in the ith direction in the associated k-way tree. Figure 1 depicts a 3-way tree and corresponding unambiguous tree. It also shows the allowable pair associated with the unambiguous tree by the one-to-one correspondence of Theorem 2.

Our first lemma gives a decomposition of an allowable pair which we use as an inductive tool throughout this section and the next. In this lemma we introduce the practice, continued in the proof of Theorem 2, of prefacing input sequences by the symbol ∞. There are two reasons for this. The first is that we often need to refer to the symbol that immediately precedes one of the symbols k in σ; and if k happens to be the first symbol of σ, we can, by use of the ∞ symbol, handle this in a uniform way. The second reason has to do with Theorem 2, where we associate unambiguous trees on n + 1 nodes with allowable pairs (σ, τ) of length n; we can then find a labeling of the tree nodes with the symbols in ∞σ.

Lemma 1 Let σ, τ be sequences of length n with a_{i} occurrences of i (for i = 1, 2, …, k). Suppose that τ is expressed as τ = τ_{0}kτ_{1} … kτ_{a_{k}} where none of the τ_{i} contain k. The pair (σ, τ) is allowable if and only if there exist subsequences σ_{0}, σ_{1}, …, σ_{a_{k}} of σ and elements x_{1}, …, x_{a_{k}} of ∞σ such that

(i) for each 0 ≤ i ≤ a_{k}, (σ_{i}, τ_{i}) is allowable,

(ii) σ with all occurrences of k removed is the sequence σ_{0}σ_{1} … σ_{a_{k}},

(iii) for each 1 ≤ j ≤ a_{k}, x_{j} is immediately before the jth k in ∞σ and the position of x_{j} in ∞σ is strictly to the left of the position of the jth k in ∞τ

Proof First assume that (σ, τ) is allowable and let G be a priority queue algorithm which transforms σ into τ. We recall our convention that occurrences of multiple copies of the same symbol are deleted from the priority queue by G in the same order as they are inserted.

For each j = 1, 2, …, a_{k}, the jth k must be deleted by G after all elements appearing before it in σ have been deleted (because those elements are all less than k or equal to and more senior than this k). Therefore, defining x_{j} to be the symbol of ∞σ immediately before the jth k, the position of x_{j} in ∞σ is strictly to the left of the position of the jth k in ∞τ; this gives condition (iii).

Define, for every i = 0, …, a_{k}, the sequence σ_{i} to be the subsequence of σ which is mapped to τ_{i} under the action of G. Since (σ, τ) is allowable, (σ_{i}, τ_{i}) is also allowable for all 0 ≤ i ≤ a_{k} and so (i) holds.

To show (ii), it is enough to prove that for any i = 0, …, a_{k−1}, if x appears in τ_{i} and y appears in τ_{i+1}, then x precedes y in σ. Assume otherwise and argue for a contradiction. Since y precedes x in σ and succeeds x in τ, it follows that y > x. However the ith k in τ appears before y in τ and so this symbol k appears before y in σ. Therefore when x is deleted from the priority queue by G, y and k must be present in the priority queue; it follows that y will be deleted before k since y < k. This is the required contradiction.

Conversely, assume there exist σ_{0}, σ_{1}, …, σ_{a_{k}} and x_{1}, …, x_{a_{k}} satisfying (i), (ii), and (iii). For each i = 0, …, a_{k} let G_{i} be a priority queue algorithm that transforms σ_{i} to τ_{i} and let A be the sequence of Insert and Delete-Minimum operations G_{0}G_{1} … G_{a_{k}}. Form a new sequence obtained from A as follows: add an extra Delete-Minimum operation at the end of each subsequence G_{i} of A (i = 0, 1, …, a_{k−1}); in the resulting sequence, if x_{j} (1 ≤ j ≤ a_{k}) is the (r +1)th element of ∞σ, add an extra Insert operation after the rth Insert operation (or at the beginning of A if r = 0). Conditions (i) and (iii) ensure that the resulting sequence of Insert and Delete-Minimum operations is a well-formed priority queue algorithm G. From condition (ii) it follows that G transforms σ into τ which completes the proof.

As an example, we consider

(σ, τ) = (3_{1}2_{1}3_{2}1_{1}1_{2}2_{2}2_{3}3_{3}1_{3}2_{4}1_{4}, 1_{1}2_{1}3_{1}1_{2}2_{2}3_{2}2_{3}1_{3}3_{3}1_{4}2_{4})

Dividing τ at each symbol 3, we obtain

\begin{matrix}i & σ_{i} & τ_{i} & x_{i} \\ 0 & 21 & 12 & – \\ 1 & 12 & 12 & ∞ \\ 2 & 21 & 21 & 2_{1} \\ 3 & 21 & 12 & 2_{3} \end{matrix}

Theorem 2 There is a one-to-one correspondence between unambiguous trees on n+1 nodes with, for 1 ≤ i ≤ k, a_{i} nodes labelled i and allowable pairs (σ, τ) where σ and τ are sequences of length n = ∑_{i=1}^{k} a_{i} with a_{i} occurrences of i (1 ≤ i ≤ k).

Proof The proof of the theorem is by construction. We shall show how to construct an unambiguous tree for each allowable pair and prove that the construction rule is a bijection between the set of allowable pairs and the set of unambiguous trees.

The tree Γ that is associated with an allowable pair (σ, τ) has nodes labelled by the elements of σ together with a label ∞, and the multisets of node labels and elements of ∞σ are, of course, equal. It will convenient to have a specific correspondence between the set of nodes of Γ and the elements of ∞σ such that each node is labelled by its corresponding element in ∞σ. Such a correspondence will be called a matching. Our construction of Γ produces a particular matching which is itself used, via induction, in defining the construction. The matching has an additional property that we call conformal: if x and y are nodes in Γ, x the parent of y, and the label of x is less than or equal to the label of y, then the element of ∞σ which matches x occurs earlier in ∞σ than the element which matches y.

The construction of Γ is inductive and the base case is when σ and τ are empty; then the corresponding tree has a single node labelled ∞ and, in the matching, this node matches the first (and only) element of ∞σ.

If σ and τ are non-empty we consider the decomposition in Lemma 1. By induction, we may assume that, for each (σ_{i}, τ_{i}), there exists an unambiguous tree Γ_{i}, and a conformal matching between its set of nodes and the elements of ∞σ_{i}.

We now form a new tree from Γ_{0}, Γ_{1}, …, Γ_{a_{k}}. The first step is to replace each of the labels ∞ on the roots of Γ_{1}, …, Γ_{a_{k}} by a label k. We regard the label on the root of Γ_{i} as corresponding to the ith k, k_{i} of ∞σ; then we have a matching μ between the elements of ∞σ and the nodes of the forest {Γ_{0}, Γ_{1}, …, Γ_{a_{k}}}. The second step is to define new edges by the following rule:

(a) if k_{j} immediately follows a symbol (x_{j}) of k_{i}σ_{i} in σ an edge is placed between Γ_{i} and Γ_{j}

(b) the edge connects the root of Γ_{j} to the node z_{j} of Γ_{i} that matches the symbol x_{j}

Condition (b) together with condition (iii) of Lemma 1 ensures that if two trees Γ_{i} and Γ_{j} are joined in this way then i < j; thus the resulting graph Γ is indeed a tree. Moreover, by the conformal property, the node z_{j} of Γ_{i} has no child node in Γ_{i} labelled k; thus Γ is unambiguous. Furthermore, μ is now a conformal matching between the nodes of Γ and the elements of ∞σ.

Notice that, in Γ, the set of subtrees Γ_{i} may be readily identified; they are the connected components that remain when all edges with a lower end point labelled k have been removed. Moreover, their order, Γ_{0}, Γ_{1}, …, Γ_{a_{k}} may be reconstructed also. Obviously Γ_{0} is the subtree whose root is labelled ∞. The immediate subtrees of it will be Γ_{1}, Γ_{2}, …, Γ_{c} and their order is determined by the order of the nodes of Γ_{0} to which they are attached. The immediate subtrees of Γ_{1} will come next (ordered by the nodes of Γ_{1} to which they are attached); then the subtrees of Γ_{2}, Γ_{3} and so on.

These observations allow the construction to be reversed. Suppose that Γ is an unambiguous tree. We can produce a corresponding allowable pair (σ, τ) and a conformal mapping between the nodes of Γ and the elements of ∞σ as follows. First we delete all edges whose lower end point in labelled k to obtain a forest of trees {Γ_{0}, Γ_{1}, …, Γ_{a_{k}}}. We let Γ_{0} be the unique tree of the forest whose root is labelled ∞; all the other subtrees have root labelled k.

We now replace all the labels k by the label ∞ to obtain a forest of unambiguous trees, and using induction, we let (σ_{i}, τ_{i}) be the allowable pair that corresponds to Γ_{i}. Again by induction there will exist conformal mappings between the nodes of each Γ_{i} and the elements of ∞σ_{i}. Now, by the remarks following the previous construction, we can determine an order on the trees Γ_{0}, Γ_{1}, …, Γ_{a_{k}} in the forest.

Finally we construct the desired pair (σ, τ) according to Lemma 1. In other words we set τ = τ_{0}kτ_{1} … kτ_{a_{k}} and define σ to be the result of inserting a_{k} symbols k in σ_{0}σ_{1} … σ_{a_{k}}; the jth k is inserted immediately after x_{j}, where x_{j} is the symbol that matches the parent of the root of Γ_{j} in Γ (notice that the unambiguous property of Γ is used here in ensuring that x_{1}, x_{2}, …, x_{a_{k}} are all different elements of σ).

We have now shown that the construction of an unambiguous tree from an allowable pair is a bijection and so the proof of Theorem 2 is complete.

As an example, we show the construction of the unambiguous tree associated with the allowable pattern

(σ, τ) = (3_{1}2_{1}3_{2}1_{1}1_{2}2_{2}2_{3}3_{3}1_{3}2_{4}1_{4}, 1_{1}2_{1}3_{1}1_{2}2_{2}3_{2}2_{3}1_{3}3_{3}1_{4}2_{4})

Decomposing this pattern in accordance with lemma 1, we obtain the table of σ_{i}, τ_{i} and x_{i} which was given just before theorem 2.

We first catalogue the unambiguous trees associated with all allowable pairs of length not more than 2.

With the empty pair (,) is associated a tree^{∞}consisting simply of a root. With the pair (i, i) is associated the unambiguous tree

[figure: ∞; i]

This is evidently the only possibility, but it is easy to check that it is produced by the construction.

For the pair (i_{1}i_{2}, i_{1}i_{2}), the only possible unambiguous tree with the proper labels is.

[figure: ∞; i_{1}; i_{2}]

For the pair (12, 12) we have to use the construction of Theorem 2. Here k = 2, a_{k} = 1 and (σ_{0}, τ_{0}) = (1, 1), (σ_{1}, τ_{1}) = (,) and x_{1} = 1.

The corresponding tree is thus:

[figure: ∞; 1; 2]

For the pair (21, 21) we have (σ_{0}, τ_{0}) = (,), (σ_{1}, τ_{1}) = (1, 1) and x_{1} = ∞. We obtain the tree:

[figure: ∞; 2; 1]

The remaining allowable pair of length 2 is (21, 12), for which we have (σ_{0}, τ_{0}) = (1, 1), (σ_{1}, τ_{1}) = (,) and x_{1} = ∞. This gives rise to the tree:

[figure: ∞; 2; 1]

This gives us the components Γ_{0}, Γ_{1}, Γ_{2} and Γ_{3} of the forest from which the unambiguous tree of figure 1 is constructed. Relabeling the roots of Γ_{1}, Γ_{2} and Γ_{3} and attaching subscripts to the labels, they are:

[figure: Γ_{0} :; ∞; 1_{1}; 2_{1}; Γ_{1} :; 3_{1}; 1_{2}; 2_{2}; Γ_{2} :; 3_{2}; 2_{3}; 1_{3}; Γ_{3} :; 3_{3}; 1_{4}; 2_{4}]

Finally, we add edges joining x_{i} to 3_{i}: between ∞ and 3_{1}; between 2_{1} and 3_{2} and between 2_{3} and 3_{3}. We can then delete the subscripts (which represent the conformal map, used in the inductive step but not needed in the final tree) to give the tree of figure 1.

The reverse construction goes straight-forwardly. Decomposing Γ, we obtain the four subtrees Γ_{0}, …, Γ_{3}, with their labels. By induction we can determine the sub-patterns σ_{i} and τ_{i}. Finally the x_{i} are determined by the positions of the edges we deleted in the decomposition. According to Lemma 1, σ and τ are determined by the σ_{i}, τ_{i} and x_{i}.

In view of Theorem 2 we must determine the number of unambiguous trees to obtain a proof of Theorem 1. Since unambiguous trees are in one-to-one correspondence with k-way trees, Theorem 1 follows from the main result of [4].

3 The number of inputs and outputs

In this section we study the two quantities t(σ) = |{τ : (σ, τ) is allowable}|, and s(τ) = |{σ : (σ, τ) is allowable}| Clearly t(σ) is the number of different outputs that may arise when a pri-

ority queue is presented with the input σ; and s(τ) is the number of inputs capable of generating the output τ.

It turns out that t(σ) can be calculated by adapting the algorithm of [2] that was developed for permutations. Assuming that a_{k} > 0 (if not, we replace k by k − 1) we may put σ = αkβ where β = b_{1}b_{2} … b_{r} contains no element equal to k. Then we note that

t(αkβ) = \{ \begin{matrix}t(α) & if r = 0 \\ t(α)t(β) + t(αb_{1}kb_{2} … b_{r}) & otherwise \end{matrix}

(the term t(α)t(β) enumerates those outputs which arise from deleting the element k from the priority queue before inserting the first symbol of β (at that point the priority queue will be empty) and the term t(αb_{1}kb_{2} … b_{r}) enumerates the outputs which arise from inserting b_{1} before the element k is deleted).

As in [2] these equations can be made the basis of a dynamic programming algorithm with execution time O(n^{4}).

The quantity s(τ) cannot be calculated by generalising the permutation algorithm of [2] (that algorithm uses the distinctness of the elements in an essential way). We can, however, use Lemma 1. In the notation of that lemma we have

s(τ) = P ∏_{i=1}^{k} s(τ_{i})

where P is the number of ways in which the a_{k} occurrences of k may be validly positioned within σ_{0}σ_{1} … σ_{a_{k}}. A valid positioning is, by Lemma 1, one where each k occurs no later than the corresponding k in τ.

In order to calculate P, let r = a_{k} and let n_{1} < n_{2} < … < n_{r} be the positions of the elements equal to k in τ. Then, clearly, P is the number of vectors (m_{1}, m_{2}, …, m_{r}) such that

1. 1 ≤ m_{1} < m_{2} < … < m_{r} ≤ n, and

2. m_{i} ≤ n_{i}

since each vector gives a possible list of positions for the elements equal to k in σ. We now give a relatively simple algorithm for computing P.

Define the (r + 1)−variable function

Q_{r+1}(m_{0}, n_{1}, n_{2}, …, n_{r}) = ∑_{m_{1}=m_{0}+1}^{n_{1}} ∑_{m_{2}=m_{1}+1}^{n_{2}} ⋯ ∑_{m_{r}=m_{r−1}+1}^{n_{r}} 1

Then P = Q_{r+1}(0, n_{1}, n_{2}, …, n_{r}) since each term in the summation corresponds to a vector satisfying the conditions above. Then the recurrences

Q_{1}(m_{r}) = 1  for all m_{r}
Q_{r−k+1}(m_{k}, n_{k+1}, …, n_{r})

= ∑_{m_{k+1}=m_{k}+1}^{n_{k+1}} Q_{r−k}(m_{k+1}, n_{k+2}, …, n_{r})

= Q_{r−k+1}(m_{k} + 1, n_{k+1}, …, n_{r}) + Q_{r−k}(m_{k} + 1, n_{k+2}, …, n_{r})

allow the values Q_{r−k+1}(m_{k}, n_{k+1}, …, n_{r}) for all values of m_{k} to be calculated in constant time per value. The quantity P can therefore be calculated in O(na_{k}) steps.

An efficient algorithm for computing s(τ) is now evident. Recursively, we compute each s(τ_{i}), compute P, and then compute s(τ). The total work done is dominated by the time taken to compute P and all the analogous quantities in the recursive steps. One of these computations is done for every symbol of τ and so the total time is O(n ∑_{i=1}^{k} a_{i}) = O(n^{2})

4 The maximum number of outputs

It appears to be impossible to find a closed formula for t(σ) valid for arbitrary re-arrangements of the multiset S. Clearly, t(σ) is minimal in the case σ = 1^{a_{1}}2^{a_{2}} … k^{a_{k}} (here t(σ) = 1). The maximal value of t(σ) occurs when σ = k^{a_{k}} … 2^{a_{2}}1^{a_{1}} and, in this section, we shall investigate this maximal value. The analogous problem for s(τ) is more straightforward: its maximal value is \binom{n}{a_{1},a_{2},...,a_{k}} since every arrangement of S can generate the output 1^{a_{1}}2^{a_{2}} … k^{a_{k}}.

Let c(a_{1}, a_{2}, …, a_{k}) = t(k^{a_{k}} … 2^{a_{2}}1^{a_{1}}). We shall derive recurrences for this quantity and a closed expression for its multi-variate generating function. Remarkably, this generating function is a symmetric function in its k variables and therefore c(a_{1}, a_{2}, …, a_{k}) is symmetric in its arguments. We know of no simple reason for this fact.

Lemma 2 Let σ = k^{a_{k}} … 2^{a_{2}}1^{a_{1}}. Then a sequence τ on the same multiset is one of the possible outputs arising from σ as input if and only if τ has no subsequence abc whose relative values are as 132

Proof When a priority queue is given input in non-increasing order the current minimal element may be taken to be the last element inserted. We may therefore presume that elements are inserted and deleted according to a Last-In, First-Out discipline; in other words the priority queue behaves like a stack. Stack permutations can be characterised by the avoidance of a forbidden pattern [9] p.239 ((132) when the input is decreasing); this remains true even when the input has repeated elements.

Remarks

1. It is convenient to describe the conclusion of this lemma by saying that an output generated by σ has “no (132) pattern”, or that (σ, τ) has “no (321, 132) pattern”

2. A more general result than this can be proved: if σ and τ are any arrangements of S then (σ, τ) is allowable if and only if it has no (12, 21) pattern nor (321, 132) pattern.

Lemma 3 c(a_{1}) = 1 and for k ≥ 2,

c(a_{1}, …, a_{k}) =

\{ \begin{matrix}∑_{r=1}^{a_{1}} c(r, a_{2} − 1, …, a_{k}) + c(a_{1} + a_{2}, a_{3}, …, a_{k}) & for a_{2} ≥ 1 \\ c(a_{1}, a_{3}, .., a_{k}) & for a_{2} = 0 \end{matrix}

Proof If a_{2} = 0 the result follows by relabeling the elements of S. Assume a_{2} ≥ 1 and let R be the set of outputs that can be generated by the input k^{a_{k}} … 2^{a_{2}}1^{a_{1}}. Let σ ∈ R be such that all the 2’s in σ come before all the 1’s, and let σ′ be the sequence obtained from σ by replacing all the 1’s by 2’s. Then σ′ is an output for the sequence k^{a_{k}} … 2^{a_{2}+a_{1}}. Conversely, for any output σ′ generated by the input k^{a_{k}} … 2^{a_{2}+a_{1}}, we can construct a sequence σ in R by replacing the last a_{1} 2’s in σ′ by 1’s. The new sequence is in R since this change cannot introduce any (132) patterns. Hence the total number of sequences in R with all the 2’s before all the 1’s is c(a_{1} + a_{2}, a_{3}, …, a_{k}).

Next consider a sequence σ in R containing at least one occurrence of a 1 before a 2. By considering the first occurrence of 1 in σ and the first 2 succeeding this 1 we obtain a unique decomposition σ = σ_{1}1α2σ_{2} where σ_{1} contains no 1’s and α contains no 2’s. But then, because σ contains no 132 pattern α has the form α = 1^{q} for some q ≥ 0.

Consider the sequence σ̂ = σ_{1}1σ_{2} obtained by removing the uniquely determined substring 1^{q}2 from σ. Clearly σ̂ has no 132 pattern either and so is one of the c(a_{1} − q, a_{2} − 1, a_{3}, …, a_{k}) outputs obtainable from the input sequence k^{a_{k}} … 2^{a_{2}−1}1^{a_{1}−q}.

Conversely, from any one of these latter outputs σ̂ we can obtain a sequence of R merely by inserting the substring 1^{q}2 immediately after the first 1 of σ̂ (since this cannot introduce a 132 pattern). Therefore the total number of sequences in R which do not have all their 1’s before all their 2’s is

∑_{r=1}^{a_{1}} c(r, a_{2} − 1, …, a_{k})

which proves the result.

Using the previous lemma one can obtain the following results fairly easily.

c(a_{1}) = 1
c(a_{1}, a_{2}) = \binom{a_{1} + a_{2}}{a_{1}}

c(a_{1}, a_{2}, a_{3}) = 2^{a_{1}+a_{2}+a_{3}} − ∑_{r=0}^{a_{1}−1} \binom{a_{1} + a_{2} + a_{3}}{r}

− ∑_{r=0}^{a_{2}−1} \binom{a_{1} + a_{2} + a_{3}}{r} − ∑_{r=0}^{a_{3}−1} \binom{a_{1} + a_{2} + a_{3}}{r}

However, obtaining an expression for c(a_{1}, a_{2}, …, a_{k}) in general appears to present more difficulty. Further progress can be made by defining

G(x_{1}, …, x_{k}) = ∑_{a_{1}=0} ⋯ ∑_{a_{k}=0} c(a_{1}, …, a_{k})x_{1}^{a_{1}} … x_{k}^{a_{k}}

as the generating function for c(a_{1}, …, a_{k}). The recurrence for c(a_{1}, …, a_{k}) above can be used to obtain a recursive formula for G(x_{1}, …, x_{k}).

Lemma 4

G(x_{1}) = \frac{1}{1 − x_{1}} ,
G(x_{1}, …, x_{k}) =

\frac{x_{2}(1 − x_{2})G(x_{2}, x_{3}, …, x_{k}) − x_{1}(1 − x_{1})G(x_{1}, x_{3}, …, x_{k})}{(1 − x_{1} − x_{2})(x_{2} − x_{1})} for k ≥ 2

Proof Clearly, c(a_{1}) = 1 for all a_{1} ≥ 0 and so G(x_{1}) = 1/(1−x_{1}). Now assume k ≥ 2.

G(x_{1}, …, x_{k})

= ∑_{a_{1}=0} ⋯ ∑_{a_{k}=0} c(a_{1}, …, a_{k})x_{1}^{a_{1}} ⋯ x_{k}^{a_{k}}

= ∑_{a_{1}=0} ∑_{a_{2}=1} ⋯ ∑_{a_{k}=0} (∑_{r=0}^{a_{1}} c(r, a_{2} − 1, …, a_{k})

− c(0, a_{2} − 1 …, a_{k}) + c(a_{1} + a_{2}, a_{3}, …, a_{k}))x_{1}^{a_{1}} ⋯ x_{k}^{a_{k}}

+ ∑_{a_{1}=0} ∑_{a_{3}=0} ⋯ ∑_{a_{k}=0} c(a_{1}, a_{3}, …, a_{k})x_{1}^{a_{1}}x_{3}^{a_{3}} ⋯ x_{k}^{a_{k}}

= x_{2} ∑_{a_{1}=0} ⋯ ∑_{a_{k}=0} ∑_{r=0}^{a_{1}} c(r, a_{2}, …, a_{k})x_{1}^{a_{1}} ⋯ x_{k}^{a_{k}}

+ x_{2} ∑_{a_{1}=0} ⋯ ∑_{a_{k}=0} (c(1 + a_{1} + a_{2}, a_{3}, …, a_{k}) − c(a_{2}, a_{3}, …, a_{k})) x_{1}^{a_{1}} … x_{k}^{a_{k}}

+ G(x_{1}, x_{3}, …, x_{k})

= x_{2} ∑_{a_{2}=0} ⋯ ∑_{a_{k}=0} ∑_{r=0} ∑_{a_{1}=r} c(r, a_{2}, …, a_{k})x_{1}^{a_{1}} ⋯ x_{k}^{a_{k}}

+ x_{2} ∑_{a_{1}=0} ⋯ ∑_{a_{k}=0} c(1 + a_{1} + a_{2}, a_{3}, …, a_{k})x_{1}^{a_{1}} ⋯ x_{k}^{a_{k}}

− \frac{x_{2}}{1 − x_{1}} G(x_{2}, x_{3}, …, x_{k}) + G(x_{1}, x_{3}, …, x_{k})

= \frac{x_{2}}{1 − x_{1}} G(x_{1}, x_{2}, …, x_{k}) − \frac{x_{2}}{1 − x_{1}} G(x_{2}, x_{3}, …, x_{k})

+ G(x_{1}, x_{3}, …, x_{k}) + H

where

H = x_{2} ∑_{a_{1}=0} ⋯ ∑_{a_{k}=0} c(1 + a_{1} + a_{2}, a_{3}, …, a_{k})x_{1}^{a_{1}} ⋯ x_{k}^{a_{k}}

= ∑_{a_{1}=0} (\frac{x_{1}}{x_{2}} )^{a_{1}} ∑_{a_{2}=0} ⋯ ∑_{a_{k}=0} c(1 + a_{1} + a_{2}, a_{3}, …, a_{k})x_{2}^{1+a_{1}+a_{2}} ⋯ x_{k}^{a_{k}}

= ∑_{a_{1}=0} (\frac{x_{1}}{x_{2}} )^{a_{1}} ( ∑_{a_{2}=0} ⋯ ∑_{a_{k}=0} c(a_{2}, a_{3}, …, a_{k})x_{2}^{a_{2}} ⋯ x_{k}^{a_{k}}

− ∑_{a_{3}=0} ⋯ ∑_{a_{k}=0} ∑_{a_{2}=0}^{a_{1}} c(a_{2}, a_{3}, …, a_{k})x_{2}^{a_{2}} ⋯ x_{k}^{a_{k}})

= ∑_{a_{1}=0} (\frac{x_{1}}{x_{2}} )^{a_{1}} G(x_{2}, …, x_{k})

− ∑_{a_{1}=0} (\frac{x_{1}}{x_{2}} )^{a_{1}} ∑_{a_{2}=0}^{a_{1}} ∑_{a_{3}=0} ⋯ ∑_{α_{k}=0} c(a_{2}, a_{3}, …, a_{k})x_{2}^{a_{2}} ⋯ x_{k}^{a_{k}}

= \frac{x_{2}}{x_{2} − x_{1}} G(x_{2}, x_{3}, …, x_{k})

− ∑_{a_{2}=0} ( ∑_{a_{1}=a_{2}} (\frac{x_{1}}{x_{2}} )^{a_{1}}) ∑_{a_{3}=0} ⋯ ∑_{a_{k}=0} c(a_{2}, a_{3}, …, a_{k})x_{2}^{a_{2}} ⋯ x_{k}^{a_{k}}

= \frac{x_{2}}{x_{2} − x_{1}} G(x_{2}, x_{3}, …, x_{k})

− ∑_{a_{2}=0} ∑_{a_{3}=0} ⋯ ∑_{a_{k}=0} \frac{x_{1}^{a_{2}}}{x_{2}^{a_{2}−1} (x_{2} − x_{1})}c(a_{2}, a_{3}, …, a_{k})x_{2}^{a_{2}} ⋯ x_{k}^{a_{k}}

= \frac{x_{2}}{x_{2} − x_{1}} (G(x_{2}, x_{3}, …, x_{k}) − G(x_{1}, x_{3}, …, x_{k}))

It follows that

G(x_{1}, …, x_{k}) =

\frac{x_{2}(1 − x_{2})G(x_{2}, x_{3}, …, x_{k}) − x_{1}(1 − x_{1})G(x_{1}, x_{3}, …, x_{k})}{(1 − x_{1} − x_{2})(x_{2} − x_{1})}

as required.

To solve this recurrence and obtain an expression for G(x_{1}, …, x_{k}) we use the notation

y_{i} = x_{i}(1 − x_{i}).

Then the recurrence becomes:

G(x_{1}) = x_{1}/y_{1}

G(x_{1}, …, x_{k}) = \frac{1}{(y_{1} − y_{2})} (y_{1}G(x_{1}, x_{3}, …, x_{k}) − y_{2}G(x_{2} …, x_{k})) .

Now let

A(z_{1}, …, z_{n}) = ∏_{1≤i<j≤n}(z_{i} − z_{j}),

for n ≥ 2, and let A(z) = 1 and A() = 1. The following result was initially conjectured as a result of computational exploration with the AXIOM system [8].

Theorem 3

G(x_{1}, …, x_{k}) = −\frac{∑_{i=1}^{k}(−1)^{i}x_{i}y_{i}^{k−2}A(y_{1}, …, y_{i−1}, y_{i+1}, …, y_{k})}{A(y_{1}, …, y_{k})}

Proof by induction on k. When k = 1, the result can be checked directly. Otherwise assume the result holds for k − 1 and substitute that twice into the recurrence above. We get

G(x_{1}, …, x_{k})

= \frac{−1}{y_{1} − y_{2}}

(\frac{y_{1} ( \begin{matrix}−x_{1}y_{1}^{k−3}A(y_{3}, …, y_{k}) \\ + ∑_{i=3}^{n}(−1)^{i−1}x_{i}y_{i}^{k−3}A(y_{1}, y_{3}, …, y_{i−1}, y_{i+1}, …, y_{k}) \end{matrix} )}{A(y_{1}, y_{3}, …, y_{k})}

− y_{2} \frac{(∑_{i=2}^{n} x_{i}y_{i}^{k−3}(−1)^{i−1}A(y_{2}, …, y_{i−1}, y_{i+1}, …, y_{k}))}{A(y_{2}, …, y_{k})}) .

Placing this over a common denominator of A(y_{1}, …, y_{k}) the numerator becomes:

x_{1}y_{1}^{k−2}A(y_{3}, …, y_{k}) ∏_{j=3}^{k}(y_{2} − y_{j})

+ ∑_{i=3}^{k}(−1)^{i}x_{i}y_{i}^{k−3}y_{1}A(y_{1}, y_{3}, …, y_{i−1}, y_{i+1}, …, y_{k}) ∏_{j=3}^{k}(y_{2} − y_{j})

− ∑_{i=2}^{k}(−1)^{i}x_{i}y_{i}^{k−3}y_{2}A(y_{2}, …, y_{i−1}, y_{i+1}, …, y_{k}) ∏_{j=3}^{k}(y_{1} − y_{j})

Collecting terms in each x_{i} and combining the products with the A(…) expressions this becomes:

x_{1}y_{1}^{k−2}A(y_{2}, …, y_{k}) − x_{2}y_{2}^{k−2}A(y_{1}, y_{3}, …, y_{k})

+ ∑_{i=3}^{k}(−1)^{i}x_{i}y_{i}^{k−3}A(y_{1}, …, y_{i−1}, y_{i+1}, …, y_{k}) (\frac{y_{1}(y_{2} − y_{i}) − y_{2}(y_{1} − y_{i})}{y_{1} − y_{2}})

Finally, we note that

\frac{y_{1}(y_{2} − y_{i}) − y_{2}(y_{1} − y_{i})}{y_{1} − y_{2}} = −y_{i}

which gives the desired result.

Corollary 2 c(a_{1}, …, a_{k}) is symmetric in a_{1}, …, a_{k}

Proof The denominator of the generating function G(x_{1}, …, x_{k}) is clearly anti-symmetric in its variables. Furthermore, it is clear that exchanging two variables x_{i} and x_{i+1} (1 ≤ i < k) in the numerator negates it, which implies that the numerator is also anti-symmetric. Thus the generating function is symmetric and the result now follows.

Remark: H.S. Wilf [13] has observed that both the numerator and the denominator of the expression for G can be viewed as determinants, giving

G(x_{1}, …, x_{k}) = \begin{matrix}| & \begin{matrix}y_{1}^{0} & y_{1}^{1} & ⋯ & y_{1}^{k−2} & x_{1}y_{1}^{k−2} \\ y_{2}^{0} & y_{2}^{1} & ⋯ & y_{2}^{k−2} & x_{2}y_{2}^{k−2} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ y_{k}^{0} & y_{k}^{1} & ⋯ & y_{k}^{k−2} & x_{k}y_{k}^{k−2} \end{matrix} & | \\ | & \begin{matrix}y_{1}^{0} & y_{1}^{1} & ⋯ & y_{1}^{k−1} \\ y_{2}^{0} & y_{2}^{1} & ⋯ & y_{2}^{k−1} \\ ⋮ & ⋮ & ... & ⋮ \\ y_{k}^{0} & y_{k}^{1} & ⋯ & y_{k}^{k−1} \end{matrix} & | \end{matrix}

This is exactly the form given by Cramer’s rule for determining the last unknown u_{k} in the system of linear equations (indexed by i):

∑_{j=1}^{k} u_{j}y_{i}^{j−1} = x_{i}y_{i}^{k−2}

Letting

P (t) = ∑_{j=0}^{k−1} u_{k−j}t^{j}

we see that u_{k} is in fact the constant term in the unique polynomial P (t) of degree k − 1 defined by

P (1/y_{i}) = x_{i}/y_{i}

It is not known whether the other coefficients of this polynomial or the polynomial itself have any combinatorial meaning. Acknowledgment We thank the referee for a number of suggestions which greatly improved the exposition of this paper.

References

[1] Atkinson M D and Thiyagarajah M: The permutational power of a priority queue, BIT 33 (1993), 2-6.

[2] Atkinson M D and Beals R: Priority queues and permutations, SIAM J. Computing 23 (1994), 1225–1230.

[3] Atkinson M D: Transforming binary sequences with priority queues, OR-DER 10 (1993), 31-36.

[4] Atkinson M D and Walker L A: Enumerating k-way trees, Information Processing Letters 48 (1993), 73-75.

[5] Cameron P J: Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, (Cambridge, New York, Melbourne) 1994.

[6] Cormen T H, Leiserson C E, Rivest R L: Introduction to Algorithms, McGraw-Hill (Cambridge, Mass.) 1992 [7] Golin M, Zaks S: Labelled trees and pairs of input-output permutations

in priority queues, Proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), München, Germany, June 1994

[8] Jenks R D, Sutor R S: Axiom, the Scientific Computation System, Springer-Verlag, (New York), 1992

[9] Knuth D E: Fundamental Algorithms, The Art of Computer Programming Vol. 1, Addison-Wesley, (Reading, Massachusetts), 1973

[10] Knuth D E: Sorting and Searching, The Art of Computer Programming Vol. 3, Addison-Wesley, (Reading, Massachusetts), 1973

[11] Moon J W: Counting Labelled Trees, Canad. Math. Monographs No. 1 (1970).

[12] Pratt V R: Computing permutations with double-ended queues, parallel stacks and parallel queues, Proc. ACM Symp. Theory of Computing 5 (1973), 268–277.

[13] Wilf H S: private communication, 1995.