Reinhard Kutzelnigg
email: reinhard.kutzelnigg@gmail.com

A further analysis of Cuckoo Hashing with a Stash and Random Graphs of Excess r

Keywords: Hashing, Cuckoo hashing, Algorithms, Generating functions, Random graphs, Saddle point method

 showed that a constant-sized additional memory, the so called stash, is sufficient to reduce the failure rate drastically. But so far, using a modified insertion procedure that demands additional running time to look for an admissible key is required. As a major contribution of this paper, we show that the same bounds on the failure probability hold even without this search process and thus, the performance increases. Second, we extend the analysis to simplified cuckoo hashing, a variant of the original algorithm offering increased performance. Further, we derive some explicit asymptotic approximations concerning the number of usual resp. bipartite graphs related to the data structures. Using these results, we obtain much more precise asymptotic expansions of the success rate. These calculations are based on a generating function approach and applying the saddle point method. Finally, we provide numerical results to support the theoretical analysis.

Introduction

In computer science, hash tables are a frequently used tool to build dictionary-like data structures that support fast insertion, search and potentially also deletion operations, see, e.g. [START_REF] Cormen | Introduction to Algorithms[END_REF]. All these algorithms are based on using hash functions that map data records (keys) to a unique memory cell of the table. We say that two different keys collide if both try to occupy a single memory slot. The critical point of each hash algorithm is the handling of colliding keys.

In particular, hash algorithms that offer constant access time even in the worst case are of high interest. One of these algorithms is cuckoo hashing that was first proposed by [START_REF] Pagh | Cuckoo hashing[END_REF]. In contrast to common hash techniques like open addressing and hashing with chaining (see, e.g., [START_REF] Knuth | The Art of Computer Programming, Volume III: Sorting and Searching[END_REF]), collisions are resolved by rearranging keys. This is achieved by using two independent hash functions h 1 and h 2 , both map a key to a unique position in the data structure. These are the only allowed storage locations of that key and, hence search operations require at most to access two memory cells. There are several different variants of cuckoo hashing known in the literature, see [START_REF] Fotakis | Space efficient hash tables with worst case constant access time[END_REF]; [START_REF] Dietzfelbinger | Balanced allocation and dictionaries with tightly packed constant size bins[END_REF] and [START_REF] Kutzelnigg | An improved version of cuckoo hashing: Average case analysis of construction cost and search operations[END_REF]. In this paper we consider the following two: The standard algorithm introduced in [START_REF] Pagh | Cuckoo hashing[END_REF] splits the available memory cells in two equal parts and grants each hash function exclusively access to one of these regions. However, this split-up is not necessary. We obtain an in some sense simplified algorithm, if both hash functions address the whole table. It is shown in [START_REF] Kutzelnigg | Random Graphs and Cuckoo Hashing[END_REF][START_REF] Kutzelnigg | An improved version of cuckoo hashing: Average case analysis of construction cost and search operations[END_REF] that this variation, henceforth referred to as simplified cuckoo hashing, offers improved search and insertion performance.

Despite this difference, the insertion process works for both algorithms considered here as follows: To insert a new key x, we put it into the table position indicated by h 1 (x). Now, if this position was previously empty, the insertion is complete. Otherwise, we kick-out the key y that previously occupied h 1 (x) = h 1 (y) and move it to its alternative position h 2 (y). If this position was already in use by a key z, we continue moving z to its alternative position. We carry on in this way until an empty cell is found or we detect an endless loop. The latter case can be uncovered by the number of kick-out steps performed. The standard way to handle this critical situation is to rebuild the complete data structure using two new hash functions. Fortunately, the occurrence of an endless loop is a rare event. More precisely, both variants of cuckoo hashing succeed with probability 1 -O(1/m), conditioned that the load factor (i) is less than 0.5, see [START_REF] Devroye | Cuckoo hashing: Further analysis[END_REF], [START_REF] Drmota | A precise analysis of cuckoo hashing[END_REF], and [START_REF] Pagh | Cuckoo hashing[END_REF].

The analysis is hereby usually based on the assumption that the values of the hash functions form a sequence of independent uniform random numbers. This seems to impose strong conditions on the hash functions in use. However, numerical results obtained using quite simple hash functions are in good accordance with the results obtained by this model. Thus, we assume the same conditions on the hash functions to be satisfied in this paper too. A further discussion of this model, hash functions suitable for practical implementation, and additional references are given in [START_REF] Kutzelnigg | Random Graphs and Cuckoo Hashing[END_REF], but see also [START_REF] Dietzfelbinger | On risks of using cuckoo hashing with simple universal hash classes[END_REF].

Although the success probability of cuckoo hashing tends to one under the conditions stated above, there is still a non negligible failure rate, even for large data structures. For instance, consider the outcome of one of the numerical experiments given in Table 8: There occurred 14355 errors among 10 7 constructions of data structures, each possessing in total 10 5 memory cells and a load factor α = 0.45. Clearly, rebuilding a table requires high additional running time. Hence, cuckoo hashing is not attractive for applications where this behavior is not acceptable. To overcome this weak point, [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF] suggested to use a small additional memory, the so called stash. This stash is used to store items that could not be placed in the table itself. Interestingly, this modification drastically reduces the failure rate. More precisely, the authors showed that an additional memory of s items is sufficient to achieve a success probability of 1 -O m -s-1 for the standard algorithm. However, the analysis is based on the usage of a modified insertion algorithm that requires additional steps to look for an admissible keys that can be placed in the stash. Details will be discussed in Section 4. We will show that the same result can be achieved without this search process, as it was already conjectured in [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF]. Next, we prove that the same bound is valid for the simplified version of cuckoo hashing. Further, we demonstrate how detailed asymptotic expansions of the success rate can be obtained using a generating function approach.

In particular, this can be used to show that the failure rate is in fact in Θ m -s-1 . Finally, we support our analysis by numerical results.

The Cuckoo Graph

Our analysis is based on the cuckoo graph, a concept first developed in [START_REF] Devroye | Cuckoo hashing: Further analysis[END_REF]. Hereby, standard cuckoo hashing without a stash is modeled using a bipartite multi graph. Each memory cell corresponds to a labeled node. Further, a node is colored "red" if and only if the according cell belongs to the first half of the memory slots. All other vertices are colored "blue". We further assume that the whole data structure contains 2m storage positions, each part numbered from 1 to m. We label the nodes accordingly. Next, each key is encoded by an edge that joins the two possible storage locations of that key. Additionally, the i-th inserted edge is labeled by i to encode the evolution. Note that the obtained graph is bipartite by construction.

Clearly, it is impossible for the algorithm to succeed if a component exists that has more edges than vertices. Thus, all components of the cuckoo graph must either be trees or unicyclic, i.e. contain either none or exactly one cycle. Interestingly, this condition is not only necessary, but also sufficient. More precisely, the key observation in [START_REF] Devroye | Cuckoo hashing: Further analysis[END_REF] is that cuckoo hashing succeeds if and only if all connected components of the cuckoo graph are either trees or unicyclic. Further, it is common to call the "bad" parts, i.e. connected components possessing more than one cycle, complex.

Concerning simplified cuckoo hashing, a similar modeling is possible, see [START_REF] Kutzelnigg | An improved version of cuckoo hashing: Average case analysis of construction cost and search operations[END_REF]. In contrast to the bipartite graph described above, the one-table data structure is represented by a non-bipartite edge and node labeled directed graph. Edges are again used to represent keys and they still connect the two possible storage locations. However, it is necessary to use directed edges, to determine the primary storage position uniquely. This is closely related to the multi graph process described in [START_REF] Janson | The birth of the giant component[END_REF]. Despite these differences in the definition of the graph model, simplified cuckoo hashing is again successful if and only if the shadow graph (ii) of its cuckoo graph does not contain a component with more than one cycle.

Additionally to the obvious implementation of the simplified algorithm that allows both storage positions of a key to be equal, there is a further method. Assume that the data structure contains 2m storage positions. For each key x, we assume that the hash value of the second hash function h 2 (x) is selected uniformly at random among the set {1, 2, . . . , 2m} \ h 1 (x). This can be achieved by using a function k(x) that maps x to a (pseudo) random number from 1 to 2m -1 and setting h 2 (x) = h 1 (x) + k(x) mod 2m. As a small drawback, the evaluation of h 2 (x) requires an additional summation. On the other hand, each key now possesses in any way two different storage positions and the corresponding cuckoo graph does not contain self-loops. Consequently, we expect increased performance. In fact, this can be verified by a theoretical analysis, see [START_REF] Kutzelnigg | An improved version of cuckoo hashing: Average case analysis of construction cost and search operations[END_REF]. However, note that the actual behavior is very similar, especially if tables are getting full.

(ii) Given a directed graph, we obtain its shadow graph by replacing each edge by an undirected one. Note that we consider multi graphs, thus multiple edges that occur in this process are retained.

Results

Theorem 1 Consider a standard cuckoo hash data structure possessing two subtables of size m and holding n = 2αm keys, where α ∈ (0, 0.5) is fixed. Whenever an endless loop is detected, the last kicked-out element is placed in the stash of size s ≥ 1. Then, the construction succeeds with probability

1 -c(α, s) m -s-1 + O m -s-2 . (1)
Hereby, c(α, s) = 0 depends on α and s, but not on m and it can be calculated explicitly with our method.

An essential difference of this result compared to [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF], Theorem 1) is that we do not require additional steps to search for admissible keys. Further, our asymptotic result is much more precise.

The proof of Theorem 1 is split up into two parts. First, a proof that the described insertion strategy succeeds with probability 1 -O m -s-1 is given in Section 4. These considerations are a refinement of the original analysis that can be found in [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF]. The further proof is based on a generating function approach on the cuckoo graph and can be found in Section 7. In particular, we prove that c(α, s) = 0 holds. Moreover, we present a method to compute this coefficient, and we have implemented it with Maple. However, note that the calculations are limited by the available memory of the machine that executed the computer algebra system. Using a workstation equipped with 12GB RAM, we were successful in solving the problem for s ∈ {0, 1, 2}.

Note that during a successful insertion procedure, each memory slot is visited at most twice. Thus, an insertion procedure in a table previously holding i keys is clearly unsuccessful if it takes more than 2i + 1 kick-outs. However, we can usually do much better and stop earlier, see [START_REF] Kutzelnigg | Random Graphs and Cuckoo Hashing[END_REF] for corresponding numerical data. On the other hand, there is a risk that we stop procedures that would have been successful. The probability can be bounded as follows: For each k, there exists a sufficiently large number β = β(k) that does not depend on m, such that the probability that there is an insertion that takes more than β log m steps is O m -k , see (Kirsch et al., 2008, Lemma 4 and (1)). Hence, (1) still holds if an insertion procedure is stopped and declared unsuccessful after β log m kick-outs performed, provided that β is chosen sufficiently large.

Furthermore, we can analyze the simplified version by similar methods, see Sections 5 and 7 for details. Note that we distinguish between the straightforward implementation, and the version without self-loops as described in the previous section.

Theorem 2 Consider a simplified cuckoo hash table possessing 2m memory cells and holding n = 2αm keys, where α ∈ (0, 0.5) is fixed. Suppose that h 2 is implemented such that h 2 (x) = h 1 (x) holds for all keys x. Whenever an endless loop is detected, the last kicked-out element is placed in the stash of size s ≥ 1. Then, the construction succeeds with probability

1 -c(α, s) m -s-1 + O m -s-2 .
Hereby, c(α, s) = 0 depends on α and s, but not on m and it can be calculated explicitly with our method.

Similar to the considerations given above, it is again possible to stop presumably unsuccessful insertion procedures early.

Until now, we have successfully calculated the numbers c(α, s) for all s ≤ 8. Unfortunately, Theorem 2 does not cover the situation where self-loops are not excluded. However, we can analyze it with our generating function approach and yield: Theorem 3 Suppose that the conditions of Theorem 2 are fulfilled, except that the data structure is implemented in the way such that self-loops may occur. Further, let s ∈ {0, 1, . . . , 8}. Then, the probability that the construction of a simplified cuckoo hash table succeeds equals

1 -ĉ(α, s) m -s-1 + O m -s-2 .
Hereby, ĉ(α, s) = 0 depends on α and s, but not on m and it can be calculated explicitly with our method.

The proof of this result can be found in Section 7.

Insertion

The results given in this section hold for both types of cuckoo graphs. However note that the original paper of [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF] considered the bipartite version only.

4.1 The insertion procedure of [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF] Once an endless loop is discovered, it is required to search for an admissible key to be put in the stash, such that the remaining keys can be placed in the original hash table. Clearly, a key is acceptable if and only if the cuckoo graph does not possess a complex component after removing the coressponding edge. We continue with an observation stated in [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF], and we are using the same notation as in that paper: Given the cuckoo graph G, we denote the total number of edges that closed a cycle when inserted by f (G). Further, the number of the connected components containing at least one cycle is denoted by T (G). Consequently, the number of elements that could not be stored in the table itself and have to be placed in the stash, equals f (G) -T (G). Moreover, we continue describing the modified insertion procedure used in [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF]: Whenever an endless loop is detected, the last insertion step created a component possessing two cycles. We proceed searching for an edge of that component that is contained in one of this two cycles. This is done by counting how often a memory cell is accessed during an insertion and thus, it is quite computational expensive resp. memory consuming. Next we delete the selected edge from the graph and put the corresponding key into the stash. Note that an edge that closes a cycle on insertion in the original graph, still closes a cycle if we have removed some edges as described above. Hence, we have found a way to remove exactly f (G) -T (G) edges, such that all conflicts are resolved. Clearly, removing less edges can not repair all problems and hence the solution has minimal cardinality.

Insertion without search for an admissible key

However, removing an edge that belongs to a cycle is not the only possible way to decrease f (G) -T (G). We can alternatively choose the edge such that T (G) increases. This corresponds to breaking up a component in two parts, but both of that new components must not be trees. We proceed using the following definition: Definition 1 Consider a connected graph H. The excess e(H) is given by e(H) = # edges(H) -# nodes(H).

Furthermore, for a graph G, we define

ẽ(G) = H max(e(H), 0) = f (G) -T (G),
where the sum is taken over all components H of G.

The insertion procedure is modified as follows: As long as no irresolvable conflict occurs in a basic cuckoo hash data structure, we perform the insertions using the original algorithm of [START_REF] Pagh | Cuckoo hashing[END_REF] that is described in Section 1. However, each time we detect an endless loop, we put the last kicked-out key in the stash, and delete the corresponding edge. More precisely, we even may select that key arbitrarily among the set of all keys that have been kicked out in the current insertion procedure, but it is of course convenient to choose the last evicted key. We then proceed in the usual way to insert further keys, until the next problem is discovered. Thus, we avoid a complicated cycle detection mechanism.

The remainder of this section is used to proof that this strategy is alway successful. First, we say that an edge is disturbing, if its insertion increases ẽ(G). Recall that we are considering labeled and thus ordered edges. Since ẽ(G) cannot decrease by inserting an additional edge (iii) , ẽ(G) equals the number of disturbing edges. However, it is possible to decrease ẽ(G) by removing certain edges:

Lemma 1 Removing an edge g of G decreases ẽ(G) if
(G \ g) = ẽ(G) -e(H) + e(H 1 ) + e(H 2 ) = ẽ(G) -1.
2

Next, we consider the influence of removed edges on further disturbing edges:

Lemma 2 Let G denote a graph arising from G, where we have already removed ẽ(G) edges such that ẽ(G ) = 0 holds. Assume that a new edge g is disturbing in G . Then, it is disturbing in G too.

Proof: We consider two different situations in G , see Figure 1. First, suppose that g is a bridge in G that connects H 1 and H 2 . By similar reasoning as in the proof of Lemma 1, both of this components cannot

H ′ 1 H ′ 2 g H 1 H 2 g H ′ g H g or or in G ′ :
in G:

Fig. 1: A disturbing edge g. We distinguish whether g is a bridge in G or not. (iii) Note that the number of nodes is fixed, and hence remains unchanged.

or Fig. 2: The two possible types of bicyclic components.

be trees, because otherwise g would not be a disturbing edge. Thus, e(H 1 ) ≥ 0 and e(H 2 ) ≥ 0 hold. Assume that g is a bridge in G that connects components H 1 ⊇ H 1 and H 2 ⊇ H 2 . We conclude that e(H 1 ) ≥ e(H 1 ) ≥ 0 and e(H 2 ) ≥ e(H 2 ) ≥ 0 are fulfilled. Hence g is disturbing in G. The proof of the two further cases follows by a similar argument as above. 2

Lemma 3 Assume that we always perform the following steps whenever the insertion procedure has entered an endless loop: We stop at an arbitrarily selected moment, put the current homeless key in the stash of potential unlimited capacity, and delete the corresponding edge. By doing so, the stash holds ẽ(G) keys finally, where G denotes the original cuckoo graph without deleted edges.

Proof: Consider the graph G that encodes the current state of the data structure. The algorithm enters an endless loop whenever a component containing two cycles is created. This can either happen by closing a further cycle in an unicyclic component or by connecting two different unicyclic components. Hence, the new edge is disturbing for G . There exist two different typical situations, depicted in Figure 2. Each of the nodes can be considered as root of an additional attached tree, not depicted in the figure . Observe that the last inserted edge must be contained in the drawn part. None of the keys belonging to one of the depicted edges has a possible storage position in these potentially attached trees. Hence the presence of this appendix has no influence on the current insertion. In particular, none of these keys can ever become kicked-out in the current insertion operation. Note that arbitrarily selection and deletion of one the drawn edge decreases ẽ, because of Lemma 1. Note that the frequency of the occurrence of a disturbing edge is bounded by ẽ(G), due to Lemma 2. Hence, we place at most ẽ(G) keys in the stash. On the other hand, this is the minimum number of elements that have to be stored outside the table .  2

To prove Theorem 1, it hence remains to show that P(ẽ(G) ≥ s+1) has asymptotic expansion (1). This is done in Section 7. Due to (Kirsch et al., 2008, (2)), the relation

P(ẽ(G) ≥ s + 1) = P(f (G) -T (G) ≥ s + 1) = O(m -s-1
) is already known. We just want to correct a minor mistake. When an insertion hits a cyclic component, several (and not only one) vertices might be visited twice. In particular, k + 1 is not a valid upper bound for the number of steps that an insertion requires in a component of size k, as claimed in [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF], Lemma 1). However, 2k is sufficient bound, see [START_REF] Devroye | Cuckoo hashing: Further analysis[END_REF] or [START_REF] Kutzelnigg | Random Graphs and Cuckoo Hashing[END_REF] for further details.

Simplified Cuckoo Hashing

Instead of segmenting the available memory, this modified version grants both hash functions access to the whole table. This variant was first mentioned in [START_REF] Pagh | Cuckoo hashing[END_REF], a detailed analysis can be found in [START_REF] Kutzelnigg | Random Graphs and Cuckoo Hashing[END_REF][START_REF] Kutzelnigg | An improved version of cuckoo hashing: Average case analysis of construction cost and search operations[END_REF]. In particular, the simplified algorithm offers improved performance of search and insertion operations.

In this section, we prove that the data structure of Theorem 2 succeeds with probability 1 -O(m -s-1 ). First, recall that all lemmata given in Section 4 did not require a bipartite structure of G. Hence, ẽ(G) still equals the number of keys that can not be stored in the table itself. Recall that we consider the implementation without self-loops only. This is based on the fact that it is possible to adopt the analysis of [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF] for this version. Nevertheless, because of the results given in Section 7, we conjecture that the same bound holds for the other implementation too. Our proof is based on a stochastic dominance argument, and we repeat resp. adopt the following definitions and results from [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF]: For a distribution D, let G(2m, D) denote the distribution over graphs with 2m nodes, obtained by sampling l ∼ D and inserting l edges independently. Hereby, start point and end point of each edge are selected uniformly and independently, except that no self loops are allowed. Clearly, the cuckoo graph of the simplified variant has distribution G(2m, D) when D is concentrated at n.

Given two graphs G and G possessing the same set of vertices, we say that G ≥ G holds if each edge of G is also contained in G . Additionally, we generalize this relation on t-tuples of graphs by applying it component-by-component, i.e.

(G 1 , . . . , G t ) ≥ (G 1 , . . . , G t ) holds if G i ≥ G i is fulfilled for all i.
Definition 2 Let µ and ν be two probability measures over t-tuples of graphs with common vertex set. Then, µ stochastically dominates ν, in short notation µ

ν, if E µ (g(G)) ≥ E ν (g(G)
) holds for all non-decreasing functions g.

Further, let Po(λ) denote the Poisson distribution with parameter λ.

Lemma 4 Assume that λ > 0 is fixed. Then, the conditional distribution of G ∼ G(2m, Po(λ)), conditioned on the property that G has at least n edges stochastically dominates G(2m, n).

Proof: The proof follows the lines of (Kirsch et al., 2008, Lemma 3). Obviously, the conditional distribution of G under the assumption that there are exactly n edges is G(2m, n). Since k 1 > k 2 implies G(2m, k 1 ) G(2m, k 2 ), the result follows.

2

It is easy to see that the parameter λ can bee chosen such that the probability that G(2m, Po(λ)) has less than n edges is exponentially small: Lemma 5 [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF]) Let ε > 0 be fixed and define λ = (1 + ε )n. Then we yield

P(Po(λ) < n) = e -Ω(n) .
Thus, it remains to show that for G ∼ G(2m, Po(λ)) the relation

P ẽ(G) ≥ s = O(m -s ) (2) holds. Given a vertex v of G ∼ G(2m, Po(λ)), let C v denote the connected component that contains v.
Furthermore, let B v denote the number of edges that belong to C v that closed a circle on insertion.

Lemma 6 Assume that ε < 1/(2α) -1 and t,k,n ≥ 1 hold. Then, we get

P(B v ≥ t| |C v | = k) ≤ 3e 5 k 3 2m t .
Proof: The condition on ε ensures that λ = (1 + ε )n is selected such that λ/m < 1 holds. As in the proof of (Kirsch et al., 2008, Lemma 5), we consider a breath first search starting at v. We bound the number of cycles that are created by visiting a new node by a Poisson random variable in each step. The only difference is that a single edge now corresponds to a Poisson random variable with parameter λ/ 2m m , instead of λ/m 2 . Thus, we can apply (Kirsch et al., 2008, Lemma 6) with m replaced by 2m and yield the claimed result.

2

By the same reasoning as [START_REF] Devroye | Cuckoo hashing: Further analysis[END_REF], Lemma 1), we obtain the following result for the size of a component:

Lemma 7 P(|C v | > k) ≤ P(Bin(nk, 1/(2m -1)) ≥ k)
Lemmata 6 and 7 together with Chernoff's bound are sufficient to prove (2), see [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF].

Enumerating complex graphs

In this section, we review resp. establish the generating functions that enable us to count the number of cuckoo graphs of certain type resp. asymptotic approximations of these numbers. First, let us consider node and edge labeled usual, but directed graphs. Let F denote a family of such graphs. Then, the corresponding bivariate generating function is the formal power series

F (x, v) = G∈F x m(G) m(G)! v n(G) n(G)! ,
where m(G) denotes the number of nodes and n(G) the number of edges of G. However, it is usually simpler to consider an univariant generating function first. For instance, node labeled rooted trees are enumerated by the well known tree function t(x) satisfying t(x) = xe t(x) , see [START_REF] Flajolet | Analytic Combinatorics[END_REF]. Since a tree possesses exactly one node more than edges, the corresponding bivariate generating function t(x, v) satisfies

t(x, v) = t(2xv) 2v .
We thus slightly abuse notation by denoting univariate and bivariate generating function by the same letter, however the correct interpretation should be clear from the context. Similarly, we define trivariate generating functions enumerating bipartite graphs:

F (x, y, v) = G∈F x m1(G) m 1 (G)! y m2(G) m 2 (G)! v n(G) n(G)! ,
Again, we avoid using the edge-counting variable v whenever possible. Further, we make use of the notation [x m ]A(x) to extract the m-th coefficient of a power series A(x) that means

[x m ]A(x) = [x m ] k≥0 a m x m = a m .

Usual graphs

Additionally to the already mentioned function t(x) counting rooted trees, the function t(x) counting unrooted trees is well-known too. In particular, the relation

t(x) = t(x) - 1 2 t(x) 2 ,
holds, see [START_REF] Flajolet | Analytic Combinatorics[END_REF]. Using these functions, we describe the generating functions of graphs with excess r ≥ 0. Since the number of nodes is uniquely determined for all these types of graphs, we can concentrate on counting nodes. Thus univariate generating functions are sufficient, because we get the bivariate function afterwards by replacing x with 2xv and multiplying the function by an additional factor of (2v) r . However, this can only be done if self-loops and multiple edges are compensated in the original construction. We follow the approach of [START_REF] Janson | The birth of the giant component[END_REF] and assign a graph with adjacency matrix A = (a ij ) ij the compensation factor

κ(A) = i 2 aii j≥i a ij ! -1
.

In particular, the following results hold for the general multi graph model:

Lemma 8 [START_REF] Janson | The birth of the giant component[END_REF]) Assume that our graph might contain self-loops. Then, the generating function C(x) of a connected graph with exactly one cycle is given by

C(x) = k≥1 1 2k t(x) k = log 1 1 -t(x) .
Further, let E r (x) denote the generating function of graphs consisting of complex components only and having excess r, i.e. exactly r more edges than vertices. Then the relation

E r (x) = 2r d=0 e rd t(x) 2r-d (1 -t(x)) 3r-d
holds. Hereby, the constants e rd are given as

(6r -2d)!P d (r) 2 5r 3 2r-d (3r -d)!(2r -d)! where P d (r) is further defined by P d (r) = [x d ]F (x) and F (x) = 6 (4x) 3 e 4x - (4x) 2 2 -4x -1 .
Since we also consider the situation where each key possesses two different storage positions, we also require the generating functions counting graphs without self-loops.

Definition 3 Let ϑ x denote the differential operator x ∂ ∂x that corresponds to marking a node.

Lemma 9 Assume that we consider a multi graph without self-loops. Then, the generating function C(x) of a connected graph with exactly one cycle is given by

C(x) = k≥2 1 2k t(x) k = log 1 1 -t(x) - 1 2 t(x).
Further, let E r (x) denote the generating function of graphs consisting of complex components only and having excess r, i.e. exactly r more edges than vertices. These functions satisfy the differential recurrence

(r + (1 -t)ϑ x ) E r = 1 2 e -C ϑ 2 x -ϑ x e C E r-1 .
(3)

Moreover, E 0 = 1 holds, since only the empty graph is complex and has excess 0.

Note that the previously mentioned results are not explicitly given in [START_REF] Janson | The birth of the giant component[END_REF]. However, the case where both, self-loops and multiple edges are forbidden, is considered in that paper. Thus, the proof of Lemma 9 follows immediately by combining these methods and results. Finally, using the differential recursion (3) and a computer algebra system, it is easy to obtain all generating functions that are required in the next section.

Bipartite graphs

In contrast to usual graphs, only few results concerning bipartite graphs are known in the literature. However, trees and unicyclic components have been studied recently, see also [START_REF] Gimenez | On the number of bases of bicircular matroids[END_REF]:

Lemma 10 (Drmota and Kutzelnigg ( 2009)) The generating functions t 1 (x, y) resp. t 2 (x, y) of rooted bipartite trees possessing a root node of first resp. second type and the generating function of unrooted bipartite trees t(x, y) are given by t 1 (x, y) = xe t2(x,y) , t 2 (x, y) = ye t1(x,y) and t(x, y) = t 1 (x, y) + t 2 (x, y) -t 1 (x, y)t 2 (x, y).

The partial derivatives of the functions t(x, y) and t 1 (x, y) are given by

∂ ∂x t(x, y) = t 1 (x, y) x , ∂ ∂y t(x, y) = t 2 (x, y) y ,
and

∂ ∂x t 1 (x, y) = t 1 (x, y) x(1 -t 1 (x, y)t 2 (x, y)) , ∂ ∂y t 1 (x, y) = t 1 (x, y) t 2 (x, y) y(1 -t 1 (x, y)t 2 (x, y))
.

Further, the generating function of a connected bipartite graph with exactly one cycle is given by

C(x, y) = k≥1 1 2k t 1 (x, y) k t 2 (x, y) k = 1 2 log 1 1 -t 1 (x, y)t 2 (x, y) .
Concerning components with positive excess, we proceed as in [START_REF] Janson | The birth of the giant component[END_REF] and adopt the calculation to the present situation. Thereby, we make use of the following shortened notation: Definition 4 Let ϑ x denote the differential operator x ∂ ∂x that corresponds to marking a vertex of first kind. Similarly, we define the operators ϑ y and ϑ v for marking a node of second kind resp. an edge.

Further, we obtain the following result:

Lemma 11 Let E = E(x, y, v) denote the generating function for the complex part of a bipartite graph that means all its components have positive excess. Then, the following equation holds:

1 v ϑ v E = (ϑ x ϑ y C)E + (ϑ x C)(ϑ y C)E + (ϑ x t)(ϑ y E) + (ϑ x E)(ϑ y t) + (ϑ x C)(ϑ y E) + (ϑ x E)(ϑ y C) + ϑ x ϑ y E (4)
Proof: Obviously, the left hand side of our equation represents all complex bipartite graphs having a marked edge with the edge count decreased by one. Thus, the right hand side should yield all ways how the complex part can grow by one edge. In particular, the terms correspond to the following operations from left to right:

• The new edge connects two edges of an unicyclic component and thus closes a further loop in it.

• It might also join two different unicyclic components, and hence a bicyclic component arises.

• Furthermore, the new edge might attach a tree to an already complex component. There are two distinct situations, the node of first kind can belong to each of the two involved components.

• Similar to the previous case, but we select an unicyclic component instead of a tree.

• Finally, we may connect two edges belonging to the complex part.

Additionally it is straightforward to verify (4) adopting the calculations of [START_REF] Janson | The birth of the giant component[END_REF], but we skip this tedious and technical alternative proof. 2

To solve the differential equation ( 4), we transform it into a recursion formula:

Lemma 12 Let E r (x, y) denote the generating function of bipartite graphs consisting of complex components only and having excess r. These functions satisfy the partial differential recurrence

(r + (1 -t 2 )ϑ x + (1 -t 1 )ϑ y ) E r = e -C ϑ x ϑ y e C E r-1 .
Moreover, E 0 = 1 holds, since only the empty graph is complex and has excess 0.

Proof: We start rewriting (4). Using Lemma 10, we obtain

ϑ x t(x, y, v) = t 1 (xv, yv) v , ϑ y t(x, y, v) = t 2 (xv, yv) v .
Furthermore, it is straightforward to verify that

(ϑ x ϑ y C)E + (ϑ x C)(ϑ y C)E + (ϑ x C)(ϑ y E) + (ϑ x E)(ϑ y C) + ϑ x ϑ y E = e -C ϑ x ϑ y e C E
holds. Thus we get (x,y,v) ϑ x ϑ y e C(x,y,v) E(x, y, v).

1 v (ϑ v -t 1 (xv, yv)ϑ y -t 2 (xv, yv)ϑ x )E(x, y, v) = e -C
(5)

Next we partition E(x, y, v) into summands of equal excess. Thus we write

E(x, y, v) = r E r (x, y, v) = r v r E r (xv, yv).
Further, we immediately yield

ϑ x E(x, y, v) = r v r x ∂ ∂x E r (xv, yv) = r v r (ϑ x E r ) (xv, yv), (6)
and similarly

ϑ v E(x, y, v) = r rv r E r (xv, yv) + v r (ϑ x + ϑ y )E r (xv, yv) (7)
holds. Hereby (ϑ x E r )(xv, yv) means ϑ x E r (x, y) with x and y subsequently replaced by xv and yv.

Finally, we plug in ( 6) and ( 7) into ( 5), equate the coefficients of v r-1 on both sides and then set v = 1.

Thus we obtain

(r + (1 -t 2 (x, y))ϑ x + (1 -t 1 (x, y))ϑ y ) E r (x, y) = e -C(x,y) ϑ x ϑ y e C(x,y) E r-1 (x, y),
what completes the proof. 2

Solving the recursion of Lemma 12 in general seems to be out of reach, but using a computer algebra system, it is quite easy to get some results. In particular, the solutions exhibit a certain pattern, hence it is possible to write down an ansatz and compute the coefficients. Thus, we get for instance

E 1 = t 1 t 2 (4 + 3t 2 + 3t 1 + 6t 1 t 2 + 2t 1 t 2 2 + 2t 2 1 t 2 ) 24(1 -t 1 t 2 ) 3
, and

E 2 = t 1 t 2 1152(1 -t 1 t 2 ) 6 720t 2 1 t 2 + 24t 2 1 + 652t 3 1 t 2 2 + 72t 4 1 t 3 2 + 156t 4 1 t 2 2 + 156t 4 2 t 2 1 + 48 + 24t 2 2 + 201t 3 1 t 2 + 4t 5 2 t 3 1 + 688t 1 t 2 + 4t 5 1 t 3 2 + 201t 1 t 3 2 + 8t 4 1 t 4 2 + 348t 3 1 t 3 2 + 72t 4 2 t 3 1 + 652t 2 1 t 3 2 + 1218t 2 1 t 2 2 + 720t 1 t 2 2 + 96t 2 + 96t 1 .

Detailed Asymptotic Expansions

In this section, we present a generating function approach that enables us to calculate detailed asymptotic expansions of the number of cuckoo graphs satisfying ẽ(G) ≤ s. Together with the number of all cuckoo graphs, we further obtain the percentage of graphs that fulfill the very same property. Hence, the proofs follow the same idea as the analysis of the success probability given in [START_REF] Drmota | A precise analysis of cuckoo hashing[END_REF] and [START_REF] Kutzelnigg | Random Graphs and Cuckoo Hashing[END_REF].

Usual graphs

We concentrate on the case where self-loops are allowed. The second case can be treated in the same way, by just exchanging the generating functions. Thus, we obtain a similar result, however the non-zero coefficients of the asymptotic expansion are different. First, it is straightforward to count all directed node and edge labeled multi graphs possessing 2m nodes an n edges:

#G 2m,n = v n n! (e v ) 2m e 2v ( 2m 2 ) = (4m 2 ) n .
Second, we determine #G r 2m,n , the number of all graphs containing a complex part with r more edges than nodes, using the generating functions given in the previous section. In particular, each of these graphs contains 2m -n + r (unrooted) tree components. This is easy to see, because of the fact that the insertion of an edge reduces the number of tree components by one, except if it increases the excess of the complex part. Next, the graph contains a (possibly empty) set of unicyclic components. Hence we infer by elementary combinatorial constructions (see e.g. [START_REF] Flajolet | Analytic Combinatorics[END_REF]):

#G r 2m,n = (2m)! n! 2 2m-n [x 2m ] t(2x) 2m-n+r (2m -n + r)! e C(2x) E r (2x) = 2 n (2m)! n! x 2m t(x) 2m-n+r e C(x) E r (x) (2m -n + r)! .
(8) We use Cauchy's Formula to obtain an integral representation of that formula. This integral can be asymptotically evaluated using the saddle point method, see Lemma 13 that can be found in the appendix. For technical reasons, we define the ratio

ε = 1 - n m = 1 - 2αm m = 1 -2α + O(m -1 ).
Then, it turns out that the saddle point is given by x 0 = (1 -ε)e ε-1 . In particular, the result for the special case r = 0 that corresponds to an empty stash, is given in [START_REF] Drmota | A precise analysis of cuckoo hashing[END_REF] and [START_REF] Kutzelnigg | Random Graphs and Cuckoo Hashing[END_REF]. However, in the present situation, it is not sufficient to provide the second order term of the expansion only, we require several further terms. The calculation of these asymptotic expansions has been done with Maple in a semi-automatic way. In particular, we obtain

#G r 2m,n = #G 2m,n c r r (ε) m r + c r r+1 (ε) m r+1 + c r r+2 (ε) m r+2 + . . . , (9)
where the c r i (ε) depend on ε, but not on m. The first non-zero coefficient is given by

c r r (ε) = E(x 0 )t(x 0 ) r 2 r , (10)
and in particular c 0 0 (ε) = 1 holds. We conclude that the fraction of cuckoo graphs that possesses a cyclic part of excess r is given by #G r 2m,n /#G 2m,n . Then, the percentage of graphs possessing a single bicyclic component of excess one equals

#G 1 2m,n #G 2m,n = c 1 1 (ε) m + c 1 2 (ε) m 2 + O 1 m 3 = (1 -ε) 2 (5 -2ε) 48ε 3 1 m + (1 -ε)(4ε 5 -104ε 4 + 481ε 3 -727ε 2 + 1127ε -925) 2304ε 6 1 m 2 + O 1 m 3 .
Furthermore, the probability that ẽ(G) is less or equal s for a randomly selected graph G is given by

P(ẽ(G) ≤ s) = s r=0 #G r 2m,n #G 2m,n = c 0 0 (ε) + 1 r=0 c r 1 (ε) m + 2 r=0 c r 2 (ε) m 2 + • • • s r=0 c r s (ε) m s + s r=0 c r s+1 (ε) m s+1 + O 1 m s+2 .
Moreover, for 0 < i ≤ 8 we verified i r=0 c r i (ε) = 0, using our Maple worksheets (iv) . Thus, we yield for s ≤ 8

P(ẽ(G) ≤ s) = 1 + s r=0 c r s+1 (ε) m s+1 + O 1 m s+2 = 1 - c s+1 s+1 (ε) m s+1 + O 1 m s+2 .
In particular,

P(ẽ(G) ≤ 1) = 1 + 2 r=0 c r 2 (ε) m 2 = 1 - (1 -ε)(4ε 5 -32ε 4 + 97ε 3 + 149ε 2 + 959ε -1465) 4608ε 6 1 m 2 + O 1 m 3
holds. Further, we can replace ε by 1 -2α + O(m -1 ). We obtain similar results for all other s, satisfying s ≤ 8, what completes the proof of Theorem 3. Finally, we prove that the failure rate of a data structure possessing a stash of size s is in fact Θ(m -s-1 ). That is, we show that c(α, s) as defined in Theorem 2, is not equal to zero. To do so, we consider a complex component of excess s + 1, consisting of exactly two nodes connected by s + 3 edges. Clearly, the bivariate resp. univariate generating function b of such a component is given by b

(x, v) = x 2 v s+3 (s + 3)! resp. b(x) = x 2 (s + 3)! .
We further consider (8) once more, but we replace E by b and repeat the application of the saddle point method. Similarly to (10), we obtain that the probability that exactly one such component occurs in the cuckoo graph, while all other components are either trees or unicyclic, is given by b(x 0 )t(x 0 ) s+1 2 s+1 m s+1 = 0.

Since the algorithm fails in the current situation, the proof of Theorem 2 is completed.

Bipartite Graphs

In general, this proof follows the same idea as the previous one. However, things are a bit more complicated because of the bivariate generating functions that capture the bipartite structure of the cuckoo graph. Again, we start counting all graphs without restrictions to the type of their components. Let G m1,m2,n denote the set of all vertex and edge labeled bipartite multi graphs

(V 1 , V 2 , E) with |V 1 | = m 1 , |V 2 | = m 2 ,
and |E| = n. By definition, it is obvious that the number of all graphs having m nodes of each type and n edges is given by #G m,m,n = m 2n .

We proceed counting all bipartite graphs possessing a complex part of excess r. As in the univariate situation, such a graph further contains 2m -n + r unrooted tree components, and a (possibly empty) set of unicyclic components:

#G r m,m,n = (m!) 2 n![x m y m ] t(x, y) 2m-n+r (2m + n -r)! e C(x,y) E r (x, y).
An asymptotic expansion can be derived applying a double saddle point method, see Lemma 14 and [START_REF] Drmota | A precise analysis of cuckoo hashing[END_REF]. The saddle point is given by x 0 = y 0 = n m e -n/m . All calculations have again been done with Maple and we obtain an expansion as we had in (9), satisfying the same properties but the non-zero coefficients are different. Finally, the probability that the construction of a data structure requires a stash of at most s items is given by

P(ẽ(G) ≤ s) = s r=0 #G r m,m,n #G m,m,n = 1 -Θ m -s-1 ,
and we yield the claimed results. In particular, setting again ε = 1 -n/m, we get

P(ẽ(G) ≤ 1) = 1 - (ε -1) 4 (4ε 6 -52ε 5 + 305ε 4 -868ε 3 + 1358ε 2 -1120ε + 385) 288(-2 + ε) 4 ε 6 1 m 2 + O 1 m 3 .
Finally, we use the same approach as for the usual graph to construct a cuckoo graph that requires a stash of size s + 1 and occurs with probability Θ(m -s-1 ). difference. From the data given in all three tables, we additionally observe the following properties: For fixed s > 0 and m, the percentage of hash tables that demand a stash of size s increases as the load factor α increases. On the other hand, increasing m while holding α constant, decreases the expected number of items in the stash. Note that these numerical results are in good accordance with the theoretical analysis. We conclude that an additional memory of small size is sufficient to reduce the failure rate of cuckoo hashing drastically. Though, small table sizes and/or load factors close to the limit load of 0.5 demand special attention.

Summary and Conclusion

We showed that it is possible to use a stash without a complicated cycle-detection mechanism to determine an admissible key that can be placed in the stash. This is because of the fact that we have proved that it is sufficient to put the last kicked-out key in the stash, whenever an otherwise unresolvable situation occurs. The new insertion procedure thus offers better performance than the modified version required in [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF]. As a further advantage, it is possible to break up large clusters and hence speed up further insertion procedures. Further, we adopted the analysis to simplified cuckoo hashing, a variant of the original algorithm that grants both hash functions access to the whole table. Finally, we presented a method to obtain exact asymptotic expansions of the failure rate. All these results extend the original analysis given in [START_REF] Kirsch | More robust hashing: Cuckoo hashing with a stash[END_REF] and verify that this algorithm offers very interesting properties.

As future work, we suggest a detailed analysis of the partial differential recursion of the generating functions of complex bipartite graphs with positive excess. Using these results, it will be possible to study the structure of these graphs.

A Asymptotic Expansions via the Saddle Point Method

This appendix provides results that are required to infer asymptotic expansions of the coefficients of generating functions counting the number of cuckoo graphs without "bad" components. These results can be obtained using a saddle point approach, see, e.g., [START_REF] Drmota | A bivariate asymptotic expansion of coefficients of powers of generating functions[END_REF]; [START_REF] Flajolet | Analytic Combinatorics[END_REF]; [START_REF] Gardy | Some results on the asymptotic behaviour of coefficients of large powers of functions[END_REF]; [START_REF] Good | Saddle-point methods for the multinomial distribution[END_REF] for details concerning this method and [START_REF] Kutzelnigg | Random Graphs and Cuckoo Hashing[END_REF] for proofs of the lemmata at full length. Note that further coefficients of the asymptotic expansions can be calculated in the same way, but the expressions are so complicated that it does not make sense to provide them outside a computer algebra system. A maple worksheet is available on request from the author.

Lemma 13 Let f (x) and g(x) be analytic functions locally around 0 such that all coefficients [x m ]f (x) and [x m ]g(x) are non negative, f (0) = 0, and such that the "aperiodicity condition" gcd{m|[x m ]f (x) > 0} = 1 holds.

Let R be a compact interval of the positive real line that is contained in the radius of convergence of f (x) and g(x). Furthermore set

S = x f (x) ∂ ∂x f (x) : x ∈ R .
Then we have

[x m ]g(x)f (x) k = g(x 0 )f (x 0 ) k x m 0 √ 2πkκ 2 1 + H 24κ 3 2 1 k + O 1 k 2 ,
uniformly for m/k ∈ S, where x 0 is uniquely determined by

m k = x 0 f (x 0 ) f (x 0 ) .
and the constants κ 2 and H are given in the following way. Let κ i and κ i be the cummulants

κ i = ∂ i ∂u i log f (x 0 e u ) u=0 , κ i = ∂ i ∂u i log g(x 0 e u ) u=0
.

Then H is given by 12κ 2 κ 3 κ 1 + 3κ 2 κ 4 -12κ 2 2 κ 2 1 -12κ 2 2 κ 2 -5κ 2 3 . Lemma 14 Let f (x, y) and g(x, y) be analytic functions locally around (x, y) = (0, 0) such that all coefficients [x m1 y m2 ]f (x, y) and [x m1 y m2 ]g(x, y) are non negative and that there exists M such that all indices (m 1 , m 2 ) with m 1 , m 2 ≥ M can be represented as a finite linear combination of the set {(m 1 , m 2 )|[x m1 y m2 ]f (x, y) > 0} with positive integers as coefficients.

Let R 1 and R 2 be compact intervals of the positive real line such that R = R 1 × R 2 is contained in the regions of convergence of f (x, y) and g(x, y). Furthermore set and the constants ∆ and H are given in the following way: Let κ ij and κ ij be the cummulants

κ ij = ∂ i ∂u i
∂ j ∂v j log f (x 0 e u , y 0 e v ) (0,0)

, κ ij = ∂ i ∂u i
∂ j ∂v j log g(x 0 e u , y 0 e v ) (0,0)

.

Then ∆ = κ 20 κ 02 -κ 2 11 holds and H is given by

H = α + β + β +

  y) : (x, y) ∈ R .Then we have[x m1 y m2 ]g(x, y)f (x, y) k = g(x 0 , y 0 )f (x 0 , y 0 ) for (m 1 /k, m 2 /k) ∈ S, where x 0 and y 0 are uniquely determined by

  and only if the removal of that edge does not create a new tree.Proof: Denote the component that contains g by H. First, if g is contained in a cycle, e(H \g) = e(H)-1 holds. Thus ẽ decreases by one, except if the excess of H equals 0. But in the latter case, H \ g is a new tree. Second, if g is not contained in a cycle, it is a bridge connecting H 1 and H 2 . Hence, the relation e(H) = e(H 1 ) + e(H 2 ) + 1 is satisfied. If both H 1 and H 2 are trees, H is also a tree and none of these components influences the calculation of ẽ. If only one component is a tree, say H 2 , e(H) = e(H 1 ) holds and ẽ remains again unchanged. However, if both H 1 and H 2 posses nonnegative excess, we obtain ẽ

  Tab. 3: Stash sizes required for simplified cuckoo hashing possessing a tables of size 2m and holding αm keys. The data structure is implemented such that both storage locations of a key are surely different (i.e. without self-loops).

	The results are measured over a sample size of 10 7 .
		stash:	0	1	2	3	4	5	6	7	8 9 10 >
	m = 500	α = 0.40: 9909928 α = 0.45: 9641228 314948 85673 α = 0.47: 9365150 523756 α = 0.48: 9154452 670044 135219 30953 7184 1655 377 88 20 7 4124 255 19 1 37399 5408 851 133 27 4 0 2 89367 17283 3550 702 149 33 5 4	1 1
	m = 5•10 3	α = 0.40: 9986083 α = 0.45: 9893396 100366 13770 α = 0.47: 9695785 266723 α = 0.48: 9467420 439340	144 5675 31588 73211 15388 3523 3 501 53 4847 846	8 174 838 210 55 10 4 1 31 6	1
	m = 5•10 4	α = 0.40: 9998537 α = 0.45: 9984860 α = 0.47: 9933804 α = 0.48: 9827037 157866 1461 14972 63485	2 167 2511 13249	1 186 1599	12 206	2 34	9

  γκ 10 + γκ 01 + δκ 10 κ 01 + ηκ 2 10 + ηκ 2 01 + 4ηκ 20 + 4ηκ 02 + 4δκ 11 , where α = 54κ 21 κ 11 κ 12 κ 20 κ 02 + 6κ 22 κ 20 κ 02 κ 2 11 -12κ 22 κ 4 11 + 4κ 03 κ 3 11 κ 30 + 36κ 21 κ 3 11 κ 12 + 6κ 22 κ 2 20 κ 2 02 + 6κ 03 κ 11 κ 30 κ 20 κ 02 , β = -5κ 3 02 κ 2 30 + 30κ 2 02 κ 30 κ 11 κ 21 -24κ 02 κ 30 κ 12 κ 2 11 -6κ 2 02 κ 30 κ 12 κ 20 -12κ 11 κ 2 02 κ 31 κ 20 -36κ 02 κ 2 21 κ 2 11 -9κ 2 02 κ 2 21 κ 20 + 3κ 3 02 κ 40 κ 20 -3κ 2 02 κ 40 κ 2 11 + 12κ 3 11 κ 02 κ 31 , γ = 12∆ κ 2 02 κ 30 -κ 11 κ 20 κ 03 -3κ 21 κ 11 κ 02 + κ 12 κ 2 11 + κ 12 (κ 02 κ 20 + κ 2 11 ) , δ = 24∆(κ 11 κ 20 κ 02 -κ 3 11 ), η = 12∆(κ 02 κ 2 11 -κ 2 02 κ 20 ), and ˆindicates to replace all functions of type κ ij by κ ji .

(i) The load factor is defined as the quotient of the number of keys stored in the data structure and the total number of storage positions.

(iv) Note that we conjecture a similar result for all further i. Moreover, for the situation of Theorem 2, this is implied by (2).

Acknowledgements

The author would like to thank Michael Drmota for helpful suggestions on this paper. Further, I am grateful for the valueable comments received during the review process.

The author was supported by the EU FP6-NEST-Adventure Programme, Contract number 028875 (NEMO), and by the Austrian Science Foundation FWF, project S9604.

1365-8050

Experimental Results

Finally, we provide some numerical results for both variants of cuckoo hashing. Thereby, we use a pseudo random generator to obtain the hash values. The stash is implemented as a linked list providing potential unlimited additional memory. Hence, the construction can never fail, but unsuccessful search operations require the inspection of all elements contained in the stash. For practical implementation on standard hardware, we suggest to implement the stash as a common hash table.

Tables 8,8, and 8 depict the required stash sizes for the standard resp. simplified algorithm. Hereby, the latter algorithm is implemented in both variants, i.e. with and without self-loops. As expected, we observe that the implementation without self-loops offers better performance, but the difference is small. Furthermore, the standard data structure exhibits an even better behavior, however there is again no wide


Miklós Bóna

The absence of a pattern and the occurrences of another

Keywords:

Following a question of J. Cooper, we study the expected number of occurrences of a given permutation pattern q in permutations that avoid another given pattern r. In some cases, we find the pattern that occurs least often, (resp. most often) in all r-avoiding permutations. We also prove a few exact enumeration formulae, some of which are surprising.

Introduction

Let q = q 1 q 2 . . . q k be a permutation in the symmetric group S k . We say that the permutation p = p 1 p 2 . . . p n ∈ S n contains a q-pattern if and only if there is a subsequence p i1 p i2 . . . p i k of p whose elements are in the same relative order as those in q, that is, p it < p iu if and only if q t < q u whenever 1 ≤ t, u ≤ k. If p does not contain q, then we say that p avoids q. For example, 41523 contains exactly two occurrences of the pattern 132, namely 152 and 153, while 34512 avoids 132. See Chapter 14 of [START_REF] Bóna | A Walk Through Combinatorics[END_REF] for an introduction to pattern avoiding permutations, and Chapters 4 and 5 of [START_REF] Bóna | Combinatorics of Permutations[END_REF] for a somewhat more detailed treatment. A recent collection of research articles can be found in [START_REF] Ruskuc | Patterns in Permutations[END_REF].

It is straightforward to compute, using the linear property of expectation, that the average number of q-patterns in a randomly selected permutation of length n is 1 k! n k , where k is the length of q. Joshua Cooper [START_REF] Cooper | Combinatorial Problems I like, internet resource[END_REF] has raised the following interesting family of questions. Let r be a given permutation pattern. What can be said about the average number of occurrences of q in a randomly selected r-avoiding permutation?

In this paper, we study this family of questions in the case when r = 132. We prove the perhaps surprising result that among patterns of a fixed length k, it is the increasing pattern 12 • • • k that occurs least often and it is the decreasing pattern k(k -1) • • • 1 that occurs most often in a randomly selected 132avoiding permutation. While pattern avoiding permutations in general has been a very popular topic in the last fifteen years, this paper joins a rather short list of articles ( [START_REF] Bóna | Where the monotone pattern (mostly) rules[END_REF] is an example) in which expectations of the number of occurrences of a pattern are computed.

Miklós Bóna

Preliminaries

The structure of 132-avoiding permutations is well understood. If p = p 1 p 2 • • • p n is such a permutation, and p i = n, then p t > p u must hold for all pairs (t, u) satisfying t < i < u. In other words, all entries on n Fig. 1: In a 132-avoiding permutation, all entries preceding the maximal entry are larger than entries following the maximal entry.

the left of the entry n must be larger than all entries of the right of n. Indeed, if this does not happen, then p t np u is a 132-pattern. This property is so central to the work carried out in this paper that we illustrate it by Figure 2.

Therefore, if C n denotes the number of 132-avoiding permutations of length n, then the numbers C n satisfy the recurrence relation

C n = n i=1 C i-1 C n-i , (1)
with C 0 = 1. Hence the numbers C n are identical to the famous Catalan numbers C n = 2n n /(n+1). See Chapter 6 of Enumerative Combinatorics [START_REF] Stanley | Enumerative Combinatorics[END_REF] for a wealth of information on Catalan numbers.

It follows from the structural property described in the first paragraph of this section that a 132-avoiding permutation either ends in its largest entry, or it is decomposable, that is, it can be cut into two parts so that every entry that precedes that cut is larger than every entry that follows that cut. Indeed, if the maximal entry n is not in the rightmost position, then one can cut the permutation immediately after n to obtain such a cut. Note that there may be additional ways to cut the same permutation. (We mention that some authors use a different definition of decomposable permutations, one that could be called the dual of this one, but the present definition suits the purposes of this paper better.)

Example 1. The permutation 76834512 is decomposable. One possible cut is 768|34512, and another one is 768345|12.

This relatively simple structure of 132-avoiding permutations enables us to give an exhaustive list of the ways in which a 132-avoiding permutation can contain a given pattern.

Fact 1. If the 132-avoiding permutation p of length n contains a copy Q of the pattern q of length k, then one of the following holds. (Note that q itself must be 132-avoiding; otherwise p clearly avoids q.) 1. If q is not decomposable, that is, if q ends in its largest entry, then (a) either all of Q must be on the left of n, (b) or all of Q must be on the right of n, (c) or Q must end in n.

For instance, if q = 123, then in p = 678952134, the subsequence 678 precedes n = 9, the subsequence 679 ends in 9, and the subsequence 134 follows 9.

2. If q is decomposable, that is, when q does not end in its largest entry, and q does not start with its largest entry, then (a) either all of Q is on the left of n, (b) or all of Q is on the right of n, (c) or the part of Q that precedes a given cut is on the left of n and the part of Q the follows that cut is on the right of n, (d) or the part of Q preceding k is on the left of n, the part of Q following k is on the right of n, and the maximal entry k of Q coincides with n.

For instance, if q = 231, then in p = 786923451, the subsequence 786 precedes 9, the subsequence 241 follows 9, the subsequence 785 has its entries 7 and 8 before 9 and its entry 5 after 9 (corresponding to the cut 23|1), and the subsequence 895 starts before 9, uses 9, and ends after 9.

3. If q is decomposable and q starts with its largest entry k, then (a) either all of Q is on the left of n, (b) or all of Q is on the right of n, (c) or the part of Q that precedes a given cut is on the left of n and the part of Q that follows that cut is on the right of n, or (d) Q starts with n, and the rest of Q is on the right of n.

Increasing Patterns

Before proving that among all patterns of length k, it is the increasing pattern 12 • • • k that occurs least often in 132-avoiding permutations, we prove a few general facts about the total number of increasing patterns in these permutations.

A formula for increasing patterns

Let a n,k be the total number of 12 • • • k-patterns in all C n permutations of length n that avoid 132. So for instance, a 2,1 = 4, a 3,1 = 15, and a 2,2 = 1.

Our goal in this subsection is to provide an explicit formula for the generating function A k (x) = n a n,k x n . We will use the well-known (see for instance Chapter 14 of [START_REF] Bóna | A Walk Through Combinatorics[END_REF]) explicit formula for the generating function of the Catalan numbers,

C(x) = n≥0 C n x n = 1 - √ 1 -4x 2x .
We will prove the following theorem.

Theorem 1. We have

A 1 (x) = n≥1 nC n x n = n≥1 2n n x n - n≥1 C n x n = 1 √ 1 -4x - 1 - √ 1 -4x 2x . (2)
Furthermore, for all positive integers k ≥ 2, we have

A k (x) = A 1 (x) xC(x) 1 -2xC(x) k-1 = A 1 (x) 1 2 √ 1 -4x - 1 2 k-1 (3) = A 1 (x)F k-1 (x).

Miklós Bóna

Proof: For k = 1, the claim is obvious, since an increasing subsequence of length one is just an entry of a permutation. For larger k, an increasing subsequence of length k is an indecomposable pattern. Hence the ways in which it can occur in the 132-avoiding permutation p are listed in Case (1) of Fact 1. This leads to the recurrence relations

a n,k = 2 n i=1 a i-1,k C n-i + n i=1 a i-1,k-1 C n-i ,
or in terms of generating functions,

A k (x) = 2xA k (x)C(x) + xA k-1 (x)C(x) (4)
= A k-1 (x) xC(x) 1 -2xC(x) , (5)
and our claim follows by induction on k.

Note that in particular, (3) implies that for 1 ≤ k < l we have

A k (x)A l (x) = A k+1 (x)A l-1 (x). (6)

Why the Increasing Pattern is Minimal

For a given pattern q, let t n (q) denote the number of all occurrences of the pattern q in all 132-avoiding permutations of length n. So, in particular, if q is the increasing pattern 12

• • • k, then t n (q) = a n,k .
The main result of this section is the following theorem, which shows that no pattern of a given length occurs less often in the set of 132-avoiding permutations than the increasing pattern of that length.

Theorem 2. Let q be any pattern of length k. Then for all positive integers n, we have t q (n) ≥ a n,k .

Before proving the theorem, we need to introduce some simple machinery to simplify notation. Definition 1. Let G(x) = n≥0 g n x n and H(x) = n≥0 h n x n be two power series. We say that G(x) ≤ H(x) if g n ≤ h n for all n ≥ 0.

Proposition 1. Let G(x), H(x) and W (x) be three power series with non-negative real coefficients so that G

(x) ≤ H(x) holds. Then G(x)W (x) ≤ H(x)W (x).
Proof:

The coefficient of x n in H(x)W (x) -G(x)W (x) is n i=0 (h i -g i )w n-i ,
which is a sum of non-negative real numbers, and is hence non-negative.

We can now return to the proof of Theorem 2.

Proof of Theorem 2:

We prove the statement by induction on k. For k = 1, the statement is obvious. Now let us assume that the statement is true for all positive integers less than k, and prove it for k. We distinguish three cases. Each of these cases will be handled by analyzing recurrence relations, which Fig. 2: Three types of patterns that we compare. may sometimes seem somewhat cumbersome. Therefore, at the beginning of each case, we will give an intuitive description of that case.

In a permutation p = p 1 p 2 • • • p n , we say that i is a descent if p i > p i+1 . Otherwise, we say that i is an ascent.

An overview of the cases is as follows. First, we treat patterns ending in their largest entry. Then we treat patterns that contain only one descent, say in position j. Finally, we treat all remaining patterns, comparing the patterns whose first descent is in position j to the pattern whose only descent is in position j. See Figure 3.2 for an illustration.

Case 1: When q ends in its largest entry k. Let q be the pattern obtained from q by removing the largest entry k from the end of q. We then show that q is more frequent than 12 • • • k by showing that q can be contained in a 132-avoiding permutation in the same ways as 12 • • • k, and then using the induction hypothesis. In other words, the difference between a n,k and t n (q) is caused by whatever happens before the last position of these patterns.

The possible ways in which q can occur in a 132-avoiding permutation p are listed in Case (1) of Fact 1. Therefore, we have the recurrence relation

t n (q) = 2 n i=1 t i-1 (q)C n-i + n i=1 t i-1 (q )C n-i ,
leading to the generating function identities

T q (x) = 2xC(x)T q (x) + xC(x)T q (x), T q (x) = T q (x) xC(x) 1 -2xC(x) . ( 7
)
Comparing formulae ( 4) and (7), we see that T q (x) is obtained from T q (x) by the same operation as A k (x) is obtained from A k-1 (x), namely by a multiplication by the power series

F (x) = xC(x) 1-2xC(x) . As [x n ]T q (x) = t n (q ) ≥ a n,k-1 = [x n ]A k-1 (x)
by our induction hypothesis, and

F (x) = n≥1 2n-1 n-1
x n has non-negative coefficients, our claim is immediate by Proposition 1.

Case 2: Let us now consider the case in which q does not end in its largest entry k, and the only descent of q is in the position in which k occurs. We will subsequently see that all remaining cases will easily reduce to this one. Let us say that k is in the jth position in q, with j < k. That is,

q = q k,j = (k -j + 1)(k -j + 2) • • • k123(k -j).
For instance, q 7,3 = 5671234. We will show that t n (q k,j ) ≥ t n (12

• • • k) = a n,k . (8)
The main idea is the following. The pattern q k,j looks very similar to the increasing pattern, hence the ways in which q k,j can be contained in a 132-avoiding permutation are also similar to the ways in which the increasing pattern can. So the numbers t n (q k,j ) and a n,k satisfy very similar recurrence relations, and where they differ, they differ in the way we predicted.

Subcase 2.1: Let us assume first that j = 1, that is, that k is not in the first position in q k,j . As q k,j is decomposable by a cut after the jth position, the ways in which q k,j can be contained in a 132-avoiding permutation are described in Case (2) of Fact 1. That list leads to the recurrence relation

t n (q k,j ) = 2 n i=1 C i-1 t n-i (q k,j ) + n i=1 a i-1,j a n-i,k-j (9)
+ n i=1 a i-1,j-1 a n-i,k-j ,
and hence

T q k,j (x) = 2xC(x)T q k,j (x) + xA j (x)A k-j (x) + xA j-1 (x)A k-j (x), T q k,j (x) = xA k-j (x)(A j (x) + A j-1 (x)) 1 -2xC(x) . (10)
We need to show that T q k,j (x) ≥ A k (x). Comparing formulae ( 3) and ( 10), the preceding inequality is equivalent to

xA k-j (x)(A j (x) + A j-1 (x)) 1 -2xC(x) ≥ A 1 (x)F (x) k-1 , or x 1 -2xC(x) A 1 (x) 2 (F (x) k-3 + F (x) k-2 ) ≥ A 1 (x)F (x) k-1 . (11)
Inequality (11) will be proved if we can show that

x 1 -2xC(x) A 1 (x)(1 + F (x)) ≥ F (x) 2 . ( 12
)
Indeed, (12) implies (11) by Proposition 1, choosing W (x) = F k-3 (x). On the other hand, (12) is equivalent to

x 2(1 -4x) 3/2 + x 2(1 -4x) - 1 4(1 -4x) + 1 4 ≥ 1 4(1 -4x) - 1 2 √ 1 -4x + 1 4 , x 2(1 -4x) 3/2 + x -1 2(1 -4x) + 1 2 √ 1 -4x ≥ 0.
The coefficient of x n on the left-hand side is 0 if n = 0, n = 1, or n = 2, and is

b n = 2n-3 n-2 (2n-1)-3•2 2n-3 + 2n-1 n-1 if n ≥ 3.
If we replace n by n+1, the negative summand in the above expression of b n , that is, 3 • 2 2n-3 , grows fourfold, whereas a routine computation shows that the sum of the two positive terms grows 4n 2 +14n+6 n 2 +3n+2fold. This fraction is larger than 4 for all n ≥ 3, showing that b n ≥ 0 for all n, and our claim is proved. Subcase 2.2: If j = 1, then a minor modification is necessary since if a copy of q contains n, then it has to start with n. Hence formula (9) becomes

t n (q k,1 ) = 2 n i=1 C i-1 t n-i (q k,1 ) + n i=1 a i-1,1 a n-i,k-1 + n i=1 C i-1 a n-i,k-1 .
So only the last sum is different from what it was in (9). This leads to the generating function identities

T q k,1 (x) = 2xC(x)T q k,1 (x) + xA k-1 (x)(A 1 (x) + C(x)), T q k,1 (x) = xA k-1 (x)(A 1 (x) + C(x)) 1 -2xC(x) . (13)
Comparing formulae ( 4) and (13), the inequality

A k (x) ≤ T q k,1 (x) is now proved by Proposition 1, since C(x) ≤ A 1 (x) + C(x).
Case 3: Finally, there is the case when k is in the jth position of q for some j < k, but j is not the only descent of q. We claim that then copies of q occur even more frequently than copies of q k,j , roughly because even in segments where q k,j is increasing, q is not.

That is, we will prove that t n (q k,j ) ≤ t n (q).

This, together with (8) will complete the proof of Theorem 2.

As q is decomposable by a cut after its jth position, the ways in which q can be contained in a 132-avoiding permutation are described in Case (2) of Fact 1. Let q <1> denote the pattern formed by the first j entries of q, and let q <2> be the pattern formed by the remaining k -j entries of q.

Then we have the recurrence relation

t n (q) ≥ 2 n i=1 C i-1 t n-i (q) + n i=1 t i-1 (q <1> )t n-i (q <2> ) + n i=1 t i-1 (q <1 > )t n-i (q <2> ).
Here q <1 > is the pattern obtained from q <1> by removing its last (and also largest) entry. Note that t n (q) is at least as large as the right-hand side, and not necessarily equal to it. That is because, unlike q k,j , the pattern q may be decomposable by other cuts, in addition to the cut after its jth entry. The existence of such cuts would add extra summands to the right-hand side.

Miklós Bóna

The last displayed inequality leads to the generating function inequalities

T q (x) ≥ 2T q (x)xC(x) + xT q <1> (x)T q <2> (x) + xT q <1 > (x)T q <2> (x), T q (x)(1 -2xC(x)) ≥ xT q 1 (x)T q 2 (x) + xT q <1 > (x)T q <2> (x).
Note that as 1/(1 -2xC(x)) = 1/ √ 1 -4x = n≥0 2n n x n has non-negative coefficients, the last displayed inequality remains true if we multiply both sides by 1/(1 -2xC(x)). This leads to the inequality

T q (x) ≥ xT q <2> (x)(T q <1> + T q <1 > (x)) 1 -2xC(x) . ( 15
)
We can now compare formulae (10) and ( 15). We see that by our induction hypothesis, each factor on the right-hand side of (15) is at least as large as the corresponding factor on the right-hand side of (10). That is, xT q <2> (x) ≥ xA k-j (x), since q <2> is a pattern of length k -j, and

T q <1> + T q <1 > (x) ≥ A k (x) + A k-1 (x)
by a summand-wise comparison. Hence, by Proposition 1, we have that T q (x) ≥ T q k,j (x).

We have considered all cases, and proved our claim in each of them, hence the proof of Theorem 2 is complete.

Decreasing Patterns

In this section we prove that the decreasing pattern k(k -1) • • • 21 occurs more frequently in 132-avoiding permutations than any other pattern of length k. The structure of the proof will be very similar to that of the minimality of the increasing pattern, but there will be more technical difficulties.

General facts about decreasing patterns

Let d n,k denote the number of decreasing subsequences of length k in all 132-avoiding permutations of length n. Then we have

d n,1 = a n,1 = nC n = n n + 1 2n n .
For larger values of k, consider the set of all C n permutations of length n that avoid 132. In that set, for every 1 ≤ j ≤ k -1, there are

n i=1 d i-1,j d n-i,k-j copies of k(k -1) • • • 1 in
which the first j entries are on the left of n, and the last k -j entries are on the right of n. (The index i denotes the position of the entry n in a permutation of length n.) In addition, there are

n i=1 C i-1 d n,k-1 copies of k(k -1) • • • 1 that
start with the entry n. Finally, there are the

2 n i=1 C i-1 d n-i,k copies of k(k -1) • • • 1 that
are either entirely on the left of n, or entirely on the right of n. This leads to the recurrence relation

d n,k = k-1 j=1 n i=1 d i-1,j d n-i,k-j + n i=1 C i-1 d n,k-1 + 2 n i=1 C i-1 d n-i,k (16)
and the generating function identities

D k (x) = 2xC(x)D k (x) + xC(x)D k-1 (x) + k-1 j=1 xD j (x)D k-j (x), D k (x) = xC(x)D k-1 (x) + k-1 j=1 xD j (x)D k-j (x) 1 -2xC(x) . ( 17
)
The following corollary provides an estimate for the "growth" of the power series D k (x). It is worth comparing this result with Theorem 1.

Corollary 1. We have

D 2 (x) = xD 1 (x) (1 -4x) , ( 18
)
and

D k (x) ≥ xD k-1 (x) (1 -4x) ( 19
)
for k ≥ 3.

Proof:

The first displayed identity (the special case of k = 2) immediately follows from (17

) if we recall that 1 -2xC(x) = √ 1 -4x and that D 1 (x) + C(x) = n≥0 2n n x n = 1 √ 1-4x
. The general formula (19) follows from (17) if we remove all summands from the right-hand side except for xC(x)D k-1 (x) and xD 1 (x)D k-1 , (we can do this since all the removed terms have non-negative coefficients), and then again, we recall that

D 1 (x) + C(x) = 1 √ 1-4x .
The following lemma is a natural counterpart of its much simpler analogue [START_REF] Stanley | Enumerative Combinatorics[END_REF]. It shows that the sequence of power series D 1 (x), D 2 (x), • • • is log-convex in a certain sense.

Lemma 1. For all positive integers 2 ≤ a ≤ b we have

D a (x)D b (x) ≤ D a-1 (x)D b+1 (x).
Proof: Induction on a + b. The smallest value of a + b for which the statement is not trivial is 4. The non-trivial statement then is that D 2 (x) 2 ≤ D 1 (x)D 3 (x). By (18), this is equivalent to

D 1 (x) 2 x 2 (1-4x) 2 ≤ D 1 (x)D 3 (x).
In order to prove the latter, it suffices to show that

D 1 (x) x 2 (1 -4x) 2 ≤ D 3 (x),
and that is immediate by (19). Now let us assume that the statement holds for a + b = m -1 and prove it for a + b = m. By (17), it suffices to show that

D a (x)C(x)D b-1 (x) + b-1 j=1 D a (x)D j (x)D b-j (x) ≤ Miklós Bóna ≤ D a-1 C(x)D b (x) + b j=1 D a-1 (x)D j (x)D b+1-j (x).
Note that the right-hand side has one more summand than the left-hand side. Now we carry out a series of pairwise comparisons. First, for the two terms preceding the summation signs, we have that

D a (x)C(x)D b-1 (x) ≤ D a-1 (x)C(x)D b (x) since C(x)
has non-negative coefficients, and by our induction hypothesis, D a (x)D b-1 (x) ≤ D a-1 (x)D b (x). For the terms after the summation signs, for j < a, we have that

D a (x)D j (x)D b-j (x) ≤ D a-1 (x)D j (x)D b+1-j (x)
since our induction hypothesis implies that

D a (x)D b-j (x) ≤ D a-1 (x)D b+1-j (x).
The induction hypothesis applies since a + b -j < a + b.

For a ≤ j ≤ b -1, we claim that D a (x)D j (x)D b-j (x) ≤ D a-1 (x)D j+1 (x)D b-j (x).
(That is, we skip one summand, and we compare the jth summand of the left-hand side to the (j + 1)st summand to the right-hand side.) Indeed, our induction hypothesis implies that

D a (x)D j (x) ≤ D a-1 (x)D j+1 (x).
The induction hypothesis applies since a + j < a + b. Finally, we point out that each summand of the left-hand side was injectively associated to a weakly larger summand of the right-hand side. This proves our claim.

Why the decreasing pattern is maximal

Now we are in a position to state and prove the main result of this section. Theorem 3. Let q be a pattern of length k. Then the inequality t n (q) ≤ d n,k holds.

Proof: We prove the statement by induction on k and n. We know that the statement holds for k = 1 and it is routine to verify it for k = 2. Let us now assume that it is true for all patterns shorter than k. Let us further assume that for patterns of length k, the statement holds for all permutations shorter than n. (The initial cases of n < k are obvious.) Let us now prove that the statement hold for permutations of length n, and patterns of length k.

Again, our proof proceeds by cases. We first handle patterns that start with their largest entry, then patterns which contain only one ascent, in position j. Finally, we cover the remaining cases, comparing patterns whose first ascent is in position j to the pattern whose only ascent is in position j. See Figure 4.2 for an illustration of some of these cases.

Case 1: Let us first consider the case when q starts with its largest entry k. In this case, simply use the fact that the pattern obtained from q by removing its first entry occurs less often than the decreasing pattern k(k -1) • • • 21, and it is decomposable by no more cuts than k(k -1) • • • 21.

In this case, q is decomposable since it can be cut right after its first entry. Let us say that q is decomposable with v distinct cuts, and let q 1,f and q 1,b denote the patterns before and after the first cut, let q 2,f and q 2,b denote the patterns before and after the second cut, and so on, up to q v,f and q v,b for the patterns on the two sides of the last cut. (The letters f and b stand for "front" and "back".)

Note that the total length of q j,f and q j,b is always k for every j, and that |q

1,f | = 1 and |q 1,b | = k -1.
Then we have the recurrence relation

t n (q) = v j=1 n i=1 t i-1 (q j,f )t n-i (q j,b ) + n i=1 C i-1 t n-i (q 1,b ) + 2 n i=1 C i-1 t n-i (q). (20)
It is now straightforward to compare d n,k and t n (q) by comparing the corresponding summands of recurrence relations ( 16) and ( 20). Let us first compare the two double sums. In those sums, j indexes the cuts of the respective patterns. As the decreasing pattern of length k has k -1 cuts, j ranges from 1 to k -1 in (16). In (20), j ranges from 1 to v, where v ≤ k -1 is the number of cuts that q has. So the first double sum has more terms. We also claim that even the terms that the second double sum does have are smaller than the corresponding terms in the first double sum.

Indeed, if |q j,f | = y and |q j,b | = k -y, then t i-1 (q j,f ) ≤ d i-1,y and t n-i (q j,b ) ≤ d n-i,k-y by our induction hypothesis, so

t i-1 (q j,f )t n-i (q j,b ) ≤ d i-1,y d n-i,k-y .
Comparing the second sums of ( 16) and ( 20) is even simpler. Their summands agree in the term C i-1 , and by our induction hypothesis, we know that t n-i (q 1,b ) ≤ d n-i,k-1 . Finally, comparing the third sums of ( 16) and (20) we use the fact that n -i < n, so by our induction hypothesis, t n-i (q) < d n-i,k .

Case 2: When q has only one ascent and q does not start with its largest entry k. Just as in the previous section, this is the heart of the proof. The remaining cases will easily reduce to this one. Let q k,h be the pattern of length k that avoids 132 and has only one ascent, in position h. As q does not start in its largest entry k, this means that k must be the (h + 1)st entry of q. That is,

q k,h = (k -1) • • • (k -h)k(k -h -1) • • • 321.
For instance q 5,2 = 43521.

The difficulty of this case is that there is a way in which q k,h can be contained in a 132-avoiding permutation in which k(k -1) • • • 21 cannot, namely by having h entries on the left of n and k -h -1 entries on the right of n. As we will see, the ways in which the decreasing pattern can be contained in such a permutation and q k,h cannot are more prevalent, but that is not obvious. We will need Lemma 1 to prove that fact.

The structure of q k,h is somewhat similar to that of the decreasing pattern. That is, q k,h can be cut after each entry starting with k (in position h + 1). Cutting immediately after position j (with j ≥ h + 1) will result in the two patterns q j,h and the decreasing pattern of length k -j. This leads to the recurrence relation

t n (q k,h ) = k-1 j=h+1 n i=1 t i-1 (q j,h )d n-i,k-j + n i=1 d i-1,h d n-i,k-h-1 +2 n i=1 C i-1 t n-i (q k,h ). ( 21
)
We can carry out a pairwise comparison of corresponding sums in formulae ( 16) and ( 21). This is easiest for the third sums in those two formulae: indeed, as n -i < n, our induction hypothesis implies that t n-i (q k,h ) ≤ d n-i,k for all k, i, and h, so the third sum appearing in ( 16) is larger than the third sum appearing in (21).

As far as the double sums are concerned, for j = h + 1, h + 2, • • • , k -1, our induction hypothesis implies that t i-1 (q j,h ) ≤ d i-1,j . Therefore, each term of the double sum of ( 21) is at most as large as the corresponding term of (16).

Therefore, the claim t n (q k,h ) ≤ d n,k will be proved if we can show that the remaining sum in ( 21) is less than the remaining sums in (16), that is, that

n i=1 d i-1,h d n-i,k-h-1 ≤ h j=1 n i=1 d j,i-1 d n-i,k-j + n i=1 C i-1 d n-i,k-1 .
We show the stronger statement that the above inequality remains true even if we remove all summands from the double sum in which j = 1. (Note that as k is not in the first position of q, we know that h -1 ≥ 1, so this will leave a non-empty set of summands.) In other words, we claim that

n i=1 d i-1,h d n-i,k-h-1 ≤ n i=1 d i-1,1 d n-i,k-1 + n i=1 C i-1 d n,k-1 .
This is equivalent to the generating function inequalities

xD h (x)D k-h-1 (x) ≤ xD 1 (x)D k-1 (x) + xC(x)D k-1 (x). D h (x)D k-h-1 (x) ≤ D k-1 (x)(1 -4x) -1/2 .
By Lemma 1, we know that D

h (x)D k-h-1 (x) ≤ D 1 (x)D k-2 (x), so it suffices to prove that D 1 (x)D k-2 (x) ≤ D k-1 (x)(1 -4x) -1/2 .
By Corollary 1, we know that x 1-4x D k-2 (x) ≤ D k-1 (x), so our claim will be proved if we can show that D 1 (x) ≤ x (1 -4x) x (1-4x) 3/2 = (2n -1) 2n-2 n-1 . A routine computation shows that the latter is larger as soon as 2 < n + 1, or 1 < n. Case 3: Finally, we consider the case when q has more than one ascent, and q does not start with its maximal entry. Let us assume that the maximal entry k of q is in the hth position. We will show that then t n (q) ≤ t n (q k,h ). The main idea behind the proof is that q k,h is decomposable at every place where q is, and after decomposition, its parts are close to the decreasing pattern.

Let us inductively assume that we know the statement t n (q) ≤ t n (q k,h ) for all patterns shorter than k.

The set of positions after which q can be cut is a subset of the set of positions after which q k,h can be cut. Just as in Case (1), let us say that q is decomposable with v distinct cuts, and let q 1,f and q 1,b denote the patterns before and after the first cut, let q 2,f and q 2,b denote the patterns before and after the second cut, and so on, up to q v,f and q v,b for the patterns on the two sides of the last cut. Note that |q 1,f | = h and |q 1,b | = k -h.

Then, similarly to Case (1), we have the recurrence relation

t n (q) = v j=1 n i=1
t i-1 (q j,f )t n-i (q j,b ) +

n i=1 t i-1 (q 1,f )t n-i (q 1,b ) + 2 n i=1 C i-1 t n-i (q), (22)
where q 1,f is the pattern q 1,f with its last (and largest) entry removed.

The inequality t n (q) ≤ t n (q k,h ) is now obvious by pairwise comparing the three summands in (21) and (22), and using the induction hypotheses. (In particular, when comparing the first summands, we use the fact that if |q j,h | = |q j,f |, then t i-1 (q j,h ) ≥ t i-1 (q j,h ) by the induction hypothesis made in this case. Recall that we assumed that for patterns q shorter than k, it is true that t n (q) ≤ t n (q |q|,h ), where h is the first ascent of q.)

Asymptotic Enumeration

Theorem 1 provides an explicit formula for A 2 (x). ¿From that formula, it is routine to deduce that

a n,2 = 2 2n-1 - 1 4 2n + 2 n + 1 - n 2n + 1 2n n ( 23
)
for n ≥ 1.

Similarly, an explicit formula for D 2 (x) can be obtained by setting k = 2 in (17). That is,

D 2 (x) = xC(x)D 1 (x) + xD 1 (x)D 1 (x) 1 -2xC(x) = x (1 -4x) 3/2 - 1 2(1 -4x) + 1 2 √ 1 -4x . (24)

Fig. 3 :

 3 Fig. 3: Three kinds of patterns we compare.

3 / 2 .

 32 The last displayed inequality holds since[x n ]D 1 (x) = n n+1 2n n whereas [x n ]

Miklós Bóna

This yields

for n = 1.

Comparing formulae (23) and (25) and using Stirling's formula, we see that in 132-avoiding permutatations of length n, there are c √ n times as many inversions as non-inversions.

Further Directions

A simple analysis of the proofs of Theorems 2 and 3 shows that the inequalities a(n, k) ≤ t n (q) ≤ d(n, k) are sharp if n is large enough compared to k.

We have seen that, if we consider 132-avoiding permutations, then among all patterns of length k, the increasing pattern is the least likely to occur and the decreasing pattern is the most likely to occur. This suggests the following natural question. Question 1. Let r be any pattern, and let t r,q (n) be the number of all copies of q in all r-avoiding permutations of length n. Let us assume that among all patterns q of length k, it is the increasing pattern that minimizes t r,q (n) for all n.

Is it then true that among all patterns q of length k, it is the decreasing pattern that maximizes t r,q (n)?

Another direction of research is the following.

Question 2. Let q 1 and q 2 be two patterns of the same length, and assume that for some positive integer N , the inequality t r,q1 (N ) < t r,q2 (N ) holds. Is it then true that t r,q1 (n

for all n > N ?

In other words, is it true that the relation between the frequency of q 1 and q 2 in r-avoiding permutations depends only on r, q 1 and q 2 , or does it depend on n as well?

Lemma 1 and formula 6 show interesting combinatorial properties of the power series D 1 (x), D 2 (x), • • • and A 1 (x), A 2 (x), • • • . These properties are easy to express in terms of combinatorial objects, without power series. However, is there a combinatorial proof for them?