Francois Viard
email: viard@math.univ-lyon1.fr.

How to get the weak order out of a digraph ?

Keywords: Tableaux, digraphs, posets, Coxeter groups, weak order, reduced decompositions

Introduction

A tableau is a map from a finite subset S ⊂ N × N to N. Some families of tableaux are very classical in combinatorics and algebra, such as standard and semi-standard tableaux which play a fundamental role in the study of symmetric functions and representation theory.

In [START_REF] Edelman | Balanced tableaux[END_REF], Edelman and Greene introduced a new family of tableaux called balanced and exhibited a beautiful connection between them and the theory of reduced decompositions in the symmetric groups. This study has been extended by Fomin et al. in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF] by considering balanced labellings of the Rothe diagram of a permutation. Those labelled diagrams are a convenient way to visualise both the inversion set of a permutation and its associated set of reduced decompositions, and can be interpreted as a generalization of standard Young tableaux. Moreover, they introduced column-strict balanced labellings which generalize the notion of semi-standard Young tableaux. Column-strict labellings of the diagram of a permutation σ yield the Stanley symmetric function F σ (introduced in [START_REF] Stanley | On the number of reduced decompositions of elements of Coxeter groups[END_REF]) in the same way semi-standard tableaux yield Schur functions. This approach has been generalized to the affine Coxeter group A n by Yun and Yoo in [START_REF] Yoo | Balanced labellings of affine permutations[END_REF], and leads to a combinatorial description in terms of tableaux of the affine Stanley symmetric function introduced by Lam in [START_REF] Lam | Affine Stanley symmetric functions[END_REF].

The main purpose of this paper is to introduce a new family of posets, defined from a simple acyclic digraph together with a valuation on its vertices, by using an iterative process which peels the graph vertex by vertex. Then, we exhibit some general properties of these posets: we show that they are complete meet semi-lattice, and we give an explicit formula to compute the values of their Möbius function. Then we give some examples of classical posets which are special instances of this construction, namely the weak order on A n-1 , B n , A n , the flag weak order on Z r S n introduced by Adin, Brenti and Roichman (2012, [START_REF] Adin | Flag weak order on wreath products[END_REF]), the tree order of any tree, and the up-set (resp. down-set) lattice of any finite poset. In the A n-1 case we explain how this description naturally leads to associate a family of tableaux to each element of A n-1 , and we explain how they can be used to find the result of [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF] again. To finish we mention that a similar method can be applied to the A n case, and we briefly mention how these combinatorial consequences can be generalized to the other examples.

Definition of the family of posets

We begin with some standard definitions about poset theory and graph theory. A poset is a couple P = (P, ≤), where P is a set and ≤ is a binary relation which is reflexive, antisymmetric, and transitive. A poset P is called a complete meet (resp. join) semi-lattice if and only if every subset S of P has an infimum (resp. supremum) in P, i.e. there exists z in P such that if y ∈ P and y ≤ x (resp. x ≤ y) for all x ∈ S, then y ≤ z (resp. z ≤ y). If P is both a complete join and meet semi-lattice, then we say that P is a complete lattice. A lower set of P is a subset A of P such that for all x ∈ A and y in P , if y ≤ x then y ∈ A. It is classical that the lower sets of P ordered by inclusion is a lattice (for more details about poset theory, see [START_REF] Stanley | Cambridge studies in advanced mathematics[END_REF]).

A simple digraph is a couple G = (V, E), where V is the set of vertices of G, and E is a subset of V × V called the set of arcs of G. A cycle of G is a finite sequence x 1 , . . . , x n of vertices of G such that (x i , x i+1 ) ∈ E for all i ∈ N, where the indices are taken modulo n. A graph G is called acyclic if it does not have any cycle. On each vertex x of G, we define the statistic

d + (x) = |{y | (x, y) ∈ E}|,
called the out-degree of x, and which is possibly infinite.

General idea of the construction

We first present a suitable method to construct all lower sets of a finite poset P = (P, ≤), using the notion of linear extension of P. A linear extension of P is an injective sequence [a 1 , . . . , a n ] (with |P | = n) of elements of P such that: if a i ≤ a j in P, then i ≤ j. It is classical that A ⊆ P is a lower set of P if and only if there exists [a 1 , . . . , a n ] a linear extension of P and 1 ≤ k ≤ n such that A = {a 1 , . . . , a k } (see [START_REF] Stanley | Cambridge studies in advanced mathematics[END_REF]). Then to construct all the lower sets of P, we just have to construct all the linear extensions of P, and this can easily be done recursively thanks to the following iterative method.

Since P is finite, there exists a 1 in P which is a minimum, that is if x ≤ a 1 in P, then x = a 1 . Set P 2 = (P \ {a 1 }, ≤) the finite poset obtained by suppressing a 1 in P. Then there exists a 2 in P 2 which is a minimum. Then we can consider the poset P 3 obtained by suppressing a 2 in P 2 , and so on. At the end we obtain an injective sequence [a 1 , . . . , a n ] of elements of P. By construction, this sequence is a linear extension of P. Furthermore, one can easily prove by induction that all the linear extensions of P can be obtained by this way.

In a certain sense, this method "peels" a finite poset element by element, in order to obtain a family of sequences which give rise to an interesting family of sets (here, the lower sets). What we propose here it is to apply a similar principle to a simple acyclic digraph. Namely, we will peel the digraph vertex by vertex, with respect to a constraint given by a valuation on its vertices. It will give rise to a family of sequences of vertices of the graph, then to a family of subsets having an interesting poset structure once ordered by inclusion.

Construction of the family of posets

We start by defining the valuation on the vertices of a simple acyclic digraph.

Definition 2.1 Set G = (V, E) a simple acyclic digraph. A valuation θ : V → N is called an out-degree compatible valuation of G (abbreviated in "OCV") if and only if for all x ∈ V , we have 0 ≤ θ x ≤ d + (x).
In what follows, we will denote G = (G, θ) the pair of a simple acyclic digraph G together with an OCV of G. Thanks to the associated OCV, some vertices of G will be of special interest. Definition 2.2 (Erasable vertex) A vertex x of G is called erasable in G if and only if:

• θ x = 0;
• for all z ∈ V such that (z, x) ∈ E, we have θ z = 0. Now we define the peeling sequences of G, which leads to the definition of the claimed poset.

(G i = (G i , θ i )) 1≤i≤n as follows. 1. Set G 1 = G.
2. If there is not any erasable vertex in G i , the process stop. Otherwise, choose x a vertex of G i which is erasable in G i , and set x i = x.

(a) Set G i+1 the simple acyclic directed graph obtained by suppressing the vertex x i in G i together with all the arcs of G i containing it.

(b) Set θ i+1 the OCV of G i+1 such that θ i+1 y = θ i y -1 if (y, x) is an arc of G i , and θ i+1 y = θ i y otherwise. Then set G i+1 = (G i+1 , θ i+1
) and go back to the Step 2.

A sequence L which comes from this process is called a peeling sequence of G, and we denote P S(G) the set of all the peeling sequences of G.

And now we give the definition of the poset.

∅ G 2 G 3 G 4 Sequence (G i ) associated with L 1 . G P(G)
3 General properties of P(G)

In this section we give the main properties of the poset P(G). We start by announcing our results, and the scheme of the proofs will be given in the sequel.

Theorem 3.1 For all G = (G, θ), the poset P(G) is a graded complete meet semi-lattice, and its rank function is ρ : A → |A|. Moreover, when the underlying graph G is finite, P(G) is a complete lattice.

In the context of these posets, it is possible to give an explicit formula for the values of their Möbius function. Recall that the Möbius function on a graded poset P = (P, ≤) is the application µ : P 2 → N recursively defined by µ(x, x) = 1 for all x ∈ P , and

x≤z≤y µ(x, z) = 0 for all (x, y) ∈ P 2 .
For the sake of clarity, we give the formula only for the couples of the form (∅, A), A ∈ IS(G), but a similar one can be stated for all couples in IS(G).

Theorem 3.2 Set A ∈ IS(G). We denote N (A) = {x ∈ A | θ x = 0}, and F(A) = {x ∈ A | A \ {x} ∈ IS(G)}.
Then we have the two following possibilities:

1. if F(A) = N (A), then µ(∅, A) = (-1) |N (A)| ; 2. otherwise, µ(∅, A) = 0.

Proof of Theorem 3.1

The proof of this theorem has to be divided into several steps. The first one is a characterization of the elements of IS(G). Proposition 3.1.1 Set A a finite subset of vertices of G. We have that A ∈ IS(G) if and only if the two following conditions are satisfied:

(1) for all x ∈ A, θ x ≤ |{ y | y ∈ A and (x, y) ∈ E}|;

(2) for all x ∈ V \ A, θ x ≥ |{ y | y ∈ A and (x, y) ∈ E}|.

Proof: The proof of the necessary condition consists in a straightforward verification using the construction of a peeling sequence. The reverse direction is proved by induction on |A|: essentially, the fact that G is acyclic together with condition (1) and (2) imply that there exists x in A which is erasable in G. Then we begin the peeling process by picking this vertex and we set G the obtained digraph and OCV. One can show that A \ {x} satisfies conditions (1) and ( 2) in G , and the induction hypothesis applies. Hence A \ {x} ∈ IS(G ) and this concludes the proof. P

The next proposition implies immediately that P(G) is a graded poset with rank function ρ : A → |A|. Construction of the meet. We consider S and X as defined in the previous lemma, and we construct a set C ∈ IS(G) as follows. If for all x ∈ X, θ x = 0, we set C = ∅. Otherwise, let z 1 ∈ X be an erasable vertex of G. We start the peeling process by picking this vertex and we denote G 2 = (G 2 , θ 2 ) the obtained graph and OCV. Then for all A ∈ S, A \ {z 1 } ∈ IS(G 2 ), so we can again apply Lemma 3.1.1 to X \ {z 1 } seen as a subset of vertices of G 2 . If for all x ∈ X \ {z 1 }, θ 2

x = 0 we set C = {z 1 }; otherwise, let z 2 ∈ X \ {z 1 } be an erasable vertex of G 2 and we perform the peeling process by picking this vertex. We repeat this procedure until there is not any erasable vertex left (this process always ends, since X is finite), and we set C the obtained set. By construction, C ∈ IS(G).

At first glance, this set C seems to depend heavily on the choices of vertices made at each step of its construction. The next proposition shows that it is not the case.

Proposition 3.1.3 Set U ∈ IS(G). If U ⊆ X, then U ⊆ C. Proof: Since U ∈ IS(G), there exists L = [x 1 , x 2 , . . .] ∈ P S(G) and k ∈ N * such that U = {x 1 , . . . , x k }. Assume that U ⊂ C and set j ≥ 1 minimal such that x j / ∈ C.
Then by construction of C and Lemma 3.1.1, x j has to be in C, which is a contradiction. P Since C ⊆ X by construction, the previous proposition leads to the following corollary. When the underlying graph G is finite, we obviously have that V , the set of all the vertices of G, satisfies the conditions of Proposition 3.1.1, hence V ∈ IS(G), and the poset P(G) is bounded. Since it is a meet semi-lattice, then P(G) is a lattice, and this concludes the proof of Theorem 3.1.

Proof of Theorem 3.2

The proof of this formula is purely combinatorial, and is based on the well-known inclusion-exclusion principle (see [START_REF] Stanley | Cambridge studies in advanced mathematics[END_REF]). For all B ∈ IS(G), we denote

[∅, B] = {U ∈ IS(G) | ∅ ⊆ U ⊆ B}. Set A, N (A)
and F(A) as defined in Theorem 3.2. For all S ⊆ F(A), we denote A S the infimum of {A \ {x} | x ∈ S} ⊆ IS(G). We have the following lemma. Lemma 3.2.1 Set S ⊆ F(A). We have that A S = ∅ if and only if N (A) ⊂ S.

Proof: We have that the intersection of all the A \ {x}, for x in S, is equal to A \ S. By Lemma 3.1.1, if N (A) ⊂ S then there exists z ∈ A \ S which is erasable in G, so the infimum of {A \ {x} | x ∈ S} is not ∅. The reciprocal is based on similar arguments. P An immediate consequence of the meet semi-lattice structure of P(G) is that, for all U and V in IS(G),

[∅, U ] ∩ [∅, V ] = [∅, U ∧ V ]
where U ∧ V is the infimum of {U, V }. This basic remark leads to the claimed formula: first, we obviously have

[∅, A] \ {A} = x∈F (A) [∅, A {x} ].
Then, by the inclusion-exclusion principle we have that

|[∅, A] \ {A}| = ∅ =S⊆F (A) (-1) |S|+1 x∈S [∅, A {x} ] = ∅ =S⊆F (A) (-1) |S|+1 |[∅, A S ]| .
Once applied to the Möbius function of P(G), this gives rise to the following identity:

µ(∅, A) = - ∅ =S⊆F (A) (-1) |S|+1 B∈[∅,A S ] µ(∅, B). (1)
By definition of the Möbius function,

B∈[∅,A S ] µ(∅, B) = 1 if A S = ∅,
µ(∅, A) = - N (A)⊆S⊆F (A) (-1) |S|+1 = (-1) |N (A)| S⊆F (A)\N (A) (-1) |S| (2) = (-1) |N (A)| (1 -1) |F (A)\N (A)| . (3)
The claimed formula follows immediately.

Applications of this construction

Let W be a Coxeter group with finite generating set S, and Coxeter matrix M = (m st ) s,t∈S . That is, M is a symmetric matrix with m ss = 1 and, for s = t, m st = m ts ∈ {2, 3, . . .} ∪ {∞}. The relations among the generators are of the form (st) mst = 1 if m st < ∞. For w ∈ W we denote by (w) the minimum length of any decomposition w = s 1 • • • s l with s i ∈ S. Such decompositions with minimum length are called reduced, and we denote by R(w) the set of all reduced decompositions of w. This statistic on W is the rank function of a poset structure (W, ≤ R ) called the (right) weak order on W , and which is defines as follows: we say that w ≤ R τ if and only if there exists s 1 , . . . , s k in S such that τ = ωs 1 • • • s k and (τ ) = (w)+k. It is classical that (W, ≤ R ) is a complete meet semi-lattice when W is infinite, a complete lattice when W is finite, and that its Möbius function take values into {±1, 0} (see [START_REF] Bjorner | Orderings of Coxeter groups[END_REF] and [START_REF] Bjorner | Combinatorics of Coxeter groups[END_REF]). Hence, it is natural to look for an interpretation of the weak order through the theory developed in the previous section. Indeed, we can provide such a description in some cases. In the next theorem, we give a list of posets which admit such an interpretation. Theorem 4.1 For each poset P in the following list, there is an explicit G = (G, θ) such that P is isomorphic to P(G).

• The (right) weak order on Coxeter groups A n-1 , B n and A n .

• The flag weak order on Z r S n (see [START_REF] Adin | Flag weak order on wreath products[END_REF]).

• The up-set (resp. down-set) lattice of any finite poset.

• The tree order of any finite tree.

In this extended abstract we will focus on the case of the symmetric group A n-1 .

The weak order on A n-1

Recall that A n-1 is the Coxeter group with generating set S = {s 1 , . . . , s n-1 }, and with Coxeter matrix given by m sisi+1 = 3 for all 1 ≤ i ≤ n -2, and m st = 2 otherwise. One can see A n-1 as the symmetric group S n by identifying the generator s i to the transposition of S n which exchanges the integers i and i + 1. The main issue that arises when we want to find a pair G = (G, θ) such that (A n-1 , ≤ R ) is isomorphic to P(G), is that on the one side we have a poset whose elements are permutation (once A n-1 identified to the symmetric group S n ), and on the other side we have a poset whose elements are sets. Fortunately, there is a canonical set associated with each permutation σ ∈ S n , its inversion set:

Inv(σ) = {(a, b) ∈ {1, . . . , n} 2 | a < b and σ -1 (a) > σ -1 (b)}. (4)
There is a deep connection between inversion sets and the weak order on S n . That is, if σ and ω are two elements of S n , then σ ≤ R ω if and only if Inv(σ) ⊆ Inv(ω). This property allows us to clarify our goal: we are looking for a pair G = (G, θ) such that, . Finally, we denote G A = (G, θ). Among others natural choices for a valuation on this digraph, this one is in fact the "good" choice as stated in the next theorem. To give a sketch of the proof of the reverse inclusion, we recall a classical concept about permutations. Set σ ∈ S n and 1 ≤ a < b ≤ n two integers. We say that a and b are adjacent in σ if and only if σ -1 (a) + 1 = σ -1 (b). This notion is linked to the weak order thanks to the following property: we have that σ ≤ R ω with (ω) = (σ) + 1 if and only if ω can be obtained from σ by exchanging the position of two adjacent entries of σ. In that case, we say that ω covers σ and we denote it σ ¡ ω. This can be transposed in the context of the inversion sets as follows: we have that σ ¡ ω if and only if Inv

Application to the Stanley series of type A

The graphical interpretation of the reduced decomposition of a permutation as set of tableaux leads to a natural question: can we define a good generalization of the concept of semi-standard Young tableaux in this context ? If this is the case, what does the associate formal power series look like ? A natural starting point is to consider tableaux defines by a "column-strictness" condition as in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF]. Definition 4.2 Set σ ∈ S n and B its associated diagram. A tableau T of shape B is a sequence of integers indexed by the elements of B, that is T = (t c ) c∈B . We say that T is σ-semi-standard if and only if there exists L = [c 1 , . . . , c k ] ∈ P S(B) such that:

1. for all i < j, t ci ≤ t cj ;

2. for all i < j such that c i and c j lies in the same column of B, t ci < t cj .

The set of the σ-semi-standard tableaux is denoted SST (σ). Finally, we denote x T the monomial c∈B x tc .

It appears that the tableaux in SST (σ) and the column-strict balanced labellings of the Rothe diagram of σ introduced in [START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF], are basically the same objects. That is, one can travel from one point of view to another just by swapping some lines of the tableaux, as depicted below.

Other cases

In the previous section we studied the case A in details, and showed how it naturally leads to a combinatorial interpretation of the associated Stanley series. A similar process can be performed in the A case, and leads to an analogous combinatorial interpretation of the reduced decompositions in A, and of the corresponding Stanley series (using [START_REF] Yoo | Balanced labellings of affine permutations[END_REF]) introduced by Lam in [START_REF] Lam | Affine Stanley symmetric functions[END_REF]. In that case, the underlying graph can be seen as an infinite version of G A , which is rolled around a cylinder. For a graphical representation, see the following figure.

In the case of the weak order on the type B, the digraph is a bit more complicated and can be visualize as a shifted diagram, where the digraph structure is given by the shifted hooks. In that case, the study of the associated formal power series which arise is undone, and the author will focus on that topic later. To conclude, we mention that some clues suggest that a description of the weak order on any Coxeter group with this theory is possible, and this will be the subject of a later publication.

We finish by giving, without justification, the graphical representation of some of these objects.

Definition 2 . 3 (

 23 Peeling process and peeling sequences) We construct recursively two sequences: a sequence L = [x 1 , x 2 , . . .] of elements of V , and a sequence

Definition 2 . 4 Example 2 . 2 . 1

 24221 Let L = [x 1 , x 2 , . . .] be a peeling sequence of G. The initial sections of L are the sets of the form {x 1 , x 2 . . . , x k } for some k ∈ N * . By convention, ∅ is an initial section of L. We set IS(G) the set of all the initial sections of all the peeling sequences of G, and we denote P(G) = (IS(G), ⊆) the poset obtained by ordering IS(G) by inclusion. Consider G as depicted in the upper left corner of the following figure. The peeling sequences of G are L 1 = [a, c, b] and L 2 = [b, c, a], thus IS(G) = {∅, {a}, {b}, {a, c}, {b, c}, {a, b, c}}.

Proposition 3 . 1 . 2

 312 Set A and B two elements of IS(G), and denote k = |A| and q = |B|. If A ⊆ B, then there exists L = [x 1 , x 2 , . . .] ∈ P S(G) such that A = {x 1 , . . . , x k } and B = {x 1 , . . . , x q }.Proof: We suppose that k < q. We construct explicitly the sequence L as follows. Since A ∈ IS(G), we can start by picking the first k elements x 1 , . . . , x k in A. Set G = (G , θ ) obtained from G after this procedure. Thus B \ A is a finite subset of vertices of G , moreover B \ A satisfy the conditions of Proposition 3.1.1, hence B \ A ∈ IS(G ). So there exists L = [x k+1 , . . . , x q , . . .] ∈ P S(G ) such that B \ A = {x k+1 , . . . , x q }. At the end if we concatenate the sequences [x 1 , . . . , x k ] and L , we obtain L = [x 1 , x 2 , . . .] which is a peeling sequence of G by construction, and satisfies all the claimed properties. P We conclude by an explicit construction of the infimum (also called the meet) of a set S ⊆ IS(G). We start by a useful lemma, which is an immediate consequence of Proposition 3.1.1. Lemma 3.1.1 Set S ⊆ IS(G), and denote X := A∈S A. If there exists x ∈ X such that θ x = 0, then there exists z ∈ X which is erasable in G.

Corollary 3 . 1 . 1

 311 The set C is the infimum of S.

  and 0 otherwise. Hence by Lemma 3.2.1, if N (A) ⊂ F(A), then µ(∅, A) = 0. As a consequence, Equation (1) becomes

1 .

 1 the vertices of the graph are indexed by the couple of integers (a, b) ∈ {1, . . . , n} 2 such that a < b; 2. the digraph structure of G, together with the valuation θ, imply that IS(G) is constituted exactly of the sets of the form Inv(σ), σ ∈ S n . There is a convenient way to represent the set {(a, b) ∈ {1, . . . , n} 2 | a < b}, by considering the n-th staircase diagram, namely the Ferrers diagram of the partition λ n = (n -1, n -2, . . . , 1) of size N = n 2 . At the left of the next figure, the diagram associated to the case n = 5 is represented. The coordinates of each box can be read thanks to the circled integers on the diagonal.

5 )Definition 4 . 1

 541 As depicted in the middle of the figure, one can easily visualize the inversion set of any element of S n as a subset of boxes in λ n . Note that the set constituted by all the boxes of the diagram corresponds to the inversion set of the reverse permutation [n, n -1, . . . , 1] ∈ S n , which is the maximal element in the weak order. We define a digraph structure G on this diagram (where the vertices are the boxes of the diagram), thanks to a classical combinatorial object associated to each box c, the hook based on c, denoted H(c) and composed of all the boxes which are on the right and below c (represented at the right of the Figure): we say that there is an arc from c to d if and only if c = d and d ∈ H(c). The obtained digraph G is obviously a simple acyclic digraph whose vertices are the boxes of the diagram. Moreover, with this definition we have that the out-degree of any box is an even number. Hence we set θ the valuation θ : c → d + (c) 2

Theorem 4 . 2

 42 Set n ∈ N and G A associated with λ n . The posets (S n , ≤ R ) and P(G A ) are isomorphic. Proof: It is enough to show that IS(G) = {Inv(σ) | σ ∈ S n }. The inclusion "⊇" is based on a verification using Proposition 3.1.1.

Example 4 . 2 . 1

 421 (ω) = Inv(σ) ∪ {(a, b)} where a and b are two adjacent entries of σ. Now consider B ∈ IS(G A ) and L = [(a 1 , b 1 ), . . . , (a N , b N )] ∈ P S(G A ) such that B = {(a 1 , b 1 ), . . . , (a k , b k )}. Set B 0 = ∅, and B i = {(a 1 , b 1 ), . . . , (a i , b i )} for all 1 ≤ i ≤ k. We can show recursively that B i is the inversion set of a permutation. Now set L = [(a 1 , b 1 ), . . . , (a k , b k )] ∈ P S(B), and denoteB i = {(a 1 , b 1 ), . . . , (a i , b i )}.By construction of the isomorphism between (S n , ≤ R ) and P(G A ), there exists σ i such that Inv(σ i ) = B i . Hence we have ∅ ⊂ Inv(σ 1 ) ⊂ . . . ⊂ Inv(σ k ). Then we transpose this expression to the weak order, and it becomes Id ¡ σ 1 ¡ . . . ¡ σ k = σ. To summarize, we associated a maximal chain (from Id to σ) to each element of P S(B), and we can show that it is a bijection. This concludes the proof.P We conclude by an example of application of this bijection to σ =[START_REF] Edelman | Balanced tableaux[END_REF][START_REF] Adin | Flag weak order on wreath products[END_REF][START_REF] Bjorner | Combinatorics of Coxeter groups[END_REF][START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF][START_REF] Bjorner | Orderings of Coxeter groups[END_REF]. Denote B the diagram associated with σ, and consider L = [(2, 3),[START_REF] Bjorner | Orderings of Coxeter groups[END_REF][START_REF] Edelman | Balanced tableaux[END_REF],[START_REF] Bjorner | Combinatorics of Coxeter groups[END_REF][START_REF] Edelman | Balanced tableaux[END_REF],[START_REF] Adin | Flag weak order on wreath products[END_REF][START_REF] Edelman | Balanced tableaux[END_REF],[START_REF] Bjorner | Orderings of Coxeter groups[END_REF][START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF]] ∈ P S(B). The maximal chain associated with L is:σ 1 = [1, 3, 2, 4, 5] = s 2 , σ 2 = [1, 3, 4, 2, 5] = σ 1 s 3 , σ 3 = [1, 4, 3, 2, 5] = σ 2 s 2 , σ 4 = [4,1, 3, 2, 5] = σ 3 s 1 , and σ 5 = [4, 1, 3, 5, 2] = σ 4 s 4 . Thus the associated reduced decomposition is s 2 s 3 s 2 s 1 s 4 . The next figure describes completely the bijection in the case of [4, 1, 3, 5, 2] (for the reader convenience, peeling sequences are represented by tableaux).

  Hence, as an immediate consequence of (Theorem 4.3,[START_REF] Fomin | Balanced Labellings and Schubert Polynomials[END_REF]), we have the following Theorem.

Theorem 4 . 3

 43 For all σ ∈ S n , F σ (x 1 , x 2 , . . .) = T ∈SST (σ)x T , where F σ is the Stanley series of type A associated with σ and defined byF σ (x 1 , x 2 , . . .) = si 1 •••si (σ) ∈R(σ) b 1 ≤b 2 ≤...≤b (σ) b j <b j+1 if i j >i j+1 x b1 x b2 • • • x b (σ) .

( A 4 ,

 4 ≤ R ) (B 4 , ≤ R )"Flag weak order" on G(2, 3).

• If we denote Id = [1, 2, . . . , n], then B 0 = Inv(Id).

• By definition of G A , we have that (a 1 , b 1 ) is of the form (j, j + 1) for some j ∈ {1, . . . , n -1}.

Since j and j + 1 are adjacent in Id, we have that Id ¡ σ 1 := [1, . . . , j + 1, j, . . . , n], thus

• Now, consider G A 2 obtained with the peeling process after we picked (a 1 , b 1 ).

Then we can show that a 2 and b 2 are adjacent in σ 1 , hence σ 1 ¡σ 2 , where σ 2 is obtained from σ 1 by exchanging the positions of a 2 and b 2 . Hence

• The sequel of the induction is similar: if there is

then we show that a j+1 and b j+1 are adjacent in σ j , and we construct σ j+1 as before. The exact proof is quite technical and is essentially based on refinements of the arguments introduced by Edelman and Greene about balanced tableaux of staircase shape. The interested reader can look at [START_REF] Viard | A natural generalisation of balanced tableaux[END_REF] for a proof using another terminology.

As an immediate consequence, B = B k = Inv(σ k ). This concludes the proof. P Proof: Recall that a maximal chain from Id to σ (in the weak order) is a sequence (σ j ) 1≤j≤k such that Id¡σ 1 ¡. . .¡σ k = σ. There is a canonical bijection between elements of R(σ) and maximal chains from Id to σ. That is, set

Conversely, if σ ¡ ω, we have that there exists s p such that ω = σs p by definition of the weak order, thus a maximal chain leads to a reduced decomposition of R(σ).


Adrien Boussicault

Simone Rinaldi

Samanta Socci

The number of directed k-convex polyominoes

Keywords: Parallelogram polyomino, directed convex polyomino, degree of convexity, tree, path, generating function

Introduction

In the plane Z × Z a cell is a unit square and a polyomino is a finite connected union of cells (see Fig. 1). Polyominoes are defined up to translations. We assume without loss of generality that the south-west corner of its minimal bounding rectangle is placed at (0, 0). A column (row) of a polyomino is the intersection of the polyomino and an infinite strip of cells whose centers lie on a vertical (horizontal) line. A polyomino is said to be column-convex (row-convex) when its intersection with any vertical (horizontal) line is connected. A polyomino is convex if it is both column-and row-convex (see Fig. 1(b)). The semiperimeter of a polyomino is naturally defined as half the perimeter. As a matter of fact, the semi-perimeter of a convex polyomino is given by the sum of the number of its rows and its columns.

In [START_REF] Castiglione | Reconstruction of L-convex Polyominoes[END_REF] the authors propose a classification of convex polyominoes in terms of paths internal to polyominoes. A convex polyomino is said to be k-convex if every pair of its cells can be connected by a path, internal to the polyomino, with at most k changes of direction. For k = 1, we have L-convex polyominoes, which have been studied by several points of view [START_REF] Castiglione | Reconstruction of L-convex Polyominoes[END_REF][START_REF] Castiglione | Combinatorial aspects of L-convex polyominoes[END_REF][START_REF] Castiglione | Enumeration of L-convex polyominoes by rows and columns[END_REF]. In particular in [START_REF] Castiglione | Combinatorial aspects of L-convex polyominoes[END_REF] it is shown that the generating function of L-convex polyominoes according to the semi-perimeter is rational. For k = 2 we have the Z-convex polyominoes, which instead have an algebraic generating function [START_REF] Duchi | The number of Z-convex polyominoes[END_REF]. The methods applied for the enumeration of L-convex and Z-convex polyminoes are not easily extendable to the general case, and, as a matter of fact, the enumeration of k-convex polyominoes is an open problem, for k > 2. Thus, in order to simplify the enumeration problem, the authors of [START_REF] Battaglino | The number of k-parallelogram polyominoes[END_REF] provide a general method to enumerate an important subclass of k-convex polyominoes, that of k-parallelogram polyominoes, i.e. k-convex polyominoes which are also parallelogram.

Let us recall some basic defintions: a polyomino is said to be directed when each of its cells can be reached from a distinguished cell, called the root (denoted by S), by a path which is contained in the polyomino and uses only north and east unit steps. A polyomino is directed convex if it is both directed and convex. The number of directed convex polyominoes with semi-perimeter n + 2 is known to be equal to 2n

n [START_REF] Bousquet-Mèlou | A Method for the Enumeration of Various Classes of Column-Convex Polygons[END_REF][START_REF] Bousquet-Mélou | Une bijection entre les polyominos convexes dirigés et les mots de Dyck bilatères[END_REF][START_REF] Lin | Rigorous results for the number of convex polygons on the square and honeycomb lattices[END_REF]. We recall that a parallelogram polyomino is a polyomino whose boundary can be decomposed in two paths, the upper and the lower paths, which are comprised of north and east unit steps and meet only at their starting and final points. It is clear that parallelogram polyominoes are also directed convex polyominoes, while the converse does not hold. It is known that the number of parallelogram polyominoes with semi-perimeter n + 1 is the nth Catalan number [START_REF] Stanley | Enumerative Combinatorics[END_REF].

In this paper we present a new bijection between directed convex polyominoes and triplets (F e , F s , λ), where F e and F s are forests of trees, and λ is a lattice path made of two types of steps, satisfying special constraints. This bijection allows to express the convexity degree of the polyomino in terms of the heights of the trees of F e and F s . Basing of this bijection, we develop a new method, for the enumeration of directed convex polyominoes, which allows us to control several statistics, including the semi-perimeter, the degree of convexity, the width, the height, the size of the last row/column and the number of corners. Our method eventually let us determine the generating function of directed k-convex polyominoes, for any k ≥ 1. This is a rational function, and it can be suitably expressed using the Fibonacci polynomials [START_REF] De Bruijn | The average height of planted plane trees, Graph Theory and Computing[END_REF]. Moreover, we provide the asymptotic behavior for the number of directed k-convex polyominoes.

While in the last years a growing interest was shown in the combinatorial properties of k-convex polyominoes, as certified by [START_REF] Brocchi | On computing the degree of convexity of polyominoes[END_REF][START_REF] Brocchi | On the Exhaustive Generation of k-Convex Polyominoes[END_REF][START_REF] Micheli | Counting k-convex polyominoes[END_REF], the general enumeration problem remains open. Thus we believe that our approach can be used to develop a bijective method for the solution of the problem of enumerating k-convex polyominoes.

For brevity sake, some of the proofs will be omitted. We point out that the full version of the paper containing all the definitions and proofs, with several examples is on the ArXiv [START_REF] Boussicault | The number of directed k-convex polyominoes[END_REF].

Notation and preliminaries

Let P be a convex polyomino whose minimal bounding rectangle has dimension l 1 ×l 2 . We number the l 1 columns and the l 2 rows from left to right and from bottom to top, respectively. Fig. 1: A path connecting two cells of the polyomino with two changes of direction; a monotone path between two cells of the polyomino with two changes of direction.

Thus, we consider the bottom (resp. top) row of P as its first (resp. last) row, and the leftmost (resp. rightmost) column of P as its first (resp. last) column. By convention, we will often write (i, j) to denote the cell of P , whose north-west corner has coordinates equal to (i, j). With that convention, the cell is at the intersection of the i-th column and the j-th row. A path is a self-avoiding sequence of unit steps of four types: north n = (0, 1), south s = (0, -1), east e = (1, 0), and west w = (-1, 0). A path connecting two cells, b and c, of a convex polyomino P , is a path, entirely contained in P , which starts from the center of b, and ends at the center of c (see Fig. 1). A path is said to be monotone if it is comprised only of steps of two types (see Fig. 1). Let p = p 1 . . . p j be a path, each pair of steps p i p i+1 such that p i = p i+1 , 1 ≤ i < j, is called a change of direction (see Fig. 1). Given k ∈ N, a convex polyomino is said to be k-convex if every pair of its cells can be connected by a monotone path with at most k changes of direction [START_REF] Castiglione | Reconstruction of L-convex Polyominoes[END_REF]. For the sake of clarity, we point out that a k-convex polyomino is also h-convex for every h > k. We define the degree of convexity of a convex polyomino P as the smallest k ∈ N such that P is k-convex. Figure 1 shows a convex-polyomino with degree of convexity k = 2. In this paper we will deal with the class D ≤k (resp. P ≤k ) of directed k-convex polyominoes (resp. k-parallelogram polyominoes), i.e. the subclass of k-convex polyominoes which are also directed convex polyominoes (resp. parallelogram polyominoes). Given a directed convex polyomino D with a minimal bounding rectangle of size l 1 × l 2 , we define P D to be the parallelogram polyomino obtained from D, extending the side of D with ordinate equal to l 2 in the east direction to the point with coordinate (l 1 , l 2 ) and extending the side of D with abscissa equal to l 1 in north direction to the point with coordinate (l 1 , l 2 )(see Fig. 2). Let b = (i, j), c = (i , j ) be two cells of D. Without loss of generality, we can suppose that i ≤ i . Now if j < j, since D is a directed convex polyomino, we can always join b and c by means of a monotone path with at most one change of direction. Therefore, from now on, we will consider the case where j ≥ j. Let us define the bounce paths joining b to c as the two monotone paths internal to D starting at (i -3 2 , j -1 2 ) (resp. at (i -1 2 , j -3 2 )) with an east (resp. north) unit step and ending at the center of c, denoted by r b,c (resp. u b,c ), where every side has maximal length (see Fig. 3(a)). Therefore, it is worth defining the degree of a cell b of a directed convex polyomino as the number of changes of direction of the minimal bounce path joining S to b.

Given a parallelogram polyomino P , we denote by E rightmost cell of the top row of P . We define the bounce paths of P to be the two bounce paths joining S to E and we will denote by r(P ) (resp. u(P )) the bounce path r S,E (resp. u S,E ) (see Fig. 3(b),(c)). Henceforth, if no ambiguity occurs, we will write u (resp. r) in place of u(P ) (resp. r(P )). The minimal bounce path of P (denoted by m(P ) or m) is the minimal bounce path joining S to E. The following lemma explains that the minimal bounce path retains all information about the degree of convexity of a parallelogram polyomino. We now introduce another class of objects, which will be useful in this paper. An ordered tree is a rooted tree for which an ordering is specified for the children of each vertex. In this paper we shall say simply tree instead of ordered tree. The size of a tree is the number of nodes, and the height is the number of nodes on a maximal simple path starting from the root. Given a tree T , we denote the height of T by h(T ). Now, let t n,≤k be the number of trees of size n and height less than or equal to k. In [START_REF] De Bruijn | The average height of planted plane trees, Graph Theory and Computing[END_REF] the generating function T ≤k of trees with height less than or equal to k is proved to be:

T ≤k = j≥0 t j,≤k z j = zF k F k+1
where F k are the Fibonacci polynomials, defined by the following recurrence relation:

F 0 = 0, F 1 = 1 and F k+2 = F k+1 -zF k for k ≥ 0.
We define by T =k the generating function of trees with height equals to k. In [START_REF] De Bruijn | The average height of planted plane trees, Graph Theory and Computing[END_REF], we can find that

T =k = z k F k F k+1 .
We recall that an ordered forest (briefly a forest) is a t-uple of ordered trees. The size of a forest is the sum of the sizes of its trees. It is known that the forests of size n are in bijection with the trees of size n + 1: to obtain a forest from a tree, we just need to remove the root of the tree.

The k-parallelogram polyominoes

In the literature there are several bijections between ordered trees and parallelogram polyominoes (see, for instance, [START_REF] Stanley | Enumerative Combinatorics[END_REF]). Here we present yet another map Φ, which builds a pair of trees from a given parallelogram polyomino, and is borrowed from [START_REF] Aval | Combinatorics of non-ambiguous trees[END_REF]. In a parallelogram polyomino P , let V P be the set of dots defined as follows:

• we enlighten P from east to west and from north to south;

• we put a dot in the enlightened cells of P except for the cell E. We define the pair of trees Φ(P ) = (T 1 , T 2 ) using the following rules:

• the nodes of T 1 and T 2 are V P ∪ {s 1 , s 2 } and the roots of T 1 and T 2 are respectively s 1 and s 2 ; nodes may refer to a dot of P or to the corresponding node in T 1 or T 2 ; • in a row (resp. column) of P , except for the top row and the rightmost column, the rightmost (resp. topmost) node is the father of each other node in the same row (resp. column), and these nodes are brothers ordered from east to west (resp. north to south); • the root s 1 of T 1 (resp. s 2 of T 2 ) is the father of all nodes of the rightmost (resp. top) column (resp. row) of P , excluding s 2 (resp. s 1 ). Figure 4 shows an example of Φ. Let the size of a pair (T 1 , T 2 ) of trees be given by the sum of the sizes of T 1 and T 2 .

Proposition 3

The map Φ is a bijection between parallelogram polyominoes with semi-perimeter n and pairs of trees with size n.

Proof: By definition of Φ, each node x = s 1 , s 2 has exactly one father, in fact:

• if x is one of nodes of the top (resp. rightmost) row (resp. column) then its father is s 2 (resp. s 1 ); • otherwise, by construction, there is exactly one topmost node in the same column of x or one rightmost node in the same row of x, but not both at the same time.

Since a father always lies above or to the right of its sons, there is no cycle in the graph obtained by means of Φ and the only two nodes without fathers are s 1 and s 2 and hence, Φ produces two ordered trees T 1 and T 2 . The size of (T 1 , T 2 ) is equal to the number of dots enlightened in the parallelogram polyomino plus two (the roots s 1 of T 1 and s 2 of T 2 ), which is exactly equal to the semi-perimeter of the parallelogram polyomino. Now we will prove that Φ is injective. Let P 1 and P 2 be two parallelogram polyominoes such that P 1 = P 2 . Since P 1 is different from P 2 then there exists a first step of the lower path (or the upper path) of P 1 different to the corresponding step in P 2 and so in one of the two trees of Φ(P 1 ) (or of Φ(P 2 ))

we can find a father with more sons that the corresponding father in the corresponding tree of Φ(P 2 ) (or of Φ(P 1 )). We deduce that Φ(P 1 ) = Φ(P 2 ). To show surjectivity, we first prove that pairs of trees with size n are bijective to trees with size n. In fact we can define a bijection Ψ which builds, starting from a pair of trees (T 1 , T 2 ) a tree T , obtained from T 1 by adding T 2 as its subtree, with the rule that s 2 is the first son of s 1 (see Fig. 4). Since it is known that parallelogram polyominoes and ordered trees are equinumerous [START_REF] Stanley | Enumerative Combinatorics[END_REF], we can conclude that Φ is a bijection. Let r and u be the two bounce paths of a parallelogram polyomino P . At every change of direction the path r (resp. u) individuates an enlightened cell. The sequence of these cells determines a path d r (resp. d u ) in T 1 or T 2 (see Figure 5). We observe that the last node of this path is s 1 or s 2 and that its length is not necessarily maximal. By l(d r ) (resp. l(d u )) we denote the length of d r (resp. d u ) and we note that l(d r ) -1 (resp. l(d u ) -1) is the number of changes of direction of r (resp. u).

2 Φ ←--→ Ψ ←--→
Lemma 4 Let P be a parallelogram polyomino and Φ(P ) = (T 1 , T 2 ). The following equivalences hold:

i. h(T 1 ) = h(T 2 ) ⇔ d r and d u are chains of different trees ⇔ l(d r ) = l(d u ); ii. h(T 1 ) > h(T 2 ) ⇔ d r and d u are chains of T 1 ⇔ |l(d r ) -l(d u )| = 1 and d r , d u ∈ T 1 ; iii. h(T 2 ) > h(T 1 ) ⇔ d r and d u are chains of T 2 ⇔ |l(d r ) -l(d u )| = 1 and d r , d u ∈ T 2 .
Proposition 5 Let P be a parallelogram polyomino, and Φ(P ) = (T 1 , T 2 ). The degree of convexity of P We are now ready to calculate the generating function for k-parallelogram polyominoes, which was determined for the first time in [START_REF] Battaglino | The number of k-parallelogram polyominoes[END_REF], by using a purely analytic method. The following proposition provides a bijective proof of this enumerative result.

is equal to max(h(T 1 ), h(T 2 )) - 1 if h(T 1 ) = h(T 2 ); 2 otherwise. Φ ← ----→ Φ ← →

Proposition 6 ([3])

The generating function of k-parallelogram polyominoes with respect to the semiperimeter is given by

P ≤k = z 2 F k+2 F k+3 2 -z 2 F k+2 F k+3 -F k+1 F k+2 2
, where F k are the Fibonacci polynomials.

Proof: As already mentioned, the function

f = z 2 F k+2 F k+3 2
is the generating function of pairs of trees with height less than or equal to k + 2 with respect to their size. According to Proposition 5, to obtain P ≤k we need to remove from f the generating function

z 2 F k+2 F k+3 -F k+1 F k+2 2
of pairs (T 1 , T 2 ) of trees with height exactly equal to k + 2 with respect to their size. 2

Directed k-convex polyominoes

Given a parallelogram polyomino P , we denote by α(P ) (resp. β(P )) the number of cells in the top row (resp. rightmost column) of P minus one. A monotone path starting with an east step and ending with a south step is said to be a cut of P if the number of east steps is equal to α(P ) + 1 and the number of south steps is equal to β(P ) + 1. We can easily check that in a directed convex polyomino D, the path λ D starting from the leftmost corner of the top row (with an east step) and following clockwise the boundary of D until it reaches the lowest corner of the rightmost column (with a south step) is a cut of P D . For instance, D being the directed convex polyomino in Fig. 2, λ D = e 2 se 2 se 2 s 3 .

Proposition 7

The directed convex polyominoes of semi-perimeter n + 2 are in bijection with triplets (F e , F s , λ) such that F e and F s are forests and λ is a monotone path, starting with an east step and ending with a south step, and having m e + 1 east steps and m s + 1 south steps. The integers m e and m s are respectively the numbers of trees in F e and F s . The sum of the sizes of F e and of F s is equal to n.

Proof: (sketch) A directed convex polyomino D is uniquely determined by P D and λ D , whereas F e and F s are obtained from Φ(P D ) = (T 1 , T 2 ) by removing the roots of T 1 and T 2 (see Fig. 6). 2

k-convexity constraint

Let b and c be two cells of a given parallelogram polyomino P . There may exist a cell starting from which the two paths r b,c and u b,c are superimposed. In this case, we denote such a cell by J b,c (J is for "joining"). Clearly J b,c may even coincide with b and if such cell does not exist, we assume that J b,c coincides with c. We denote by J or J(P ) the cell J S,E . Let D be a directed convex polyomino; a sequence of cells of P D is naturally determined by the points where the bounce paths r(P D ) and u(P D ) cross each other. The sequence of these cells (denoted by L h = (i h , j h )) starts from S and ends with J. Let M be the index such that L M = J. We extend (L h ) h to a new sequence (I h ) h by defining I h≤M = L h , and I h>M by the cells where the two superimposed bounce paths change direction. Each cell I h will be labelled by h. From now on, we will refer to the set of directed convex polyominoes such that J(P D ) = E, as flat directed convex polyominoes.

I h-1 = (i h-1 , j h-1
) and I h = (i h , j h ). Then we have: 1) each cell (i, j) of P D (resp. D) with i h-1 < i ≤ i h and j h-1 < j has degree h; 2) each cell (i, j) of P D (resp. D) with j h-1 < j ≤ j h and i h < i has degree h; 3) each cell (i, j) of P D (resp. D) with i h < i and j h < j has degree greater than h.

The content of Proposition 9 is illustrated by Figure 7. Now, given a parallelogram polyomino P with degree of convexity equal to k, we define R P as the set of cells c = (i, j) of P such that i k-1 < i and j k-1 < j.

Corollary 10 Let D be a directed convex polyomino such that P D has degree of convexity k. Then the cells of R P D (resp. R P D ∩ D) are the only cells with degree k in P D (resp. D).

Lemma 11 If D is a flat directed convex polyomino, then R P D is a non empty rectangle.

Let P be a flat parallelogram polyomino with degree of convexity k. Let a and b be the width and the height of R P , respectively. We denote by λ R P the cut ee α(P )-a s b e a s β(P )-b s of P , which is precisely the cut of the directed convex polyomino obtained removing R P from P .

Enumeration of directed k-convex polyominoes

Now we present a general method, based on Proposition 7, to enumerate several statistics on families of directed convex polyominoes. This method contains 3 steps:

Step 1: Determine a combinatorial characterization of the cut λ and the two forests F e and F s associated with the considered class C of directed convex polyominoes;

Step 2: Determine the generating functions with respect to the studied statistics for all the cuts λ, and for all the trees of F e and F s associated with the class C;

Step 3: The generating function of the class C is then obtained by performing the composition of the generating function of the cuts with all the generating functions of the trees of F e and F s . This method is generic and very simple, and it allows us to obtain generating functions for several subclasses of directed convex polyominoes according to several different parameters, such as: the semiperimeter, the degree of convexity, the width, the height, the size of the last row/column and the number of corners in D/P D . Let us begin with a classical example. We will count directed convex polyominoes according to semi-perimeter, width and height. We point out that these results were first discovered by K. Y. Lin and S. J. Chang in [START_REF] Lin | Rigorous results for the number of convex polygons on the square and honeycomb lattices[END_REF] and then by M. Bousquet-Mélou in [START_REF] Bousquet-Mélou | Une bijection entre les polyominos convexes dirigés et les mots de Dyck bilatères[END_REF].

Proposition 12 ([15, 6]) The generating function of directed convex polyominoes according to the semiperimeter, the width and the height of the polyominoes is

xyz 2 √ (1-(x+y)z) 2 -4xyz 2 .
Proof: Let z, x, y take into account the semi-perimeter, the width and the height of the polyominoes, respectively. Let us apply the 3 steps of our method:

Step 1: According to Proposition 7, directed convex polyominoes are in bijection with triplets (F e , F s , λ) where: to each east step of λ is bijectively associated a tree of F e , except for the last east step of λ, and to each south step of λ is associated a trees of F s , except for the first south step. There is no constraint on the trees of F e and F s .

Step 2: The width (resp. height) of D is given by the number of cells of P D which are enlightened from north to south (resp. from east to west). By construction of Φ, the cells contributing to the width (resp. height) of D are associated with the nodes having an odd (resp. even) height in F e (resp. F s ) and with the nodes having an even (resp. odd) height in F s (resp. F e ). So we need the two generating functions T e and T s for the trees of F e and F s , respectively. The nodes at odd (resp. even) height in T e (resp. T s ) are labelled by xz and the nodes at even (resp. odd) height are labelled by yz. The two generating functions are obtained by solving the following system: T e = xz 1-Ts and T s = yz 1-Te , from which T e (x, y) =

1+(x-y)z- √ (1+(x-y)z) 2 -4xz 2
and T s (x, y) = T e (y, x). The generating function for the cut is G(e, s, z e , z s ) = xzeyzs 1-(e+s) , where z s and z e represent the first south step and the last east step of the cut, while e and s represent all the other east and south steps of the cut.

Step 3: The final generating function is :

G(T e , T s , z, z) = xyz 2 √ (1-(x+y)z) 2 -4xyz 2 . 2
The following statement gives a characterization of the class D ≤k , which will lead us to the desired generating function.

Proposition 13 Every directed k-convex polyomino D is uniquely determined by one of the two (mutually exclusive) situations: 1) a k-parallelogram polyomino P and a cut λ, which is a cut of P , or, 2) a flat k +1-parallelogram polyomino P , with degree of convexity k + 1, and a cut λ, which is a cut of P such that λ ⊆ λ R P , where the notation λ ⊆ λ R P is used to mean that the path λ R P is weakly above λ.

Our aim is to use the three steps of our method to obtain the generating function of directed k-convex polyominoes. However, since the characterization of the cut turns out to be quite complex, it will be easier to obtain the desired generating function by difference.

Let D - ≤k be the class of directed convex polyominoes which are bijective to triplets (F e , F s , λ) where λ is a generic cut, and F e and F s are forests with heights less than or equal to k, according to the mapping described in Proposition 7. Proposition 13 and the bound on the height of the forests ensure that D - ≤k is included in D ≤k . Now FD =k is the set of the flat directed convex polyominoes with degree of convexity k. The following result can be proved using Proposition 13 and the bijection Φ. Proposition 14 For any integer k ≥ 1, we have D - ≤k+1 = D ≤k FD =k+1 where is the disjoint union.

We just need to determine the generating functions for D - ≤k+1 and FD =k+1 .

Proposition 15 For any integer k ≥ 1, the generating function for D - ≤k is z 2 F k+1 F k+2 -zF k where z takes into account the semi-perimeter.

Proof: The g.f. for the cut is G(e, s) = z 2 1-(s+e) . Then, the desired result is G(T ≤k , T ≤k ).

2

Proposition 16 For any k ≥ 1, the generating function for FD =k+1 according to the semi-perimeter is

z 2 • z k+1 F 2k+3 2 • F k+2 (F k+3 -zF k+1 )
.

Proof: We will detail the 3 steps of our method:

Step 1: Let D be a flat directed polyomino with degree of convexity equal to k. Let us describe the trees of F e and F s of P D . From Lemma 11 we know that R P D is a non empty rectangle and I k = E. Let R (resp. C) be the row (resp. column) containing the cell I k-1 . By construction of Φ, the roots of F e (resp. F s ) are associated with the cells of the topmost (resp. rightmost) row (resp. column) of P D . Hence, the height of the trees depends on the position of their roots:

• if the root is on the left (resp. above) of C (resp. R) the height of the tree is less than or equal to k;

• if the root belongs to C (resp. R), the height is exactly equal to k + 1 (the two bounce paths have k + 1 changes of direction and are the image through φ -1 of chains d r and d u of F e and F s ); • if the root is on the right (resp. left) of C (resp. R), the height is less than equal to k + 1.

Let us now give a characterization of the cuts. In the cuts, we will label the east steps by e 1 (resp. e 2 ) if they are mapped onto trees with height less than or equal to k (resp. k + 1). Similarly, we will label the south steps by s 1 (resp. s 2 ) if they are mapped onto trees with height less than or equal to k (resp. k + 1). Moreover, the first south (resp. last east) step of the cut is labelled s 2 (resp. e 2 ). Since these two steps are not mapped onto a tree, at the end of the process, we will obtain a bad generating function G for the cut. The correct generating function is then obtained by multiplying G by zezs e2s2 . We can use this trick because all the cuts have at least one south step and one east step. Since D is flat, the cut contains two special steps u e and u s in the columns C and R, respectively. As D is exactly k + 1-convex, from Corollary 10 we have that R P D ∩ D is non empty. We also observe that in the cut u e precedes u s . Let p l , τ and p r be 3 paths such that p l • u e • τ • u s • p r is the cut λ. The path p l can be empty or it starts with an east step followed by any sequence of east/south steps. East steps are mapped onto trees having height less then or equal to k, so they are labelled by e 1 . South steps are mapped onto trees having height less then or equal to k +1, so they are labelled by s 2 . So, an unambiguous regular expression describing p l is 1 + e 1 (e 1 + s 2 ) * . For similar argument, a regular expression for p r is 1 + s 1 (s 1 + e 2 ) * . Consider now τ : all south and east steps are mapped onto trees with height less then or equal to k + 1, so τ is a word in e 2 and s 2 . Previously we have seen that there is at least one cell in R P D ∩ D, so τ should contain at least an occurrence of e 2 and s 2 . An unambiguous regular expression for τ is s * 2 e 2 (e 2 + s 2 ) * s 2 e * 2 . Now we just have to remark that the steps u e and u s are mapped onto trees having an height exactly equal to k + 1.

Step 2: The generating function G(e 1 , s 1 , e 2 , s 2 , u e , u s , z e , z s ) for the cut

p l • u e • τ • u s • p r is z e z s e 2 s 2 • 1 + e 1 1 -e 1 -s 2 • u e • e 2 s 2 (1 -e 2 ) • (1 -e 2 -s 2 ) • (1 -s 2 ) • u s • 1 + s 1 1 -s 1 -e 2 ,
which is equal to

1 1-e1-s2 • zezsueus 1-e2-s2 • 1 1-s1-e2
. The generating function for the trees associated with s 1 and e 1 (resp. s 2 and e 2 ) is T ≤k (resp. T ≤k+1 ), and the generating function for the trees associated with u e and u s is T =k+1 .

Step 3: The final generating function is G(T ≤k , T ≤k , T ≤k+1 , T ≤k+1 , T =k+1 , T =k+1 , z, z) and is equal to

T =k+1 1-T ≤k -T ≤k+1 2 • z 2 1-2T ≤k+1 = z 2 • z k+1 F 2k+3 2 • F k+2 (F k+3 -zF k+1 ) . 2
As a consequence of Propositions 14, 15 and 16 we have Proposition 17 For k = 0 the generating function for directed k-convex polyominoes is equal to z 2 •(1+z) 1-z , while for any k ≥ 1, the generating function for directed k-convex polyominoes according to the semiperimeter is equal to z

2 • F k+2 F 2k+3 2 • F 2k+2 .
Proof: We just observe that directed 0-convex polyominoes are precisely vertical and horizontal bars. For k ≥ 1, the result can be obtained as the difference of the generating functions of D - ≤k+1 and FD =k+1 . 2

Asymptotic behavior

It is now interesting to study some facts about the asymptotic behavior of the sequence (d n,≤k ) n,k of directed k-convex polyominoes with semi-perimeter n.

Proposition 18

The number d n,≤k of directed k-convex polyominoes with semi-perimeter n grows like

C k • 4 cos 2 (π/2k + 3) n • n , where C k is a k-dependent constant. Proof: Since D ≤k (z) = z 2 (F k+2 ) 2 (F 2k+2 ) (F 2k+3 ) 2
is a rational function, it is known that the asymptotic form of the coefficients is

d n,≤k = [z n ]D ≤k (z) ∼ C k •µ(k) n •n where C k is a k-dependent constant, µ(k) is given by 1/d 2k+3
, where d 2k+3 is the smallest real root of F 2k+3 . The fact that there is a double pole in D ≤k is responsible for the factor n. In [START_REF] De Bruijn | The average height of planted plane trees, Graph Theory and Computing[END_REF] the authors observe that the roots of F k (z) = 0 are (4 cos 2 (jπ/k)) -1 , for 1 ≤ j < k/2. In particular the reciprocals of the roots of F 2k+3 (z) = 0 are (4 cos 2 (jπ/2k + 3)), for 1 ≤ j ≤ k + 1. With basic calculus one can easily prove that the biggest reciprocal occurs for j = 1, and so µ(k) = 4 cos 2 (π/2k + 3).

2

Proposition 19 Let D ≤k and D be the generating functions of directed k-convex polyominoes and of directed convex polyominoes with respect to the semi-perimeter, respectively. Then, lim k→+∞ D ≤k = D.

Conclusions and further work

In this paper we present a general method to calculate generating functions for different families of directed convex polyominoes with respect to several statistics, including the degree of convexity. This allows to solve the problem of enumerating directed k-convex polyominoes, which was presented in [START_REF] Battaglino | The number of k-parallelogram polyominoes[END_REF] as an open problem. Our idea is that, for any statistic on directed convex polyominoes that can be read on the associated trees or on the cut, then our method can suitably be applied to obtain a generating function according to these parameters. We believe that our method can be applied in several different enumeration problems related with directed convex polyominoes, mainly because in Proposition 7 the sets of trees and the cut are not constrained. Moreover, Proposition 7 can be used to write out efficient algorithms to generate directed convex polyominoes with different combinations of fixed constraints. As a matter of fact, we used our method to implement a code (i) in the open-source software Sage [START_REF]The Sage-Combinat community, Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics[END_REF][START_REF] Stein | Sage Mathematics Software (Version 6.4.beta6)[END_REF] for the enumeration of directed convex polyominoes. The code will be soon available in a future Sage release.

Moreover, we would like to point out that the main bijection and the general approach can be expressed using the formalism of the theory of Species [START_REF] Bergeron | Combinatorial Species and Tree-Like Structures[END_REF]. For example, by using our bijection, we can define the species of directed convex polyominoes by X 2 • k≥0 (A L + A L ) k where X, and A L are respectively the species of singletons and trees.

There are several guidelines for further research. One is to study the probability distributions of the convexity degree for directed convex polyominoes with a fixed semi-perimeter. Moreover, directed convex polyominoes can be seen as special kind of tree-like tableaux and the cut represents the states of the PASEP (i) An implementation of k-directed polyominoes in Sage: http://trac.sagemath.org/ticket/17178 . (cf. [START_REF] Aval | Tree-like tableaux[END_REF] for tree-like tableaux context and definitions). So, our aim is to generalize Proposition 7 for treelike tableaux. In tree-like tableaux T associated with directed convex polyominoes, the area counts the number of some patterns in the permutation associated with T . We can try to obtain some generating function counting the area statistic.

Fig. 2 :

 2 Fig. 2: A directed convex polyomino D and its associated parallelogram polyomino PD. We observe that the bounce paths joining two cells b and c are slightly different from the paths from b to c, due to the presence of the tails. This is just a precaution to ensure that the two bounce paths are always different, and it will not affect the computation of the degree of convexity. The minimal bounce path joining b to c (denoted by m b,c ) is the bounce path joining b to c with the minimal number of changes of direction. If the two bounce paths joining b to c have the same number of changes of direction, by convention we define the minimal bounce path joining b to c to be the bounce path r b,c . Proposition 1 Let D be a directed convex polyomino. Given k ≥ 1, then D is a directed k-convex polyomino if and only if S can be connected to each cell of D by means of a path having at most k changes of direction.

Lemma 2 Fig. 3 :

 23 Fig. 3: (a) The bounce paths joining two cells of a directed convex polyomino; (b), (c) The bounce paths of a parallelogram polyomino.

Fig. 4 :

 4 Fig. 4: The bijections Φ and Ψ.

Fig. 5 :

 5 Fig. 5: The simple paths dr and du associated with the bounce paths r(P ) and u(P ) respectively.

= e 2 sese 3 s 2 Fig. 6 :

 26 Fig.6: A directed convex polyomino with the corresponding triplet (Fe, Fs, λ).

Fig. 7 :

 7 Fig. 7: The degrees of the cells in a flat and a non flat parallelogram polyomino.

Corollary 8 Proposition 9

 89 Let D be a directed convex polyomino such that the degree of convexity of P D is k. The sequence (I h ) h has length k. If D is flat then I k = E; otherwise I k = E and I k is the cell where the minimal bounce path m of P D has the last change of direction. Let D be a directed convex polyomino. Let us consider the cells

Fig. 8 :

 8 Fig. 8: A directed convex polyomino D where the paths p l , τ and pr of λD are highlighted.

Acknowledgements

The authors are grateful to Tony Guttmann and Mireille Bousquet-Mélou for their help in the writing process of this article.


Martin Rubey
email: martin.rubey@tuwien.ac.at

Bruce W Westbury
email: bruce.westbury@warwick.ac.uk

Combinatorics of symplectic invariant tensors

Keywords: invariant tensors, cyclic sieving phenomenon, matchings, classical groups Dedicated

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The primary motivation of this article is a specific example of the cyclic sieving phenomenon, as introduced by Reiner, Stanton and White [START_REF] Reiner | The cyclic sieving phenomenon[END_REF], concerning the set X(r, n) of (n + 1)-noncrossing perfect matchings of {1, . . . , 2r}. These are perfect matchings that do not contain any set of (n + 1) pairs (a 1 , b 1 ), . . . , (a n+1 , b n+1 ) with a

1 < • • • < a n+1 < b 1 < • • • < b n+1 .
A standard visualisation of a perfect matching is obtained by placing the numbers from 1 to 2r in this order on a circle and connecting two numbers by a straight edge if they form a pair in the matching. Using this visualisation, a perfect matching is (n + 1)-noncrossing if at most n edges cross mutually. The set X(r, n) carries a natural action of the cyclic group of order 2r, given by ρ : i → i (mod 2r) + 1, i.e., the rotation map.

With this definition we can state what might be taken as the main theorem of this article:

Theorem. Let P (q) = T q maj T ,
where the sum is over all n-symplectic oscillating tableaux of length 2r and weight 0 and maj T is the sum of the positions of the descents in T , as defined in [START_REF] Rubey | Descent sets for symplectic groups[END_REF].

Then the triple X(r, n), ρ, P (q) exhibits the cyclic sieving phenomenon.

However, we would like to stress that this is merely a by-product of the approach taken in this article to the invariant theory of the classical groups, aiming at tying together their representation theory and combinatorics in a concrete fashion.

In our main example we consider tensor powers of the defining representation V of the symplectic group Sp(2n), the group acting diagonally. The symmetric group S r also acts on ⊗ r V , by permuting tensor positions. This action is inherited by the subspace of ⊗ r V which is invariant under the action of Sp(2n).

An effective method to understand both the tensor powers ⊗ r V and their invariant subspaces is to use diagram categories. In the case at hand this is a specialisation D Sp(2n) of the Brauer category. The objects of this category are the natural numbers and Hom D Sp(2n) (r, s) is the vector space whose basis is the set of perfect matchings of {1, . . . , r + s}, with a natural composition, see Section 2.

The connection to the tensor powers of the defining representation of Sp(2n) is established by considering the category T Sp(2n) of invariant tensors of the defining representation of the symplectic group, and a certain functor ev Sp(2n) from the diagram category D Sp(2n) to T Sp(2n) , see Definition 2.1.

The first fundamental theorem, Weyl [21, Theorem (6.1A)], due to Brauer [START_REF] Brauer | On algebras which are connected with the semisimple continuous groups[END_REF], is equivalent to the statement that this functor is full, that is, surjective on morphisms. What is traditionally named second fundamental theorem is a description of the kernel of the linear map from Hom D Sp(2n) (r, s) to Hom T Sp(2n) (r, s) induced by ev Sp(2n) . We provide the following explicit formulation, which is also a key ingredient for the proof of Theorem 3.5.

Theorem. Let Pf ∈ Hom D Sp(2n) 0, 2(n + 1) be the sum of all perfect matchings of {1, . . . , 2(n + 1)} and let Pf (n) be the 'pivotal symmetric' † ideal generated by Pf. Then the categories D Sp(2n) /Pf (n) and T Sp(2n) are isomorphic. Moreover, the set X(r, n) is a basis of Hom D Sp(2n) /Pf (n) (0, 2r).

Remarkably, a well-known result due to Sundaram [START_REF] Sundaram | On the combinatorics of representations of the symplectic group[END_REF] states that the cardinality of X(r, n) equals the dimension of Hom Sp(2n) (C, ⊗ 2r V ). In fact, Sundaram also computed the Frobenius character of this representation, and, more generally, of Hom Sp(2n) W (µ), ⊗ r V for any irreducible representation W (µ) of the symplectic group Sp(2n).

We note that the same categorical setup was employed by Lehrer and Zhang [START_REF] Lehrer | The Brauer Category and Invariant Theory[END_REF] to show that Pf (n) restricted to the Brauer algebra Hom D Sp(2n) (r, r) is in fact generated as a two-sided ideal by a single element.

Fundamental theorems

The theorems of this section connect the Brauer category with the invariant theory of the defining representation of the symplectic group by providing an explicit isomorphism of categories.

First we recall the definition of the Brauer category. Let D(r, s) be the set of perfect matchings on [r] [s]. In particular, D(r, s) = ∅ if r + s is odd. An element of D(r, s) is visualised as a set of (r + s)/2 strands drawn in a rectangle, with r endpoints on the top edge of the rectangle and s endpoints on the bottom edge.

The composition of two diagrams x ∈ D(r, s) and y ∈ D(s, t) is obtained by identifying the points on the bottom edge of x with the points on the top edge of y. Let c(x, y) be the number of closed loops in the resulting diagram and let x • y ∈ D(r, t) be the perfect matching obtained by removing all closed loops.

The Brauer category D Br has objects N. Its morphisms Hom D Br (r, s) are given by the free Z[δ]-module with basis D(r, s). The composition of morphisms is defined on basis elements by

x • y = δ c(x,y) x • y (1)
and extended bilinearly. The endomorphism algebra Hom D Br (r, r) is the Brauer algebra, which will be denoted by D r from now on. Finally, let D Sp(2n) be the specialisation of D Br obtained by applying the homomorphism

Z[δ] → C, δ → -2n.
The Brauer category also has a tensor product. The tensor product x ⊗ y of two diagrams x and y is obtained by putting the diagrams side-by-side, identifying the right hand edge of x with the left hand edge of y.

We now turn to the definition of the category of invariant tensors T Sp(2n) . Recall that the symplectic group Sp(V ) is the group of linear transformations of a 2n-dimensional complex vector space V that preserve a non-degenerate skew-symmetric bilinear form , . However, the categorical machinery we use requires that a symmetric bilinear form is preserved. Therefore, we regard V as an odd vector space, which has precisely the desired effect. Among the further consequences we remark that in this convention the dimension of V is -2n and symmetric and exterior powers are interchanged.

Let {b 1 , . . . , b 2n } be a basis of V and let { b1 , . . . , b2n } be the dual basis, so bi , b j = δ i,j . Let T Sp(2n) be the category whose objects are again the natural numbers and whose morphisms Hom T Sp(2n) (r, s) are the equivariant maps

Hom Sp(2n) (⊗ r V, ⊗ s V ) = {φ : ⊗ r V → ⊗ s V | g • φ(v) = φ(g • v), g ∈ Sp(2n)}. Note that the invariant subspace of ⊗ r V is precisely Hom T Sp(2n) (0, r) = Hom Sp(2n) (C, ⊗ r V ).
The connection between D Sp(2n) and T Sp(2n) is established by a functor we now define:

Definition 2.1. Let ev Sp(2n) be the evaluation functor D Sp(2n) → T Sp(2n) . Explicitly, ev Sp(2n) sends the object r ∈ N to ⊗ r V . It is defined on the generators by

ev Sp(2n) = u ⊗ v → -v ⊗ u ev Sp(2n) = 1 → i b i ⊗ bi ev Sp(2n) = u ⊗ v → u, v .
and is then uniquely determined by the following three properties

• it is a functor, so ev Sp(2n) (x • y) = ev Sp(2n) (x) • ev Sp(2n) (y),
• it respects tensor products, so ev Sp(2n) (x ⊗ y) = ev Sp(2n) (x) ⊗ ev Sp(2n) (y),

• it is linear.

The first fundamental theorem for the symplectic group can now be stated as follows:

Theorem 2.2.

[1],[21, Theorem (6.1A)] For all n > 0 the functor ev Sp(2n) : D Sp(2n) → T Sp(2n) is full.

In the remainder of this section we provide an explicit description of the kernel of ev Sp(2n) as an ideal in the Brauer category. We will denote this ideal with Pf (n) because of its intimate connection to the Pfaffian. Moreover we obtain a simple basis for the vector space Hom D Sp(2n) /Pf (n) (0, r). This basis is preserved by rotation, which we will use in Section 3 to exhibit a cyclic sieving phenomenon.

The fundamental object involved is an idempotent E(n + 1) of the Brauer algebra D n+1 for which we have ev Sp(2n) E(n + 1) = 0. This element can be characterised as follows.

Let ρ be the one dimensional representation of D n+1 which on diagrams is given by

ρ(x) = 1 if pr(x) = n + 1 0 if pr(x) < n + 1,
where pr(x) is the propagating number of a diagram x, i.e., the number of strands connecting a point on the top edge with a point on the bottom edge.

The element E(n + 1) of D n+1 is determined, up to scalar multiple, by the properties

xE(n + 1) = ρ(x)E(n + 1) = E(n + 1)x. (2)
It follows that E(n+1) can be scaled so that it is idempotent and these properties now determine E(n+1).

It is clear that E(n + 1) is a central idempotent and that its rank equals one. We will give two constructions of E(n + 1). The first is as a simple linear combination of diagrams.

Definition 2.3.

E(n + 1) = 1 (n + 1)! x∈D(n+1,n+1)
x Lemma 2.4. For δ = -2n, the element E(n + 1) in Definition 2.3 satisfies the properties (2).

Proof: If pr(x) = n + 1 then x acts as a permutation on the set of diagrams D(n + 1, n + 1), so this case is clear.

Let J r (p) be the ideal of the Brauer algebra D r generated by the diagrams with propagating number at most p. The elements u i , 1 ≤ i ≤ n generate the ideal J n+1 (n) so it is sufficient to show that u i E(n + 1) = 0 and E(n + 1)u i = 0 for 1 ≤ i ≤ n. We will now show that u i E(n + 1) = 0. The case

E(n + 1)u i = 0 is similar. It is clear that u i E(n + 1
) is a linear combination of diagrams which contain the pair (i, i + 1). Hence it is sufficient to show that the coefficient of each of these diagrams is 0. Let x be a diagram which contains the pair (i, i + 1). The set {y ∈ D(n + 1, n + 1) : u i y = x} has cardinality 2n and there is precisely one diagram z with u i z = δx. Therefore the coefficient of x is δ + 2n, which vanishes for δ = -2n.

The set of 2n diagrams is constructed as follows. The diagram x contains n pairs other than (i, i + 1). For each of these pairs we construct two elements of the set. Take the pair (u, v), and replace the two pairs (i, i + 1) and (u, v) by (i, u) and (i + 1, v) and by (i + 1, u) and (i, v) keeping all the remaining pairs. However it is not clear from this construction that ev Sp(2n) E(n+1) = 0. We now give an alternative construction which does make this clear. Definition 2.5. For 1 ≤ i ≤ n define u i ∈ D(n + 1, n + 1) to consist of the pairs (a, a ) for a / ∈ {i, i + 1} together with the pairs (i, i + 1) and (i , (i + 1) ) and define s i ∈ D(n + 1, n + 1) to consist of the pairs (a, a ) for a / ∈ {i, i + 1} together with the pairs (i, (i + 1) ) and (i , i + 1):

u i = i -1 n -i -1 s i = i -1 n -i -1 Definition 2.6. For k ∈ Z and 1 ≤ i ≤ n define R i (k) ∈ D n+1 by R i (k) = 1 k + 1 1 + ks i - 2k δ + 2k -2 u i
Proposition 2.7. These elements satisfy

R i (h)R i+1 (h + k)R i (k) = R i+1 (k)R i (h + k)R i+1 (h) R i (h)R j (k) = R j (k)R i (h) for |i -j| > 1
Proof: The second relation is clear. The first relation is known as the Yang-Baxter equation and is checked by a direct calculation. This calculation can be carried out using generators and relations or by using a faithful representation.

Definition 2.8. The element E(n + 1) is defined recursively by

E(n + 1) = E(n)R n (n)E(n)
There are other equivalent definitions, for example,

E(n + 1) = E(n)R n (n)R n-1 (n -1) . . . R 1 (1) E(n + 1) = R 1 (1)R 2 (2) . . . R n (n)E(n)
The proof that these definitions are equivalent and the proof that for δ = -2n this element satisfies the properties (2) are both calculations using the Yang-Baxter equation Proposition 2.7.

Proposition 2.9.

ev Sp(2n) (E(n + 1)) = 0

Proof: Because ev Sp(2n) is a functor, ev Sp(2n) (E(n + 1)) is an idempotent in T Sp(2n) , too. Moreover, ev Sp(2n) preserves the trace of morphisms. Recall that the (diagrammatic) trace tr n of a diagram α in D n is defined as The rank of an idempotent is equal to its trace so it is sufficient to show that tr n+1 E(n + 1) = 0 for δ = -2n.

η 2n • (α ⊗ id n ) • η *
We now compute the trace by expanding R n (n) = 1 n+1 (1 + ns n + nu n ):

tr n+1 E(n + 1) = 1 n + 1 (δ + n + n) tr n+1 E(n).
Substituting -2n for δ gives tr n+1 E(n + 1) = 0.

We will now describe the kernel of ev Sp(2n) in terms of diagrammatic Pfaffians. Note that for r, s = n + 1 and f = ∅ we have, by Definition 2.3, E(n + 1) = 1 (n+1)! Pf(∅). Definition 2.11. For r, s ≥ 0, the subspace Pf (n) (r, s) in the ideal Pf (n) of D Sp(2n) is spanned by the set

Pf (n) (r, s) = {Pf(f ) : f a perfect matching of a subset of [r] [s] of cardinality r + s -2(n + 1) }.
Definition 2.12. Let ev Sp(2n) : D Sp(2n) /Pf (n) → T Sp(2n) be the functor that factors ev Sp(2n) through the quotient.

We can now state the main theorem of this section, also known as the second fundamental theorem for the symplectic group: Theorem 2.13. The functor ev Sp(2n) : D Sp(2n) /Pf (n) → T Sp(2n) is an isomorphism of categories.

Proof: Since ev Sp(2n) is obviously bijective on objects and full by the first fundamental theorem, it is sufficient to show dim Hom D Sp(2n) /Pf (n) (r, s) ≤ dim Hom T Sp(2n) (r, s).

This is achieved by combining Lemma 2.14, Lemma 2.16, Theorem 2.18 and Lemma 2.19 below.

We first restrict our attention to the invariant tensors:

Recall that if ρ : S r → End(U ) is a representation of S r then the Frobenius character ch(U ) is the homogeneous symmetric function of degree r given by

ch(U ) = 1 r! π∈Sr tr ρ(π)p λ(π)
where p λ is the power sum symmetric function and λ(π) is the cycle type of π.

The fake degree, fd, is a linear map from symmetric functions to polynomials in q. On the basis of Schur functions it is given by fd(s λ ) =

T q maj(T )
where the sum is over standard tableaux of shape T and maj(T ) is the major index of the tableau T .

A general technique to obtain a cyclic sieving polynomial P (q) is provided by the following result from [START_REF] Westbury | Invariant tensors and the cyclic sieving phenomenon[END_REF]: Theorem 3.2. Let U be a representation of S r and let X ⊂ U be a basis which is permuted by the long cycle c. Then X, c, P (q) exhibits the cyclic sieving phenomenon, where

P (q) = fd ch(U ).
The most straightforward application of this theorem is to permutation representations of S r . Here the representation and the basis are given so it remains to determine the Frobenius character and its fake degree polynomial. In general, the action of the symmetric group on the space of invariant tensors is not a permutation representation, that is, there is no basis of the space of invariant tensors that is permuted by the action of S r .

As mentioned in the introduction, the Frobenius character of Hom Sp(V ) W (µ), ⊗ r V was obtained in [START_REF] Sundaram | On the combinatorics of representations of the symplectic group[END_REF] (using combinatorics) and in [START_REF] Tokuyama | Highest weight vectors associated with some branchings[END_REF] (using representation theory). For the special case of the invariant tensors, a geometric proof can be found in Procesi [START_REF] Procesi | Lie groups. Universitext. An approach through invariants and representations[END_REF]Equation 11.5.1.6].

Lemma 3.3.

ch Hom T Sp(2n) (0, 2r) = λ 2r columns of even length (λ)≤2n

s λ t .
Remark 3.4. The partitions indexing the Schur functions appearing in the Frobenius character are all transposed, since we defined V to be an odd vector space.

Theorem 3.5. Let X = X(r, n) be the set of (n + 1)-noncrossing perfect matchings on {1, . . . , 2r} and let ρ be the rotation map acting on X. Let

P (q) = λ 2r columns of even length (λ)≤2n fd s λ t
Then the triple X, ρ, P (q) exhibits the cyclic sieving phenomenon. The two extreme cases of Theorem 3.5, n = 1 and n ≥ r are known. Putting n = 1, X(r, 1) is the set of non-crossing perfect matchings. The corresponding cyclic sieving phenomenon can be found in [START_REF] Rhoades | Cyclic sieving, promotion, and representation theory[END_REF] and [START_REF] Petersen | Promotion and cyclic sieving via webs[END_REF]. For n ≥ r, X(r, n) is the set of all perfect matchings. The Frobenius character of this permutation representation was expanded by Littlewood into Schur functions. Using • for plethystic composition, we have h r • h 2 = λ 2r rows of even length s λ . Remark 3.6. Let T be an oscillating tableau. The descent set of T is defined in [START_REF] Rubey | Descent sets for symplectic groups[END_REF] and is denoted by Des(T ). The major index of T is

maj(T ) = i∈Des(T ) i
Then the main result of [START_REF] Rubey | Descent sets for symplectic groups[END_REF] is that

P (q) = T q maj(T )
where the sum is over n-symplectic oscillating tableaux of length 2r and weight 0.

Theorem 3.5 can be generalised. Informally, we consider the set of k-regular graphs (with loops prohibited but multiple edges allowed) on r vertices which are also (n + 1)-noncrossing. More precisely, consider {1, . . . kr} as a cyclically ordered set, partitioned into r blocks of k consecutive elements each. Let X = X(r, n, k) be the set of (n + 1)-noncrossing perfect matchings of {1, . . . kr} such that there is no pair contained in a block and if two pairs cross then the four elements are in four distinct blocks, see Figure 1 for an example. Finally, let ρ be rotation by k points, i.e., ρ(i) = i + k -1 (mod kr) + 1.

For n > kr, the set X(r, n, k) is independent of n and can be identified with the set of k-regular graphs with multiple edges allowed but loops prohibited. These k-regular graphs would normally be considered as a permutation representation of S r acting by permuting the vertices. Here the action of S r is a linear action on the space with basis X(r, n, k). Example 3.11 below shows that these actions are different. Lemma 3.7. The invariant tensors corresponding to the diagrams X(r, n, k) form a basis of the space of Sp(2n)-invariants in the r-th tensor power of the k-th symmetric power of the defining representation of Sp(2n).

The Frobenius character of this representation is given by an application of [START_REF] Westbury | On enumeration in classical invariant theory[END_REF]Theorem 1]. Lemma 3.8. The Frobenius character of the space of Sp(2n)-invariants in the r-th tensor power of the k-th symmetric power of the defining representation of Sp(2n) is

λ kr columns of even length (λ)≤2n h r X • e k (Y ) , s λ t (Y ) Y (3)
where e k is the k-th elementary symmetric function and , Y denotes the scalar product of symmetric functions with respect to the alphabet Y .

Theorem 3.9. Let X = X(r, n, k) and let ρ be the rotation map. Define P (q) to be the fake degree of the symmetric function [START_REF] Gavarini | A Brauer algebra-theoretic proof of Littlewood's restriction rules[END_REF]. Then (X, ρ, P ) exhibits the cyclic sieving phenomenon.

The case k = 1 is Theorem 3.5 and the case k = 2 is related to the invariant tensors of the adjoint representation in [START_REF] Hanlon | On the decomposition of the tensor algebra of the classical Lie algebras[END_REF]. The case n = 1 is implicit in [START_REF] Frenkel | Canonical bases in tensor products and graphical calculus for U q (sl 2 )[END_REF] and the case n = 2 is related to the C 2 webs in [START_REF] Kuperberg | Spiders for rank 2 Lie algebras[END_REF].

Instead of the k-th symmetric power of V we can also consider the k-th fundamental representation of Sp(2n). Again using [20, Theorem 1] we obtain the following expression for the Frobenius character of its tensor powers.

Lemma 3.10. The Frobenius character of the space of Sp(2n)-invariants in the r-th tensor power of the k-th fundamental representation of Sp(2n) is

|λ|≤kr columns of even length (λ)≤2n h r X • (h k -h k-2 )(Y ) , s λ t (Y ) Y (4)
Note that in general, this space cannot have a basis invariant under cyclic rotation. For example, for n = 1, k = 3 and r = 2 its Frobenius character evaluates to s 1,1 with fake degree polynomial equal to q, which is not a cyclic sieving polynomial.

However, let us compare the two Frobenius characters for n > kr.

Setting H = 1 + h 1 + h 2 + • • • we obtain for the symmetric powers h r X • e k (Y ) , H(h 2 (Y )) Y (5)
whereas for the fundamental representation the expression becomes

h r X • (h k -k k-2 )(Y ) , H(h 2 (Y )) Y (6)
For n > kr, the set X(r, n, k) is independent of n and can be identified with the set of k-regular graphs with multiple edges allowed but loops prohibited. This is a species whose Frobenius character is given by equation ( 6), see Travis [START_REF] Travis | Graphical enumeration: A species-theoretic approach[END_REF].

The action of the symmetric group in the first case is defined using a sign and is therefore not a permutation representation, as illustrated by the following example.

Partitions and directed matchings

The discussion in the previous sections has been about the Brauer category and the categories of invariant tensors for the vector representation of Sp(2n). In this section we discuss two other examples where we have a diagram category which is related to a sequence of categories of invariant tensors.

In the first example we consider the linear representation V of the symmetric group S n associated to its defining representation. The diagram category in this case is the partition category studied in [START_REF] Halverson | Partition algebras[END_REF].

Let I(r, n) = Hom Sn (C, ⊗ r V ) be the space of invariant tensors with the action of S r and let X(r, n) be the set of set partitions of {1, . . . , r} into at most n blocks. Then there is a map X(r, n) → I(r, n) such that the image is a basis. Furthermore this basis is preserved by the action of S r . It follows that the Frobenius character is the homogeneous component of degree r in h n • H, where

H = 1 + h 1 + h 2 + • • • .
As in the case of the Brauer category, this result can be generalised, by considering the tensor powers of the k-th symmetric power of the defining representation. The resulting set X(r, n, k) is then the set of multiset partitions into at most n blocks of the multiset {1, . . . , 1, 2, . . . , 2, . . . , r, . . . , r}, each label occuring precisely k times. The symmetric group S r acts on this set by permuting the labels. The Frobenius character can be obtained using [START_REF] Westbury | On enumeration in classical invariant theory[END_REF]Theorem 1] or alternatively with the calculus of species and is given by h r X • h k (Y ) , h n (H(Y )) Y .

In the second example we consider the adjoint representation V of the general linear group GL(n). In this case the diagrams are Brauer diagrams in which every edge is directed.

For n ≥ 2r let X(r) be the set of permutations with the conjugation action of S r . Its Frobenius character is obtained in [START_REF] Stanley | The stable behavior of some characters of SL(n, C)[END_REF] using character calculations. Our methods give a simple proof. The Frobenius character is Let I(r, n) = Hom GL(n) (C, ⊗ r V ) be the space of invariant tensors with the action of S r . Considering the diagrams we obtain the new result that the Frobenius character of this representation is λ r (λ)≤n s λ * s λ However, for n < 2r it is an open problem to determine a set X(r, n) with a map X(r, n) → I(r, n) such that the image is a basis and is preserved by the action of the long cycle. So we are not able to exhibit an example of the cyclic sieving phenomenon in this case.

2n

  where η 2n ∈ D(0, 2n) is the diagram that consists of n nested arcs. The following properties are easily verified. tr n+1 (α ⊗ id 1 ) = δ tr n α tr n+1 αs n β = tr n αβ tr n+1 αu n β = tr n αβ for α, β diagrams on n strings.

Definition 2 . 10 ([ 3 ,

 2103 Definition 3.4 (b)]). Let S be a 2(n + 1)-element subset of [r] [s] and let f be a perfect matching of [r] [s] \ S. Then the diagrammatic Pfaffian of order 2(n + 1) corresponding to f is Pf(f ) = s a perfect matching of S (s ∪ f ).

Fig. 1 :

 1 Fig. 1: The six elements of X(4, 2, 2).

Example 3 . 11 .

 311 Putting k = 2 and r = 6, the formula (5) for invariant tensors gives 1 72 (13p

  λ * s λ where * denotes the Kronecker or inner product.

  1 6 + 12p 21 4 + 63p 2 2 1 2 + 54p 2 3 + 4p 31 3 -12p 321 + 28p 3 2 + 18p 41 2 + 36p 42 + 36p 6 ) (7) + 24p 21 4 + 63p 2 2 1 2 + 54p 2 3 + 4p 31 3 + 12p 321 + 28p 3 2 + 18p 41 2 + 36p 42 + 36p 6 )

	and the formula (6) for regular graphs gives
	1 72	(13p 1 6

† We define pivotal and symmetric ideals in[START_REF] Rubey | A combinatorial approach to classical representation theory[END_REF], and restrict ourselves here to down-to-earth language in Definitions 2.10 and 2.11.

Lemma 2.14. We have isomorphisms of vector spaces Hom D Sp(2n) /Pf (n) (r, s) ∼ = Hom D Sp(2n) /Pf (n) (0, r + s) Hom T Sp(2n) (r, s) ∼ = Hom T Sp(2n) (0, r + s).

Let us recall an indexing set for the basis of Hom T Sp(2n) (0, r): Definition 2.15. An n-symplectic oscillating tableau of length r (and final shape ∅) is a sequence of partitions

such that the Ferrers diagrams of two consecutive partitions differ by exactly one cell and every partition µ i has at most n non-zero parts.

Lemma 2.16. Hom T Sp(2n) (0, ⊗ r V ) has a basis indexed by n-symplectic oscillating tableaux.

Proof: This follows immediately from the branching rule for tensoring the defining representation with an irreducible representation of Sp(2n), see [START_REF] Littlewood | Products and plethysms of characters with orthogonal, symplectic and symmetric groups[END_REF]Theorem II].

Next we exhibit a set of diagrams that span Hom D Sp(2n) /Pf (n) (0, r). In fact, this is the key observation.

Definition 2.17. Let d be a diagram in D(0, r). Then an n-crossing in d is a set of n distinct strands such that every pair of strands crosses, i.e., d contains strands

Theorem 2.18. The (n + 1)-noncrossing diagrams form a basis of Hom D Sp(2n) /Pf (n) (0, r).

Proof: We only need to show that the set spans. For each f we write Pf(f ) as a rewrite rule. The term that is singled out is the perfect matching of S in which every pair of strands crosses. The diagrams which cannot be simplified using these rewrite rules are the (n + 1)-noncrossing diagrams. The procedure terminates because the number of pairs of strands which cross decreases.

We can now use a bijection due to Sundaram [START_REF] Sundaram | On the combinatorics of representations of the symplectic group[END_REF]Lemma 8.3] to finish the proof of our main theorem.

Lemma 2.19. For all n and r there is a bijection between the set of n-symplectic oscillating tableaux of length r and the set of (n + 1)-noncrossing diagrams in D(0, r).

Cyclic sieving phenomenon

We now use the results obtained so far to exhibit instances of the cyclic sieving phenomenon: Definition 3.1. Let X be a finite set and let ρ be a cyclic group of order r acting on X. Let P (q) be a polynomial with non-negative integer coefficients such that

where ζ is a primitive r-th root of unity. Then the triple X, ρ, P (q) exhibits the cyclic sieving phenomenon.