Matthieu Josuat-Verg Ès

Vladimir Arnol

ENUMERATION OF SNAKES AND CYCLE-ALTERNATING PERMUTATIONS

Keywords: 2000 Mathematics Subject Classification, Primary: 05A15, 05A19, Secondary: 11B83

Springer numbers are analogs of Euler numbers for the group of signed permutations. Arnol'd showed that they count some objects called snakes, which generalize alternating permutations. Hoffman established a link between Springer numbers, snakes, and some polynomials related with the successive derivatives of trigonometric functions.

The goal of this article is to give further combinatorial properties of derivative polynomials, in terms of snakes and other objects: cycle-alternating permutations, weighted Dyck or Motzkin paths, increasing trees and forests. We obtain some exponential generating functions in terms of trigonometric functions, and some ordinary generating functions in terms of J-fractions. We also define natural q-analogs, make a link with normal ordering problems and the combinatorial theory of differential equations.

Introduction

It is well-known that the Euler numbers E n defined by

∞ n=0 E n z n n! = tan z + sec z (1)
count alternating permutations in S n , i.e. σ such that σ 1 > σ 2 < σ 3 > . . . σ n . The study of these, as well as other classes of permutations counted by E n , is a vast topic in enumerative combinatorics, see the survey of Stanley [START_REF] Stanley | A survey of alternating permutations[END_REF]. By a construction due to Springer [START_REF] Springer | Remarks on a combinatorial problem[END_REF], there is an integer K(W ) defined for any finite Coxeter group W such that K(S n ) = E n . As for the groups of signed permutations, Arnol'd [START_REF] Arnol | d: The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF] introduced some particular kind of signed permutations called snakes, counted by the numbers K(S B n ) and K(S D n ). Thus snakes can be considered as a "signed analog" of alternating permutations. Algorithmically, Arnol'd [START_REF] Arnol | d: The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF] gives a recursive method to compute these integers with triangular arrays similar to the Seidel-Entriger triangle of Euler numbers E n (see for example [START_REF] Gélineau | Bijections for Entriger families[END_REF]).

In this article, we are mostly interested in the numbers S n = K(S B n ), which were previously considered by Glaisher [12, § § 109 and 119] in another context. Springer [START_REF] Springer | Remarks on a combinatorial problem[END_REF] shows that they satisfy

∞ n=0 S n z n n! = 1 cos z -sin z , (2)
and we call S n the nth Springer number (although there is in theory a Springer number associated with each finite Coxeter group, this name without further specification usually refers to type B). Another link between snakes and trigonometric functions has been established by Hoffman [START_REF] Hoffman | Derivative polynomials, Euler polynomials, and associated integer sequences[END_REF], who studies some polynomials P n (t) and Q n (t) related with the successive derivatives of tan and sec by: d n dx n tan x = P n (tan x),

d n dx n sec x = Q n (tan x) sec x. (3)
Among various other results, Hoffman proves that Q n (1) = S n and P n (1) = 2 n E n , moreover this number 2 n E n counts some objects called β-snakes, which are a superset of type B snakes.

The main goal of this article is to give combinatorial models of these derivative polynomials P n and Q n (as well as another sequence Q (a) n related the with the ath power of sec), in terms of several objects:

• Snakes (see Definition 3.2). Besides type B snakes and β-snakes of Arnol'd, we introduce another variant. • Cycle-alternating permutations (see Definition 3.7). These are essentially the image of snakes via Foata's fundamental transform [START_REF] Lothaire | Combinatorics on words[END_REF]. • Weighted Dyck prefixes and weighted Motzkin paths (see Section 3). These are two different generalizations of some weighted Dyck paths counted by E n . • Increasing trees and forests (see Section 4). The number E 2n+1 counts increasing complete binary trees, and E 2n "almost complete" ones, our trees and forests are generalizations of these.

Various exponential and ordinary generating functions are obtained combinatorially using these objects. They will present a phenomenon similar to the case of Euler numbers E n : they are given in terms of trigonometric functions for the exponential generating functions, and in terms of continued fractions for the ordinary ones. For example, in Theorem 3.17, we obtain bijectively a continued fraction for the (formal) Laplace transform of (cos z -t sin z) -a . While this result was known analytically since long ago [START_REF] Stieltjes | Sur quelques intégrales définies et leur développement en fractions continues[END_REF], we show here that it can be fully understood on the combinatorial point of view. This article is organized as follows. In Section 2, we give first properties of the derivative polynomials, such as recurrence relations, generating functions, we also introduce a natural q-analog and link this with the normal ordering problem. In Section 3, we give combinatorial models of the derivative polynomials in terms of subset of signed permutations, and obtain the generating functions. In Section 4, we give combinatorial models of the derivative polynomials in terms of increasing trees and forests in two different ways: via the combinatorial theory of differential equations [START_REF] Leroux | Combinatorial resolution of systems of differential equations, I. Ordinary differential equations[END_REF] and via the normal ordering problem and results from [START_REF] Flajolet | Combinatorial aspects of continued fractions[END_REF].

Derivative polynomials

The derivative polynomials for tangent and secant have been introduced by Knuth and Buckholtz [START_REF] Knuth | Computation of tangent, Euler and Bernoulli numbers[END_REF], and several results such as the generating functions have been proved by Hoffman [START_REF] Hoffman | Derivative polynomials, Euler polynomials, and associated integer sequences[END_REF][START_REF] Hoffman | Derivative polynomials for tangent and secant[END_REF].

2.1. Definitions. We generalize the polynomials Q n (t) defined in [START_REF] Chen | Labelled ballot paths and the Springer numbers[END_REF], by considering Q

Besides Q n which is the case a = 1 in Q (a)

n , the case a = 2 will be particularly interesting. We denote R n = Q [START_REF] Flajolet | Combinatorial models of creation-annihilation[END_REF] n . Since sec 2 x is the derivative of tan x, it follows that there is the simple relation P n+1 (t) = (1 + t 2 )R n (t).

By differentiating (3) and ( 4), we obtain the relations:

P n+1 = (1 + t 2 )P ′ n , Q (a) n+1 = (1 + t 2 ) d dt Q (a) n + atQ (a) n , (5)
together with P 0 = t and Q (a) 0 = 1. Let us give other elementary properties which are partly taken from [START_REF] Hoffman | Derivative polynomials, Euler polynomials, and associated integer sequences[END_REF].

Proposition 2.1. The polynomial Q (a)
n has the same parity as n, i.e.

Q (a) n (-t) = (-1) n Q (a)
n (t), and P n has different parity. We have:

P n (1) = 2 n E n , Q n (1) = S n , R n (1) = 2 n E n+1 . (6)
(Recall that Q n = Q (1)
n and R n = Q (2)
n .) The generating functions are:

∞ n=0 P n (t) z n n! = sin z + t cos z cos z -t sin z , ∞ n=0 Q (a) n (t) z n n! = 1 (cos z -t sin z) a . ( 7
)
Proof. The generating function of {Q

n } n≥0 is not present in the reference [START_REF] Hoffman | Derivative polynomials, Euler polynomials, and associated integer sequences[END_REF], but can be obtained in the same way as in the particular case a = 1 (which is in [START_REF] Hoffman | Derivative polynomials, Euler polynomials, and associated integer sequences[END_REF]). By a Taylor expansion and a trigonometric addition formula, we have:

∞ n=0 Q (a) n (tan u) sec a u z n n! = sec a (u + z) = sec a u (cos z -tan u sin z) a , (8)
We can divide on both sides by sec a u, let t = tan u, and the result follows.

These exponential generating functions will be obtained combinatorially in Section 3. It is interesting to note that P (z, t) = P n z n /n! is a Möbius transformation as a function of t, in such a way that z → (t → P (z, t)) is a group homomorphism from R to the elliptic Möbius transformations of C fixing i and -i. This has an explanation through the fact that P (z, t) = tan(arctan t + z), (9) and consequently, as observed in [START_REF] Hoffman | Derivative polynomials, Euler polynomials, and associated integer sequences[END_REF]:

P (z, P (z ′ , t)) = P (z + z ′ , t), (10)
which is the concrete way to say that z → (t → P (z, t)) is a group homomorphism.

2.2.

Operators and q-analogs. Let D and U be linear operators acting on polynomials in the variable t by

D(t n ) = [n] q t n-1 , U (t n ) = t n+1 , (11)
where [n] q = 1-q n 1-q is the usual q-integer. The first one is known as the q-derivative or Jackson derivative, and an important relation is DU -qU D = I, where I is the identity. Definition 2.2. Our q-analogs of the polynomials Q n and R n are defined by:

Q n (t, q) = (D + U DU ) n 1, R n (t, q) = (D + DU U ) n 1, (12)
where 1 should be seen as t 0 , the operators acting on polynomials in t.

Remark 2.3. Of course, there are many choices for defining a q-analog, leading to various different properties. We have to mention that another choice can be obtained as a particular case of the multivariable tangent and secant q-derivative polynomials studied by Foata and Han in [START_REF] Foata | Multivariable tangent and secant q-derivative polynomials[END_REF].

Proposition 2.4. We have

Q n (-t, q) = (-1) n Q n (t, q), R n (-t, q) = (-1) n R n (t, q), (13)
moreover Q n (t, q) and R n (t, q) are polynomials in t and q with nonnegative coefficients such that

Q n (t, 1) = Q n (t) and R n (t, 1) = R n (t).
Proof. From DU -qU D = I, we can write

D + U DU = (I + qU 2 )D + U, D + DU U = (I + q 2 U 2 )D + (1 + q)U, (14)
then from ( 12) and ( 14) it follows that

Q n+1 (t, q) = (1 + qt 2 )D Q n (t, q) + tQ n (t, q), (15)
R n+1 (t, q) = (1 + q 2 t 2 )D R n (t, q) + (1 + q)tR n (t, q), (16)
which generalize the recurrences for Q n and R n (a = 1 and a = 2 in ( 5)). The elementary properties given in the proposition can be proved recursively using [START_REF] Han | Un autre q-analogue des nombres d'Euler[END_REF] and ( 16).

The fact that Q n (t, q) and R n (t, q) have simple expressions in terms of D and U permits to make a link with normal ordering [START_REF] Flajolet | Combinatorial models of creation-annihilation[END_REF]. Starting from an expression f (D, U ) of D and U , the problem is to find some coefficients c i,j such that we have the normal form:

f (D, U ) = i,j≥0 c i,j U i D j . ( 17
)
When f (D, U ) is a polynomial, we can always find such coefficients using the commutation relation DU -qU D = I, and a finite number of them are non-zero. For example, this is what we have done in [START_REF] Gélineau | Bijections for Entriger families[END_REF]. In Section 4, we will use some general results on normal ordering to give combinatorial models of P n and Q n (when q = 1).

What is interesting about normal ordering is that having the coefficients c i,j gives more insight on the quantity f (D, U ). For example, consider the case of Q n (t, q) and let f (D, U ) = (D + U DU ) n , then we have

Q n (t, q) = (D + U DU ) n 1 = i,j≥0 c i,j U i D j 1 = i≥0 c i,0 t i , (18)
i.e. we can directly obtain the coefficients of Q n (t, q) through this normal form.

Continued fractions.

Let D 1 and U 1 be the matrices of the operators D and U in the basis {t i } i∈N . Moreover, let W 1 be the row vector (t i ) i∈N and V 1 be the column vector (δ i,0 ) i∈N where we use Kronecker's delta. We have W 1 = (1, t, t 2 , . . . ), and:

D 1 =      0 [1]q (0) 0 [2]q 0 . . . (0) . . .      , U 1 =      0 (0) 1 0 1 0 (0) . . . . . .      , V 1 =      1 0 0 . . .      . ( 19
)
From the previous definitions, it follows that:

Q n (t, q) = W 1 (D 1 + U 1 D 1 U 1 ) n V 1 , R n (t, q) = W 1 (D 1 + D 1 U 1 U 1 ) n V 1 , (20)
D 1 U 1 -qU 1 D 1 = I, W 1 U 1 = tW 1 , D 1 V 1 = 0. ( 21
)
The point of writing this is that, from [START_REF] Koekoek | Hypergeometric orthogonal polynomials and their q-analogues[END_REF], we only need the relations in [START_REF] Leroux | Combinatorial resolution of systems of differential equations, I. Ordinary differential equations[END_REF] to calculate Q n (t, q) and R n (t, q). Even more, if D 2 , U 2 , W 2 , and V 2 are a second set of matrices and vectors satisfying relations in [START_REF] Leroux | Combinatorial resolution of systems of differential equations, I. Ordinary differential equations[END_REF], we also have

Q n (t, q) = W 2 (D 2 + U 2 D 2 U 2 ) n V 2 and R n (t, q) = W 2 (D 2 + D 2 U 2 U 2 ) n V 2 .
Indeed, when we have the relation [START_REF] Hoffman | Derivative polynomials for tangent and secant[END_REF] for a given f (D, U ), the coefficients c i,j are obtained only using the commutation relation, so the same identity also holds with either (D 1 , U 1 ) or (D 2 , U 2 ). We can take

W 2 = (1, 0, 0, . . . ), V 2 = V 1 , D 2 = D 1
, and:

U 2 =      t (0)
1 tq

1 tq 2 (0) . . . . . .      . ( 22
)
Then we have indeed

D 2 U 2 -qU 2 D 2 = I, W 2 U 2 = tW 2 , and D 2 V 2 = 0.
What is nice about this second set of matrices and vectors is that it enables us to make a link with continued fractions.

Definition 2.5. For any two sequences {b h } h≥0 and {λ h } h≥1 , let J(b h , λ h ) denote

J(b h , λ h ) = 1 1 -b 0 z - λ 1 z 2 1 -b 1 z - λ 2 z 2 . . . . (23)
We will always use z as variable and h as index of the two sequences so that there should be no ambiguity in the notation.

These are called J-fractions, or Jacobi continued fractions. They are related with moments of orthogonal polynomials (see [START_REF] Viennot | Une théorie combinatoire des polynômes orthogonaux, Lecture notes, UQ ÀM[END_REF]), but let us give the results for Q n (t, q) and R n (t, q) before we give more details about this. Proposition 2.6. We have:

∞ n=0 Q n (t, q)z n = J(b Q h , λ Q h ), ∞ n=0 R n (t, q)z n = J(b R h , λ R h ), (24)
where:

b Q h = tq h ([h] q + [h + 1] q ), b R h = tq h (1 + q)[h + 1] q , (25)
λ Q h = (1 + t 2 q 2h-1 )[h] 2 q , λ R h = (1 + t 2 q 2h )[h] q [h + 1] q . ( 26
)
Proof. First, observe that for any matrix M = (m i,j ) i,j∈N , the product W 2 M n V 2 is the upper-left coefficient (M n ) 0,0 of M n . We can obtain this coefficient of W 2 M n V 2 in the following way:

W 2 M n V 2 = i 1 ,...,i n-1 ≥0 m 0,i 1 m i 1 ,i 2 . . . m i n-2 ,i n-1 m i n-1 ,0 . (27)
When the matrix is tridiagonal, we can restrict the sum to the indices i 1 , . . . , i n-1 such that |i j -i j+1 | ≤ 1, so that they are the successive heights in a Motzkin path.

Then [START_REF] Stanley | A survey of alternating permutations[END_REF] shows that W 2 M n V 2 is the generating function of Motzkin paths of length n with some weights given by the coefficients of M , and using a classical argument [START_REF] Flajolet | Combinatorial aspects of continued fractions[END_REF] it follows that

∞ n=0 (W 2 M n V 2 )z n = J(m h,h , m h-1,h m h,h-1
). In the present case, it suffices to check that D 2 + U 2 D 2 U 2 and D 2 + D 2 U 2 U 2 are tridiagonal and calculate explicitly their coefficients to obtain the result. See also (34) and (36) below for a more general result.

In particular, it follows from the previous proposition that we have:

Q 2n (0, q) = E 2n (q), R 2n (0, q) = E 2n+1 (q), (28)
where E 2n (q) and E 2n+1 (q) are respectively the q-secant and q-tangent numbers defined by Han, Randrianarivony, Zeng [START_REF] Han | Un autre q-analogue des nombres d'Euler[END_REF] using continued fractions.

Remark 2.7. From the fact that Q n (1) = S n and R n (1) = 2 n E n+1 , the previous proposition implies

∞ n=0 S n z n = J(2h + 1, 2h 2 ), ∞ n=0 E n+1 z n = J(h + 1, h(h+1) 2 ). ( 29
)
We found only one reference mentioning the latter continued fraction, Sloane's OEIS [START_REF] Sloane | The on-line encyclopedia of integer sequences[END_REF], but there is little doubt it can be proved by classical methods. For example, using a theorem of Stieltjes and Rogers [13, Theorem 5.2.10], the continued fraction can probably be obtained through an addition formula satisfied by the exponential generating function of {E n+1 } n≥0 (this function is the derivative of tan z + sec z, i.e.

(1 -sin z) -1 ). Combinatorially, the result can be proved using André trees [9, Section 5] and the bijection of Françon and Viennot [START_REF] Goulden | Combinatorial Enumeration[END_REF]Chapter 5]. More generally, this shows that if we add a parameter x, then J(h + 1, x h(h+1)

2

) is the generating function of the André polynomials defined by Foata and Schützenberger [START_REF] Foata | Nombres d'Euler et permutations alternantes[END_REF].

An important property of J-fractions is the link with moments of (formal) orthogonal polynomials, and we refer to [START_REF] Flajolet | Combinatorial aspects of continued fractions[END_REF][START_REF] Viennot | Une théorie combinatoire des polynômes orthogonaux, Lecture notes, UQ ÀM[END_REF] for the relevant combinatorial facts. We consider here the continuous dual q-Hahn polynomials p n (x; a, b, c|q), or p n (x) for short. In terms of the Askey-Wilson polynomials which depend on one other parameter d, p n (x) is just the specialization d = 0 (see [START_REF] Koekoek | Hypergeometric orthogonal polynomials and their q-analogues[END_REF] for the definitions of these classical sequences, but our notations differ, in particular because of a rescaling x → x/2). We have the three-term recurrence relation

xp n (x) = p n+1 (x) + a + 1 a -A n -C n p n (x) + A n-1 C n p n-1 (x), (30)
together with p -1 (x) = 0 and p 0 (x) = 1, where

A n = 1 a (1 -abq n )(1 -acq n ) and C n = a(1 -q n )(1 -bcq n-1 ). ( 31
)
The p n (x) are orthogonal with respect to the scalar product (f, g) → L(f g) where L is the linear form such that

∞ n=0 L(x n )z n = J a + 1 a -A h -C h , A h-1 C h . (32)
The quantity L(x n ) is called the nth moment of the orthogonal sequence {p n (x)} n≥0 . Let µ n (a, b, c) denote this nth moment of the continuous dual q-Hahn polynomials p n (x). An elementary calculation shows the following:

Proposition 2.8. We have

Q n (t, q) = µ n (i √ q, -i √ q, t) (1 -q) n , R n (t, q) = µ n (iq, -iq, t) (1 -q) n . ( 33
)
Proof. We have to identify the ordinary generating functions of both sides in each identity. This is possible because we know in each case the explicit form of the Jfraction expansion, from (32) and Proposition 2.6. See also (34) and ( 35) below for a more general result.

This very simple link between our polynomials and the moments µ n (a, b, c) is one of the properties indicating that Q n (t, q) and R n (t, q) are interesting q-analogs of Q n (t) and R n (t). Note that in view of ( 15) and ( 16), it is tempting to define a q-analog Q

(a) n (t, q) of Q (a)
n (t) by the recurrence:

Q (a) n+1 (t, q) = (1 + q a t 2 )D Q (a) n (t, q) + [a] q tQ (a) n (t, q), (34)
together with Q (a) 0 (t, q) = 1. Though we will not study these apart from the particular cases a = 1 and a = 2, it is worth mentioning that a natural generalization of the previous proposition holds, more precisely we have:

Q (a) n (t, q) = µ n (iq a/2 , -iq a/2 , t) (1 -q) n , (35)
which can be proved by calculating explicitly the matrix

(I + q a U 2 2 )D 2 + [a] q U 2 .
The entries of this matrix show that the generating function of {Q (a) n (t, q)} has a J-fraction expansion with coefficients:

b h = tq h [h -1 + a] q + q a-1 [h + 1] q , λ h = (1 + t 2 q 2h-2+a )[h] q [h -1 + a] q . ( 36
)
Indeed we have the same coefficients if we replace (a, b, c) with (iq a/2 , -iq a/2 , t) in ( 31) and (32).

Combinatorial models via signed permutations

Definition 3.1. We denote [n] = {1 . . . n} and [[n]] = {-n . . . -1}∪{1 . . . n}. A signed permutation is a permutation π of [[n]] such that π(-i) = -π(i) for any i ∈ [[n]
]. It will be denoted π = π 1 . . . π n where π i = π(i), and S ± n is the set of all such π. We will also use the cycle notation, indicated by parenthesis: for example π

= 3, -1, 2, 4 is (1, 3, 2, -1, -3, -2)(4)(-4) in cycle notation.
We consider here two classes of signed permutations: snakes and cycle-alternating permutations. These will give combinatorial models of the derivative polynomials. As for the q-analog, going through other objects (weighted Dyck prefixes) we can obtain a statistic on cycle-alternating permutations following the parameter q.

We note that Elizalde and Deutsch defined cycle up-down permutations in [START_REF] Deutsch | Cycle-up-down permutations[END_REF], our cycle-alternating permutations are a variant.

3.1.

Snakes. There are several types of snakes to be distinguished, so let us first give the definition:

Definition 3.2. A signed permutation π = π 1 . . . π n is a snake if π 1 > π 2 < π 3 > . . . π n . We denote by S n ⊂ S ±
n the set of snakes of size n. Let S 0 n ⊂ S n be the subset containing the snakes π satisfying π 1 > 0, and S 00 n ⊂ S 0 n be the subset containing the snakes π satisfying π 1 > 0 and (-1) n π n < 0.

The sets S n and S 0 n were introduced by Arnol'd [START_REF] Arnol | d: The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF], under the name "β-snake" and "snakes of type B", respectively. The third set S 00 n is a new variant. It is practical to make a convention for the values π 0 and π n+1 . If π ∈ S n (respectively, π ∈ S 0 n , π ∈ S 00 n ) we define π 0 = -(n + 1) and π n+1 = (-1) n (n + 1) (respectively, π 0 = 0 and π n+1 = (-1) n (n + 1), π 0 = π n+1 = 0). This is not consistent with the inclusions S 00 n ⊂ S 0 n ⊂ S n , so we can think of these sets to be disjoint to avoid ambiguity in the sequel. Then, an element of any of these three sets is a π ∈ S ± n such that π 0 < π 1 > π 2 < π 3 > . . . π n+1 . For example in the case of S 00 n , the condition (-1) n π n < 0 means that if n is odd, π n > π n+1 = 0, and if n is even, π n < π n+1 = 0. For clarity, we will write π = (π 0 ), π 1 , . . . , π n , (π n+1 ). Definition 3.3. Let π be a snake in one of the sets S n , S 0 n , or S 00 n , and π 0 , π n+1 as above. We define a statistic cs(π) as the number of changes of sign through the values π 0 , . . . , π n+1 , i.e. cs(π

) = #{ i | 0 ≤ i ≤ n, π i π i+1 < 0 }.
Using this statistic, we have combinatorial models of the derivative polynomials. Theorem 3.4. For any n ≥ 0, we have:

P n (t) = π∈Sn t cs(π) , Q n (t) = π∈S 0 n t cs(π) , R n (t) = π∈S 00 n+1 t cs(π) . ( 37
)
Proof. We check that the right-hand sides satisfy the recurrences in (5) (case a = 1 or a = 2), but we only detail the case of R n (case a = 2), the other ones being similar.

We have R 0 = 1, and this corresponds to the snake (0), 1, (0). Also R 1 = 2t, and this corresponds to (0), 1, -2, (0) and (0), 2, -1, (0). Suppose the result is proved for R n-1 . Then, to prove it for R n , we distinguish three kinds of elements in S 00 n+1 (the convention is π 0 = π n+2 = 0). We will denote by π - i the number π i -1 if π i > 0 and

π i + 1 if π i < 0. • First, suppose that |π n+1 | = 1, hence π n+1 = (-1) n . Let π ′ = π - 1 . . . π - n .
Depending on the parity of n, we have either π n < π n+1 = 1 or π n > π n+1 = -1, and it follows on one hand that (-1) n π n < 0, on the other hand that π n π n+1 < 0. Thus π ′ ∈ S 00 n , and cs(π ′ ) = cs(π) -1. The map π → π ′ is bijective, and with the recurrence hypothesis, it comes that the set of π ∈ S 00 n+1 with |π n+1 | = 1 has generating function tR n-1 .

• Then, suppose that π 1 = 1, and let

π ′ = -π - 2 , . . . , -π - n+1 . From π 1 > π 2 , we obtain π 2 < 0, hence -π - 2 > 0. It follows that π ′ ∈ S 00 n . Moreover, since π 1 π 2 < 0 we obtain cs(π ′ ) = cs(π) -1.
With the recurrence hypothesis, it comes that the set of π ∈ S 00 n+1 with π 1 = 1 has generating function tR n-1 . • Eventually, suppose that there is j ∈ {2 . . . n} such that |π j | = 1. We have either π j-1 > π j < π j+1 or π j-1 < π j > π j+1 , and it follows that π j-1 and π j+1 have the same sign. We will obtain the term R ′ n-1 in the subcase where π j have also the same sign as π j-1 and π j+1 , and the term t 2 R ′ n-1 otherwise. Let us prove the first subcase, the second will follow since it suffices to consider snakes of the first subcase where π j is replaced with -π j .

Let

π ′ = π - 1 , . . . , π - j-1 , -π - j+1 , . . . , -π - n+1 .
Then we can check that π → (π ′ , j) is a bijection between π of the first subcase, and couples (π ′ , j) where π ′ ∈ S 0 n and j ∈ {2 . . . n} is such that π ′ j-1 π ′ j < 0. At the level of generating function, choosing a sign change in π ′ is done by differentiation with respect to t, and this explains why π of the first subcase are counted by R ′ n-1 .

Adding the different terms, we obtain (1+t 2 )R ′ n-1 +2tR n-1 = R n . This completes the recurrence. The difference for Q n (respectively, P n ) is roughly that only the second and third cases (respectively, only the third case) are to be considered.

The exponential generating function of {Q n (t)} n≥0 can be directly obtained using snakes in the form

∞ n=0 Q n (t) z n n! = sec z 1 -t tan z . ( 38
)
To prove this, let π ∈ S 0 n , and consider its unique factorization π = f 1 . . . f k , where each f k is a maximal non-empty factor such that all its entries have the same sign. Each of these factor has odd length, except possibly the last one. So it is convenient to think that if the last factor f k has odd size, there is also an empty factor f k+1 at the end, and consider the new factorization π = f 1 . . . f j (with j = k or j = k + 1). Note that cs(π) = j -1. The factorization proves (38), because π is built by assembling alternating permutations of odd size f 1 . . . f j-1 , and an alternating permutation of even size f j .

Using snakes, we can also directly obtain that

∞ n=0 R n (t) z n n! = ∞ n=0 Q n (t) z n n! 2 . (39)
Indeed, let π = (0), π 1 . . . π n+1 , (0) be among snakes counted by R n (t), i.e. π ∈ S 00 n+1 . There is j ∈ {1 . . . n+1} such that |π j | = n+1. We define π ′ = (0), π 1 . . . π j-1 , (π j ) and π ′′ = (0), (-1) n π n+1 , . . . , (-1) n π j+1 , ((-1) n π j ). After some relabelling, these define two snakes in S 0 j-1 and S 0 n-j+1 . We have cs(π) = cs(π ′ ) + cs(π ′′ ), and π is built by assembling π ′ and π ′′ , so this proves (39).

Another interesting question concerning snakes is the following. For a given permutation σ = σ 1 . . . σ n ∈ S n , the problem is to choose signs ǫ = ǫ 1 . . . ǫ n ∈ {±1} n such that π = ǫ 1 σ 1 , . . . , ǫ n σ n is a snake. Arnol'd [START_REF] Arnol | d: The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF] described the possible choices such that π ∈ S 0 n in terms of ascent and descent sequences in the permutation. Let i ∈ {2 . . . n -1}, then a case-by-case argument from [START_REF] Arnol | d: The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF] shows that:

• if σ i-1 < σ i < σ i+1 , then ǫ i = ǫ i+1 , • if σ i-1 > σ i > σ i+1 , then ǫ i-1 = ǫ i , • if σ i-1 > σ i < σ i+1 , then ǫ i-1 = ǫ i+1 . ( 40
)
Following this, we can answer the problem of building a snake from a permutation in terms of some permutations statistics. We can apply this argument to the three sets S n , S 0 n , and S 00 n , essentially by varying the conventions on σ(0) and σ(n + 1). Definition 3.5. Let σ = σ 1 . . . σ n ∈ S n , we make the convention that σ 0 = σ n+1 = n + 1. We also need to consider other conventions, so let S 0 n and S 00 n be "copies" of the set S n , where:

• If σ ∈ S 0 n , we set σ 0 = 0 and

σ n+1 = n + 1. • If σ ∈ S 00
n , we set σ 0 = σ n+1 = 0. Let σ be in one of the sets S n , S 0 n , or S 00 n . An integer

i ∈ [n] is a valley of σ if σ i-1 > σ i < σ i+1 , a peak if σ i-1 < σ i > σ i+1 , a double descent if σ i-1 > σ i > σ i+1
, and a double ascent if σ i-1 < σ i < σ i+1 . Let va(σ) denote the number of valleys in σ, pk(σ) denote the number of peaks in σ, and dda(σ) denote the number of double descents and double ascents in σ.

For example, we see 1, 3, 2 ∈ S 0 3 as (0), 1, 3, 2, (4). Then 3 is a valley. On the other hand, we see 1, 3, 2 ∈ S 00 3 as (0), 1, 3, 2, (0). Then 3 is a double descent. We note that the result below has also been obtained by Ma [START_REF] Ma | Derivative polynomials and enumeration of permutations by number of interior and left peaks[END_REF] (in the case of P n and Q n ). Proposition 3.6. When n ≥ 1, we have:

P n (t) = σ∈Sn t dda(σ) (1 + t 2 ) va(σ) = σ∈S 00 n t dda(σ) (1 + t 2 ) pk(σ) , (41)
Q n (t) = σ∈S 0 n t dda(σ) (1 + t 2 ) va(σ) , R n (t) = σ∈S 00 n+1 t dda(σ) (1 + t 2 ) va(σ) . ( 42
)
The last two identities are also true when n = 0.

Proof. This follows from Theorem 3.4 and (40), which now can be extended to the cases i = 1 or i = n using the conventions on σ 0 and σ n+1 (note that we also need to consider ǫ 0 and ǫ n+1 ). Let us first prove the case of P n , σ ∈ S n and π ∈ S n .

We have ǫ 0 = -1 since we require that π 0 = -(n + 1). The first two rules in (40) show that to each double ascent or double descent we can associate a sign change in π, and that the only remaining choices to be done concern the valleys. At a valley

σ i-1 > σ i < σ i+1 , we can have either ǫ i-1 = ǫ i = ǫ i+1 , or ǫ i-1 = -ǫ i = ǫ i+1 , i.
e. 0 or 2 sign changes. This proves the first equality in (41), and the second follows by taking the complement permutation. The cases of Q n and R n are proved similarly, except that we do not consider ǫ 0 and we have ǫ 1 = 1.

An important property of the statistics va(σ) and dda(σ) is that they can be followed through the bijection of Françon and Viennot (see for example the book [START_REF] Goulden | Combinatorial Enumeration[END_REF]). Omitting details, this gives combinatorial proof of:

∞ n=0 Q n (t)z n = J (2h + 1)t, (1 + t 2 )h 2 , ( 43
) ∞ n=0 R n (t)z n = J (2h + 2)t, (1 + t 2 )h(h + 1) , (44)
which is the particular case q = 1 of Proposition 2.6. Unfortunately, it seems difficult to follow the parameter q through this bijection, and obtain nice statistics on S 0 n and S 00 n+1 corresponding to Q n (t, q) and R n (t, q).

Cycle-alternating permutations.

From the combinatorial interpretations of derivative polynomials in terms of snakes, we can derive other ones using simple bijections. We need some general definitions concerning signed permutations.

Definition 3.7. Let π ∈ S ± n . We denote neg(π) the number of i ∈ [n] such that π i < 0. For any orbit O of π, let -O = {-x | x ∈ O}. A cycle of π is an unordered pair of orbits {O 1 , O 2 } such that -O 1 = O 2 . It is called a one-orbit cycle if O 1 = O 2
and two-orbit cycle otherwise. (This is known to be a natural notion of cycle since there is a decomposition of any signed permutation into a product of disjoint cycles.) For any signed permutation π, its arch diagram is defined as follows: draw on the horizontal axis 2n nodes labelled by the integers in [[n]] in increasing order, then for any i draw an arch from i to π(i) such that the arch is above the horizontal axis if i ≤ π(i) and below the axis otherwise.

See Figure 1 for an example of an arch diagram. Since the labels from -n to n are in increasing order we do not need to explicitly write them. See also Figure 2 further for another example. We did not specify what happens with the fixed points in the arch diagram. Although this will not be really important in the sequel, we can choose to put a loop at each positive fixed point and a loop at each negative fixed point. This way, the arch diagram of a signed permutation is always centrally symmetric.

Definition 3.8. Let π ∈ S ± n . An integer i ∈ [[n]] is a cycle peak of π if π -1 (i) < i > π(i), and it is a cycle valley of π if π -1 (i) > i < π(i). The signed permutation π is cycle-alternating if every i ∈ [[n]
] is either a cycle peak or a cycle valley. Let C n ⊂ S ± n denote the subset of cycle-alternating signed permutations, and C • n ⊂ C n be the subset of π ∈ C n with only one cycle. Lemma 3.9. Let π ∈ C • n . Then n is even (respectively, odd) if and only if π has a two-orbit cycle (respectively, a one-orbit cycle).

Proof. In a cycle-alternating permutation, each orbit has even cardinality because there is an alternation between the cycle peaks and cycle valleys. So, if there are two opposite orbits of size n, n is even.

In the cycle-alternating permutation π, -n is a cycle valley and n is a cycle peak. If there is one orbit, it can be written π = (n, i 1 , . . . , i n-1 , -n, -i 1 , . . . , -i n-1 ) in cycle notation. Because of the alternation of cycles peaks and cycle valleys, it follows that n is odd. Theorem 3.10. We have :

P n (t) = π∈C • n+1 t neg(π) , Q n (t) = π∈Cn t neg(π) , R n (t) = π∈C • n+2 π 1 >0 t neg(σ) . (45)
Proof. There are simple bijections between snakes and cycle-alternating permutations to prove this from Theorem 3.4. Let us begin with the case of P n , so let π ∈ S n . Suppose first that n is odd, hence π 0 = π n+1 = -(n + 1). We can read π in cycle notation and consider the two-orbit cycle π ′ = (π 0 , π 1 , . . . , π n )(-π 0 , -π 1 , . . . , -π n ). Then π ′ ∈ C • n+1 . When n is even, we have -π 0 = π n+1 = n + 1, and the bijection is defined by taking π ′ = (π 0 , π 1 , . . . , π n , -π 0 , -π 1 , . . . , -π n ). The map π → π ′ is clearly invertible, and using the previous lemma, we have a bijection between S n and C • n+1 . Let i ∈ {0, . . . , n}, then π i π i+1 < 0 is equivalent to π ′ (|π i |) = -|π i+1 | < 0, and it follows that cs(π) = neg(π ′ ). This proves the first equality of the theorem.

The case of R n is slightly different. In this proof, we will denote by π + i the number

π i + 1 if π i > 0, and π i -1 if π i < 0. Let π ∈ S 00 n+1 . If n + 1 is odd, hence π n+1 > 0, we define π ′ = (1, π + 1 , . . . , π + n+1 )(-1, -π + 1 , . . . , -π + n+1 ). If n + 1 is even, hence π n+1 < 0,
we define π ′ = (1, π + 1 , . . . , π + n+1 , -1, -π + 1 , . . . , -π + n+1 ). In each case, it is easily checked that this defines a bijection from S 00 n+1 to the subset of π ∈ C • n+2 satisfying π 1 > 0, so that a change of sign in π correspond to a i > 0 with π ′ (i) < 0.

The case of Q n requires more attention. Let π ∈ S 0 n , we need to split it into blocks that will correspond to the cycles of an element π ′ ∈ C n . This can be done by a variant of Foata's fundamental transform [START_REF] Lothaire | Combinatorics on words[END_REF]. Let a 1 < • • • < a k be the left-to-right maxima of |π 1 | . . . |π n | ∈ S n (recall that u is a left-to-right maximum of σ ∈ S n when σ(i) < σ(u) for any i < u). We consider the factors of π, f 1 = π a 1 . . . π a 2 -1 , f 2 = π a 2 . . . π a 3 -1 , up to f k = π a k . . . π n (we can take the convention a k+1 = n + 1). We form π ′ by putting together some cycles as follows: if f i has odd length, it gives a one-orbit cycle (π a i . . . π a i+1 -1 , -π a i . . . -π a i+1 -1 ), and if it has even length, it gives a two-orbit cycle (π a i . . . π a i+1 -1 )(-π a i . . . -π a i+1 -1 ). The definition of a i shows that π a i is greater than π a i +1 . . . π a i+1 -1 , and consequently these cycles are indeed alternating. The inverse bijection is easily deduced: we can write π ′ ∈ C n as a product of cycles π ′ = c 1 . . . c k , where the cycles are sorted so that their maximal entries are increasing. To each c i we associate a word f i so that c i is either (f i , -f i ) or (f i )(-f i ), and such that the first letter of f i is the maximum entry of c i . Then we can form the snake π = f 1 , ǫ 2 f 2 , . . . , ǫ k f k , where the signs ǫ 2 , . . . , ǫ k ∈ {±1} are chosen so that π is alternating (there is a unique choice).

It is in order to give examples of the previous two bijections. If we start from a snake π = (0), 4, -2, -1, -5, 3, -6, (7) ∈ S 0 6 , the left-to-right maxima of |π| are 1, 4, 6, and this gives π ′ = (4, -2, -1, -4, 2, 1)(-5, 3)(5, -3)(6, -6) ∈ C 6 . As for the other direction, let π ′ = (5, -2, 3, -5, 2, -3)(6, -1)(-6, 1)(7, -4)(-7, 4) ∈ C 7 . It is a product of three cycles so that the snake π is formed by putting together three words 5, -2, 3, and 6, -1, and 7, -4. We need to change the signs of the second and third words to obtain a snake, which is π = (0), 5, -2, 3, -6, 1, -7, 4, (-8) ∈ S 0 7 . One can check on the examples that in both cases we have cs(π) = neg(π ′ ), but this does not immediately follows the construction and need to be proved now. Let a, b > 0, such that π ′ (a) = -b, we can associate a sign change in π to each such pair (a, b). The two integers are in the same cycle c i . If the word f i is of the form . . . , a, -b, . . . or . . . , -a, b, . . . , then either the factor a, -b or -a, b appears in the word ǫ i f i , and consequently appears in π as a sign change. The other possibility is that f i = b, . . . , -a which only occur when f i has even length, and f i = b, . . . , a which only occur when f i has odd length. If b (respectively -b) appear in π, it is greater (respectively, smaller) than his neighbor entries, and after examining a few cases it comes that the same is true for a. It follows that there is a sign change in π between the last entry of ǫ i f i and its right neighbor. This completes the proof.

Using cycle-alternating permutations, we can give a bijective proof of the fact that P n+1 = (1 + t 2 )R n . This can be written

π∈C • n+2 t neg(π) = (1 + t 2 ) σ∈C • n+2 σ 1 >0 t neg(σ) . ( 46
)
Now, consider the conjugation by the transposition (1, -1), i.e. the map that sends π to (1, -1)π(1, -1). This is a fixed point free involution on C • n+2 which proves combinatorially (46), as it is easily seen on the arch diagrams. Indeed, in this representation the involution exchanges the dot labelled 1 with the dot labelled -1, see Figure 2. We have π(1) > 0 if and only if its image π ′ = (1, -1)π(1, -1) does not satisfy π ′ (1) > 0, and if π(1) > 0, we have neg(π ′ ) = neg(π) + 2. This proves (46). Note that it is also possible to prove P n+1 = (1 + t 2 )R n on the snakes, using Proposition 3.6, but this is more tedious. Using cycle-alternating permutations, we can also obtain the exponential generating function of {P n } n≥0 , knowing the one of {Q n } n≥0 . Indeed, a cycle-alternating permutation is an assembly of cycle-alternating cycles, in the sense of combinatorial species, and this gives immediately:

∞ n=0 P n (t) z n+1 (n + 1)! = log ∞ n=0 Q n (t) z n n! = log 1 cos z -t sin z , (47)
and after differentiation, we obtain the formula for P n (t) z n n! as in Equation ( 7). 3.3. The q-analogs. It is possible to give combinatorial interpretations of Q n (t, q) and R n (t, q) using cycle-alternating permutations, and the notion of crossing for signed permutations which was defined in [START_REF] Corteel | Matrix Ansatz, orthogonal polynomials and permutations[END_REF]. But in the case of cycle-alternating permutations, there is a more simple equivalent definition which is the following. Definition 3.11. A crossing of π ∈ C n is a pair (i, j) ∈ [[n]] 2 such that i < j < π(i) < π(j). Equivalently, it is the number of intersection points among the arches above the horizontal axis in the arch diagram of π. We denote by cr(π) the numbers of crossings in π.

Because of the symmetry in the arch diagram, cr(π) is half the total number of intersection points among the arches. For example, the two permutations in Figure 2 have respectively 2 and 3 crossings. This kind of statistic can be followed through bijections between permutations and paths [START_REF] Corteel | Crossings and alignments of permutations[END_REF], but let us first show that Q n (t, q) and R n (t, q) are related with some weighted Dyck prefixes (a Dyck prefix being similar to a Dyck path except that the final height can be non-zero). Definition 3.12. Let P n be the set of weighted Dyck prefixes of length n, where

• each step ր between heights h and h+1 has a weight q i for some i ∈ {0, . . . , h+1},

• each step ց between heights h and h + 1 has a weight q i for some i ∈ {0, . . . , h}. Let P ′ n ⊂ P n be the subset of paths p such that there is no step ր starting at height h with the maximal weight q h+1 . For any p ∈ P n , let fh(p) be its final height, and let w(p) be its total weight, i.e. the product of the weights of each step. Proposition 3.13. We have:

Q n (t, q) = p∈P ′ n t fh(p) q w(p) , R n (t, q) = p∈Pn t fh(p) q w(p) . (48)
Proof. In the proof of Proposition 2.6, we have used the matrices

D 2 + U 2 D 2 U 2 and D 2 + D 2 U 2 U 2
, thought of as transfer matrices for walks in the non-negative integers. We can do something similar with the matrices

D 1 + U 1 D 1 U 1 =      0 [1]q (0) [1]q 0 [2]q [2]q 0 . . . (0) . . . . . .      , D 1 + D 1 U 1 U 1 =      0 [1]q (0) [2]q 0 [2]q [3]q 0 . . . (0) . . . . . .      . (49)
Recall that we have [START_REF] Koekoek | Hypergeometric orthogonal polynomials and their q-analogues[END_REF], where W 1 = (1, t, t 2 , . . . ). In terms of paths, the coefficients in the matrices and vectors have the following meaning: from V 1 = (1, 0, . . . ) * , we only consider paths starting at height 0, and from W 1 = (1, t, t 2 , . . . ) there is the weight t fh(p) for the path p. The coefficients (h+1, h) in the matrices give the possible weights on steps ր from height h to h + 1, the coefficients (h, h + 1) in the matrices give the possible weights on steps ց from height h + 1 to h. The result follows.

Proposition 3.14. There is a bijection Ψ : C n → P ′ n such that neg(π) = fh(p) and cr(π) = w(p) if the image of π is p.

Proof. We can use the bijection Ψ F Z from [START_REF] Corteel | Crossings and alignments of permutations[END_REF] between permutations and weighted Motzkin paths. To do this, we identify S ± n with a subset of S 2n via the orderpreserving bijection [[n]] → [2n]. This subset is characterized by the fact that the arrow diagrams are centrally symmetric, and via Ψ F Z from [START_REF] Corteel | Crossings and alignments of permutations[END_REF], it is in bijection with some weighted Motzkin paths that are vertically symmetric. Cycle-alternating permutations correspond to the case where there is no horizontal step, i.e. they are in bijection with some weighted Dyck paths that are vertically symmetric. Keeping the first half of these Dyck paths gives the desired bijection.

For convenience, we rephrase here explicitly the bijection of the previous proposition. Let π ∈ C n , then we define a Ψ(π) ∈ P ′ n such that, for any j ∈ {-n . . . -1}: • the (n + 1 + j)th step is ր if π -1 (j) > j < π(j) and ց if π -1 (j) < j > π(j),

• if the (n + 1 + j)th step is ր, it has a weight q k where k is the number of i such that (i, j) is a crossing, i.e. i < j < π i < π j , • if the (n + 1 + j)th step is ց, it has a weight q k where k is the number of i such that (-i, -j) is a crossing, i.e. -i < -j < -π i < -π j . See Figure 3 for an example.

→

q 0 q 1 q 0 q 0 q 2 q 1 q 0 Through this bijection we obtain combinatorial models of Q n (t, q) and R n (t, q) using the notion of crossing. Proposition 3.15. We have

Q n (t, q) = π∈Cn t neg(π) q cr(π) , R n (t, q) = π∈C n+1 π n+1 <0 t neg(π)-1 q cr(π) . (50)
Alternatively, the condition π n+1 < 0 in the second identity can be replaced with π -1 (n + 1) < 0.

Proof. The first identity follows from Proposition 3.13 and the bijection Ψ between C n and P ′ n , but the second one is not as immediate. First, note that the bijection π → π -1 stabilizes the set C n and preserves the number of crossings, since it is just an horizontal symmetry on the arch diagrams. This proves the fact that we can replace π n+1 < 0 with π -1 (n + 1) < 0.

Then, let us consider the subset P ′′ n+1 ⊂ P ′ n+1 of elements p such that there is no step ց from height h + 1 to h with weight q h (note that this condition implies there is no return to height 0). There is an obvious bijection from P ′′ n+1 to P n , because removing the first step in p ∈ P ′′ n+1 gives a path which is in P n with respect to the shifted origin [START_REF] Arnol | d: The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF][START_REF] Arnol | d: The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF]. This proves:

R n (t, q) = p∈P ′′ n+1 t fh(p)-1 q w(p) . (51)
It remains to show that the image of P ′′ n+1 via Ψ -1 is precisely the set of π ∈ C n+1 such that π -1 (n + 1) < 0. Essentially, this follows from the fact that there are some steps in the path which characterize the right-to-left minima in π, and we can use Lemma 3.2.2 from [START_REF] Josuat-Vergès | Combinatoric of the three-parameter PASEP partition function[END_REF]. In our case, the subset P ′′ n+1 ⊂ P ′ n+1 corresponds to a subset of S 2n+2 (via the identification S ± n+1 → S 2n+2 ), more precisely to the subset of σ having no right-to-left minima among 1 . . . n + 1, i.e. σ -1 (1) > n + 1. In terms of π ∈ S ± n+1 , this precisely means that π -1 (-n -1) > 0 and completes the proof. Remark 3.16. Chen, Fan and Jia [START_REF] Chen | Labelled ballot paths and the Springer numbers[END_REF] gave a bijection between snakes of type B and Dyck prefixes such that there are h + 1 possible choices on each step between height h and h + 1, and their statistic α(π) (see Theorem 4.5) is the same as our statistic cs(π), though defined differently. We can have such a bijection by composing two we have presented (their bijection is not the same as ours and does not seem to be directly related).

3.4. Another variant of Ψ F Z . With another adaptation of this bijection, we can link C n and some weighted Motzkin path, so that we obtain a combinatorial proof of a J-fraction generalizing (43) and (44) in Theorem 3.17 below. As a consequence of Theorem 3.10, we have:

Q (a) n (t) = π∈Cn a cyc(π) t neg(π) (52)
where cyc(π) is the number of cycles, indeed since there is a "cycle structure" in C n it suffices to take the ath power of the exponential generating function to have a parameter a counting cyc(π). With the recurrence for Q n (t) in ( 5) and with the same method as in the case of Q n and R n , we can prove a continued fraction for the ordinary generating function of {Q (a) n (t)} n≥0 . We prove here bijectively this continued fraction, by going from C n to weighted Motzkin paths. To this end, we use another representation of a signed permutation, the signed arch diagram. Let π ∈ S ± n , this diagram is obtained the following way: draw n dots labelled by 1 . . . n from left to right on the horizontal axis, then for each i ∈ [n], draw an arch from i to |π i |, and label this arrow with a + if π i > 0 and with a -if π i < 0. We understand that as in the previous arch notation, the arch is above the axis if i ≤ |π i | and below otherwise. See the left part of Figure 4 for an example. (In the case |π i | = i, the arch is a loop attached to the dot i.) A case-by-case study shows that π is cycle-alternating if and only if it avoids certain configurations in the signed arch diagram, which are listed in the right part of Figure 4 (± being either + or -). Note that these forbidden configurations are reminiscent of (40). Once we know the forbidden configurations, it is possible to encode the signed arch diagram of π ∈ C n by a weighted Motzkin path of n steps, in a way similar to Ψ F Z from [START_REF] Corteel | Crossings and alignments of permutations[END_REF]. The diagram of π is scanned from left to right, and the path is built such that:

• If the ith node in π is then the ith step of p if ր, moreover this step has label + (resp. -) if the two arches starting from the ith node have label + (resp. -).

• If the ith node in π is then the ith step of p if →. Moreover this step has label (j) if the left strand in the ith node is connected to the jth strand of the "partial" signed arch diagram (say, from bottom to top). See for example the left part of Figure 5 where there are three possible choices to connect this kind of node. We can see that the possible labels are (1), . . . , (h) where h is the starting height of the ith step in the path.

• Similarly if the ith node in π is then the ith step of p if →, and this step has label (j ′ ) if the ith node is connected on the left to the jth strand of the "partial" signed arch diagram (say, from top to bottom).

• If the ith node in π is then the ith step is → with label (0).

• If the ith node in π is then the ith step is ց with a label (j, k) where j and k respectively encode where the upper and lower strands are connected, as in the case of and above.

+ -

+ - - - - + + + + . . . → + (1)
+ ( 2) Quite a few bijections of this kind are known so we will not give further details. We have also used this kind bijection in [START_REF] Corteel | Crossings of signed permutations and q-Eulerian numbers of type B[END_REF], for example. As for the parameters a and t, they are taken into account in the following way:

- ( 2
• For each arch with label -linking i and j where i < j, we give a weight t to the ith step in the path. Thus there is a weight t 2 on the step ր with label -, and a weight t on each step →. • For each i which is the maximal element of a cycle, we give a weight a to the ith step. Thus each step → with weight (0) has a weight a, since these correspond to nodes or cycles of the form (i, -i). Besides, there is a weight a on some of the step ց. More precisely, there are h 2 possible labels on a step ց starting at height h, and h of them have this weight a. Indeed, for each choice of where to connect the upper strand of the node there is a unique choice of where to connect the lower strand so that a new cycle is "closed".

Using the classical correspondence between weighted Motzkin paths and J-fractions [START_REF] Flajolet | Combinatorial aspects of continued fractions[END_REF], this bijection proves the following theorem. Theorem 3.17. Let Q (a) n (t) be the polynomials in a and t with exponential generating function (cos z-t sin z) -a , or defined combinatorially by (52). Then, using the notation in Definition 2.5, we have:

∞ n=0 Q (a) n (t)z n = J (2h + a)t, h(h -1 + a)(1 + t 2 ) . (53)
Apart from the combinatorial side, this result was already known by Stieltjes [START_REF] Stieltjes | Sur quelques intégrales définies et leur développement en fractions continues[END_REF]. Besides his analytical proof, it is also possible to obtain the continued fraction by showing that the exponential generating function satisfies some particular kind of addition formula which permits to make use of a theorem of Stieltjes and Rogers, see for example [START_REF] Goulden | Combinatorial Enumeration[END_REF]Theorem 5.2.10]. We thank Philippe Flajolet for communicating these facts and references.

Increasing trees and forests

So far, we have only used recurrence relations and bijections to derive our new models of the derivative polynomials. Some more elaborate methods apply as well to give combinatorial models in terms of increasing trees and forests. We first present how to use the combinatorial theory of differential equations, as exposed by Leroux and Viennot in [START_REF] Leroux | Combinatorial resolution of systems of differential equations, I. Ordinary differential equations[END_REF], and secondly how to use recent results of B lasiak and Flajolet related with operators and normal ordering [START_REF] Flajolet | Combinatorial aspects of continued fractions[END_REF].

4.1. Increasing trees via differential equations. An archetype example in the combinatorial theory of differential equation is the one of the tangent and secant functions (see [START_REF] Leroux | Combinatorial resolution of systems of differential equations, I. Ordinary differential equations[END_REF]), and it has become a classical method to show that Euler numbers E n count some increasing trees, i.e. labelled trees where labels are increasing from the root to the leaves. Here we have a system of two differential equations similar to the one of tangent and secant, except that an initial condition is given by the parameter t instead of 0. This will give rise to more general trees where we allow some leaves with no label having a weight t. Lemma 4.1. Let f = P n z n /n! and g = Q n z n /n!, then we have:

f ′ = 1 + f 2 f (0) = t, g ′ = f g g(0) = 1. (54)
Proof. Of course, this can be checked on the closed form given in [START_REF] Deutsch | Cycle-up-down permutations[END_REF]. Also, f ′ = 1+ f 2 can be directly checked on the snakes as in the case of alternating permutations [START_REF] Stanley | A survey of alternating permutations[END_REF], and g ′ = f g follows from f = (log g) ′ previously seen.

It is adequate to rewrite the equations in the following way:

f = t + z + f 2 , g = 1 + f g. (55)
Let us begin with the case of f (z). From f = t + z + f 2 , and proceeding as in [START_REF] Leroux | Combinatorial resolution of systems of differential equations, I. Ordinary differential equations[END_REF], f (z) counts increasing trees that are recursively produced by the following rules, starting from an isolated node marked by f :

• a node marked by f can become a leaf with no label (this corresponds to the term t in f = t + z + f 2 , f (z), so these leaves will have a weight t), • a node marked by f can become a leaf with an integer label, this label being the smallest integer that does not already appear in the tree (this corresponds to the term z in f = t + z + f 2 ), • a node marked by f can become an internal node having an integer label and two (ordered) sons marked by f (this corresponds to the last term f 2 in f = t + z + f 2 ). As before, the integer label is the smallest integer that does not already appear in the tree. More precisely, the coefficient of z n in f (z) counts these trees having n integer labels. See Figure 6 for an example of tree produced by these rules.

f → 1 f f → 1 f 2 f f → 1 2 f f → 1 2 3 f → 1 2 3 4
= t + z + f 2 .
The case of g(z) is quite similar. Starting from an isolated node marked by g, each node marked by g can become either a leaf with no label, or an internal node having two sons respectively marked by f and g. Note that we need the production rules for f to build a tree counted by g, and note also that g can produce an empty leaf which has no weight t, contrary to the empty leaves produced by f .

The two kinds of tree can also be given a non-recursive definition.

Definition 4.2. Let T n be the set of complete binary trees, such that:

• except some leaves that are empty, the nodes are labelled by integers so that each i ∈ [n] appears exactly once,

• the labels are increasing from the root to the leaves. Let em(T ) be the number of empty leaves of T ∈ T n , and let T * n ⊂ T n be the subset of trees such that the rightmost leaf is empty.

The production rules for f (respectively, g) can be checked on the set T n (respectively T * n ), so that the result of the above discussion is the following. Theorem 4.3. We have:

P n (t) = T ∈Tn t em(T ) , Q n (t) = T ∈T * n t em(T )-1 . ( 56
)
term in D + aU + U U D. More precisely, to each term U k D ℓ we associate a gate consisting of one node with k outgoing strands and ℓ ingoing strands. See the left part of Figure 7. Then, c n,i,j count labelled diagrams obtained by connecting n of these gates such that:

• i outgoing strands and j ingoing strands are not connected,

• all other strands are connected, so that each ingoing strand is connected with an outgoing strand and these form a directed edge,

• the gates are labelled by the integers in {1, . . . , n}, and labels are increasing when we follow a directed edge,

• at each node, the ingoing strands on one side and the outgoing strands on another side are ordered,

• there is a weight a at each gate corresponding to the term U . We have

Q (a)
n (t) = (D + aU + U U D) n 1 = i,j≥0 c i,j U i D j 1 = i≥0 c i,0 t i (59) so that we can only consider diagrams with no unconnected ingoing strand, and t counts the unconnected outgoing strands. The labelled diagrams described by the above rules are essentially the same as elements in F n : it suffices to add an empty leaf at each unconnected outgoing strand to see the equivalence. It is clear that the node corresponding to the term U will appear exactly once in each connected component of the labelled diagrams, so the parameter a counts indeed the connected components.

In the case of P n , we can also consider f n (D, U ) = (D + U U D) n U and c n,i,j the coefficient of U i D j in its normal form, as in [START_REF] Hoffman | Derivative polynomials for tangent and secant[END_REF]. This case is somewhat different since f n (D, U ) is not the nth power of some expression, but similar arguments apply as well: the labelled diagrams that appear have n + 1 gates, the gate labelled 1 is of type U , all other gates are of type D or U U D. These labelled diagrams are the same as elements in U n+1 , as in the previous case we just have to add an empty leaf to each unconnected outgoing strand to see the equivalence. As previously said, we refer to [START_REF] Flajolet | Combinatorial models of creation-annihilation[END_REF] for precisions about this proof. There is a simple bijection between T n and U n+1 : given T ∈ T n , relabel the nodes by i → i + 1, then add a new node with label 1 on top of the root. There is also a simple bijection between T * n and F n : let T ∈ T * n , remove the rightmost leaf, as well as all edges in the path from the root to the rightmost leaf, then the remaining components form the desired forest. See Figure 8 for an example.

Thus, Theorems 4.3 and 4.5 are essentially equivalent although obtained by different methods. It is also in order to give a bijection between U n and C • n , and by applying this bijection componentwise it will give a bijection between F n and C n . It is more practical to give the bijection from T n to S n (recall that we already have simple bijections T n → U n+1 and S n → C • n+1 ), so let T ∈ T n . Consider the "reading word" of this tree (it can be defined by w(T ) = w(T 1 ) i w(T 2 ) if the tree T has a root labelled i, left son T 1 and right son T 2 ). This word contains integers from 1 to n, and some letters (say •) to indicate the empty leaves. The first step is to replace each i with n + 1 -i in this word. To obtain the snake, replace each integer i by (-1) j+1 i where j is the number of • before i in the word, then remove all •. See Figure 9 for an example. Actually, this bijection can be highlighted by Proposition 3.6 and the discussion leading to it. Indeed, it is just a variant of a classical bijection between permutations and unary-binary increasing trees [START_REF] Viennot | Une théorie combinatoire des polynômes orthogonaux, Lecture notes, UQ ÀM[END_REF], where double ascents and double descents correspond to nodes having only one child, and valleys correspond to leaves. Via these bijections, removing the empty leaves of T ∈ T n is the same as taking the absolute value of a snake S ∈ S n . In the other direction, T seen as a unary-binary tree together with the data of the empty leaves, is the same as a permutation together with a choice of signs making it into a snake.

  (a)n (t) such that d n dx n sec a x = Q (a)n (tan x) sec a x.

Figure 1 .

 1 Figure 1. The arch diagram of π = 2, -4, 6, 1, -3, 7, 5.

Figure 2 .

 2 Figure 2. The arch diagram of the cycle-alternating permutation π = (1, 4, -5, -2, -3, -1, -4, 5, 2, 3) ∈ C • 5 , and of its conjugate (1, -1)π(1, -1).

Figure 3 .

 3 Figure 3.The bijection Ψ from C n to P ′ n in the case of π = 3, 4, -7, 2, 6, 1, 5.

Figure 4 .

 4 Figure 4. The signed arch diagram of π = 2, -4, -6, 5, -3, -1, 7, and the forbidden configurations in the signed arch diagram of a cyclealternating permutation.

Figure 5 .

 5 Figure 5. Construction of the bijection from the signed arch diagram of π ∈ C n to a labelled Motzkin path.

Figure 6 .

 6 Figure 6. Tree produced via the equation f = t + z + f 2 .

Figure 7 .

 7 Figure 7. The "gates" corresponding to terms in D + aU + DU U , and a labelled diagram obtained by connecting them.

Figure 8 .

 8 Figure 8. The bijection from T * n to F n .

4 → 3 , 2 ,Figure 9 .

 4329 Figure 9. The bijection from T n to S n .

Acknowledgement

Part of this research was done during a visit of the LABRI in Bordeaux, and I thank all the Bordelais for welcoming me and for various suggestions concerning this work. I thank the reviewers who provided relevant references.

Supported by the French National Research Agency ANR, grant ANR08-JCJC-0011, and the Austrian Science Foundation FWF, START grant Y463. 1

4.2.

Increasing trees via normal ordering. Some recent results of B lasiak and Flajolet [START_REF] Flajolet | Combinatorial models of creation-annihilation[END_REF] directly apply in the present context and also give models of P n (t) and Q (a) n (t) in terms of increasing trees and forests. Let D be the derivation with respect to t and U the multiplication by t (i.e. we are in the particular q = 1 of operators defined in [START_REF] Flajolet | Combinatorial aspects of continued fractions[END_REF]). We have DU -U D = I. A general idea in [START_REF] Flajolet | Combinatorial models of creation-annihilation[END_REF] is that the coefficients c i,j in the normal form of f (D, U ) as in [START_REF] Hoffman | Derivative polynomials for tangent and secant[END_REF], at least for certain particular forms of f (D, U ), naturally counts some labelled directed graphs which are produced by connecting some "gates". In the present case, when

n , and we obtain some increasing trees and forests. The theorem of this subsection is a direct application of a main result of Flajolet and B lasiak [2, Theorem 1], so as a proof we will roughly explain some ideas leading to the definition below and refer to [START_REF] Flajolet | Combinatorial models of creation-annihilation[END_REF] for more details. Definition 4.4. Let F n be the set of plane rooted forests satisfying the following conditions:

• each root has exactly one child, and each of the other internal nodes has exactly two (ordered) children,

• there are n nodes labelled by integers from 1 to n, but some leaves can be nonlabelled (these are called empty leaves), and labels are increasing from each root down to the leaves. Note that the trees forming a forest are unordered. Let U n ⊂ F n be the subset of trees, i.e. forests with one connected component. For any tree or forest T , let em(T ) be the number of empty leaves, and let cc(T ) be its number of connected components.

For example, there are 11 elements in F 3 and they are:

Theorem 4.5. We have:

For example, the forests in F 3 given above illustrate Q 3 = 6t 3 + 5t. The last four elements of the list are the trees, and illustrate P 2 = 2t 3 + 2t. By counting with a weight 2 on each connected component, we obtain from this list that R 3 = 24t 3 + 16t.

Proof. From the definition of derivative polynomials in terms of D and U , and the relation DU -U D = I, we have:

Let us consider the case of Q

n . Let f n (D, U ) = (D + aU + U U D) n and c n,i,j the coefficient of U i D j in its normal form, as in [START_REF] Hoffman | Derivative polynomials for tangent and secant[END_REF]. Then from [2, Theorem 1], c n,i,j counts labelled diagrams obtained by connecting three kinds of "gates", one for each


Jean Cousty
email: j.cousty@esiee.fr

Laurent Najman
email: l.najman@esiee.fr

Yukiko Kenmochi
email: y.kenmochi@esiee.fr

Silvio Guimarães
email: s.guimaraes@esiee.fr

New characterizations of minimum spanning trees and of saliency maps based on quasi-flat zones

Keywords: Hierarchy, saliency map, minimum spanning tree

come   L'archive ouverte pluridisciplinaire

Introduction

Many image segmentation methods look for a partition of the set of image pixels such that each region of the partition corresponds to an object of interest in the image. Hierarchical segmentation methods, instead of providing a unique partition, produce a sequence of nested partitions at different scales, enabling to describe an object of interest as a grouping of several objects of interest that appear at lower scales (see references in [START_REF] Najman | A graph-based mathematical morphology reader[END_REF]). This article deals with a theory of hierarchical segmentation as used in image processing. More precisely, we investigate different representations of a hierarchy: by a dendrogram (direct set representation), by a saliency map (a characteristic function), and by a minimum spanning tree (a reduced domain of definition). Our contributions are threefold:

1. a new bijection theorem between hierarchies and saliency maps (Th. 1) that relies on the quasi-flat zones hierarchies and that is simpler and more general than previous bijection theorem for saliency maps; and 2. a new characterization of the saliency map of a given hierarchy as the minimum function for which the quasi-flat zones hierarchy is precisely the given hierarchy (Th. 2); and 3. a new characterization of the minimum spanning trees of a given edgeweighted graph as the minimum subgraphs (for inclusion) whose quasi-flat zones hierarchies are the same as the one of the given graph (Th. 3).

The links established in this article between the maps that weight the edges of a graph G, the hierarchies on the vertex set V (G) of G, the saliency maps on the edge set E(G) of G, and the minimum spanning trees for the maps that weight the edges of G are summarized in the diagram of Fig. 1.

Q F Z Saliency maps on E(G) (P1): Φ -1 = Q F Z Q F Z Connected hierarchies on V (G)
Maps on E(G) Minimum spanning trees the ≤ ordering on maps.

Fig. 1. A diagram that summarizes the results of this article. The solutions to problems (P1), (P2), and (P3) are given by Ths. 1, 2, and 3, respectively. The constraint involved in (P2) and (P3) is to leave the induced quasi-flat zones hierarchy unchanged.

In the diagram, QFZ stands for quasi-flat zones (Eq. 3), and the symbols Φ and Ψ stand for the saliency map of a hierarchy (Eq. 5) and of a map respectively (Section 5).

One possible application of these results is the design of new algorithms for computing hierarchies. Indeed, our results allow one to use indifferently any of the three hierarchical representations. This can be useful when a given operation is more efficiently performed with one representation than with the two others. Naturally, one could work directly on the hierarchy (or on its tree-based representation) and finally compute a saliency map for visualization purposes. For instance, in [START_REF] Guigues | Scale-sets image analysis[END_REF][START_REF] Ravi Kiran | Global-local optimizations by hierarchical cuts and climbing energies[END_REF], the authors efficiently handle directly the tree-based representation of the hierarchy. Conversely, thanks to Th. 1, one can work on a saliency map or, thanks to Th. 3, on the weights of a minimum spanning tree and explicitly computes the hierarchy in the end. In [START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF][START_REF] Najman | Playing with kruskal: algorithms for morphological trees in edge-weighted graphs[END_REF], a resulting saliency map is computed before a possible extraction of the associated hierarchy of watersheds. In [START_REF] Guimarães | A hierarchical image segmentation algorithm based on an observation scale[END_REF], a basic transformation that consists of modifying one weight on a minimum spanning tree according to some criterion is considered. The corresponding operation on the equivalent dendrogram is more difficult to design. When this basic operation is iterated on every edge of the minimum spanning tree, one transforms a given hierarchy into another one. An application of this technique to the observation scale of [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] has been developed in [START_REF] Guimarães | A hierarchical image segmentation algorithm based on an observation scale[END_REF] (see Fig. 2).

Another interest of our work is to precise the link between hierarchical classification [START_REF] Nakache | Approche pragmatique de la classification: arbres hiérarchiques, partitionnements[END_REF] and hierarchical image segmentation. In particular, it suggests that hierarchical image segmentation methods can be used for classification (the converse being carried out for a long time). Indeed, our work is deeply related to hierarchical classification, more precisely, to ultrametric distances, subdominant ultrametrics and single linkage clusterings. In classification, representation of hierarchies, on which no connectivity hypothesis is made, are studied since the 60's (see references in [START_REF] Nakache | Approche pragmatique de la classification: arbres hiérarchiques, partitionnements[END_REF]). The framework presented in this article deals with connected hierarchies and a graph needs to be specified for defining the connectivity of the regions of the partitions in the hierarchies. The connectivity of regions is the main difference between what has been done in classification and in segmentation. Rather than restricting the work done for classification, the framework studied in this article generalizes it. Indeed the usual notions of classification are recovered from the definitions of this article when a complete graph (every two points are linked by an edge) is considered. For instance, when a complete graph is considered, a saliency map becomes an ultrametric distance, which is known to be equivalent to a hierarchy. However, Th. 1 shows that, when the graph is not complete, we do not need a value for each pair of elements in order to characterize a hierarchy (as done with an ultrametric distance) but one value for each edge of the graph is enough (with a saliency map). Furthermore, when a complete graph is considered, the hierarchy of quasi-flat zones becomes the one of single linkage clustering. Hence, Th. 3 allows to recover and to generalize a well-known relation between the minimum spanning trees of the complete graph and single linkage clusterings.

Connected hierarchies of partitions

A partition of a finite set V is a set P of nonempty disjoint subsets of V whose union is

V (i.e., ∀X, Y ∈ P, X ∩ Y = ∅ if X = Y and ∪{X ∈ P} = V ).
Any element of a partition P of V is called a region of P. If x is an element of V , there is a unique region of P that contains x; this unique region is denoted by [P] x . Given two partitions P and P of a set V , we say that P is a refinement of P if any region of P is included in a region of P. A hierarchy (on V ) is a sequence H = (P 0 , . . . , P ) of indexed partitions of V such that P i-1 is a refinement of P i , for any i ∈ {1, . . . , }. If H = (P 0 , . . . , P ) is a hierarchy, the integer is called the depth of H. A hierarchy H = (P 0 , . . . , P ) is called complete if P = {V } and if P 0 contains every singleton of V (i.e.,

P 0 = {{x} | x ∈ V }).
The hierarchies considered in this article are complete. Figure 3 graphically represents a hierarchy H = (P 0 , P 1 , P 2 , P 3 ) on a rectangular subset V of Z 2 made of 9 dots. For instance, it can be seen that P 1 is a refinement of P 2 since any region of P 1 is included in a region of P 2 . It can also be seen that the hierarchy is complete since P 0 is made of singletons and P 3 is made of a single region that contains all elements.

In this article, we consider connected regions, the connectivity being given by a graph. Therefore, we remind basic graph definitions before introducing connected partitions and hierarchies.

A (undirected) graph is a pair G = (V, E), where V is a finite set and E is composed of unordered pairs of distinct elements in

V , i.e., E is a subset of {{x, y} ⊆ V | x = y}. Each element of V is called a vertex or a point (of G), and each element of E is called an edge (of G). A subgraph of G is a graph G = (V , E ) such that V is a subset of V , and E is a subset of E. If G is a subgraph of G, we write G G.
The vertex and edge sets of a graph X are denoted by V (X) and E(X) respectively.

Let G be a graph and let (x 0 , . . . , x k ) be a sequence of vertices of G. The sequence (x 0 , . . . , x k ) is a path (in G) from x 0 to x k if, for any i in {1, . . . , k}, {x i-1 , x i } is an edge of G. The graph G is connected if, for any two vertices x and y of G, there exists a path from x to y. Let X be a subset of V (G). The graph induced by X (in G) is the graph whose vertex set is X and whose edge set contains any edge of G which is made of two elements in X. If the graph induced by X is connected, we also say, for simplicity, that X is connected (for G) . The subset X of V (G) is a connected component of G if it is connected for G and maximal for this property, i.e., for any subset Y of V (G), if Y is a connected superset of X, then we have Y = X. In the following, we denote by C(G) the set of all connected components of G. It is well-known that this set C(G) of all connected components of G is a partition of V (G). This partition is called the (connected components) partition induced by G. Thus, the set [C(G)] x is the unique connected component of G that contains x.

Given a graph G = (V, E), a partition of V is connected (for G) if any of its regions is connected and a hierarchy on V is connected (for G) if any of its partitions is connected.

For instance, the partitions presented in Fig. 3 are connected for the graph given in Fig. 4(a). Therefore, the hierarchy H made of these partitions, which is depicted as a dendrogram in Fig. 3 (rightmost subfigure), is also connected for the graph of Fig. 4(a).

For image analysis applications, the graph G can be obtained as a pixel or a region adjacency graph: the vertex set of G is either the domain of the image to be processed or the set of regions of an initial partition of the image domain. In the latter case, the regions can in particular be "superpixels". In both cases, two typical settings for the edge set of G can be considered: (1) the edges of G are obtained from an adjacency relation between the image pixels, such as the well known 4-or 8-adjacency relations; and (2) the edges of G are obtained by considering, for each vertex x of G, the nearest neighbors of x for a distance in a (continuous) features space onto which the vertices of G are mapped.

Hierarchies of quasi-flat zones

As established in the next sections, a connected hierarchy can be equivalently treated by means of an edge-weighted graph. We first recall in this section that the level-sets of any edge-weighted graph induce a hierarchy of quasi-flat zones. This hierarchy is widely used in image processing [START_REF] Meyer | Morphological scale-space representation with levelings[END_REF].

Let G be a graph, if w is a map from the edge set of G to the set R + of positive real numbers, then the pair (G, w) is called an (edge-)weighted graph. If (G, w) is an edge-weighted graph, for any edge u of G, the value w(u) is called the weight of u (for w).

Important notation. In the sequel of this paper, we consider a weighted graph (G, w). To shorten the notations, the vertex and edge sets of G are denoted by V and E respectively instead of V (G) and E(G). Furthermore, we assume that the vertex set of G is connected. Without loss of generality, we also assume that the range of w is the set E of all integers from 0 to |E| -1 (otherwise, one could always consider an increasing one-to-one mapping from the set {w(u) | u ∈ E} into E). We also denote by E • the set E ∪ {|E|}.

Let X be a subgraph of G and let λ be an integer in E • . The λ-level set of X (for w) is the set w λ (X) of all edges of X whose weight is less than λ:

w λ (X) = {u ∈ E(X) | w(u) < λ}. (1)
The λ-level graph of X is the subgraph w V λ (X) of X whose edge set is the λ-level set of X and whose vertex set is the one of X:

w V λ (X) = (V (X), w λ (X)). (2)
The connected component partition C(w V λ (X)) induced by the λ-level graph of X is called the λ-level partition of X (for w).

For instance, let us consider the graph G depicted in Fig. 4(a) and the map w shown in Fig. 4(b). The 0-, 1-, 2and 3-level sets of G contain the edges depicted in Figs. 4(c),(d), (e), and (f), respectively. The graphs depicted in these figures are the associated 0-, 1-, 2and 3-level graphs of G and the associated 0-, 1-, 2and 3-level partitions are shown in Fig. 3.

Let X be a subgraph of G. If λ 1 and λ 2 are two elements in E • such that λ 1 ≤ λ 2 , it can be seen that any edge of the λ 1 -level graph of X is also an edge of the λ 2 -level graph of X. Thus, if two points are connected for the λ 1 -level graph of X, then they are also connected for the λ 2 -level graph of X. Therefore, any connected component of the λ 1 -level graph of X is included in a connected component of the λ 2 -level graph of X. In other words, the λ 1 -level partition of X is a refinement of the λ 2 -level partition of X. Hence, the sequence

QFZ(X, w) = (C(w V λ (X)) | λ ∈ E • ) (3)
of all λ-level partitions of X is a hierarchy. This hierarchy QFZ(X, w) is called the quasi-flat zones hierarchy of X (for w). It can be seen that this hierarchy is complete whenever X is connected.

For instance, the quasi-flat zones hierarchy of the graph G (Fig. 4(a)) for the map w (Fig. 4(b)) is the hierarchy of Fig. 3.

For image analysis applications, we often consider that the weight of an edge u = {x, y} represents the dissimilarity of x and y. For instance, in the case where the vertices of G are the pixels of a grayscale image, the weight w(u) can be the absolute difference of intensity between x and y. The setting of the graph (G, w) depends on the application context.

In the previous section, we have seen that any edge-weighted graph induces a connected hierarchy of partitions (called the quasi-flat zones hierarchy). In this section, we tackle the inverse problem:

(P 1 ) given a connected hierarchy H, find a map w from E to E such that the quasi-flat zones hierarchy for w is precisely H.

We start this section by defining the saliency map of H. Then, we provide a one-to-one correspondence (also known as a bijection) between saliency maps and hierarchies. This correspondence is given by the hierarchy of quasi flat-zones. Finally, we deduce that the saliency map of H is a solution to problem (P 1 ).

Until now, we handled the regions of a partition. Let us now study their "dual" that represents "borders" between regions and that are called graph-cuts or simply cuts. The notion of a cut will then be used to define the saliency maps.

Let P be a partition of V , the cut of P (for G), denoted by φ(P), is the set of edges of G whose two vertices belong to different regions of P:

φ (P) = {{x, y} ∈ E | [P] x = [P] y } . (4)
Let H = (P 0 , . . . , P ) be a hierarchy on V . The saliency map of H is the map Φ(H) from E to {0, . . . , } such that the weight of u for Φ(H) is the maximum value λ such that u belongs to the cut of P λ :

Φ (H) (u) = max {λ ∈ {0, . . . , } | u ∈ φ (P λ )} . (5)
In fact, the weight of the edge u = {x, y} for Φ(H) is directly related to the lowest index of a partition in the hierarchy H for which x and y belong to the same region:

Φ (H) (u) = min λ ∈ {1, . . . , } | [P λ ] x = [P λ ] y -1. (6)
For instance, if we consider the graph G represented by the gray dots and line segments in Fig. 5(a), the saliency map of the hierarchy H shown in Fig. 3 is the map shown with black numbers in Fig. 5(a). When the 4-adjacency relation is used, a saliency map can be displayed as an image (Figs. 5(e,f) and Fig. 2) which is useful for visualizing the associated hierarchy at a glance.

We say that a map w from E to E is a saliency map if there exists a hierarchy H such that w is the saliency map of H (i.e. w = Φ(H)).

If ϕ is a map from a set S 1 to a set S 2 and if ϕ -1 is a map from S 2 to S 1 such that the composition of ϕ -1 with ϕ is the identity, then we say that ϕ -1 is the inverse of ϕ.

The next theorem identifies the inverse of the map Φ and asserts that there is a bijection between the saliency maps and the connected hierarchies on V .

Theorem 1 The map Φ is a one-to-one correspondence between the connected hierarchies on V of depth |E| and the saliency maps (of range E). The inverse Φ -1 of Φ associates to any saliency map w its quasi-flat zones hierarchy: Φ -1 (w) = QFZ(G, w). Hence, as a consequence of this theorem, we have QFZ(G, Φ(H)) = H, which means that H is precisely the hierarchy of quasi-flat zones of G for its saliency map Φ(H). In other words, the saliency map of H is a solution to problem (P 1 ). For instance, if we consider the hierarchy H shown in Fig. 3, it can be observed that the quasi-flat zones hierarchy for Φ(H) (see Fig. 5) is indeed H. We also deduce that, for any saliency map w, the relation Φ(QFZ(G, w)) = w holds true. In other words, a given saliency map w is precisely the saliency map of its quasi-flat zones hierarchy.

From this last relation, we can deduce that there are some maps that weight the edges of G and that are not saliency maps. Indeed, in general, a map is not equal to the saliency map of its quasi-flat zones hierarchy. For instance, the map w in Fig. 4 is not equal to the saliency map of its quasi-flat zones hierarchy which is depicted in Fig. 5. Thus, the map w is not a saliency map. The next section studies a characterization of saliency maps.

Characterization of saliency maps

Following the conclusion of the previous section, we now consider the problem:

(P 2 )
given a hierarchy H, find the minimal map w such that the quasi-flat zones hierarchy for w is precisely H.

The next theorem establishes that the saliency map of H is the unique solution to problem (P 2 ). Before stating Th. 2, let us recall that, given two maps w and w from E to E, the map w is less than w if we have w (u) ≤ w(u) for any u ∈ E.

Theorem 2 Let H be a hierarchy and let w be a map from E to E. The map w is the saliency map of H if and only if the two following statements hold true:

1. the quasi-flat zones hierarchies for w is H; and 2. the map w is minimal for statement 1, i.e., for any map w such that w ≤ w, if the quasi-flat zones hierarchy for w is H, then we have w = w .

Given a weighted graph (G, w), it is sometimes interesting to consider the saliency map of its quasi-flat zones hierarchy. This saliency map is simply called the saliency map of w and is denoted by Ψ (w). From Th. 2, the operator Ψ which associates to any map w the saliency map Φ(QFZ(G, w)) of its quasi-flat zones hierarchy, is idempotent (i.e. Ψ (Ψ (w)) = Ψ (w)). Furthermore, it is easy to see that Ψ is also anti-extensive (we have Ψ (w) ≤ w) and increasing (for any two maps w and w , if w ≥ w , then we have Ψ (w) ≥ Ψ (w )). Thus, Ψ is a morphological opening. This operator is studied, in different frameworks, under several names (see [START_REF] Leclerc | Description combinatoire des ultramétriques[END_REF][START_REF] Najman | On the equivalence between hierarchical segmentations and ultrametric watersheds[END_REF][START_REF] Kiran | Scale space operators on hierarchies of segmentations[END_REF][START_REF] Ronse | Ordering partial partitions for image segmentation and filtering: Merging, creating and inflating blocks[END_REF][START_REF] Nakache | Approche pragmatique de la classification: arbres hiérarchiques, partitionnements[END_REF]). When the considered graph G is complete, it is known in classification (see, e.g., [START_REF] Nakache | Approche pragmatique de la classification: arbres hiérarchiques, partitionnements[END_REF]) that this operator is linked to the minimum spanning tree of (G, w). The next section proposes a generalization of this link.

Minimum spanning trees

Two distinct maps that weight the edges of the same graph (see, e.g., the maps of Figs. 4(b) and 5(a)) can induce the same hierarchy of quasi-flat zones. Therefore, in this case, one can guess that some of the edge weights do not convey any useful information with respect to the associated quasi-flat zones hierarchy. More generally, in order to represent a hierarchy by a simple (i.e., easy to handle) edgeweighted graph with a low level of redundancy, it is interesting to consider the following problem: (P 3 ) given an edge-weighted graph (G, w), find a minimal subgraph X G such that the quasi-flat zones hierarchies of G and of X are the same.

The main result of this section, namely Th. 3, provides the set of all solutions to problem (P 3 ): minimum spanning trees of (G, w). The minimum spanning tree problem is one of the most typical and well-known problems of combinatorial optimization (see [START_REF] Cormen | Introduction to algorithms[END_REF]) and Th. 3 provides, as far as we know, a new characterization of minimum spanning trees based on the quasi-flat zones hierarchies as used in image processing.

Let X be a subgraph of G. The weight of X with respect to w, denoted by w(X), is the sum of the weights of all the edges in E(X): w(X) = u∈E(X) w(u). The subgraph X is a minimum spanning tree (MST) of (G, w) if:

1. X is connected; and 2. V (X) = V ; and 3. the weight of X is less than or equal to the weight of any graph Y satisfying (1) and (2) (i.e., Y is a connected subgraph of G whose vertex set is V ).

For instance, a MST of the graph shown in Fig. 4(b) is presented in Fig. 6(a).

Theorem 3 A subgraph X of G is a MST of (G, w) if and only if the two following statements hold true:

1. the quasi-flat zones hierarchies of X and of G are the same; and 2. the graph X is minimal for statement 1, i.e., for any subgraph Y of X, if the quasi-flat zones hierarchy of Y for w is the one of G for w, then we have Y = X.

Theorem 3 (statement 1) indicates that the quasi-flat zones hierarchy of a graph and of its MSTs are identical. Note that statement 1 appeared in [START_REF] Cousty | Constructive links between some morphological hierarchies on edge-weighted graphs[END_REF] but Th. 3 completes the result of [START_REF] Cousty | Constructive links between some morphological hierarchies on edge-weighted graphs[END_REF]. Indeed, Th. 3 indicates that there is no proper subgraph of a MST that induces the same quasi-flat zones hierarchy as the initial weighted graph. Thus, a MST of the initial graph is a solution to problem (P 3 ), providing a minimal graph representation of the quasi-flat zones hierarchy of (G, w), or more generally by Th. 1 of any connected hierarchy. More remarkably, the converse is also true: a minimal representation of a hierarchy in the sense of (P 3 ) is necessarily a MST of the original graph. To the best of our knowledge, this result has not been stated before.

For instance, the level sets, level graphs and level partitions of the MST X (Fig. 6(a)) of the weighted graph (G, w) (Fig. 4) are depicted in Figs. 6(b),(c),(d). It can be observed that the level partitions of X are indeed the same as those of G. Thus the quasi-flat zones hierarchies of X and G are the same.

Saliency map algorithms

When a hierarchy H is stored as a tree data structure (such as e.g. the dendrogram of Fig. 3), the weight of any edge for the saliency map of this hierarchy can be computed in constant time, provided a linear time preprocessing. Indeed, the weight of an edge linking x and y is associated (see Eq. 6) to the lowest index of a partition for which x and y belongs to the same region. This index can be obtained by finding the index of the least common ancestor of {x} and {y} in the tree. The algorithm proposed in [START_REF] Bender | The LCA problem revisited[END_REF] performs this task in constant time, provided a linear time preprocessing of the tree. Therefore, computing the saliency map of H can be done in linear O(|E| + |V |) time complexity. Thus, the complete process that computes the saliency map Ψ (w) of a given map w proceeds in two steps: i) build the quasi-flat zones hierarchy H = QFZ(G, w) of G for w; and ii) compute the saliency map Ψ (w) = Φ(H).

On the basis of [START_REF] Cousty | Constructive links between some morphological hierarchies on edge-weighted graphs[END_REF], step i) can be performed with the quasi-linear time algorithm shown in [START_REF] Najman | Playing with kruskal: algorithms for morphological trees in edge-weighted graphs[END_REF] and step ii) can be performed in linear-time as proposed in the previous paragraph. Thus, the overall time complexity of this algorithm is quasilinear with respect to the size |E| + |V | of the graph G.

The algorithm sketched in [START_REF] Najman | On the equivalence between hierarchical segmentations and ultrametric watersheds[END_REF], based on [START_REF] Couprie | Quasi-linear algorithms for the topological watershed[END_REF], for computing the saliency map of a given map w has the same complexity as the algorithm proposed above. However, the algorithm of [START_REF] Najman | On the equivalence between hierarchical segmentations and ultrametric watersheds[END_REF] is more complicated since it requires to compute the topological watershed of the map. This involves a component tree (a data structure which is more complicated than the quasi-flat zones hierarchy in the sense of [START_REF] Cousty | Constructive links between some morphological hierarchies on edge-weighted graphs[END_REF]), a structure for computing least common ancestors, and a hierarchical queue [START_REF] Couprie | Quasi-linear algorithms for the topological watershed[END_REF], which is not needed by the above algorithm. Hence, as far as we know, the algorithm presented in this section is the simplest algorithm for computing a saliency map. It is also the most efficient both from memory and execution-time points of view. An implementation in C of this algorithm is available at http://www.esiee.fr/˜info/sm.

Conclusions

In this article we study three representations for a hierarchy of partitions. We show a new bijection between hierarchies and saliency maps and we characterize the saliency map of a hierarchy and the minimum spanning trees of a graph as minimal elements preserving quasi-flat zones. In practice, these results allow us to indifferently handle a hierarchy by a dendrogram (the direct tree structure given by the hierarchy), by a saliency map, or by an edge-weighted tree. These representations form a toolkit for the design of hierarchical (segmentation) methods where one can choose the most convenient representation or the one that leads to the most efficient implementation for a given particular operation. The results of this paper were used in [START_REF] Guimarães | A hierarchical image segmentation algorithm based on an observation scale[END_REF] to provide a framework for hierarchicalizing a certain class of non-hierarchical methods. We study in particular a hierarchicalization of [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF]. The first results are encouraging and a short term perspective is the precise practical evaluation of the gain of the hierarchical method with respect to its non-hierarchical counterpart.

Another important aspect of the present work is to underline and to precise the close link that exists between classification and hierarchical image segmentation. Whereas classification methods were used as image segmentation tools for a long time, our results incite us to look if some hierarchies initially designed for image segmentation can improve the processing of non-image data such as data coming from geography, social network, etc.. This topic will be a subject of future research.

⊆(

  P2): constrained minimization for Φ (P3): constrained minimization for Ψ the inclusion relation ⊑ on graphs.

Fig. 2 .

 2 Fig. 2. Top row: some images from the Berkeley database [1]. Middle row: saliency maps according to [9] developed thanks to the framework of this article. Bottom row: segmentations extracted from the hierarchies with (a) 3, (b) 18, (c) 6 and (d) 16 regions.

Fig. 3 .

 3 Fig.3. Illustration of a hierarchy H = (P0, P1, P2, P3). For every partition, each region is represented by a gray level: two dots with the same gray level belong to the same region. The last subfigure represents the hierarchy H as a tree, often called a dendrogram, where the inclusion relation between the regions of the successive partitions is represented by line segments.

Fig. 4 .

 4 Fig. 4. Illustration of quasi-flat zones hierarchy. (a) A graph G; (b) a map w (numbers in black) that weights the edges of G (in gray);(c, d, e, f) the λ-subgraphs of G, with λ = 0, 1, 2, 3. The associated connected component partitions that form the hierarchy of quasi-flat zones of G for w is depicted in Fig.3.

Fig. 5 .

 5 Fig. 5. Illustration of a saliency map. The map (depicted by black numbers) is the saliency map s = Φ(H) of the hierarchy H shown in Fig. 3 when we consider the graph G depicted in gray. (b, c, d) the 1-, 2-, and 3-level graphs of G for s. The vertices are colored according to the associated 1-, 2-, and 3-level partitions of G: in each subfigure, two vertices belonging to a same connected components have the same grey level. Subfigures (e) and (f) show possible image representations of a saliency map when one considers the 4-adjacency graph.

Fig. 6 .

 6 Fig.6. Illustration of a minimum spanning tree and of its quasi-flat zones hierarchy. (a) A minimum spanning tree X (black edges and black circled vertices) of the weighted graph of Fig.4(b); (b, c, d) the 1-, 2-, and 3-level graphs of X. The vertices are colored according to the associated 1-, 2-, and 3-level partitions of X: in each subfigure, two vertices belonging to the same connected components have the same color.

This work received funding from ANR (contract ANR-2010-BLAN-0205-03), CAPES/PVE (grant 064965/2014-01), and CAPES/COFECUB (grant 592/08).