{'fraction_non_alphanumeric': 0.05631826069204859, 'fraction_numerical': 0.01730121465754823, 'mean_word_length': 3.6180768324298844, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Towards a q-analogue of the Harer-Zagier formula via rook placements

In 1986 Harer and Zagier computed a certain matrix integral to determine an influential closed-form formula for the number of (orientable) one-face maps on n vertices colored from N colors. Kerov (1997) provided a proof which computed the same matrix integral differently, which gave an interpretation of these numbers as also counting the number of placements of non-attacking rooks on Young diagrams. Bernardi (2010) provided a bijective proof of this formula by putting one-face maps in bijection with tree-rooted maps, which are orientable maps with a designated spanning tree. In the first part of the paper, we explore the connection between these rook placements and tree-rooted maps by developing a bijection between these objects. Rook placements on Young diagrams have a q-analogue due to Garsia and Remmel (1986). In the second part of the paper, we propose a statistic on rook placements that leads to a conjectured identity which is a q-analogue of part of the Harer-Zagier formula. This identity is also expressed in terms of moments of orthogonal polynomials which are rescaling of q-Hermite polynomials. We then use these moments to give a recurrence for the proposed q-analogue.


Introduction: Overview of Problem and Main Results
The Harer-Zagier formula involves the enumeration of unicellular (one-face) maps -embeddings of graphs with n edges on orientable surfaces (up to homeomorphism) such that cutting the surface along the edges of the graph results in a disk (the face). Because the map is required to have one face, the equation 2 − 2g = v − e + f = v − n + 1 shows that the genus g is determined uniquely by the number v of vertices and vice-versa. The formula is where ε g (n) is the number of distinct unicellular maps with n edges on a surface of genus g (for definitions, see Section 2) and N is a positive integer. Equation Kerov [8] showed that the matrix integral (1.2) could also be interpreted as counting ways of placing n non-attacking rooks on a board consisting of any Young diagram that can fit in an n × n board with k columns of length n added on the left that are required each to have a rook (see Figure 1). To do this, he first transformed the integral into a sum of moments of Hermite polynomials, then evaluated them via the Flajolet-Viennot combinatorial theory of orthogonal polynomials [18], and also put the rook placements in bijection with certain involutions to enumerate them explicitly. Of the three rooted one-face maps with n = 2 edges on the left, two of them are embedded on the sphere (g = 0) and one is embedded on the torus (g = 1). For the rook placements on the right, there are 3, 12 and 12 placements of n = 2 rooks on Young diagrams inside a 2 × 2 board with k = 0, 1 and 2 columns of length 2 added to the left that are required to have a rook.
Combinatorial proofs of (1.1) have been given by Lass [11], Goulden-Nica [7], and Bernardi [2]. In particular, Bernardi proved (1.1) by interpreting each side as counting all colored unicellular maps with colors chosen from [N ] = {1, 2, . . . , N } (we will use the notation [n] = {1, 2, . . . , n} throughout), where on the left side each vertex of the map is colored independently with a color from [N ] and on the right side a subset of k + 1 colors is first chosen and the map is required to use all of them. The right side was counted directly via a bijection between unicellular maps with vertices colored with colors in [k + 1] and tree-rooted maps with vertex set [k + 1], maps whose graphs contain distinguished spanning trees, each of which has a root vertex.
A natural question arises from these results. Mainly, the only extant connection between unicellular maps or (equivalently) Bernardi's tree-rooted maps and Kerov's rook placements is through the matrix integral. To provide a more direct connection between these two types of objects, we establish a bijection between tree-rooted maps and involutions which, along with Kerov's and Bernardi's bijections, yields the following corollary: There is an explicit bijection mapping rook placements in RC k (n, s) to tree-rooted maps with n edges and vertex set {s + 1} ∪ V where V ⊂ [s] and #V = k.
The set RC k (n, s) of rook placements is defined below. We note that Bernardi [1] also has an explicit bijection between the objects above.
One motivation for finding such a bijection is that it may preserve interesting properties of either object. In particular, from the work of Garsia-Remmel [5] rook placements on Young diagrams have very simple q-analogues. One might then ask what could serve as a q-analogue of the numbers C(n, N ), and whether this q-analogue can be expressed in other forms, in the same way that C(n, N ) can be expressed as a matrix integral or as a sum of moments of Hermite polynomials. Section 5 addresses this with the following conjecture (verified up to n = 10 and s = 5): Conjecture 5.2. The following identity holds: where Y (n, s) is the set of Young diagrams µ with n rows µ i such that s ≤ µ 1 ≤ µ 2 ≤ . . . ≤ µ n ≤ n+s. In Section 4, we show that the expressions in Conjecture 5.2 are indeed related to a q-analogue H n (x, q) of the Hermite Polynomials defined by H n+1 (x, q) = xH n (x, q) − q n−1 [n] q H n−1 (x, q) with H 0 = 1 and H 1 = x. This relationship is described in the following theorem: Theorem 4.15. The moments of the q-Hermite polynomials H n (x, q) against the Gaussian q- .
(For definitions of the q-number [n] q , q-integration and the Gaussian q-distribution, see Section 4).
Work towards a proof of Conjecture 5.2 is given in Sections 4 and 5, in the form of a detailed study of these q-Hermite polynomials and identities involving them and their moments (of the form in Theorem 4.15). We note that Stanton has provided a proof of Conjecture 5.2 [15] using techniques involving hypergeometric series which can be found in [6], but that finding a combinatorial proof is still an open problem. Outline In short, the structure of the paper is as follows: In Section 2, we give background material and definitions we give as much background about maps and rook placements as is needed to discuss the bijection in Section 3. In Section 3, we describe and demonstrate the veracity of our bijection. In Section 4, we discuss the form of q-Hermite polynomials that we use in this paper (as well as supplementing necessary background material about q-analogues). In Section 5, we present a conjectured identity that gives a q-analogue for a formula counting rook placements, and use the integral formulation to provide a recurrence for this quantity. We conclude with closing remarks and possible future work in Section 6.

Background and Definitions
We begin by reviewing maps, which constitute one of the types of objects in the bijection in Section 3. Maps are treated extensively in [10].
A unicellular map is an embedding of a connected graph in a smooth, compact surface (up to homeomorphism) with the property that the complement of the graph in the surface is homeomorphic to a disk. A rooted unicellular map is a unicellular map with one side of an edge distinguished as the root and oriented. For our purposes, the surface containing a map must be orientable. Rooted unicellular maps with n edges can be obtained by gluing the edges of a rooted 2n-gon (2n-gon with one edge distinguished as the root and assigned a direction). A gluing of the 2n-gon has n edges and 1 face by construction, so the formula for the Euler characteristic χ of the surface in which the map is embedded is χ = v − n + 1, where v is the number of vertices. Since χ = 2 − 2g where g is the genus of the surface, we have 2 − 2g = v − n + 1 → v = n + 1 − 2g. So we can take the sum is the number of distinct unicellular maps with n edges on a surface of genus g, and N is a positive integer. This sum can be interpreted as counting the unicellular maps with n edges and vertices colored from [N ].
Because multiple vertices may have the same color, we can count the same objects by first choosing a set of k + 1 colors (in N k+1 ways) and insisting the coloring use all of them. In [2], Bernardi bijectively counted the number of unicellular maps with n edges that use exactly k + 1 colors by constructing a bijection to tree-rooted maps, which are maps with a designated rooted spanning tree T (a spanning tree of a map is a subgraph of the underlying graph of the map that includes all of the vertices and is a tree; to say that it is rooted means that it has a vertex distinguished as the root). By construction, if a unicellular map has n edges and uses k + 1 colors, the corresponding tree-rooted map has n edges and vertex set [k + 1].
An important part of Bernardi's bijection is the fact that a graph and its rotation system (the cyclic order of half-edges around the vertices of the graph) are sufficient to construct a unique map (see [10]). From this it is not difficult to see that a graph with a rooted rotation system (one vertex is the root, around which there is a total order of half-edges) can be used to construct a rooted map (the root outgoing edge is the smallest element around the root vertex of the graph). For an example of a graph with a rooted rotation system and rooted spanning tree, see figure 2. Figure 2: On the left is a tree-rooted map with 3 vertices and 6 edges. On the right is the corresponding graph with its rotation system indicated by the gray arrows. The order around the root is broken at the root-edge. The spanning trees are in bold. Bold black arrows point to the root.
We now turn to the other type of objects in the bijection in Section 3, rook placements on Young diagrams.
A board is a set of pairs (i, j) which give the coordinates of the positions on the board. A non-attacking rook placement C on a board B is a set of positions C = {(x i , y i )} ⊂ B with at most one rook in each row and column, that is, x i = x j if and only if i = j (similarly y i = y j if and only if i = j) for all (x i , y i ) and (x j , y j ) in C. A Young diagram with n rows is a sequence of nonnegative integers {µ i } n i=1 such that 0 ≤ µ 1 ≤ µ 2 ≤ . . . ≤ µ n , where µ i gives the length of row i (that is, a Young diagram can be interpreted as a board with rows of lengths given by the µ i in order from the top). The number of placements of n rooks on a Young diagram, call it µ, with n rows is which follows from the fact that there are µ 1 ways to place a rook on the first row, µ 2 − 1 ways to place one on the second row (since µ 1 ≤ µ 2 ), µ 3 − 2 ways to place a rook on the third row (since We define the set Y (n, s) = {boards µ with n rows | s ≤ µ 1 ≤ µ 2 ≤ . . . ≤ µ n ≤ s + n}. Each board µ in Y (n, s) can be thought of as being obtained from a Young diagram that fits in an n × n box with s extra columns added to the left (for an example, see Figure 3. We then define the set of all rook placements of n rooks on boards in Y (n, s), RC(n, s) = {(µ, C) | µ ∈ Y (n, s), C a placement of n non-attacking rooks on µ}.
The subset RC k (n, s) ⊂ RC(n, s) consists of all elements (µ, C) of RC(n, s) where exactly k rooks of C are in the first s columns of µ. Kerov provided a bijection (which we will call here κ) between RC k (n, s) and another set I k (n, s), defined as the set of involutions (matchings) on the set {−s, −s+ 1, . . . , −1, 1, 2, . . . , 2n} such that exactly k negative points are matched (s−k are not), each negative point is matched to a positive one, and exactly k positive points are unmatched. Under the bijection κ between RC k (n, s) and I k (n, s), each rook in a placement C on a board µ defines an arc of the corresponding involution. One can think of each point in the set {−s, −s + 1, . . . , −1, 1, 2, . . . , 2n} as corresponding to a segment on the path defining the upper and right boundaries of µ, which consists of s + 2n segments (s horizontal segments for the first s columns, 2n segments defining the n × n Young diagram), so that a rook defines an arc between the points corresponding to the horizontal segment at the top of the rook's column and the vertical segment at the right boundary of the rook's row. For an example, see Figure 3.  (7,8). In this case, n = 4, s = 3, and k = 2. On the right is the corresponding rook placement. The numbers indicate which segments of the upper and right boundaries correspond to which points of the involution, the dotted lines show how the arcs of the involution correspond to rooks.

A Bijection Between Involutions and Tree-Rooted Maps
We define the set I k (n) as the set of involutions on the set of points {−k, −k +1, . . . , −1}∪[2n] with the property that for any involution A ∈ I k (n), if p < 0 then A(p) > 0, and #{p ∈ [2n] | A(p) = p} = k (this is essentially equivalent to I k (n, s) where s = k). We now state the main theorem of this section: Theorem 3.1. There is an explicit bijection Ψ mapping involutions in I k (n) to tree-rooted maps in T n (k + 1).
Which gives the following corollary: There is a bijection Ψ mapping rook placements in RC k (n, s) to tree-rooted maps with n edges and vertex set {s + 1} ∪ V where V ⊂ [s] and #V = k.
We will prove that Corollary 3.2 follows from Theorem 3.1 here, while the proof of Theorem 3.1 will be given later. Proof of Corollary 3.2. Given a rook placement R in RC k (n, s), we construct the rook placement R in RC k (n, k) by simply removing the columns in the first s columns which are empty (those which do not contain a rook). We can then find an involution A = κ(R ) in I k (n) corresponding bijectively to R . Furthermore, define the set V as the set of indices of columns in the first s columns of R which contain rooks; that is, if the 1 st column from the left has a rook, 1 is in the set V , if the 2 nd column from the left has a rook, 2 is in V , etc. We find Ψ(A), which has vertex set [k + 1]. There is a unique order-isomorphic correspondence between V ∪ {s + 1} and [k + 1] which is obtained by and s + 1 is mapped to k + 1); we define Ψ (R) as the relabeling of Ψ(A) under this correspondence. To find Ψ −1 (M ) for a tree-rooted map M with n edges, and k vertices labeled from [s] as well as one vertex labeled s + 1 (that is, we set s + 1 = max{labels of vertices}) first create the map M by relabeling the vertices of M with the elements of [k + 1] in an order-isomorphic way, then find Ψ −1 (M ), an involution in I k (n). Next, find the rook placement R = κ −1 (Ψ −1 (M )). Lastly, create R = Ψ −1 (M ) by inserting empty columns between the first k columns of R so that the indices of the columns containing rooks (which are in the first s columns) match the original labels of M .
Before we can prove Theorem 3.1, we note some classical results. In our description of the bijection, we use the term path (not the same as the weighted paths used to compute the moments of the Hermite polynomials) to refer to a sequence of steps, each of which can be up or down. An up step begins at a level l and ends at level l + 1, whereas a down step begins at a level l and ends at level l − 1. We can also think of these as paths from (0, 0) to (L, 0) (for some L ∈ Z + ) in the lattice Z 2 , where the level corresponds to the y-coordinate, in which case an up step moves in the direction (1, 1) while a down step moves in the direction (1, −1). The first step of a path always begins at level 0 and, for our purposes, the last step must end at level 0 (note that this means there must be an equal number of up and down steps, hence the length of the path must be even). The number of steps in the path is the length of the path. A Dyck path is a path with no step ending on a level below 0. We will also define the number of flaws in a path to be the number of up steps starting below 0.
We make use of a classical bijection (which we'll denote by β) between Dyck paths and trees that uses a breadth-first (as opposed to the also-common depth-first) method. Under this correspondence, the number of consecutive up steps after each down step is the number of children of the next vertex in the tree, where the vertices are ordered lexicographically such that the subtree beginning from any vertex v comes before the next vertex to the right of v on the same level. We state this as a lemma, noting that the result is classical: Lemma 3.3. The map β described above is bijective.
Remark 3.4. The above method of constructing a tree from a Dyck path gives a natural correspondence between the down steps of the path and the non-root vertices of the tree, where a down step s i corresponds to the vertex with (the number of) children given by the number of up steps following s i .
Example 3.5. Let P = U U DU U DDDU DU U DU DD. Proceeding as described above, we see that v 0 has two children because there are two consecutive up steps at the beginning. The next two down steps both have 0 up steps after them so the two children of v 1 have no children. After the next down step, there is an up step, so the next vertex v 4 (the right child of v 0 ) has one child, and so on. This path and the resulting tree are shown in Figure 4. It is well-known that the number of Dyck paths of length 2k is the k th Catalan number Cat k = 1 k+1 2k k , while the number of paths of length 2k is simply 2k k . This suggests a (k + 1)-to-1 correspondence between paths and Dyck paths. The classical Chung-Feller Theorem [12] gives the equidistribution of the number of flaws in a path; the following lemma uses this to construct such a correspondence.
Lemma 3.6. (Chung-Feller). The set of paths of length 2k can be partitioned into disjoint subsets of size k + 1 such that for each j, 0 ≤ j ≤ k there is exactly one path with exactly j flaws in each subset. So paths of length 2k can be put into a (k + 1)-to-1 correspondence with Dyck paths, by letting each path correspond to the Dyck path in the same subset of this partition.
Proof. We will define a set of bijections φ j (P ) between paths with j − 1 flaws and j flaws (j > 0). Let P be a path of length 2k with j > 0 flaws. Call the i th step of P s i ; we write P = s 1 s 2 . . . s 2k . To find the image of P under φ j (which we want to be a path with j − 1 flaws), find the first up step s f ending at level 0. φ j (P ) is then given by s f +1 s f +2 . . . s 2k s f s 1 s 2 . . . s f −1 . That this is a bijection with the desired properties is shown in [12]. We then construct a set for each Dyck path D. Define We then form the set S(D) = {S 0 (D), S 1 (D), . . . , S k (D)}. which clearly contains k + 1 elements, with S i (D) having i flaws. Furthermore, because the φ i are bijections, We are now ready to prove Theorem 3.1. Proof of Theorem 3.1. We construct the bijection Ψ : I k (n) → T n (k + 1) as follows. Let A be an involution in I k (n). We indicate by a i the i th point of A that is either a fixed point of A or the image of a negative point under A. We construct a path P = s 1 s 2 . . . s 2k with labeled down steps (separate from the notation s i , which simply refers to the i th step) from this sequence by the rule that s i is an up step if A(a i ) = a i , otherwise it is a down step with the label p where A(p) = a i (p < 0). This path starts and ends on the same level (which we'll call 0) by virtue of the fact that there are k fixed points and k negative points so the numbers of up and down steps in the path are equal.
The number of flaws in P determines the root vertex in Ψ(A): if there are j flaws, the root is the vertex j + 1. We now find the Dyck path P = s 1 s 2 . . . s 2k corresponding to P under the correspondence described in Lemma 3.6. From this we construct the spanning tree of T of Ψ(A) by the procedure described in Lemma 3.3.
Example 3.8. With P and A as in Example 3.7: P has 3 flaws, so the root of the corresponding tree is vertex 4. To find the tree, applying Lemma 3.6, we take P = φ 1 φ 2 φ 3 (P ). P is a Dyck path, so we can then construct a tree using β as in Lemma 3.3, taking T = β(P ). Figure 6 shows the application of Lemma 3.6 to get a Dyck path. Figure 6: Application of lemma 3.6. The path on the far left has 3 flaws, so applying φ 3 yields the next-leftmost path with 2 flaws, and so on, until we have a Dyck path.
At this point, the root vertex and the spanning tree of Ψ(A) have been determined; what remains is to determine the labeling of the non-root vertices, to insert half-edges which are not part of the spanning tree, and to pair these half-edges.
We label the non-root vertices of T as follows: As noted in Remark 3.4, the method for building the spanning tree from P gives a natural correspondence between the down steps of P and the non-root vertices of T . There is also a unique order-isomorphic (using the order on the negative points of A, which are the labels of the down steps) relabeling of the down steps with the labels that must be given to the non-root vertices in T (the set [k + 1]\{j + 1}, where j + 1 was the label given to the root). The labeling of a non-root vertex in T is then given by the label of the corresponding southeast segment of P .
Example 3.9. With A, P , P , and T as in Examples 3.7 and 3.8, we use the order-isomorphic correspondence −3 ↔ 1, −2 ↔ 2, and −1 ↔ 3 and the correspondence between the down steps of P and the non-root vertices of T as noted in remark 3.4 to label the non-root vertices. This is shown in Figure 7.
To insert and pair half-edges in T , we first construct a modified version of A from the path P which simply rearranges the a i in an analogous manner: define A = σAσ −1 where σ is the unique permutation defined by σ(a i ) = a j if and only if s i = s j .   Figure 8: σ is constructed so that taking σAσ −1 performs the exact same rearrangement of the points in A that we performed when rearranging the steps in P .
We take the set H of positive points H = [2n]\{a i } 2k i=1 , which can be partitioned into blocks We see that all the points of H are fixed by σ, so for any h ∈ H, i=1 so the structure of this partition is preserved in A . We now group the sets B i by isolating the k points a − m with A (a − m ) < 0, constructing the k + 1 sets V m such that V m is the union of all the sets B i such that for each where in the case m = 0 or k the left or right bound is ignored, respectively.
Each set V m determines the half-edges to be placed around a vertex of Ψ(A): V 0 gives the halfedges to be placed around the root vertex, and under the same order-isomorphic correspondence between the points −k, . . . , −1 and the non-root vertices of Ψ(A), V m gives the half-edges to be placed around the vertex corresponding to A (a − m ) for m > 0. We see that each V m is the disjoint union of exactly as many sets B i as there are "slots" around the corresponding vertex (areas between outgoing edges of T ), with the counterclockwise order of these slots (starting from the edge leading to the parent in T ) corresponds to the natural order of the B i . We place #B i half-edges into the slot corresponding to B i . The counterclockwise order of these is similarly given by the natural order of the points in B i . So each point in V m corresponds to a precise outgoing (currently un-paired) half edge from the corresponding vertex in T . The pairing of the half-edges is then given by the pairing of the points in H.
So, 1 corresponds to the first half-edge (in counterclockwise order) around the root, 3 is the 2nd half-edge around the root but it is on the other side of T because A (2) = 2, and 8 and 9 are two half-edges around vertex 1. Because A (1) = 9 and A (3) = 8, the first half-edge around the root is paired with the second half-edge around vertex 1, leaving the 2nd half-edge around the root to be paired with the 1st half-edge around vertex 1. This is shown in Figure 9.  Now define an ordered sequence of points a i (the labels a i are currently just labels but will later take on specific integer values), setting A(a i ) = a i if s i is an up step, and A(a i ) = p if s i is a down step with label p. We denote by n k the subsequence of indices with A(a n k ) < 0 (which were down steps in P ). As described previously, each of the a n k corresponds to a unique non-root vertex v of M , and each point a i with n k < i < n k+1 is a fixed point and corresponds to an outgoing half-edge from v which is part of T , with the left-to-right order of these fixed points corresponding to the counterclockwise order of the outgoing half-edges from v. So each pair (a i , a i+1 ) corresponds to a unique slot between two edges of T .
So, for each outgoing half-edge from v which is not part of T , we add a point between a i and a i+1 where (a i , a i+1 ) corresponds to the slot containing the half-edge. If p 1 and p 2 are two points added in this manner, and the half-edges to which they correspond are the two halves of the same edge, then we set A(p 1 ) = p 2 (and therefore also A(p 2 ) = p 1 , since A is an involution). This brings the total number of positive points to 2n. Now label the positive points in order with the integers in [2n] (this also gives the definite values for the labels a i ). Lastly, find the path P = s 1 s 2 . . . s 2k with j flaws which corresponds to P under the correspondence described in Lemma 3.6. Define σ as before, setting σ(a i ) = a j if and only if s i = s j . Then Ψ −1 (M ) is given by σ −1 A σ. So Ψ is bijective.
This concludes the proof of Theorem 3.1.

Orthogonal Polynomials and q-analogues
With this combinatorial connection established, we study rook placements and related q-analogues to work towards a q-analogue of one side of (1.1), beginning with a few more definitions: A Motzkin path ω is a sequence of lattice points (p 0 = (x 0 , y 0 ), p 1 = (x 1 , y 1 ), . . . , p n = (x n , y n )) such that for each i, (x i+1 , y i+1 ) = (x i + 1, y i − 1) or (x i + 1, y i ) or (x i + 1, y i + 1). The pair (p i−1 , p i ) is called the i th step of ω. The i th step of ω is said to be southeast, east, or northeast if p i−1 and p i satisfy the first, second or third of the possible relations, respectively. The i th step is said to start on level y i−1 and end on level y i .
In [18], Viennot elucidated the following important result (due to Viennot and Flajolet): 18]). For polynomials defined by P n+1 = (x − b n )P n − λ n P n−1 with P 0 = 1 and P 1 = x, which are orthogonal with respect to a weight function w( where the sum on the right is over Motzkin paths ω of length n starting on level i and ending on level j, and V (ω) is defined as the product of the weights of each step in the path, where the weight of a step starting on level k is 1 if it is northeast, b k if it is east, and λ k if it is southeast. ∞ −∞ x 2n H 2 s e − x 2 2 dx are closely related to rook placements on boards in Y (n, s): by Lemma 4.1, this integral is a sum over weighted Motzkin paths of length 2n beginning and ending at level s. However, because b n = 0 we can take the sum to be over only paths with no east segments. Paths with no east segments of length 2n beginning and ending at level s are in obvious correspondence with boards in Y (n, s) (see Figure 10).
Because λ n = n, the weight V (ω) of such a path ω exactly counts the number of placements of n non-attacking rooks on the corresponding board (see (2.1)). So we have that We will also need some preliminary definitions to discuss q-analogues. Many q-analogues are built from simpler q-analogues, the simplest being the q-analogue of an integer n, defined as [n] q = 1 + q + q 2 + . . . + q n−1 = 1−q n 1−q . The notation [· · · ] q is sometimes referred to as the q-bracket (not to be confused with the notation [n] = {1, . . . , n}), and generally denotes a q-analogue. For example, from this simple q-analogue one can then define a q-analogue of factorial, the q-factorial One can then further define the q-binomial coefficient We briefly recall how the above q-analogues of n k and (2n − 1)!! can be seen as a generating series with a certain statistic.
1. The following can be found in [14, page 65]: Where the sum is over all choices of a k-element subset α ⊂ [n], and the statistic size is given by size(α) := i∈α #{j ∈ [n] | j ∈ α; j < i}.
Note that it follows immediately from this identity that the q-binomial coefficients are, in fact, polynomials in q with nonnegative integer coefficients.
2. The following can be found in [13, (5,4)] and [4]: where M 2n is the set of perfect matchings on [2n] and the statistic cn(m) is given by #{crossings} + 2(#{nestings}) where a crossing is an instance of arcs (i, j) and (k, l) with i < k < j < l and a nesting is an instance of arcs (i, j) and (k, l) with i < k < l < j.
3. Note that we could define the statistics size and cn on perfect matchings m of a 2k-element subset α ⊂ [n] (strictly speaking, we would have a pair (α, m) of a subset and a matching, and we could then take the matching to be of [2k]) by having size(m) = size(α) and cn(m) defined as before (the points outside α contribute nothing to the number of crossings or nestings as they are defined above, as those only depend on arcs of the matching), and with this we would have where the sum is over all choices of a 2k-element subset of [n] and a matching of that subset (all the pairs (α, m) as described above). This identity follows from the previous two, as well as the fact that the matching and the choice of a subset can be made completely independently.
In [5], Garsia and Remmel introduced a q-analogue of the number of rook placements on a Young diagram-shaped board µ with n rows: where the statistic inv (the inversions) is obtained from a board and a rook placement on it by the following procedure: for each rook, cross out the square where the rook is, each square below it in its column and each square to the left of it in its row. After this has been done for all rooks, the number of squares on µ that have not been crossed out is the number of inversions inv(C). For an example, see Figure 11. This identity is proven by a simple induction on the rows of the board. To express the q-analogues in Conjecture 5.2 as moments of polynomials, we will also need qanalogues of the Hermite polynomials, a q-analogue of the Gaussian measure (in particular, one by which our q-Hermite polynomials are orthogonal), and a q-analogue of integration.
Our q-Hermite polynomials H n (x, q) (the symbol H n will refer to these q-analogues from here on) will be defined by the recurrence We note that these are closely related to the Discrete q-Hermite I polynomials h n (x, q) [9] defined by the recurrence The relationship is the following: H n (x, q) = a −n h n (ax, q), where a = 1 − q, (4.8) which follows simply by checking the recurrence. In fact, we have an explicit formula for H n , which we will later use to set up a "q-inclusionexclusion" formula which could potentially be used to prove Conjecture 5.2 combinatorially: Lemma 4.9. We have the following formula for H n (x, q): Lemma 4.9 will be proved in the Appendix. A q-analogue of integration (also called the Jackson integral) and of the Gaussian measure were used in [4], and we will use these with our q-Hermite polynomials. Many facts about Jackson integrals and q-differentiation can be found in [9]. We will use the notation b a f (x)d q x for the Jackson integral.
In general, two q-analogues of exponential functions are defined as These satisfy the following relation [4]: e x q E −x q = 1. With this, the Gaussian q-distribution is defined as The moments of w G (x) are given [4] by (4.11) In [9, page 118], the orthogonality relation for the h n is given: where We can now prove the orthogonality of our q-Hermite polynomials H n with the Gaussian qdistribution w G , which we can then use to apply Lemma 4.1: Lemma 4.13. We have the orthogonality relation 14) where ν = 1/ √ 1 − q, c(q) is as in (4.11), and δ mn is the Kronecker delta.
Proof. Making the variable transformation x → ax in (4.12) and multiplying both sides by a −(m+n) , (4.12) becomes where we have replaced a −(m+n) on the right with a −2n because of the presence of δ mn . Using (4.8), the fact that a −2 (1 − q i ) = [i] q , and a = ν −1 , this is It now remains to show that w(ax) = w G (x) and √ 1 − q c(q) = c(q). Given w(ax) = w G (x), the latter follows easily from the fact that we must havec(q) = 1 −1 w(x)d q (x) since by Lemma 4.1 (which applies because of the orthogonality), the norms of the h n are given by and use the q-binomial theorem ([14, page 72]) to obtain . Making the substitution x → ax gives and the lemma is proved.
We can now use the orthogonality (4.14) to prove the following theorem: Theorem 4.15. The moments of the q-Hermite polynomials against the q-Gaussian distribution are given by Proof. Because of the orthogonality (4.14), we can apply Lemma 4.1: where the product λ 1 λ 2 · · · λ s became q ( s 2 ) [s] q ! because λ i = q i−1 [i] q and the sum over Motzkin paths of length 2n was replaced with the sum over Young shapes µ ∈ Y (n, s) by the same method that Kerov used to do it in the q = 1 case.

Towards a q-analogue of one side of the Harer-Zagier Formula
As described in Section 2, the total number of rook placements on boards with a shape described by some µ in Y (n, s) is given by #RC(n, s) = µ∈Y (n,s) n i=1 (µ i −i+1). Kerov's bijection between rook placements and involutions provided an alternative way of counting rook placements which gives the expression on the right of (1.1). So we have the identity As was discussed in Section 4, there is a known q-analogue of the left side of this equation which is obtained by summing q inv(C) over elements of RC(n, s), where the statistic inv counts the number of blank squares left on µ after crossing out any square directly to the left or above a rook (see Figure 11). This gives For a q-analogue of (5.1), we have the following conjecture: Conjecture 5.2. The following identity holds: (1 + q n+i ), (5.4) where Y (n, s) is the set of all Young diagrams with n rows of lengths between s and n + s.
The rest of this section is devoted to proving some special cases of Conjecture 5.2 (Section 5.1), and giving a recurrence that the left-hand-side of (5.4) satisfies (Section 5.2).
Remark 5.5. A full proof of Conjecture 5.2 was given by Stanton [15], which used techniques of hypergeometric series which can be found in [6]. However, no combinatorial proof has yet been obtained.
5.1 Some special cases of Conjecture 5.2: s = 0 and k = n We will verify conjecture 5.2 for two special cases: s = 0 and k = n (that is, if we restrict the sum to only rook placements with all n rooks in the first s columns). Proof. By equation (4.7), and by Theorem 4.15, where the last step uses the fact that the 2n th moment of w G (x) is [2n − 1] q !! [4].
(ii) In [4], [2n − 1] q !! is expressed as a generating series over the same objects, placements C of n non-attacking rooks on a Young shape µ inside n n , but with respect to a different statistic than inv(C) + |µ| − n+1 2 . Such statistic is in terms of the crossings and nestings of the arcs of the involution corresponding to the pair (µ, C) under Kerov's bijection κ [13, (5,4)] (see (4.5)). For general s, we were unable to find a corresponding equidistributed statistic for the pairs (µ, C) in Y (n, s) × RC n (n, s).
Proposition 5.9. Conjecture 5.2 holds in the case k = n, that is, µ∈Y (n,s) rook placements C∈RCn(n,s) (1 + q n+i ). (5.10) Proof. Because inversions are squares with no rook directly to the right of or above them, every square in the last n columns (the n × n Young shape) will always be an inversion. Furthermore, the inversions in the first s columns are independent of the shape of the board, so the sum factors: µ∈Y (n,s) rook placements C∈RCn(n,s) (1 + q n+i ), (5.16) and the proposition is proved. Because we already have the equality (4.16), proof of Conjecture 5.2 is reduced to proving that the integral on the left of (4.16) also evaluates to (5.4).

A recurrence for Conjecture 5.2
The motivation behind the following lemma is that one could, in principle, prove Conjecture 5.2 by verifying the recurrence given in the lemma for (5.4) as well and show that the integral in (4. 16) and (5.4) are equal in the s = 0 and s = 1 cases, the latter part of which is trivially easy. However, we have not been able to verify the recurrence for (5.4).
Proof. First we verify the initial conditions: f (n, 0) = 1 follow from the computation of the moments in [4]. To verify the recurrence, first define Using the recurrence defining H s (x, q), we have Again using this recurrence, we also have We now show that by showing that the expression on the right also satisfies this recurrence and agrees with f × on initial values. We have that Furthermore, f × (n, 0) = 0 since H −1 = 0, and we see that the sum on the right of (5.22) is trivially 0 because s − 2 = −2 < 0 and l ≥ 0. So the lemma is proved.
Remark 5.26. Another potential method of proof of Conjecture 5.2 would be to compute the integral in (4.16) explicitly using the expression in Lemma 4.9 and knowledge of the moments of w G (x) to obtain the following: Then using the expansions (4.5) and (4.6) for the q-analogues of (2n − 1)!! and n 2k (2k − 1)!!, (5.27) becomes , β is a perfect matching on a subset of size 2(t − a); and m 3 is a perfect matching on the remaining set [2n + 2s]\(α ∪ β). The RHS of (5.28) has the flavor of an inclusion-exclusion expression, and suggests a possible approach to a combinatorial proof of Conjecture 5.2 (no such proof has yet been found).

Concluding remarks
In Section 3, we successfully constructed a bijection between tree-rooted maps and the rook placements. However, part of the motivation behind this effort was the intent of obtaining a bijection which preserved interesting properties of either type of object (tree-rooted maps or rook placements). One relevant statistic for tree-rooted maps is the degree of the vertices (because of the symmetry property [3, Thm. 1.3.]). We could not explicitly trace the degree through the bijection. On the other side, the statistic inv counting inversions is very important in the analysis of rook placements, so if inversions could be traced through the bijection, we could find an analogous statistic on tree-rooted maps. Moreover, tracing inversions could also be useful since this statistic is one of the building blocks for Conjecture 5.2. Though we have been unable to prove Conjecture 5.2, we have verified it empirically up to n = 10 and s = 5. If it is proved, then there are a number of questions that arise. where [#RC(n, s)] q denotes the expression in (5.4). We can ask many questions about this though: (ii) Is it possible to emulate the basis change in (1.1) (N v → N k+1 ) in the reverse direction for the q-analogue? This would ostensibly give a q-analogue of the numbers ε g (n).
(iii) Can one continue to "reverse engineer" a matrix integral in the q case? We were able to go back as far as writing [#RC(n, s)] q as a moment of some q-Hermite polynomials (Theorem 4.15), but it may be possible to continue to go backwards through the process in Kerov's paper to arrive at a matrix integral. We note that the work of Venkataramana [17, Section 6] may provide insight in this direction.