Jean-Christophe Aval

Adrien Boussicault

Mathilde Bouvel

Matteo Silimbani

COMBINATORICS OF NON-AMBIGUOUS TREES

Keywords: 2010 Mathematics Subject Classification. 05A05, 05A10, 05A15, 05A19 Trees, posets, parallelogram polyominoes, tree-like tableaux, Bessel function, permutations excedances

come

Introduction

It is well known that the Catalan numbers C n = 1 n+1 2n n enumerate many combinatorial objects, such as binary trees and parallelogram polyominoes. Several bijective proofs in the literature show that parallelogram polyominoes are enumerated by Catalan numbers, the two most classical being Delest-Viennot's bijection with Dyck paths [START_REF] Delest | Algebraic languages and polyominoes enumeration[END_REF] and Viennot's bijection with bicolored Motzkin paths [START_REF] Delest | Algebraic languages and polyominoes enumeration[END_REF].

In this paper we demonstrate a bijection -which we believe is more natural -between binary trees and parallelogram polyominoes. In some sense, we show that parallelogram polyominoes may be seen as two-dimensional drawings of binary trees. This point of view gives rise to a new family of objects -we call them non-ambiguous trees -which are particular compact embeddings of binary trees in a grid.

The tree structure of these objects leads to a hook formula for the number of non-ambiguous trees with a given underlying tree. Unlike the classical hook formula for trees due to Knuth (see [START_REF] Knuth | The art of computer programming[END_REF], §5.1.4, Exercise 20), this one is defined on the edges of the tree.

Non-ambiguous trees are in bijection with permutations such that all their (strict) excedances stand at the beginning of the permutation word. Ehrenborg and Steingrímsson in [START_REF] Ehrenborg | The excedance set of a permutation[END_REF] give a closed formula (involving Stirling numbers of the second kind) for the number of such permutations. We show that this formula can be easily proved using non-ambiguous trees and a variation of the insertion algorithm for tree-like tableaux introduced in [START_REF] Aval | Tree-like tableaux[END_REF]. Indeed, non-ambiguous trees can also be seen as a subclass of tree-like tableaux, objects defined in [START_REF] Aval | Tree-like tableaux[END_REF] and that are in bijection with permutation tableaux [START_REF] Steingrímsson | Permutation tableaux and permutation patterns[END_REF] or alternative tableaux [START_REF] Nadeau | The structure of alternative tableaux[END_REF][START_REF] Viennot | Alternative tableaux, permutations and partially asymmetric exclusion process[END_REF].

A particular subclass of non-ambiguous trees leads to unexpected combinatorial interpretations. We study complete non-ambiguous trees, defined as non-ambiguous trees such that their underlying binary tree is complete, and show that their enumerating sequence is related to the formal power series of the logarithm of the Bessel function of order 0. This gives rise to new combinatorial interpretations of some identities due to Carlitz [START_REF] Carlitz | A sequence of integers related to the Bessel functions[END_REF], and to the proof of a related identity involving Catalan numbers, which had been conjectured by P. Hanna.

The paper is organized as follows: in Section 2 we define non-ambiguous trees. Then, in Section 3 we give the enumeration of non-ambiguous trees satisfying certain constraints: those contained in a given rectangular box, and those with a fixed underlying tree. Section 4 introduces the family of complete non-ambiguous trees, studies the relations between this family and the Bessel function, and proves combinatorial identities involving Catalan numbers and the sequence enumerating complete non-ambiguous trees. In Section 5 we describe our new bijection between binary trees and parallelogram polyominoes. To conclude, we present in Section 6 some perspectives related to our study.

Definitions and notations

In this paper, trees are embedded in a bidimensional grid N × N. The grid is not oriented as usual: the x-axis has south-west orientation, and the y-axis has south-east orientation, as shown on Figure 1. Every x-oriented (resp. y-oriented) line will be called column (resp. row). Each column (resp. row) on this grid is numbered with an integer corresponding to its y (resp. x) coordinate. A vertex v located on the intersection of two lines has the coordinate representation: (X(v), Y (v)).

A non-ambiguous tree may be seen as a binary tree embedded in the grid in such a way that its edges may be recovered from the embedding of its vertices in the grid (Figure 2). In other words, the vertices determine the tree without ambiguity, whence the name of these objects.

Formally, a non-ambiguous tree of size n is a set A of n points (x, y) ∈ N × N such that:

(1) (0, 0) ∈ A; we call this point the root of A;

(2) given a non-root point p ∈ A, there exists one point q ∈ A such that Y (q) < Y (p) and X(q) = X(p), or one point r ∈ A such that X(r) < X(p), Y (r) = Y (p), but not both (which means that the pattern is avoided); (3) there is no empty line between two given points: if there exists a point p ∈ A such that X(p) = x (resp. Y (p) = y), then for every x ′ < x (resp. y ′ < y) there exists q ∈ A such that X(q) = x ′ (resp. Y (q) = y ′ ). Figure 3 shows some examples and counterexamples of non-ambiguous trees. It is straightforward that a non-ambiguous tree A has a tree structure: except for the root, every point p ∈ A has a unique parent, which is the nearest point q preceding p in the same row (resp. column). In this case, we will say that p is the right child (resp. left child ) of q. In this paper, we orient every edge of a tree from the root to the leaves. We shall denote by T(A) the underlying binary tree associated to A.

Figure 4 shows all the non-ambiguous trees of size 4, grouping inside a rectangle those having the same underlying binary tree. Remark 1. A tree-like tableau [START_REF] Aval | Tree-like tableaux[END_REF] of size n is a set of n points placed in the boxes of a Ferrers diagram such that conditions 1, 2, 3 defining non-ambiguous trees are satisfied. Figure 5 shows an example of a tree-like tableau of size 7. It should be clear that non-ambiguous trees are in bijection with tree-like tableaux with rectangular shape.

Figure 5. A tree-like tableau.

Enumeration of non-ambiguous trees

Even though non-ambiguous trees are new combinatorial objects, their enumeration has been previously studied. Indeed, non-ambiguous trees of size n are in bijection with permutations of size n with all their strict excedances at the beginning, whose enumeration has been studied by Ehrenborg and Steingrímsson in [ES00]. The size preserving bijection (that we do not detail here) between these two families of combinatorial objects is a consequence of Lemma 5 in [START_REF] Steingrímsson | Permutation tableaux and permutation patterns[END_REF] and of results proved in [START_REF] Aval | Tree-like tableaux[END_REF]. The sequence (a n ) n≥1 counting the number of non-ambiguous tree of size n is referenced in [Slo] as A136127 = [1, 2, 5, 16, 63, 294, 1585, 9692, . . . ], but no simple formula is known. In this section, we provide enumerative formulas for non-ambiguous trees with additional constraints.

3.1. Non-ambiguous trees inside a fixed rectangle. In this section, we make extensive use of Remark 1 and we view non-ambiguous trees as tree-like tableaux of rectangular shape. For brevity, we write TLT for tree-like tableau in the sequel. Of particular importance for our purpose is the insertion procedure for TLTs, which gives to these objects a recursive structure. Since it is not the central purpose of the present paper, we shall not recall here all the definitions and properties of TLTs, and we refer the reader to [START_REF] Aval | Tree-like tableaux[END_REF]. Figure 5 shows an example of a TLT of size 7. In full generality, the size of TLT is given by the numbers of dotted cells.

Moreover, in this section, we use a different drawing convention for non-ambiguous trees, inherited from the drawing convention for TLTs: we will draw non-ambiguous trees with the x-axis vertical, and the y-axis horizontal.

Given a non-ambiguous tree, its x-size (resp. y-size) may be defined as the maximum of the x-coordinate (resp. y-coordinate) of its points. The aim of this subsection is to give a formula for the number A(k, ℓ) of non-ambiguous trees with x-size equal to ℓ and y-size equal to k. Because the size of a TLT is given by its semi-perimeter-1, remark that the size n of such a non-ambiguous tree is given by n = k + ℓ -1.

We denote by c(n, j) the unsigned Stirling numbers of the first kind, i.e. the number of permutations of size n with exactly j disjoint cycles.

We shall prove that for every integers n, ℓ, one has:

(1)

n k=1 c(n, k) A(k, ℓ) = n ℓ-1 n! .
Inverting Equation (1), we obtain that it is equivalent to Equation (2) below:

(2) Our goal is to prove Equation (1) directly and combinatorially. For this purpose, we provide combinatorial interpretations of the numbers c(n, k) and A(k, ℓ) that appear in Equation (1) with TLTs and non-ambiguous trees respectively. As mentioned in Remark 1, non-ambiguous trees are nothing but TLTs with a rectangular shape, so that our interpretation of c(n, k) and A(k, ℓ) is then with unified objects. This is the key in proving Equation (1) by a combinatorial approach.

A(k, ℓ) = k i=1 (-1) k-i S(k, i) i! i ℓ-
Recall that by definition A(k, ℓ) is the number of non-ambiguous trees with x-size equal to ℓ and y-size equal to k. On the other hand, we claim that c(n, j) counts the number of TLTs of size n with exactly j points in their first row. Indeed, this follows by definition of c(n, j) and the fact that TLTs of size n with exactly j points in their first row are in bijection with permutations of size n with exactly j disjoint cycles. This is a consequence of Theorem 4.2 in [START_REF] Burstein | On some properties of permutation tableaux[END_REF], re-formulated in terms of TLTs as in [START_REF] Aval | Tree-like tableaux[END_REF].

Proposition 2. For every integers n, ℓ, we have the following identity:

(3)

n k=1 c(n, k) A(k, ℓ) = n ℓ-1 n!
where c(n, k) denotes the number of TLTs of size n with exactly k points in their first row.

The proof consists in two steps:

• introduce a set T n,ℓ whose cardinality will be proved to be n ℓ-1 n! (Lemma 3); • prove that the elements of T n,ℓ are in bijection with pairs (b, a) enumerated by the left-hand side of (3) (Lemma 4).

We define T n,ℓ as the set of TLTs of size n + ℓ -1 whose first ℓ rows are of equal length. Figure 6 shows an element of T 5,2 . Figure 6. A tree-like tableau of T 5,2 .

To compute the cardinality of T n,ℓ , we will use a slight variation of the insertion procedure defined in [START_REF] Aval | Tree-like tableaux[END_REF]. This new insertion procedure depends on ℓ, and we shall call it the ℓ-insertion procedure.

The ℓ-insertion procedure. Let T be an element of T n,ℓ . The ℓ-special box of T is defined as

• the right-most box of the ℓ-th row, if the (ℓ + 1)-st row is strictly smaller;

• the right-most dotted box at the bottom of a column, otherwise. Given an integer m in {1, . . . , n}, we associate to it an edge e m of the south-east border of T by labeling these edges from south-west to north-east. Note that we exclude the (vertical) edges e n+1 , . . . , e n+ℓ at the right of the first ℓ rows of T . As in the insertion procedure of [START_REF] Aval | Tree-like tableaux[END_REF], if e m is a horizontal (resp. vertical) edge of the border of T , we add a row (resp. column) to T below (resp. to the right of) e m , composed of empty boxes except for one dotted box: the one below (resp. to the right of) e m . Next, if the dotted box added is to the left of the ℓ-special box of T , we add a ribbon (a connected set of empty boxes without any 2 × 2 square) adjacent simultaneously to the ℓ-special box of T and to the dotted box added.

Figure 7 illustrates the ℓ-insertion procedure. Lemma 3. The cardinality of T n,ℓ is given by

(4) #T n,ℓ = n ℓ-1 n! .
Proof. We prove the above by induction on ℓ. By [ABN11, Theorem 2.2], the number of unrestricted TLTs of size n is equal to n!, thus (4) is true for ℓ = 1. For the inductive step, we claim that the ℓ-insertion procedure gives a bijection between T n,ℓ × {1, . . . , n} and T n,ℓ+1 . To prove this fact, we first notice that the result of the ℓ-insertion procedure on T ∈ T n,ℓ and e m with m ∈ {1, . . . , n} is a TLT whose first ℓ + 1 rows are of equal length, thus an element of T n,ℓ+1 . Next, as explained in [START_REF] Aval | Tree-like tableaux[END_REF], we observe that the new box added by ℓ-insertion in an element of T n,ℓ+1 is easy to recognize: it is the rightmost among dotted boxes at the bottom of a column. Thus we are able to invert the ℓ-insertion procedure. This ends the proof of the lemma. Now we will send bijectively an element of T n,ℓ on pairs of objects (b, a) enumerated by the left-hand side of (3). The bijection relies on the ℓ-cut procedure described below, and illustrated in Figure 8. The ℓ-cut procedure. Let T be an element of T n,ℓ . We first cut T by putting the first ℓ rows in a ′ and the next rows in b ′ . Now we see b ′ as part of a TLT. We add to it a first row whose length equals the width of a ′ . We observe that there is exactly one way to put dots in this row to obtain a TLT, that we denote b: we are forced to put dots in the boxes corresponding to non-empty columns in a ′ . Next we remove empty columns in a ′ to get a non-ambiguous tree with ℓ rows, denoted a. Proof. It should be clear the ℓ-cut procedure is invertible, which implies the lemma.

Putting together Lemmas 3 and 4 gives a bijective proof of Proposition 2.

3.2. Non-ambiguous trees with a fixed underlying tree: a new hook formula. Let T be a binary tree. We define N A(T ) as the number of non-ambiguous trees A such that their underlying binary tree T(A) is T . The aim of this section is to get a formula for N A(T ): this will be done by Proposition 8, which shows that N A(T ) may be expressed by a new and elegant hook formula on the edges of T . To do this, we encode any non-ambiguous tree A by a triple Φ(A) = (T, α L , α R ) where T is a binary tree, and α L (resp. α R ) is a word called the left (resp. right) code of A.

To distinguish the vertices of A, we label them by integers from 1 to the size of A, as shown on Figure 9. These labels are only names given to the vertices, and our constructions do not depend on this labeling. The first entry in Φ(A) is the underlying binary tree T associated to A. Observe that we keep the labels on vertices when we extract the underlying binary tree. Now we define two posets V L and V R . Poset V L (resp. V R ) is defined by

• its vertices: the end points of the left (resp. right) edges of A; • its order relations: for a, b ∈ V L (resp. V R ), we say that a ≤ b if and only if there exists a path in the oriented tree starting from a and ending at b. The definition of non-ambiguous trees ensures that the set

{X(v), v ∈ V L } is the interval {1, . . . , |V L |}. Thus for i = 1, . . . , |V L |, we may set α L (i) as the unique label v ∈ V L such that X(v) = i,
and we proceed symmetrically for α R . On the example of Figure 9, we have: α L = 2378 and α R = 564. Our starting point is the following lemma.

Lemma 5. The application Φ which sends A to the triple (T, α L , α R ) is injective.

Proof. Consider a non-ambiguous tree A with n vertices and Φ(A) = (T, α L , α R ). From the definition of non-ambiguous tree, we know that the X and Y -coordinates of the root r are X(r) = Y (r) = 0. Moreover, for every left edge (s, t) of T we have

Y (s) = Y (t) and α L (X(t)) = t,
namely, X(t) is the position where t appears in α L . Similarly, for every right edge (s, t), we have

X(s) = X(t) and α R (Y (t)) = t,
namely, Y (t) is the position where t appears in α R . It is easy to check that we have 2n independent equations in 2n variables (the X and Y -coordinates of the vertices), so we get a unique nonambiguous tree.

Lemma 5 allows us to encode a non-ambiguous tree A by a triple (T, α L , α R ), where T is a binary tree, and α L (resp. α R ) is a word in which every label v ∈ V L (resp. V R ) appears exactly once. Of course, Φ is not surjective on such triples. If we take T = 1 2 3 , it should be clear that α L is forced to be 23. Consequently, our next task is to characterize the pairs of codes (α L , α R ) which are compatible with a given binary tree T , i.e. such that (T, α L , α R ) is in the image of Φ.

The next lemma is the crucial step to prove Proposition 8.

Lemma 6. Given a binary tree T , the pairs of codes compatible with T are exactly the pairs (α L , α R ) where α L is a linear extension of V L and α R is a linear extension of V R . Moreover, such pairs (α L , α R ) are in bijection with non-ambiguous trees with underlying tree T . Proof. Given a tree T , consider the map Φ T defined on the set of non-ambiguous trees with underlying tree T by Φ T (A) := (α L , α R ), where Φ(A) = (T, α L , α R ). We prove that the image of

Φ T is L(V L ) × L(V R )
, where we denote by L(P ) the set of linear extensions of a poset P . The second statement in Lemma 6 will then follow, since we deduce from the injectivity of Φ (Lemma 5) that Φ T is also injective.

First, we prove that Im Φ T ⊆ L(V L ) × L(V R ). Without loss of generality, we will prove that α L ∈ L(V L ). We need to prove that, if s < V L t, then s precedes t in α L , which we shall write s < α L t. If s < V L t, there exists a path in T starting from s and ending at t. When we go through the path, the X-coordinates of the vertices remain unchanged along right edges, while they increase along left edges. Since s = t, we have X(s) < X(t), which is equivalent to s < α L t.

Now the hard part is to prove that

L(V L ) × L(V R ) ⊆ Im Φ T . Let (α L , α R ) ∈ L(V L ) × L(V R ).
From the triple (T, α L , α R ), we may build a set of points in the grid, denoted A, as follows: we place a point (the root) at position (0, 0) and one point for every vertex v in T at coordinates

X(v) = i with α L (i) = v and Y (v) = Y (parent(v)) if v ∈ V L ; X(v) = X(parent(v)) and Y (v) = j with α R (j) = v if v ∈ V R .
We now prove that A is a non-ambiguous tree, whose underlying binary tree is of course T . This will follow from the three following statements, that we prove below.

i. for every left (resp. right) edge (s, t) of T , we have X(s) < X(t) (resp. Y (s) < Y (t)) in A; ii. A avoids the pattern ; iii. two different vertices in T correspond to points at different positions in A. Proof of i. Without loss of generality, we show this property for the set of left edges. First of all, we define the oldest left (resp. right) ancestor of a vertex u to be the vertex v such that the path going from v to u contains only right (resp. left) edges and this path is the longest with this property.

For example, in Figure 12 the vertices named v are the oldest left ancestors of those named u. Let v be the oldest left ancestor of s in T . Our construction of the set A implies that X(v) = X(s). Moreover, since (s, t) is a left edge, we have α L (X(t)) = t. Keeping in mind these two facts, we consider the following two cases:

• if v is the root of the tree, then X(v) = 0. Since X(t) ∈ [1, n], we have 0 = X(s) < X(t); • otherwise, v is the ending point of a left edge in T , and α L (X(v)) = v. Since in T there exists a path form v to t, then v < V L t. Moreover, we know that α L ∈ L(V L ), so v < α L t and X(v) < X(t)
, implying that X(s) < X(t). Proof of ii. We proceed by way of contradiction. Suppose that there are three points s, t, u ∈ A such that s -t -u form the pattern s t u . We remark that these three points are different from the root, because for each of them either the X or the Y -coordinate is nonzero. Without loss of generality, we suppose that t is the end of a left edge. Let v be the oldest left ancestor of s. By construction, Y (v) ≤ Y (s) < Y (t), and hence t = v. Since X(v) = X(s) = 0, v is the end of a left edge. The points v and t therefore both belong to V L and have the same X-coordinate, enventhough they are distinct. This is impossible, since α L is a linear extension of V L , and hence all points in V L must have different X-coordinates.

Proof of iii. We proceed by way of contradiction. Suppose that there are two different vertices s, t ∈ T whose positions in A coincide. By construction, they cannot be the root of the tree. We have two cases:

• one of the vertices is the end of a left edge, and the other is the end of a right edge. In this case, we find an occurrence of the forbidden pattern ; • s and t are both the end of a left edge (the other case is similar). In this case, we have s, t ∈ V L and X(s) = X(t) which is impossible. Now we come to the final step toward proving Proposition 8.

Lemma 7. The Hasse diagrams of V L and V R are forests.

Proof. We prove this proposition by way of contradiction. Suppose that there is a cycle in the Hasse diagram of V R (the case of V L is analogous). We can deduce from the poset structure that there are two paths in V R starting from an element v and ending at w. This would imply that in the tree there are two different paths from v to w, and hence there would be a cycle in the tree.

Figure 13 shows an example of the forests obtained by computing the Hasse diagrams of V L and V R . Proposition 8. The number of non-ambiguous trees with underlying tree T is given by

(5) N A(T ) = #{left edges}! #{right edges}! e∈V L n e e∈V R n e
where, for every left edge (resp. right edge) e, n e is the number of left edges (resp. right edges) contained in the subtree whose root is the ending point of e, plus 1.

Proof. Recall that Knuth's hook formula [START_REF] Knuth | The art of computer programming[END_REF] gives the number of linear extensions of a poset V whose Hasse diagram is a forest: namely, the number of these linear extensions is |V |! divided by the product of the hook lengths of all vertices in V . Therefore, by Lemmas 6 and 7, the number of non-ambiguous trees with underlying tree T is given by the product of the results of Knuth's hook formula applied to the Hasse diagrams of V L and V R . Specifically, when applying Knuth's formula to V L (resp. V R ), the hook length of any vertex v in V L (resp. V R ) is the number of descendants of v in V L (resp. V R ) including v, which corresponds exactly to n e for the left (resp. right) edge e whose end point is v.

This new hook formula is illustrated by Figure 14.

N A             1 1 2 1 2 6 1 8 1 1 3 1 1 2 4 1 2             = 11! • 6! 1 • 1 • 1 • 1 • 1 • 1 • 2 • 2 • 3 • 6 • 8 • 1 • 1 • 1 • 2 • 2 • 4
Figure 14. A hook formula for non-ambiguous trees on an example.

Complete non-ambiguous trees and combinatorial identities

A non-ambiguous tree is complete whenever its vertices have either 0 or 2 children. An example of complete non-ambiguous tree can be found in Figure 15. A complete non-ambiguous tree always has an odd number of vertices. Moreover, as in complete binary trees, a complete non-ambiguous tree with 2k + 1 vertices has exactly k internal vertices, k + 1 leaves, k right edges and k left edges. Denote by b k the number of complete non-ambiguous trees with k internal vertices. The sequence (b k ) k≥0 is known in [Slo] as A002190 = [1, 1, 4, 33, 456, 9460, . . . ]. We give in this section the first combinatorial interpretation for this integer sequence, in terms of complete non-ambiguous trees. Moreover, we use this interpretation to give in Propositions 9 and 11 combinatorial proofs of two identities due to Carlitz [START_REF] Carlitz | A sequence of integers related to the Bessel functions[END_REF].

Enumeration of complete non-ambiguous trees, and connection to Bessel function.

Denote by C n the number of complete binary trees with n internal vertices. It is well-known that C n = 1 n+1 2n n is the n-th Catalan number, and that, for every n ≥ 0, we have the identity: (6)

C n+1 = i+j=n C i C j .
Proposition 9 gives a variant of this identity for complete non-ambiguous trees:

Proposition 9. For every n ≥ 0, we have:

(7) b n+1 = i+j=n n + 1 i n + 1 j b i b j .
Proof. The proof of this proposition is similar to the classical proof of (6): the left (resp. right) subtree A L (resp. A R ) of a complete non-ambiguous tree A with n + 1 internal vertices is a complete non-ambiguous tree with i (resp. j) internal vertices, where i + j = n. Figure 15 shows an example of left and right subtree of a complete non-ambiguous tree.

A = -→ A L = A R = Figure 15
. The root suppression in a complete non-ambiguous tree.

Hence, in order to construct an arbitrary complete non-ambiguous tree A with n + 1 internal vertices, we need to choose:

• the number i of internal vertices contained in A L (i may range between 0 and n, the number j is equal to n -i);

• the complete non-ambiguous tree structure of A L (resp. A R ) -we have b i (resp. b j ) choices; • the way of interlacing the right (resp. left) edges of A L and A R . We denote by u 1 , u 2 , . . . , u i (resp. v 1 , v 2 , . . . , v j ) the end points of the right edges in

A L (resp. A R ) such that if k < l, then Y (u k ) < Y (u l ) (resp. Y (v k ) < Y (v l ))
, and by u 0 and v 0 the roots of A L and A R . Now, if we want to interlace the right edges in A L with those in A R , we need to decide at what positions we want to insert the vertices u 1 , u 2 , . . . , u i with respect to v 0 , v 1 , v 2 , . . . , v j , saving the relative order among u 0 , u 1 , u 2 , . . . , u i and v 0 , v 1 , v 2 , . . . , v j . A vertex u k can be placed either to the left of v 0 , or between v t and v t+1 (0 ≤ t ≤ j -1), or to the right of v j .

we must choose the i positions of u 1 , u 2 , . . . , u i (multiple choices of the same position are allowed) among j + 2 possible ones. Thus we have i+j+1 i = n+1 i ways to interlace the right edges of the subtrees A L and A R . Analogous arguments apply to left edges. In this case, we have n+1 j different interlacements. This ends the proof.

We shall use doubly exponential generating functions for the integer sequence b k , and define:

(8) B(x) = n≥1 b n-1 x n (n!) 2 .
Corollary 10. We have the following formula: 2p is characterized (see, e.g., [START_REF] Abramowitz | Handbook of mathematical functions with formulas, graphs, and mathematical tables[END_REF]) by the following differential equation

(9) B(x) = -ln J 0 (2 √ x) . Proof. The Bessel function J 0 (x) = ∞ p=0 (-1) p (p!) 2 (x/2)
(10) ∂ 2 x y + 1 x ∂ x y + y = 0,
together with the conditions in 0: J 0 (0) = 1 and ∂ x J 0 (0) = 0. Elementary computations show that both B(x) (because of Proposition 9) and -ln (J 0 (2 √ x))

(because of (10)) satisfy:

(11) ∂ x (x ∂ x y) = 1 + x (∂ x y) 2 ,
with conditions: y(0) = 1 and ∂ x y(0) = 1. This proves Corollary 10.

Combinatorial identities.

Corollary 10 shows that non-ambiguous trees provide a combinatorial interpretation -and to our knowledge, the first one -of sequence A002190 [Slo].

In [START_REF] Carlitz | A sequence of integers related to the Bessel functions[END_REF], the author shows analytically that identities (7) and (12) below are equivalent. We give a combinatorial proof of this fact.

Proposition 11. For every n ≥ 1, we have:

(12) n-1 k=0 (-1) k n k + 1 n -1 k b k = 1.
Proof. We fix an integer n and we take 0 ≤ k ≤ n -1. We define a gridded tree of size (k, n) to be a set of 2k + 1 points placed in a n × n grid, such that Condition 2 defining non-ambiguous trees is satisfied (which means we consider a non-ambiguous tree of size 2k + 1 embedded in a n × n grid) and such that the underlying tree is complete and that its root belongs to the first column. This implies that there are n -k -1 empty columns and n -k -1 empty rows, and that the first column is not empty. Figure 16 shows an example of a gridded tree of size (2, 6).

It is easy to verify that there are n k+1 n-1 k b k gridded trees of size (k, n). We call trivial gridded tree the tree of size (0, n) consisting of a single vertex in (0, 0). Now, for every integer n, we define an involution on the set of non trivial gridded trees. This involution associates a gridded tree of size (k, n) with a gridded tree either of size (k -1, n) or (k + 1, n). To define this involution, consider a gridded tree of size (k, n) and add a virtual root at position (-1, 0); the previous root becomes the left child of the virtual root. Now consider the path starting Figure 16. An example of gridded tree with 2 internal vertices drawn on a 6 × 6 grid.

from the virtual root, going down through the tree, turning at each internal vertex, and ending at a leaf. This path is unique. There are two cases:

(1) the path does not cross an empty row, nor an empty column: we erase the leaf and its parent from the tree, getting a new gridded tree of size (k -1, n). We can always erase the leaf and its parent, except if the parent is the virtual root. This happens only if the tree is the trivial gridded tree. As we restricted to non trivial gridded trees, this case never happens.

(2) the path crosses an empty row or an empty column: we choose the first empty row or column met while visiting the path. Without loss of generality, we suppose that it is a column, say c. Then, we add a new vertex v at the position where c crosses the path, and we add in the same column a new leaf (whose parent is v) in the topmost empty row. While visiting the path, we did not meet an empty row. Since there are as many empty rows as empty columns, there is always an empty row below v. This operation gives rise to a new gridded tree of size (k + 1, n). Remark that adding (resp. removing) a leaf and its parent p in (resp. from) a gridded tree following the previous algorithm does not remove (resp. add) any empty row or column that crosses the path from the virtual root to p. For this reason, this operation is an involution. Figure 17 shows how the involution acts on two examples. ----→ ← ----2.

r r

1.

----→ ← ---- We now state and prove an identity satisfied by Catalan numbers, whose proof is similar to Proposition 11, and which will be used to get Corollary 13. Proposition 12. For every n ≥ 1, we have:

(13) n k=0 (-1) n+k n + k n -k C k = 0.
Proof. We define a (k, ℓ)-labeled binary tree as a complete binary tree with k internal vertices together with a labeling of its 2k + 1 (internal or external) vertices by non-negative integers, such that the sum of these labels is equal to ℓ. Since n+k n-k is the number of ways to choose n -k elements with repetition in a set of cardinality 2k + 1, we may interpret n+k n-k C k combinatorially as the number of (k, n -k)-labeled binary trees. Indeed, a (k, n -k)-labeled binary tree may be described by a complete binary tree with k internal vertices, together with a choice of n-k vertices (with possible repetition) among its 2k + 1 (internal or external) vertices, any vertex receiving label i when it has been chosen i times. Now the proof is based on an involution defined on (k, n-k)-labeled binary trees, for 0 ≤ k ≤ n, which modifies the parameter k by ±1. This involution is defined in a way similar to the one used in the proof of Proposition 11. Let us consider a (k, n -k)-labeled binary tree. We add to it a virtual root and consider the path starting from the virtual root, going down through the tree, turning at each internal vertex, and ending at a leaf. Two cases occur:

(1) If all the vertices on this path are labeled by zero, then we erase the leaf y at the end of this path, together with its parent, and we increase by one the label of the sibling of y. This produces a (k -1, n -k + 1)-labeled binary tree.

(2) Otherwise we consider the first time this path encounters a vertex v that has a non-zero label. We decrease by one the label of v and we add a new vertex x on the edge between v and its parent, having two children: v and a new leaf y (the new sibling of v). The labels associated to the new vertices x and y are zero, so that the tree obtained is a (k + 1, n -k -1)-labeled binary tree. Figure 18 illustrates this operation on two examples (labels zero are omitted on this figure). It is clear that we define in this way an involution that modifies the parameter k by ±1, which implies (13). ----→ ← ---- ----→ ← ---- We are now able to obtain a new identity involving Catalan numbers and the sequence b k , which has been conjectured by P. Hanna (see [Slo], sequence A002190).

Corollary 13. For every n ≥ 1, we have:

(14) n k=0 (-1) k b k C k n + k n -k 2 = 0.
Proof. We fix an integer n 0 ≥ 1 and define the matrix D(n 0 ) = (D(n 0 ) i,j ) 0≤i,j≤n0 as follows:

D(n 0 ) i,j = 0 if i = 0 (-1) j i+j i-j 2 C j otherwise .
We also set b(n 0 ) to be the column vector whose entries are (b 0 , b 1 , . . . , b n0 ). With this notations, Identity (14) holds for every n = 1, 2 . . . , n 0 if and only if D(n 0 ) • b(n 0 ) = 0(n 0 ), where 0(n 0 ) is the column vector whose n 0 + 1 entries are all 0. Analogously, we define the matrix A(n 0 ) = (-1) j i+1 j+1 i j 0≤i,j≤n0

and set 1(n 0 ) to be the column vector whose n 0 + 1 entries are all 1.

Then, Identity (12) for all n from 1 to n 0 + 1 yields that A(n 0 ) • b(n 0 ) = 1(n 0 ). Because the matrix A(n 0 ) is lower triangular with ±1 entries on the diagonal, it is invertible, and we can write b(n 0 ) = A(n 0 ) -1 • 1(n 0 ). Hence, setting H(n 0 ) = (H(n 0 ) i,j ) 0≤i,j≤n0 = D(n 0 ) • A(n 0 ) -1 , to conclude the proof of Corollary 13, it is enough to prove that:

(15) H(n 0 ) • 1(n 0 ) = 0(n 0 ).
Notice first that H(n 0 ) 0,j = 0 for any n 0 ≥ 1 and 0 ≤ j ≤ n 0 . This follows immediately from the definition of H(n 0 ) = D(n 0 ) • A(n 0 ) -1 and the fact that D(n 0 ) 0,j = 0 for all 0 ≤ j ≤ n 0 . The main part of the proof is now to show that for 1 ≤ i ≤ n 0 , 0 ≤ j ≤ n 0 , we have H(n 0 ) i,j = (-1) i+j i+j i-j C j . Indeed, Proposition 12 then ensures that for all i ≥ 1,

i j=0 (-1) i+j i + j i -j C j = 0, hence, for all 1 ≤ i ≤ n 0 , i j=0 H(n 0 ) i,j = 0.
Notice that for j > i, i+j i-j = 0. Consequently, the above equality is equivalent to

for all 1 ≤ i ≤ n 0 , n0 j=0 H(n 0 ) i,j = 0.
Combined with H(n 0 ) 0,j = 0 for all 0 ≤ j ≤ n 0 , this yields H(n 0 ) • 1(n 0 ) = 0(n 0 ) as desired.

So let us focus on proving that for 1 ≤ i ≤ n 0 , 0 ≤ j ≤ n 0 , H(n 0 ) i,j = (-1) i+j i+j i-j C j . Since H(n 0 ) is characterized by H(n 0 ) • A(n 0 ) = D(n 0 ), we have to prove that, for every i, j such that 1 ≤ i ≤ n 0 and 0 ≤ j ≤ n 0 , (16

) n0 k=0 (-1) i+k i + k i -k k + 1 j + 1 k j C k = i + j i -j 2 C j .
If k > i, the summand vanishes. Moreover, it is easy to check that, if j > i, both sides in Identity ( 16) vanish, since all terms are 0. Hence, to conclude the proof, it is sufficient to prove that the following identity holds for any i > 0 and 0 ≤ j ≤ i:

(17) i k=0 (-1) i+k i + k i -k k + 1 j + 1 k j C k = i + j i -j 2 C j
For this purpose, for any i > 0, k ≥ 0 and 0 ≤ j ≤ i, we define

F j (i, k) = (-1) i+k i+k i-k k+1 j+1 k j C k i+j i-j 2 C j ,
and we show that for any i > 0 and 0 ≤ j ≤ i i k=0

F j (i, k) = 1.
In order to prove this identity, we apply the WZ method described in [PWZ96]. We look for a function G j (i, k) that satisfies the following identity:

(18)

F j (i + 1, k) -F j (i, k) = G j (i, k + 1) -G j (i, k).
Using the package of Mathematica, we determine that G j (i, k) should be defined by

G j (i, k) = (-1) i+k i+k+1 i-k+1 k+1 j+1 k j C k i+j i-j 2 C j • 2(i + 1)(k -j) 2 (i + j + 1) 2 (i + k + 1)
.

Indeed we then have

F j (i + 1, k) -F j (i, k) -G j (i, k + 1) + G j (i, k) = w j (i, k) • (-1) i+k i+k+1 i-k+1 k+1 j+1 k j C k i+j i-j 2 C j ,
where the term

w j (i, k) = - (i -j + 1) 2 (i + j + 1) 2 - i -k + 1 i + k + 1 + 2(i + 1)(i -k + 1) (i + j + 1) 2 + 2(i + 1)(k -j) 2 (i + k + 1)(i + j + 1) 2
can be proved to be equal to zero by straightforward computations. Now, if we sum up both sides of Identity (18) over 0 ≤ k ≤ i + 1, we can easily see that the right hand side telescopes to G j (i, i + 2) -G j (i, 0) = 0. Indeed, we have that G j (i, i + 2) = 0, since the binomial coefficient i+k+1 i-k+1 vanishes for k = i + 2. And we also have G j (i, 0) = 0, since k j vanishes for k = 0 and j > 0, and (k -j) 2 = 0 for k = j = 0. This implies that i+1 k=0

F j (i + 1, k) -F j (i, k) = 0. We remark that F j (i, i + 1) = 0, since i+k i-k vanishes if k = i + 1,
and we deduce that f j (i) :

= i k=0 F j (i, k) is independent of i.
Observing finally that f j (j) = F j (j, j) (all other terms vanish, since k j = 0 for k < j), we deduce that f j (j) = 1, and we get the assertion.

A new bijection between trees and parallelogram polyominoes

We recall that a parallelogram polyomino of size n is a pair of lattice paths of length n + 1 with south-west and south-east steps starting at the same point, ending at the same point, and never meeting each other. Figure 19 shows some examples of parallelogram polyominoes of size 4. The two paths defining a given parallelogram polyomino delimit a connected set of boxes. We will consider the parallelogram polyomino from this point of view. We now describe a bijection between parallelogram polyominoes of size n and binary trees with n vertices by showing that a parallelogram polyomino hides a non-ambiguous tree. In Subsection 5.1 we describe an injective map Ψ from parallelogram polyominoes to trees. In Subsection 5.2 we describe a map Λ from trees to parallelogram polyominoes, and prove in Subsection 5.3 that it is the inverse of Ψ.

5.1. The map Ψ from parallelogram polyominoes to trees. Given a parallelogram polyomino P , we place in it a set S(P ) of dots defined as follows: a box b of P contains a dot of S(P ) if and only if there are no boxes of P to the north-west of b or no boxes of P to the north-east of b (or both). For an example, see Figure 20, left. Lemma 14. For any parallelogram polyomino P , S(P ) is a non-ambiguous tree.

Proof. The above construction ensures that it is impossible to have three dots in S(P ) forming the pattern . Moreover, there is only one box b of P such that there are no boxes of P to the north-west nor to the north-east of b: it is the northernmost box of P . This implies that every dot (except for the one in the northernmost box) has a parent.

Let Ψ be the application that associates to any parallelogram polyomino of size n the underlying binary tree of S(P ) (that has n vertices). An example of this application is shown in Figure 20. Proof. Parallelogram polyominoes may be constructed incrementally, by adding, at every step the construction process, one step to each of the two paths defining the parallelogram polyomino. Along the construction of any parallelogram polyomino P , we may build simultaneously a nonambiguous tree whose underlying binary tree is Ψ(P ). More precisely, when adding one step to each of the two paths defining P , we add the dot(s) in S(P ) corresponding to the inserted steps, when needed. Figure 21 shows an example of this construction. Considering two different parallelogram polyominoes P and P ′ , there is a first step in the construction process when the new step added to one path in the construction of P differs from its homologous in P ′ . We prove that this implies that Ψ(P ) = Ψ(P ′ ). Indeed, w.l.o.g, the step added to P is south-west-oriented, while the corresponding step added to P ′ is south-east-oriented. This means that only one of these steps is associated with a new dot, connected to its parent v. The dot v exists in both trees Ψ(P ) and Ψ(P ′ ), but it does not have the same number of children in both trees.

Since it is known that there are as many parallelogram polyominoes of size n as binary trees with n vertices, we deduce from Proposition 15 that the map Ψ is a bijection. However, it is actually possible to describe the inverse of Ψ. In what follows, we first describe a map Λ from binary trees to parallelogram polyominoes, and we next prove that it is the inverse of Ψ. 5.2. The map Λ from trees to parallelogram polyominoes. The map Λ we define here builds a parallelogram polyomino of size n from any binary tree T with n vertices. The main part of the construction is to associate to T a specific non-ambiguous tree A(T ) whose underlying binary tree is T . The parallelogram polyomino Λ(T ) is then immediately obtained from A(T ).

5.2.1.

Building the non-ambiguous tree A(T ). The main difficulty in describing A(T ) is to decide where the points corresponding to the vertices of T should be drawn in the plane. Like in Subsection 3.2, their relative position is encapsulated in two total orders α L and α R on the set of vertices of T that are the end of a left or right edge. We will define these orders in Equation (19) p.18, but it requires some auxiliary definitions and lemmas.

Let T be a tree and T r be the tree obtained by grafting T as the right child of a new vertex r called the virtual root. We define two labelings of the vertices of T : the turn labeling and the zigzag labeling.

The turn labeling, denoted by t, is the application on the vertices s of T defined by: t(s) = the number of turns in the path from r to s in T r .

For example, in Figure 22, every vertex s is labeled by t(s).

T = 0 1 0 1 2 0 1 2 1 T r = r 0 1 0 1 2 0 1 2 1
Figure 22. The turn labeling.

The zigzag labeling, denoted by z, is the application on the vertices s of T defined by:

z(s) = |E(T, s)|
where E(T, s) is defined on T r as follows:

• let P be the path from the virtual root r to s;

• let s 1 , s 2 , . . . , s k be the vertices of P where P is turning;

• E(T, s) is the set of all vertices x of T except those such that one of the followings holds: -x = s is a descendant of s, or x belongs to the right (resp. left) subtree of s i and the path P takes a left (resp. right) turn at s i . Because E(T, s) can be seen as obtained from T by removing some vertices with all their descendants, it is straightforward that the vertices remaining in E(T, s) always form an induced subtree of T .

To illustrate the above definitions, Figure 23 shows a tree T with the induced subtree E(T, s) associated to the vertex s of T , together with the complete zigzag labeling of T . With the turn and zigzag labelings of T , we will define (see Equation (19) p.18) the orders α L and α R on the vertices of T from which A(T ) (and later Λ(T )) is deduced.

T r = r s 1 s 2 s E(T, s) =
An important fact in the construction is that the zigzag labeling is a bijection1 between the set of vertices of T and {1, 2, . . . , n}, n denoting the number of vertices of T . This will follow as a consequence of Lemma 16 below, for which we introduce some more definitions.

Let u and v be two vertices of a tree T . The lowest common ancestor of u and v is the last common vertex between the path going from the root to u and the path going from the root to v. We denote by LCA(u, v) that vertex.

Figure 26 p.21 shows an example of lowest common ancestor.

Lemma 16. Let u and v be two different vertices of a tree T , then

E(T, u) E(T, v) or E(T, v) E(T, u).
Moreover, E(T, u) E(T, v) holds if and only if the following holds:

             u = LCA(u, v) or u, v = LCA(u, v) and LCA(u, v) is in V L and u is in the right subtree of LCA(u, v) or u, v = LCA(u, v) and LCA(u, v) is in V R and u is in the left subtree of LCA(u, v)             
Recall from Subsection 3.2 that V L (resp. V R ) denotes the set of the end points of the left (resp. right) edges of T .

Proof. Let u, v be two different vertices of a tree T . By definition of LCA(u, v), there exists a unique vertex α ∈ {u, v} (we denote by β the other vertex such that {u, v} = {α, β}) such that one of the three following cases occurs:

(

1) α = LCA(u, v) (2) LCA(u, v) ∈ {u, v} and LCA(u, v) ∈ V L and α is in the right subtree of LCA(u, v) (3)
LCA(u, v) ∈ {u, v} and LCA(u, v) ∈ V R and α is in the left subtree of LCA(u, v) We will now prove that cases 1, 2 and 3 imply E(T, α) E(T, β). For the first case, E(T, α) E(T, β) is a direct consequence of the definition of E. For the two other cases, we just have to remark that

• the path from the virtual root to α turns at LCA(α, β),

• the path from the virtual root to β goes through but doesn't turn at LCA(α, β), to conclude that E(T, α) E(T, β). Now, Lemma 16 follows immediately.

Corollary 17. The labeling z is a bijection between the set of vertices V of T and {1, 2, . . . , |V |}. Moreover, for all vertices u and v in V , we have: z(u) < z(v) ⇐⇒ E(T, u) E(T, v).

Corollary 17 is the key to defining the total orders α L and α R on the vertices of T , from which A(T ) and Λ(T ) will be derived.

We define the partial orders α L (resp. α R ) on the ends of the left (resp. right) edges of T by the relation:

(19) u < α L v (resp. u < α R v) if and only if (t(u), z(u)) < lex (t(v), z(v))
where < lex is the lexicographic order relation. Because z is a bijection, α L and α R are actually total orders.

For any binary tree T , we set A(T ) to be the triple (T, α L , α R ).

Lemma 18. For any binary tree T , A(T ) defines a non-ambiguous tree.

Proof. Let us denote A(T ) = (T, α L , α R ). We prove that α L (resp. α R ) is a linear extension of the poset V L (resp. V R ) of T (see Subsection 3.2 for the definition of these posets). By Lemma 6 (p. 7), this ensures that (T, α L , α R ) encodes a non-ambiguous tree of shape T . Let u and v be two vertices of V L (resp. V R ) such that u < V L v (resp. u < V R v). By definition, there exists a path from vertex u of V L (resp. V R ) to vertex v of V L (resp. V R ). We deduce that t(u) ≤ t(v). Therefore:

• if t(u) < t(v) then, by definition of α L , u < α L v (resp. u < α R v ); • if t(u) = t(v)
then, since there is a path from u to v, we have u = LCA(u, v). We deduce from Lemma 16 that z(u) < z(v). Hence,

u < α L v (resp. u < α R v).
We conclude that α L (resp. α R ) is a linear extension of V L (resp. V R ).

5.2.2.

From A(T ) to the parallelogram polyomino Λ(T ). In the sequel, by the notation (resp. ) we mean that there are two cells at coordinates (x 1 , y 1 ) and (x 2 , y 2 ) with

x 1 > x 2 and y 1 < y 2 that contain dots (or vertices), and such that the cell at coordinates (x 1 , y 2 ) does not contain (resp. contains) a dot (or vertex). Notice that it is not necessary that x 1 = x 2 + 1 nor that y 1 = y 2 -1 to have an occurrence of either the pattern or .

For any non-ambiguous tree A, consider the operation which converts every pattern to a pattern . We shall call this operation the filling of A, and denote it F (A).

For any binary tree T , we define Λ(T ) = F (A(T )). Figure 24, shows all the steps of the construction.

a b c d e f g h i j k l Computation of ----------→ (t,z) (0, 1) (1, 2) (0, 3) (1, 4) (1, 7) (1, 10) (0, 12) (2, 5) (3, 6) (2, 8) (2, 9)
(2, 11) Lemma 19. Let A be a non-ambiguous tree, and define V L and V R as usual. F (A) is a parallelogram polyomino as soon as for any two different vertices u, v in V L (resp. V R ) we have X

-→ α L = bdefi α R = cghjkl -→
(u) < X(v) ⇒ Y (u) ≤ Y (v) (resp. Y (u) < Y (v) ⇒ X(u) ≤ X(v)).
Proof. In the proof of this lemma, we use a characterization of parallelogram polyominoes (see [START_REF] Delest | Parallelogram polyominoes and corners[END_REF] for more details): a parallelogram polyomino is a polyomino P (i.e., a finite set of unit cells on the grid N × N -oriented as shown on Figure 1 -that is edge-connected) such that:

• P is row and column convex, i.e. each of its rows and columns is connected;

• if we consider the minimum rectangle R bounding P , then P contains the top-most and bottom-most corners of R. Suppose that for every u, v ∈ V L we have X(u) < X(v) ⇒ Y (u) ≤ Y (v) and that, for every t, w ∈ V R , we have Y (t) < Y (w) ⇒ X(t) ≤ X(w). Recall that {X(v), v ∈ V L } is the interval {1, . . . , |V L |}. Without loss of generality, we will show that F (A) is column convex. Suppose that F (A) contains the two cells (a, y 0 ) and (b, y 0 ), a < b. We want to show that F (A) contains all the cells (c, y 0 ), with a < c < b. The two cells (a, y 0 ) and (b, y 0 ) can correspond either to a vertex of A or to the 0 of a pattern in A. We study the case where both cells correspond to occurrences of the pattern , the other three possible cases being analogous. Denote by g the southwestern-most vertex of A such that X(g) < a and Y (g) = y 0 and by h the southeasternmost vertex of A such that X(h) = b and Y (h) < y 0 . Let h ′ ∈ V L be the oldest left ancestor of h. We choose now a cell f = (c, y 0 ), where a < c < b. Because X(h ′ ) = b, c < b and {X(v), v ∈ V L } = {1, . . . , |V L |}, there exists some vertex h ′′ ∈ V L such that X(h ′′ ) = c. But by our assumption, we deduce from X(h ′′ ) < X(h ′ ) that Y (h ′′ ) ≤ Y (h ′ ) < y 0 . Hence, h ′′ , f , and g

give rise to an occurrence of the pattern , as shown in Figure 25. This implies that f belongs to F (A), and hence F (A) is column convex. Now we will prove that F (A) is connected. Consider two cells c 1 , c 2 ∈ F (A). We suppose that both c 1 and c 2 correspond to the 0 of two patterns of type , the other possible cases being easier to prove. Denote by d i , i = 1, 2, the southwestern-most vertex of A such that X(d i ) < X(c i ) and Y (d i ) = Y (c i ). Since F (A) is column convex, it contains the vertical strip S 1 (resp. S 2 ) joining d 1 and c 1 (resp. d 2 and c 2 ). Now d 1 and d 2 belong to A, and they are connected by a sequence of edges, that correspond to a subset S of F (A). Indeed, F (A) is both row and column convex, and it contains all the cells corresponding to the vertices of A. Then, the two cells c 1 and c 2 are connected by S 1 ∪ S 2 ∪ S. Finally, we consider the minimum rectangle R bounding F (A). The root of A occupies the top-most corner, which is therefore contained in F (A). Moreover, it is obvious that both the southwestern-most row and the southeastern-most column of R contain a vertex of A, and for this reason, the bottom-most corner of R is the 0 in a pattern of A. Therefore, F (A) contains also the bottom-most corner of R.

All these arguments prove that F (A) is a parallelogram polyomino.

Remark 20. We may prove that the condition in Lemma 19 is also necessary:

if F (A) is a parallelogram polyomino, then for any two different vertices u, v in V L (resp. V R ) we have X(u) < X(v) ⇒ Y (u) ≤ Y (v) (resp. Y (u) < Y (v) ⇒ X(u) ≤ X(v)).
Proposition 21. For any binary tree T , Λ(T ) is a parallelogram polyomino.

One additional definition is used in our proof of Proposition 21. Let u be the end of a left (resp. right) edge of T . The direct oldest ancestor of a vertex u is oldest ancestor of u that can reach u using left (resp. right) edges only. We denote by DOA(u) that vertex.

Figure 26 shows an example of direct oldest ancestor. If DOA(u) = DOA(v), the above claim is clear. Let us therefore assume that DOA(u) = DOA(v).

Because u and v are in V L , we obtain immediately that t(DOA(u)) = t(u)-1 and t(DOA(v)) = t(v) -1. Moreover, since X(u) < X(v) Lemma 18 and the definitions of Subsection 3.2 ensure that u < α L v. We now distinguish two cases, following the definition of α L . Case 1: t(u) < t(v).

• If DOA(u) is the root then Y (DOA(u)) = 0 and Y (DOA(u)) ≤ Y (DOA(v)).

• If DOA(v) is the root, since t(u) < t(v), DOA(u) is the root and we conclude as above.

• Otherwise, DOA(u) and DOA(v) are the end of a right edge. From t(u) < t(v), we obtain that t(DOA(u)) < t(DOA(v)). Hence DOA(u) < α R DOA(v). As before, we deduce that Y (DOA(u)) < Y (DOA(v)). Case 2: t(u) = t(v) and z(u) < z(v). Since t(u) = t(v) we have t(DOA(u)) = t(DOA(v)). We deduce that the following equivalence holds:

z(DOA(u)) < z(DOA(v)) ⇔ DOA(u) < α R DOA(v) ⇔ Y (DOA(u)) < Y (DOA(v)).
We shall therefore prove that z(DOA(u)) < z(DOA(v)). This will follow from the two claims below:

(1) LCA(u, v) = u and LCA(u, v) = v.

(2) LCA(u, v) = LCA(DOA(u), DOA(v)). Proof of Claim 1. As u, v are in V L , u and v can't be the root. We deduce that DOA(u) = u and DOA(v) = v. Because we assumed that DOA(u) = DOA(v) and t(u) = t(v), we deduce that LCA(u, v) = u and LCA(u, v) = v.

Proof of Claim 2. This is also a consequence of DOA(u) = DOA(v) and t(u) = t(v). • We finally prove that the case LCA(DOA(u), DOA(v)) = DOA(v) is not possible. Indeed, assume that LCA(DOA(u), DOA(v)) = DOA(v). If DOA(v) were the root of T , then we would have z(DOA(v)) = 1, which is a contradiction to z(u) < z(v). So DOA(v) is the end of a left (resp. right) edge. Hence by definition, v is in the right (resp. left) subtree of DOA(v). But from Claim 2, we have LCA(u, v) = DOA(v). Lemma 16 then ensures that z(v) < z(u), which is a contradiction to z(u) < z(v).

5.3.

Proving that Λ is the inverse of Ψ. We want to prove that the maps Ψ and Λ defined in the previous subsections are inverse of one another. First of all, we define a diagram to be a finite collection of cells in the square grid N × N. Then, define the set D 0 (resp. D 1 ) of all the diagrams that avoid the pattern (resp.

). We remark that every parallelogram polyomino belongs to D 0 , since it is convex and contains the bottom-most point of the minimum rectangle bounding it. Moreover, every non-ambiguous tree belongs to D 1 by definition.

We extend the map S defined in Subsection 5.1 to the set D 0 , defining Ŝ as follows: for every diagram U ∈ D 0 , Ŝ(U ) is the diagram obtained by replacing every 1 of U occurring as the bottommost 1 of a pattern by a 0. Analogously, we can define the extension F of F to the set The final step toward proving that Ψ and Λ are inverse of one another is the following lemma:

Lemma 23. For any binary tree T , we have A(T ) = S(Λ(T )).

Proof. Let T be a binary tree. Proposition 21 states that Λ(T ) = F (A(T )) is a parallelogram polyomino, hence S(Λ(T )) is well defined. Then, Lemma 22 implies that S(Λ(T )) = S(F (A(T ))) = Ŝ( F (A(T ))) = A(T ).

Proposition 24. Ψ and Λ are inverse of one another.

Proof. By Lemma 23, we get that Ψ • Λ is the identity over the set of binary trees. This implies in particular that Ψ is surjective, and that Λ is injective. Recall from Proposition 15 that Ψ is also injective, so that we obtain that Ψ is a bijection whose inverse is Λ.

Perspectives

In this work, we used the notion of non-ambiguous tree for the study of various combinatorial problems. Several questions related to these objects remain open.

(i). The first perspective concerns the bivariate generating function of non-ambiguous trees within a rectangular box. This point will be developed in a future work, together with related algebraic investigations. Nevertheless, we point out the following fact. With the notations of Subsection 3.1, we may define

F (u, v) = k,ℓ≥1 A(k, ℓ) u k k! v ℓ ℓ! .
From Equation (2) p.4, together with the formula for Stirling numbers of the second kind S(k, i) =

1 i! i j=0 (-1)
i-j i j j k , we get

F (u, v) = i,k,ℓ≥1 i≥0 (-1) k-j i j j k i ℓ-1 u k k! v ℓ ℓ!
from which an elementary computation leads to (20) F (u, v) = -ln(e u + e v -e u+v ).

It would be nice to obtain (20) directly with generating functions arguments.

(ii). Another perspective is about Bessel functions. We recall that parallelogram polyominoes are enumerated with respect to their area, width and height through the quotient of analogues of the Bessel functions J 0 and J 1 [START_REF] Bousquet-Mélou | Empilements de segments et q-énumération de polyominos convexes dirigés[END_REF]. This double appearance of Bessel functions in close contexts is striking, but unexplained for the moment. In the same vein, recall that we were able to build combinatorial objects which interpret combinatorially the integers b k that appear in the development of J 0 -namely complete non-ambiguous trees. Is it possible to generalize this construction to coefficients of general Bessel functions J k ?

(iii). Bessel function also appears in combinatorics as generating function of pairs of permutations with no common rise. More precisely, let ω(n) denote the number of pairs of permutations (π, ρ) of size n such that consecutive entries cannot be rising both in π and ρ; Carlitz et. al. [START_REF] Carlitz | Enumeration of pairs of permutations and sequences[END_REF] proved that (21)

∞ n=0 ω(n) x n (n!) 2 = J 0 (2 √ x) -1 .
Let us define non-ambiguous complete forests as objects satisfying the definition of non-ambiguous complete trees, but without the condition on the root, and denote by τ (n) the number of these objects in size n. Corollary 10 then implies that the doubly exponential generating function for non-ambiguous complete forests is given by:

(22) ∞ n=0 τ (n) x n (n!) 2 = J 0 (2 √ x) -1 .
This shows that non-ambiguous complete forests are equinumerous to pairs of permutations of the same size with no common rise. A bijective proof of this fact is an open question.

(iv). For what concerns generalizations, an intriguing question would be to define and study nice analogues of non-ambiguous trees in higher dimensions. This is indeed work in progress.

(v). We conclude with an open problem of a more algebraic nature. The Loday-Ronco Hopf algebra Y Sym of planar binary trees [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF] has basis elements indexed by planar binary trees. In this setting, two permutations are in the same class when they have the same underlying tree, when coded as binary search trees. It would be interesting to study an analogous problem in which we refine these classes with respect to the underlying non-ambiguous tree.

Figure 1 .←→Figure 2 .

 12 Figure 1. The underlying grid for non-ambiguous trees.

Figure 3 .

 3 Figure 3. Some examples and counterexamples of non-ambiguous trees.

Figure 4 .

 4 Figure 4. The 16 non-ambiguous trees of size 4.

Figure 7 .

 7 Figure 7. The ℓ-insertion procedure on two examples for ℓ = 3 and m = 5.

Figure 8 .

 8 Figure 8. The ℓ-cut procedure for ℓ = 3.

Figure 9 .

 9 Figure 9. A non-ambiguous tree A with labeled vertices, and the associated binary tree T .

Figure 10 (Figure 10 .

 1010 Figure10(with minima at the top) illustrates this notion. We shall prove at Lemma 7 that V L and V R are forests.

Figure 11 Figure 11 .

 1111 Figure11gives these compatible codes, together with the corresponding non-ambiguous trees, in the case of the tree T of Figure10.

Figure 12 .

 12 Figure 12. The oldest left ancestors.

Figure 13 .

 13 Figure 13. The Hasse diagrams H(V L ) and H(V R ) of V L and V R are forests.

Figure 17 .

 17 Figure 17. The involution acting on two examples of non trivial gridded trees.

Figure 18 .

 18 Figure 18. The involution acting on two examples of (4, 7)-and (2, 4)-labeled trees.

Figure 19 .

 19 Figure 19. Example of parallelogram polyominoes of size 4.

Figure 20 .

 20 Figure 20. Parallelogram polyominoes are just a way of drawing a binary tree in the plane.

Figure 21 .

 21 Figure 21. An example of parallelogram polyomino with its tree under construction.

Figure 23 .

 23 Figure 23. The zigzag labeling.

Figure 24 .

 24 Figure 24. The map Λ.

Figure 25 .

 25 Figure 25. The positions of h ′′ , f and g.

Figure 26 .

 26 Figure 26. Example of lowest common ancestor and direct oldest ancestor.

•

  If LCA(DOA(u), DOA(v)) = DOA(u) and LCA(DOA(u), DOA(v)) = DOA(v), we apply Lemma 16 simultaneously on u and v on one side, and on DOA(u) and DOA(v) on the other side. Because LCA(u, v) = LCA(DOA(u), DOA(v)), we deduce that: E(T, u) E(T, v) ⇔ E(T, DOA(u)) E(T, DOA(v)). With Corollary 17, this is equivalent to z(u) < z(v) ⇔ z(DOA(u)) < z(DOA(v)). As z(u) < z(v), we conclude that z(DOA(u)) < z(DOA(v)). • If LCA(DOA(u), DOA(v)) = DOA(u), then we apply Lemma 16 on DOA(u) and DOA(v) to deduce that E(T, DOA(u)) E(T, DOA(v)), hence z(DOA(u)) < z(DOA(v)).

D 1 :

 1 for every diagram W ∈ D 1 , F (W ) is the diagram obtained by replacing each occurrence of the pattern in W with an occurrence of . Obviously, we have that Ŝ : D 0 → D 1 , F : D 1 → D 0 , Ŝ| P = S, and F | Im(A) = F , where P is the set of all parallelogram polyominoes and Im(A) is the image of the map T → A(T ). By definition of Ŝ and F , we easily deduce that: Lemma 22. Ŝ = F -1 .

  1 , where S(k, i) denotes the Stirling numbers of the second kind, i.e. the number of partitions of a set of k elements into i non-empty parts. It is known [SW07, ABN13] that A(k, ℓ) is equal to the number of permutations of size k + ℓ -1 with exactly k strict excedances in position 1, 2, . . . , k.

Consequently, Corollary 6.6 in

[START_REF] Ehrenborg | The excedance set of a permutation[END_REF]

provides a proof of Equation (1). More precisely, in

[START_REF] Ehrenborg | The excedance set of a permutation[END_REF]

, Ehrenborg and Steingrímsson prove (2) by an inclusion-exclusion argument, and then deduce (1) by inversion.

In fact this labeling may also be obtained by performing a kind of "zigzag" depth-first traversal of T .

Acknowledgements. We thank Philippe Nadeau for helpful discussions around rectangular alternative tableaux. We are grateful to Christian Krattenthaler and Cyril Banderier for their advice that guided our proof of Corollary 13. We also thank the anonymous referee for enlightening comments and suggestions (in particular the link with [CSV74]).

This research was driven by computer exploration using the open-source mathematical software Sage [S + 12] and its algebraic combinatorics features developed by the Sage-Combinat community [SCc12].

All authors are supported by ANR -PSYCO project (ANR-11-JS02-001).