# A q, t-analogue of Narayana numbers.

1 Introduction

Given two natural numbers m and n, the set of m x n rectangular polyominoes [Polyo.sub.m,n] is known to have cardinality equal to N(m + n - 1, m), where for positive integers a,b [member of] N,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

are the famous Narayana numbers.

In  two authors of this work introduced two statistics on these combinatorial objects, area and bounce, which led to a q, t-analogue of the Narayana numbers N(m + n - 1, m), namely

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In that same work it was conjectured that these polynomials were symmetric both in q and t, and in m and n.

In this work we introduce a new statistic dinv, which gives a new q, t-analogue of the same numbers

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The following theorem establish a relation between these two polynomials.

Theorem 1.1 For all m [greater than or equal to] 1 and n [greater than or equal to] 1, we have

[Nara.sub.m,n] (q,t) = [Nara.sub.n,m] (q, t).

The main result of this paper is the proof of the symmetries conjectured in .

Theorem 1.2 For all m [greater than or equal to] 1 and n [greater than or equal to] 1, we have

[Nara.sub.m,n] (q,t) = [Nara.sub.m,n] (t, q)

and

[Nara.sub.m,n] (q,t) = [Nara.sub.n,m] (q, t).

In order to prove this result, we use a symmetric functions interpretation of our q, t-Narayana numbers:

Theorem 1.3 For all m [greater than or equal to] 1 and n [greater than or equal to] 1 we have

[Nara.sub.m,n] (q, t) = [(qt).sup.m+n-1] x <[nabla][e.sub.m+n-2], [h.sub.m-1] [h.sub.n-1]>,

where [e.sub.k] and [h.sub.k] are the elementary and the homogeneous symmetric functions of degree k respectively, [nabla] is the well known nabla operator introduced by Bergeron and Garsia (see [2, Section 9.6]), and the scalar product is the usual Hall inner product on symmetric functions.

This result brings a surprising link with the famous diagonal harmonics [DH.sub.n], since [nabla][e.sub.n] is the Frobenius characteristic of this important module of the symmetric group [[??].sub.n], as it was shown by Haiman in .

Haglund in  gave a combinatorial interpretation of the polynomial <[nabla][e.sub.m+n-2], [h.sub.m-1] [h.sub.n-1]> in terms of parking functions. In fact Haglund's result would be an easy consequence of the famous shuffle conjecture, which predicts a combinatorial interpretation of [nabla][e.sub.n] in terms of parking functions (see [5, Chapter 6]).

In order to prove our main result, we used the recursion already established for [Nara.sub.m,n (q, t), proving that the combinatorial polynomials in Haglund's result satisfy the same recursion.

This paper is organized in the following way:

* In Section 2 we give the basic definitions, introducing our statistics and our q, t-analogues of Narayana numbers.

* In Section 3 we provide a bijection between [Polyo.sub.m,n] and [Polyo.sub.n,m] sending the bistatistic (area, bounce) in the bistatistic (dinv, area), so establishing Theorem 1.1.

* In Section 4 we provide a recursion satisfied by both our q, t-Narayana, which gives another proof of Theorem 1.1.

* In Section 5 we provide the necessary background to state Theorem 1.3, we see some of its consequences, and we explain the strategy of its proof.

2 The statistics

In these paper we consider polyominoes in rectangular boxes. More precisely, consider a square grid in [Z.sup.2] of width m and height n. On this grid consider two paths, both starting from the South-West corner and arriving at the North-East corner, travelling on the grid, performing only North or East steps, with the further restriction that they touch each other only at the starting point and at the ending point. The region between the two paths is called the interior of the polyomino.

In Figure 1 there is an example where m =12 and n = 7, and the interior is shadowed.

We encode the polyomino in an area word consisting of natural numbers and natural numbers with a bar on top, in the following way.

We will label each North step of the upper (red) path with a number with a bar, and each East step of the lower (green) path with a number without a bar. We do this in two stages.

First, for each East step of the lower path we draw a line starting with the East endpoint and going North-West until reaching the upper path: we label this step with the number of squares crossed by this line.

Second, we label each North step of the upper path by the number of squares in the interior of the polyomino to the East of it which were not crossed by any of the lines that we drew at the previous stage.

An example of this labelling is shown in Figure 2, where we put a black dot in the non-crossed squares.

Once we have done this labelling, we read the labels in the following order: starting from South-West and going to North-East imagine to span the polyomino with a straight line oriented North-West to South-East, and when we encounter vertical steps of the upper path or horizontal steps of the lower path we write the corresponding labels, recalling that if we encounter both types of steps at the same time we write the label of the upper path first.

For example, the area word of the example in Figure 2 is [bar.0]1[bar.1]2[bar.2]322[bar.2]1[bar.1]211[bar.1]2[bar.2]22.

Notice that the sum of these numbers (disregarding the bars) gives the area of the polyomino, which is the first of the statistics that are relevant to us. In the example the area is 30.

The next statistic that we want to consider is the bounce. Consider the following path in a given polyomino: we start with a single East step from the South-West corner, and then we move North until we reach the East endpoint of a horizontal step of the upper path; at this point we "bounce", i.e. we start moving East, until we reach the North endpoint of a vertical step of the lower path; at this point we "bounce" again, starting moving North, and we repeat this procedure until we reach the North-East corner.

Once we have the bounce path, starting from South-West, we label each step of the first sequence of vertical steps with 1, then each step of the second of such sequences with 2, and so on; while we label each step of the first sequence of horizontal steps with 0, then each step of the second of such sequences with 1, and so on. See Figure 3 for an example.

We define the bounce of the polyomino to be the sum of the labels of the bounce path, disregarding the bars. For example the bounce of the example in Figure 3 is 41.

Consider now the total order on the labels

[bar.0] < 1 < [bar.1] < 2 < [bar.2] < 3 < [bar.3 ]< 4 < [bar.4] < ... .

Given a polyomino with area word [a.sub.1] [a.sub.2] ... [a.sub.k], we define the dinv as the number of pairs [a.sub.i], [a.sub.j], with i < j and a, is the successor of [a.sub.i] in the fixed order. For example the dinv of the polyomino in Figure 2 is 35.

We fix the following notations: let [Polyo.sub.m,n] be the set of polyominoes in a rectangle m times n, and let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The polynomials [Nara.sub.m,n] (q, t) where first introduced in  by two of the authors of the present work. In the same paper, it was conjectured that these polynomials where symmetric both in q and t, and in m and n.

3 Bijection sending (area, bounce) in (dinv, area)

This section is dedicated to prove Theorem 1.1, which we restate here for convenience.

Theorem 3.1 For all m and n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In order to prove it, we now describe a bijection between [Polyo.sub.m,n] and [Polyo.sub.n,m] which sends the bi-statistic (area, bounce) in the bi-statistic (dinv, area). Clearly this implies the theorem.

Starting from the polyomino, we read the labels of its bounce path, getting a word in integers and integers with a bar on top. Then, starting from the bottom-left corner, for each turn of the bounce path, we look at the part of the path (upper or lower) that includes it. For example in the polyomino of Figure 3 or 6, the first turn of the bounce path is between [bar.0] and the next 1 in the labelling of the bounce path. The including path consists of the first 4 steps (counted from the South-West corner) of the upper path. We label the vertical steps of the including path with the labels used for the vertical steps in that part of the bounce path, and the horizontal steps of the including path with the labels used for the horizontal steps in that part of the bounce path. See Figure 6 for an example.

Then we read the new labels by following the including path from North-East down to South-West. In the example we read 0111.

The rule is to preserve the relative positions of these labels along the rest of the construction.

We then repeat the algorithm with the second turn. In the example this occurs between the last 1 and the first 1 in the bounce path. This time the including path consists of the steps of the lower path between the second and the eighth. We repeat the procedure that we used before, and the word that we get reading the new labels will prescribe the relative positions of the 1's and the 1's. In the example (see Figure 5) we get the prescriptions 11[bar.11]1[bar.11]. This together with the other prescription gives a partial word [bar.0]11[bar.11]1[bar.11]. In general we will construct this partial word in a way that it can be the word of a polyomino and respecting all the prescriptions. This will always be possible since the first step of the including path that we read will always be labelled by the smallest of the two types of labels that we are considering: this is due to the definition of the bounce path.

We keep doing this until all the labels of the bounce path are included. At the end we will get a word of a polyomino. In the example, at the next step we get the prescriptions [bar.11]2[bar.11], which gives the partial word [bar.0]11[bar.11]21[bar.11]; then we get the prescriptions 2[bar.22], which gives the partial word [bar.0]11[bar.11]2[bar.22]1[bar.11]; then we get the prescriptions [bar.22]3, which gives the partial word [bar.01]1[bar.11]2[bar.22]31[bar.11]; then we get the prescriptions 3[bar.333], which gives the partial word [bar.0]11[bar.11]2[bar.22]3[bar.333]1[bar.11]; then we get the prescriptions [bar.33]44[bar.3], which gives the partial word [bar.0]11[bar.11]2[bar.22]3[bar.33]44[bar.3]1[bar.11]; and finally we get the prescriptions 44[bar.44], which gives the final word [bar.0]11[bar.11]2[bar.22]3[bar.33]44[bar.443]1[bar.11].

With this construction we get a polyomino, which is clearly in a rectangle n times m, since the number of integers without a bar is n and the number of integers with the bar is m by construction. Moreover it has clearly area equal to the bounce of the original polyomino, again by construction. See Figure 6 for a picture of the image polyomino of the example.

We need to show that the dinv of the new polyomino is equal to the area of the original one.

To see this, recall how we constructed the word of the new polyomino: for consecutive types of labels, we prescribed the relative positions by reading the corresponding including path. But each pair of a vertical step and an horizontal step in the including path contributing to the dinv corresponds to a square in the area of the polyomino.

It remains to see that this is a bijection. To see this, we can consider the inverse function: given a polyomino, write in weakly increasing order its word, and draw it as a bounce path with labels. Then reading the relative positions of consecutive types of labels you can reconstruct piecewise both the upper and lower path. This completes the proof.

Let us observe some consequence of this result.

First of all, notice that iterating this bijection a second time, we get a bijection of the polyominoes in a rectangle m times n into themselves which sends the bounce in the area. Moreover, applying the inverse and composing it with the flip along the South-West to North-East line that pass through the South-West corner (which obviously preserves the area) we get a bijection of the polyominoes in a rectangle m times n into themselves which sends the dinv in the area.

In conclusion we see that all our three statistics are equidistributed both inside the same rectangle m times n and with the polyominoes in the flipped rectangle n times m.

4 A recursion

In this section we prove that both [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] satisfy a certain recursion. As an immediate byproduct we get another proof of the identity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] stated in Theorem 1.1.

We call [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the set of polyominoes in a rectangle m x n whose labelled bounce path has r many 1's and s many [bar.1]'s. In other words, r is the number of steps between the first and the second bounce of the bounce path, while s is the number of steps between the second and the third bounce.

We fix the notation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the sum over all r and s of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Also, for all positive integers n,

[[n].sub.q] := [1 - [q.sup.n]/1 - q] = 1 + q + [q.sup.2] + ... + [q.sup.-1]

denotes the q-analogue of n (by convention we set [.sub.q] := 1),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

denotes the q-analogue of the factorial n!, and finally for n [greater than or equal to] k [greater than or equal to] 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

denotes the q-analogue of the binomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 4.1 For all m [greater than or equal to] 1 and n [greater than or equal to] 1, and for 1 [less than or equal to] r [less than or equal to] n and 0 [less than or equal to] s [less than or equal to] m - 1 we have the recursion with initial conditions

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

with initial conditions

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For a proof see .

Let us denote by [Polyo.sup.(r,s).sub.n,m] the set of polyominoes in a rectangle n x m whose area word has r many 1's and s many 1's.

We fix the notation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the sum over all r and s of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

These polynomials satisfy the same recursion satisfied by the [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

Theorem 4.2 For all m [greater than or equal to] 1 and n [greater than or equal to] 1, and for [less than or equal to] r [less than or equal to] n and 0 [less than or equal to] s [less than or equal to] m - 1 we have the recursion

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

with initial conditions

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and

[Nara.sup.(r,0).sub.n,1] (q, t) = 0 for r < n.

For a proof see .

These recursions give immediately [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and hence another proof of the identity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

5 Symmetric functions interpretation

In this section we will use some tools from the theory of Macdonald polynomials. For a quick survey of what we need (and more), we refer to the book , in particular Chapters 3 and 9.

Here we will recall only some basic facts, mostly to fix the notation.

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the space of symmetric functions with coefficients in C(q, t), where q and t are variables, with its natural decomposition in components of homogeneous degree.

Recall the fundamental bases of symmetric functions: elementary [{[e.sub.[mu]]}.sub.[mu]], homogeneous [{[h.sub.[mu]]}.sub.[mu]] power [{[p.sub.[mu]]}.sub.[mu]] monomial [{[m.sub.[mu]]}.sub.[mu]] and Schur [{[s.sub.[mu]]}.sub.[mu]], where the indices [mu] are partitions.

A scalar product is defined on [LAMBDA] by declaring the Schur basis to be orthonormal:

<[s.sub.[lambda]], [s.sub.[mu]]> = [chi] ([lambda] = [mu]),

where [chi] is the indicator function, which is 1 when its argument is true, and 0 otherwise.

Another fundamental basis of [LAMBDA] [{[[??].sub.[mu]]}.sub.[mu]] has been introduced by Macdonald, and its elements are called Macdonald polynomials.

The fundamental ingredient of the theory is the nabla operator [nabla] acting on [LAMBDA]. This is an homogeneous invertible operator introduced by F. Bergeron and A. Garsia in the study of the famous diagonal harmonics [DH.sub.n] of [S.sub.n]. In fact, it turns out that [nabla][e.sub.n] gives precisely the bigraded Frobenius characteristic of [DH.sub.n].

The so called shuffle conjecture predicts a combinatorial interpretation of [nabla][e.sub.n] in terms of parking functions. Special cases of this conjecture have been proven by several authors. In particular J. Haglund proved the combinatorial interpretation of

<[nabla][e.sub.n], [h.sub.j][h.sub.n-j]>

for 1 [less than or equal to] j [less than or equal to] n predicted by the shuffle conjecture.

Surprisingly, this same polynomial provides the symmetric functions interpretation of our q, t-Narayana numbers.

More precisely, we have Theorem 1.3, which is the main result of this paper. For a proof see .

Theorem 5.1

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We give here an immediate corollary.

Corollary 5.2 The polynomials [Nara.sub.m,n] (q, t) are symmetric both in q and t, and in m and n. Moreover, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof of the Corollary: The symmetry in q and t comes from a general property of the nabla operator, which is easy to show: nabla applied to any Schur function is symmetric in q and t.

s The symmetry in m and n is obvious from the formula.

Now the fact that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a direct consequence of the symmetries and of Theorem 1.1.

In order to prove Theorem 1.3, we used the combinatorial interpretation given by Haglundfor <[nabla][e.sub.m+n-2], [h.sub.m-1][h.sub.n]>. In order to state it, we need some definitions.

For us a Dyck path of order k will be given by an area word, i.e. a sequence of non-negative integers [b.sub.1] [b.sub.2] ... [b.sub.k] such that [b.sub.1] = 0, and [b.sub.i+1] [less than or equal to] [b.sub.i] + 1 for all i = 1,2, ..., k - 1.

A parking function of order k will be given by a domino sequence, i.e. sequence of dominoes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] like [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [b.sub.1] [b.sub.2] ... [b.sub.k] is the area word of a Dyck path, and the [a.sub.i]s are the integers from 1 to k, and they satisfy [a.sub.i] < [a.sub.i+1] if [b.sub.i] < [b.sub.i+1].

For example [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a parking function of order 11.

The set of parking functions of order k is denoted by [PF.sub.k].

Given a parking function, we can reorder its dominoes by comparing first the bottom numbers, from the biggest to the smallest, and then, we place the dominoes with the same bottom number in order as we read them from right to left in the parking function. The reading word [sigma] (PF) associated to the parking function PF is the permutation that we obtain by reading the upper entries of this reordered sequence of dominoes.

For example, the parking function that we have seen before get reordered as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

so the corresponding reading word is

[sigma] (PF) = 2 10 7 9 4 8 1 11 3 6 5.

Given a parking function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we define its area area(PF) as the sum [[summation].sup.k.sub.i=1] [b.sub.i] of the bottom numbers of the dominoes, and its dinv dinv(PF) as the number of pairs of dominoes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of PF with i < j, where [b.sub.i] = [b.sub.j] and [a.sub.i] < [a.sub.j], or [b.sub.i] = [b.sub.j] + 1 and [a.sub.i] > [a.sub.j].

For example the area of the parking function of our previous example is 14, while its dinv is 8.

Given two disjoint sequences of numbers A and B, we denote by A [union] [union] P the set of shuffles of A and B, i.e. the sequences consisting of the numbers from A [union] B in which all the elements of A and B appear in their original order, so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For any a and b in N, we call [Park.sub.a,b] the set of parking functions PF of order a + b such that [sigma] (PF) [member of] (1, 2, ..., a) [union] [union] (a + 1, a + 2, ..., a + b).

We finally set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We can state now the result of Haglund (see  for a proof, and  for the needed background).

Theorem 5.3 (Haglund) For all m [greater than or equal to] 1 and n [greater than or equal to] 1, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Hence in order to prove Theorem 1.3, it remains to show that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We proved this by showing that they both satisfy the recurrence given in Section 4. See  for the details.

Acknowledgements

We warmly thank Adriano Garsia for helpful conversations.

References

 AVAL, J.-C., D'ADDERIO, M., DUKES, M., HICKS, A., LE BORGNE, Y., Statistics on parallelogram polyominoes and a q,t-analogue of Narayana numbers, arXiv:1301.4803.

 BERGERON, F., Algebraic Combinatorics and Coinvariant Spaces, CMS Treatise in Mathematics, CMS and A.K. Peters, 2009.

 DUKES, M., LE BORGNE, Y., Parallelogram polyominoes, the sandpile model on a complete bipartite graph, and a q,t-Narayana polynomial, Journal of Combinatorial Theory Series A 120 (2013), no. 4, 816-842.

 HAGLUND, J., A proof of the q, t-Schroder conjecture, Internat. Math. Res. Notices 11, 2004, 525-560.

 HAGLUND, J., The q, t-Catalan numbers and the space of Diagonal Harmonics, AMS University Lecture Series, 2008.

 HAIMAN, M., Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, Invent. Math. 149 (2002), no. 2, 371-407.

Jean-Christophe Aval (1)

Mark Dukes (3)

Angela Hicks (4)

Yvan Le Borgne (1)

(1) LaBRI, University Bordeaux 1, 351 cours de la Liberation, 33405 Talence cedex, France

(2) University Libre de Bruxelles (ULB), Boulevard du Triomphe, B-1050 Bruxelles, Belgium

(3) University of Strathclyde, 16 Richmond Street, Glasgow G1 1XQ, Scotland, United Kingdom

(4) UCSD, 9500 Gilman Drive, 92093-0112 La Jolla, USA
Author: Printer friendly Cite/link Email Feedback Aval, Jean-Christophe; D'Adderio, Michele; Dukes, Mark; Hicks, Angela; Le Borgne, Yvan DMTCS Proceedings Report 4EUFR Jan 1, 2013 4114 EL-labelings and canonical spanning trees for subword complexes. The critical surface fugacity for self-avoiding walks on a rotated honeycomb lattice. Combinatorics Geometric figures Mathematical analysis Mathematical research Natural numbers Numbers, Natural