Matthieu Josuat-Verg

Jean-Christophe Ès

Jean-Yves Novelli

Thibon

THE ALGEBRAIC COMBINATORICS OF SNAKES

Snakes are analogues of alternating permutations defined for any Coxeter group. We study these objects from the point of view of combinatorial Hopf algebras, such as noncommutative symmetric functions and their generalizations. The main purpose is to show that several properties of the generating functions of snakes, such as differential equations or closed form as trigonometric functions, can be lifted at the level of noncommutative symmetric functions or free quasisymmetric functions. The results take the form of algebraic identities for type B noncommutative symmetric functions, noncommutative supersymmetric functions and colored free quasi-symmetric functions.

Introduction

Snakes, a term coined by Arnol'd [START_REF] Arnol | The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF], are generalizations of alternating permutations. These permutations arose as the solution of what is perhaps the first example of an inverse problem in the theory of generating functions: given a function whose Taylor series has nonnegative integer coefficients, find a family of combinatorial objects counted by those coefficients. For example, in the expansions [START_REF] André | Sur les permutations alternées[END_REF] tan z = n≥0 E 2n+1 z 2n+1 (2n + 1)! and sec z = n≥0 E 2n z 2n (2n)! ,

the coefficients E n are nonnegative integers. It was found in 1881 by D. André [START_REF] André | Sur les permutations alternées[END_REF] that E n was the number of alternating permutations in the symmetric group S n .

Whilst this result is not particularly difficult and can be proved in several ways, the following explanation is probably not far from being optimal: there exists an associative (and noncommutative) algebra admitting a basis labelled by all permutations, and such that the map φ sending any σ ∈ S n to z n n! is a homomorphism. In this algebra, the formal series (alternating sums of even and odd identity permutations) are respectively mapped to cos z and sin z by φ. The series C is clearly invertible, and one can see by a direct calculation that C -1 + C • S -1 is the sum of all alternating permutations [START_REF] Gelfand | Noncommutative symmetric functions[END_REF].

Such a proof is not only illuminating, it says much more than the original statement. For example, one can now replace φ by more complicated morphisms, and obtain generating functions for various statistics on alternating permutations.

The symmetric group is a Coxeter group, and snakes are generalizations of alternating permutations to arbitrary Coxeter groups. Such generalizations were first introduced by Springer [START_REF] Springer | Remarks on a combinatorial problem[END_REF]. For the infinite series A n , B n , D n , Arnol'd [START_REF] Arnol | The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF] related the snakes to the geometry of bifurcation diagrams.

The aim of this article is to study the snakes of the classical Weyl groups (types A, B and D) by noncommutative methods, and to generalize the results to some series of wreath products (colored permutations).

The case of symmetric groups (type A) is settled by the algebra of Free quasisymmetric functions FQSym (also known the Malvenuto-Reutenauer algebra) which is based on permutations, and its subalgebra Sym (noncommutative symmetric functions), based on integer compositions. To deal with the other types, we need an algebra based on signed permutations, and some of its subalgebras defined by means of the superization map introduced in [START_REF] Novelli | Superization and (q, t)-specialization in combinatorial Hopf algebras[END_REF].

After reviewing the necessary background and the above mentioned proof of the result of André, we recover results of Chow [START_REF] Chow | Noncommutative symmetric functions of type B[END_REF] on type B snakes, and derive some new generating functions for this type. This suggests a variant of the definition of snakes, for which the noncommutative generating series is simpler. These considerations lead us to some new identities satisfied by the superization map on noncommutative symmetric functions. Finally, we propose a completely different combinatorial model for the generating function of type B snakes, based on interesting identities in the algebra of signed permutations. We also present generalizations of (Arnol'd's) Euler-Bernoulli triangle, counting alternating permutations according to their last value, and extend the results to wreath products and to type D, for which we propose an alternative definition of snakes.

Permutations and noncommutative trigonometry

2.1. Free quasi-symmetric functions. The simplest way to define our algebra based on permutations is by means of the classical standardization process, familiar in combinatorics and in computer science. Let A = {a 1 , a 2 , . . . } be an infinite totally ordered alphabet. The standardized word Std(w) of a word w ∈ A * is the permutation obtained by iteratively scanning w from left to right, and labelling 1, 2, . . . the occurrences of its smallest letter, then numbering the occurrences of the next one, and so on. Alternatively, σ = std(w) -1 can be characterized as the unique permutation of minimal length such that wσ is a nondecreasing word. For example, std(bbacab) = 341625.

We can now define polynomials

(3) G σ (A) := std(w)=σ w .

It is not hard to check that these polynomials span a subalgebra of C A , denoted by FQSym(A), an acronym for Free Quasi-Symmetric functions.

The multiplication rule is, for α ∈ S k and β ∈ S ℓ , (4)

G α G β = γ∈α * β G γ ,
where α * β is the set of permutations γ ∈ S k+ℓ such that γ = u • v with std(u) = α and std(v) = β. This is the convolution of permutations (see [START_REF] Reutenauer | Free Lie algebras[END_REF]). Note that the number of terms in this product depends only on k and ℓ, and is equal to the binomial coefficient k+ℓ k . Hence, the map

(5) φ : σ ∈ S n -→ z n n! is a homomorphism of algebras FQSym → C[z].
2.2. Noncommutative symmetric functions. The algebra Sym(A) of noncommutative symmetric functions over A is the subalgebra of FQSym generated by the identity permutations [START_REF] Gelfand | Noncommutative symmetric functions[END_REF][START_REF] Duchamp | Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras[END_REF] (6)

S n (A) := G 12...n (A) = i 1 ≤i 2 ≤•••≤in a i 1 a i 2 . . . a in .
These polynomials are obviously algebraically independent, so that the products (7)

S I := S i 1 S i 2 . . . S ir
where I = (i 1 , i 2 , . . . , i r ) runs over compositions of n, form a basis of Sym n , the homogeneous component of degree n of Sym.

Recall that a descent of a word w = w 1 w 2 . . . w n ∈ A n is an index i such that w i > w i+1 . The set of such i is denoted by Des(w). Hence, S n (A) is the sum of all nondecreasing words of length n (no descent), and S I (A) is the sum of all words which may have a descents only at places from the set [START_REF] Gelfand | Noncommutative symmetric functions[END_REF] Des

(I) = {i 1 , i 1 + i 2 , . . . , i 1 + • • • + i r-1 }, called the descent set of I. Another important basis is (9) R I (A) = Des(w)=Des(I) w = Des(σ)=Des(I) G σ ,
the ribbon basis, formed by sums of words having descents exactly at prescribed places. From this definition, it is obvious that if

I = (i 1 , . . . , i r ), J = (j 1 , . . . , j s ) (10) R I (A)R J (A) = R IJ (A) + R I⊲J (A)
with IJ = (i 1 , . . . , i r , j 1 , . . . , j s ) and I ⊲ J = (i 1 , . . . , i r + j 1 , j 2 , . . . , j s ).

S n (A + B) = n i=0 S i (A)S n-i (B) (S 0 = 1). (11)
If we assume that A and B commute, this operation defines a coproduct, for which Sym is a graded bialgebra, hence a Hopf algebra. The same is true of FQSym. Symmetric functions of the virtual alphabet (-A) are defined by the condition

(12) n≥0 S n (-A) = n≥0 S n (A) -1
and more generally, for a difference A -B,

(13) n≥0 S n (A -B) = k≥0 S k (B) -1 l≥0 S l (A)
(note the reversed order, see [START_REF] Krob | Noncommutative symmetric functions II: Transformations of alphabets[END_REF] for detailed explanations).

2.4. Noncommutative trigonometry.

2.4.1. André's theorem. One can now define "noncommutative trigonometric functions" by ( 14)

cos(A) = n≥0 (-1) n S 2n (A) and sin(A) = n≥0 (-1) n S 2n+1 (A).
The image by φ of these series are the usual trigonometric functions. With the help of the product formula for the ribbon basis, it is easy to see that ( 15)

sec := cos -1 = n≥0 R (2 n ) and tan := cos -1 sin = n≥0 R (2 n 1)
which implies André's theorem: the coefficient of z n n! in sec(z) + tan(z) is the number of alternating permutations of S n (if we choose to define alternating permutations as those of shape (2 n ) and (2 n 1)). In FQSym, [START_REF] Novelli | Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions[END_REF] sec

+ tan = σ alternating G σ . 2.4.2. Differential equations. If ∂ is the derivation of Sym such that ∂S n = S n-1 , then (17)
X = tan = m≥0 R (2 m 1) and Y = sec = m≥0 R (2 m )
satisfy the differential equations

(18) ∂X = 1 + X 2 , ∂Y = XY .
These equations can be lifted to FQSym, actually to its subalgebra PBT, the Loday-Ronco algebra of planar binary trees (see [START_REF] Hivert | The algebra of binary search trees[END_REF] for details). Solving them in this algebra provides yet another combinatorial proof of André's result. Let us sketch it for the tangent. The original proof of André relied upon the differential equation [START_REF] Reutenauer | Free Lie algebras[END_REF] dx dt = 1 + x 2 whose x(t) = tan(t) is the solution such that x(0) = 0. Equivalently, x(t) is the unique solution of the functional equation ( 20)

x(t) = t + t 0 x(s) 2 ds
which can be solved by iterated substitution.

In general, given an associative algebra R, we can consider the functional equation for the power series

x ∈ R[[t]] (21) x = a + B(x, x)
where a ∈ R and B(x, y) is a bilinear map with values in R[[t]], such that the valuation of B(x, y) is strictly greater than the sum of the valuations of x and y. Then, Equation ( 21) has a unique solution [START_REF] Springer | Remarks on a combinatorial problem[END_REF] x = a + B(a, a) + B(B(a, a), a) + B(a, B(a, a))

+ • • • = T ∈CBT B T (a)
where CBT is the set of (complete) binary trees, and for a tree T , B T (a) is the result of evaluating the expression formed by labeling by a the leaves of T and by B its internal nodes. Pictorially,

x = a + B(a, a) + B(B(a, a), a) + B(a, B(a, a)) + . . . = a + B e e } } a a + B b b b } } B g g } } a a a + B e e Ð Ð Ð a B e e { { a a + . . .
It is proved in [START_REF] Hivert | The algebra of binary search trees[END_REF] that if one defines

(23) ∂G σ := G σ ′
where σ ′ is obtained from σ by erasing its maximal letter n, then ∂ is a derivation of FQSym. Its restriction to Sym coincides obviously with the previous definition.

For α ∈ S k , β ∈ S ℓ , and

n = k + ℓ, set (24) B(G α , G β ) = γ=u(n+1)v std(u)=α,std(v)=β G γ . Clearly, (25) ∂B(G α , G β ) = G α G β ,
and our differential equation for the noncommutative tangent is now replaced by the fixed point problem

(26) X = G 1 + B(X, X) .
of which it is the unique solution. Again, solving it by iterations gives back the sum of alternating permutations. As an element of the Loday-Ronco algebra, tan appears as the sum of all permutations whose decreasing tree is complete. The same kind of equation holds for Y :

(27) Y = 1 + B(X, Y ) .
Hence, the noncommutative secant sec is therefore an element of PBT, so a sum of binary trees. The trees are well-known: they correspond to complete binary trees (of odd size) where one has removed the last leaf.

2.5. Derivative polynomials. For the ordinary tangent and secant, the differential equations imply the existence [START_REF] Hoffman | Derivative polynomials, Euler polynomials, and associated integer sequences[END_REF] of two sequences of polynomials P n , Q n such that (28) d n dz n (tan z) = P n (tan z) and

d n dz n (sec z) = Q n (tan z) sec z.
Since ∂ is a derivation of Sym, we have as well for the noncommutative lifts

(29) ∂ n (X) = P n (X) and ∂ n (Y ) = Q n (X)Y .
Hoffman [START_REF] Hoffman | Derivative polynomials, Euler polynomials, and associated integer sequences[END_REF] gives the exponential generating functions (30)

P (u, t) = n≥0 P n (u) t n n! = sin t + u cos t cos t -u sin t and Q(u, t) = n≥0 Q n (u) t n n! = 1 cos t -u sin t .
The noncommutative version of these identities can be readily derived as follows. We want to compute (31)

P (X, t) = n≥0 P n (X) t n n! = e t∂ X .
Since ∂ is a derivation, e t∂ is an automorphism of Sym. It acts on the generators S n by (32)

e t∂ S n (A) = n k=0 S n-k (A) t k k! = S n (A + tE)
where tE is the "virtual alphabet" such that S n (tE) = t n n! . Hence, P (X, t) = tan(A + tE) = cos(A + tE) -1 sin(A + tE) = (cos t -X sin t) -1 (sin t + X cos t) (33) as expected. Similarly,

Q n (X, t) = n≥0 Q n (X) t n n! = (e t∂ Y )Y -1 (34) = cos(A + tE) -1 cos(A) = (cos t -X sin t) -1 . (35)

The uniform definition of snakes for Coxeter groups

Before introducing the relevant generalizations of Sym and FQSym, we shall comment on the definitions of snakes and alternating permutations for general Coxeter groups.

It is apparent in Springer's article [START_REF] Springer | Remarks on a combinatorial problem[END_REF] that alternating permutations can be defined in a uniform way for any Coxeter group. Still, little attention has been given to this fact. For example, 20 years later, Arnol'd [START_REF] Arnol | The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF] gives separately the definitions of snakes of type A, B and D, even though there is no doubt that he was aware of the uniform definition. The goal of this section is to give some precisions and to simplify the proof of Springer's result in [START_REF] Springer | Remarks on a combinatorial problem[END_REF].

Let (W, S) be an irreducible Coxeter system. Recall that s ∈ S is a descent of w ∈ W if ℓ(ws) < ℓ(w) where ℓ is the length function. When J ⊂ S, we denote by D J the descent class defined as {w ∈ W : ℓ(ws) < ℓ(w) ⇔ s ∈ J}. Following Arnol'd, let us consider the following definition.

Definition 3.1. The Springer number of the Coxeter system (W, S) is

(36) K(W ) := max J⊆S (#D J ).
The aim of [START_REF] Springer | Remarks on a combinatorial problem[END_REF] is to give a precise description of sets J realizing this maximum. The result is as follows: Theorem 3.2 (Springer [START_REF] Springer | Remarks on a combinatorial problem[END_REF]). Let J ⊆ S. Then, K(W ) = #D J if and only if J and S\J are independent subsets of the Coxeter graph S ( i.e., they contain no two adjacent vertices). In particular, there are two such subsets J which are complementary to each other.

Therefore we can choose a subset J such that K(W ) = #D J and call snakes of W the elements of D J . The other choice S\J would essentially lead to the same objects, since there is a simple involution on W exchanging the subsets D J and D S\J .

We are thus led to the following definition: Definition 3.3. Let (W, S) be a Coxeter group, and J be a maximal independent subset of S. The snakes of (W, S) are the elements of the descent class D J .

This definition depends on the choice of J, so that we can consider two families of snakes for each W . In the case of alternating permutations, these are usually called the up-down and down-up permutations, and are respectively defined by the conditions (37)

σ 1 < σ 2 > σ 3 < . . . or σ 1 > σ 2 < σ 3 > . . .
It is natural to endow a descent class with the restriction of the weak order, and this defines what we can call the snake poset of (W, S). Known results show that this poset is a lattice [START_REF] Björner | Orderings of Coxeter groups, Combinatorics and algebra[END_REF]. Let us now say a few words about the proof of Theorem 3.2, which relies upon the following lemma. Lemma 3.4 (Springer [START_REF] Springer | Remarks on a combinatorial problem[END_REF]). Let J ⊆ S, and assume that there is an edge e of the Coxeter graph whose endpoints are both in J or both not in J. Let S = S 1 ∪ S 2 be the connected components obtained after removing e.

Let J ′ = (S 1 ∩ J) ∪ (S 2 ∩ (S\J)). Then, #D J < #D J ′ .
Using the above lemma, we see that if J or complementary is not independent, we can find another subset J ′ having a strictly bigger descent class, and Theorem 3.2 then follows. Whereas Lemma 3.4 is the last one out of a series of 5 lemmas in Springer's article, we give here a simple geometric argument.

Let R be a root system for (W, S), and let Π = (α s ) s∈S be a set of simple roots. There is a bijection w → i(w) between W and the set of Weyl chambers, so that s ∈ S is a descent of w ∈ W if and only if i(w) lies in the half-space {v ∈ R n : v, α s ≥ 0}. For any J ⊂ S, let (38)

C J = {v ∈ R n : v, α s ≥ 0 if s ∈ J, and v, α s ≤ 0 if s / ∈ J}.
It is the closure of the union of Weyl chambers i(w) where w ∈ D J . Now, let e, S 1 , S 2 and J ′ be as in the lemma, and let x ∈ S 1 and y ∈ S 2 be the endpoints of e.

Note that either x or y is in J ′ but not both. Let σ be the orthogonal symmetry through the linear span of {α j : j ∈ S 1 }. We claim that σ(C J ) C J ′ , and this implies #D J < #D J ′ since C J contains strictly less Weyl chambers than C J ′ .

So it remains to show that σ(C J ) C J ′ . It is convenient to use the notion of dual cone, which is defined for any closed convex cone C ⊂ R n as (39)

C * := {v ∈ R n : v, w ≥ 0 for any w ∈ C}.
The map C → C * is an inclusion-reversing involution on closed convex cones, and it commutes with any linear isometry, so that we have to prove that σ(

C * J ′ ) C * J . Since (C 1 ∩ C 2 ) * = C * 1 + C * 2 and since the dual of the half-space {v ∈ R n : v, w ≥ 0} is the half-line R + w, the dual of C J ′ is (40) C * J ′ = s∈S u s α s : u s ≥ 0 if s ∈ J ′ , and u s ≤ 0 if s / ∈ J ′ ,
and the same holds for

C * J . A description of σ(C * J ′ ) is obtained easily by linear- ity since σ(α s ) = α s if s ∈ S 1 , σ(α s ) = -α s if s ∈ S 2 \y, and σ(α y ) = -α y + 2 α x , α y α x , α x -1 α x . Indeed, let v = s∈S u s α s ∈ C * J ′ , we have: (41) σ(v) = s∈S 1 u s α s - s∈S 2 \y u s α s -u y α y + 2u y α x , α y α x , α x -1 α x .
Since u x and u y have different signs and α x , α y < 0, we obtain σ(v) ∈ C * J . We have thus proved σ(C * J ′ ) ⊂ C * J . To show the strict inclusion, note that either α y or -α y is in C * J . But none of these two elements is in σ(C * J ′ ), because in the above formula for σ(v), if u y = 0 there is a nonzero term in α x as well. This completes the proof.

Signed permutations and combinatorial Hopf algebras

Whereas the constructions of the Hopf algebras Sym, PBT, and FQSym appearing when computing the usual tangent are almost straightforward, the situation is quite different in type B. First, there are at least three different generalizations of Sym to a pair of alphabets, each with its own qualities either combinatorial or algebraic. Moreover, there are also two different ways to generalize FQSym. The generalizations of PBT are not (yet) defined in the literature but the computations done in the present paper give a glimpse of what they should be.

Here follows how they embed each in the other. All embeddings are embeddings of Hopf algebras except the two embeddings concerning BSym which is not itself an algebra. However, the embedding of Sym(A| Ā) into Sym (2) obtained by composing the two previous embeddings is a Hopf embedding:

(42) Sym(A| Ā) ֒→ BSym ֒→ Sym (2) ֒→ FQSym(A| Ā) ֒→ FQSym (2) . We denote by Sym (2) = MR [START_REF] Mantaci | A generalization of Solomon's descent algebra for hyperoctahedral groups and wreath products[END_REF] the free product Sym ⋆ Sym of two copies of the Hopf algebra of noncommutative symmetric functions. In other words, MR is the free associative algebra on two sequences (S n ) and (S n) (n ≥ 1). We regard the two copies of Sym as noncommutative symmetric functions on two auxiliary alphabets: S n = S n (A) and S n = S n ( Ā). We denote by F → F the involutive automorphism1 which exchanges S n and S n. And we denote the generators of Sym (2) by S (k,ǫ) where ǫ = {±1}, so that S (k,1) = S k and S (k,-1) = Sk.

Noncommutative supersymmetric functions. The second generalization of

Sym comes from the transformation of alphabets sending A to a combination of A and Ā. It is the algebra containing the type B alternating permutations.

We define Sym(A| Ā) as the subalgebra of Sym (2) generated by the S # n where, for any

F ∈ Sym(A), (43)
F # = F (A| Ā) = F (A -q Ā)| q=-1 ,
called the supersymmetric version, or superization, of F [START_REF] Novelli | Superization and (q, t)-specialization in combinatorial Hopf algebras[END_REF].

The expansion of an element of Sym(A| Ā) as a linear combination in Sym (2) is done thanks to generating series. Indeed, (44)

σ # 1 = λ1 σ 1 = k≥0 Λ k m≥0 S m
where Λ k = I|=k (-1) ℓ(I)-k S I , as follows from λ1 = (σ -1 ) -1 (see [START_REF] Krob | Noncommutative symmetric functions II: Transformations of alphabets[END_REF]). For example, (45)

S # 1 = S 1 + S 1 , S # 2 = S 2 + S 11 -S 2 + S 11 , (46)
S # 3 = S 3 + S 12 + S 111 -S 21 + S 111 -S 21 -S 12 + S 3 .

4.3.

Noncommutative symmetric functions of type B. The third generalization of Sym is not an algebra but only a cogebra but is the generalization one gets with respect to the group B n : its graded dimension is 2 n and, as we shall see later in this paragraph, a basis of BSym is given by sums of permutations having given descents in the type B sense. This algebra contains the snakes of type B.

Noncommutative symmetric functions of type B were introduced in [START_REF] Chow | Noncommutative symmetric functions of type B[END_REF] as the right Sym-module BSym freely generated by another sequence ( Sn ) (n ≥ 0, S0 = 1) of homogeneous elements, with σ1 grouplike. This is a coalgebra, but not an algebra.

We embed BSym as a sub-coalgebra and right sub-Sym-module of MR as follows. The basis element SI of BSym, where I = (i 0 , i 1 , . . . , i r ) is a B-composition (that is, i 0 may be 0), can be embedded as (47) SI = S i 0 (A)S i 1 i 2 ...ir (A| Ā) .

In the sequel, we identify BSym with its image under this embedding.

As in Sym, one can define by triangularity the analog of the ribbon basis ( [START_REF] Chow | Noncommutative symmetric functions of type B[END_REF]):

(48) SI = J≤I RJ ,
where J ≤ I if the B-descent set of J is a subset of the B-descent set of I. Note that we have in particular S0n = R0n + Rn . Note also that, thanks to that definition, S I # = SI and, thanks to the transitions between all bases, (49) R # I = R0I + RI . 4.4. Type B permutations and descents in B n . The hyperoctahedral group B n is the group of signed permutations. A signed permutation can be denoted by w = (σ, ǫ) where σ is an ordinary permutation and ǫ ∈ {±1} n , such that

w(i) = ǫ i σ(i). If we set w(0) = 0, then, i ∈ [0, n -1] is a B-descent of w if w(i) > w(i + 1). Hence, the B-descent set of w is a subset D = {i 0 , i 0 + i 1 , . . . , i 0 + • • • + i r-1 } of [0, n -1].
We then associate with D the type-B composition (i 0 -0, i 1 , . . . , i r-1 , n -i r-1 ). 4.5. Free quasi-symmetric functions of level 2. Let us now move to generalizations of FQSym. As in the case of Sym, the most natural way is to change the usual alphabet into two alphabets, one of positive letters and one of negative letters and to define a basis indexed by signed permutations as a realization on words on both alphabets. This algebra is FQSym (2) , the algebra of free quasi-symmetric functions of level 2, as defined in [START_REF] Novelli | Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions[END_REF].

Let us set

A (0) = A = {a 1 < a 2 < • • • < a n < . . . } , (50)
A (1) = Ā = {• • • < ān < • • • < ā2 < ā1 } , (51)
and order A = Ā ∪ A by āi < a j for all i, j. Let us also denote by std the standardization of signed words with respect to this order.

We shall also need the signed standardization Std, defined as follows. Represent a signed word w ∈ A n by a pair (w, ǫ), where w ∈ A n is the underlying unsigned word, and ǫ ∈ {±1} n is the vector of signs. Then Std(w, ǫ) = (std(w), ǫ).

Then, FQSym (2) is spanned by the polynomials in A ∪ Ā (52) G σ,u :=

w∈A n ;Std(w)=(σ,u) w ∈ Z A .
Let (σ ′ , u ′ ) and (σ ′′ , u ′′ ) be signed permutations. Then (see [START_REF] Novelli | Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions[END_REF][START_REF] Novelli | Superization and (q, t)-specialization in combinatorial Hopf algebras[END_REF])

(53) G σ ′ ,u ′ G σ ′′ ,u ′′ = σ∈σ ′ * σ ′′ G σ,u ′ •u ′′ .
We denote by m(ǫ) the number of entries -1 in ǫ.

4.6.

Free super-quasi-symmetric functions. The second algebra generalizing the algebra FQSym is FQSym(A| Ā). It comes from the transformation of alphabets applied to FQSym as Sym(A| Ā) comes from Sym. To do this, we first need to recall that FQSym (2) is equipped with an internal product. Indeed, viewing signed permutations as elements of the group {±1} ≀ S n , we have the internal product

(54) G α,ǫ * G β,η = G (β,η)•(α,ǫ) = G β•α,(ηα)•ǫ , with ηα = (η α(1) , . . . , η α(n) ) and ǫ • η = (ǫ 1 η 1 , . . . , ǫ n η n ).
We can now embed FQSym into FQSym (2) by ( 55)

G σ → G (σ,1 n ) ,
which allows us to define (56)

G # σ := G σ (A| Ā) = G σ * σ # 1 , so that FQSym(A| Ā) is the algebra spanned by the G σ (A| Ā). Theorem 4.1 ([17], Thm. 3.1). The expansion of G σ (A| Ā) on the basis G τ,ǫ is (57) G σ (A| Ā) = std(τ,ǫ)=σ G τ,ǫ .
4.6.1. Embedding Sym # and BSym into FQSym (2) . One can embed BSym into FQSym (2) as one embeds Sym into FQSym (see [START_REF] Chow | Noncommutative symmetric functions of type B[END_REF]) by

(58) RI = Bdes(π)=I G π ,
where I is any B-composition.

Given Equation (49) relating R # I and the RI , one has (59)

R ♯ I = Des(π)=I G π ,
where I is any (usual) composition. Here are the alternating permutations of type B for n ≤ 4:

(60) Hence, π is alternating iff π is a β-snake in the sense of [START_REF] Arnol | The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF]. Hence, the sum in FQSym (2) of all G π labeled by alternating signed permutations is, as already proved in [START_REF] Chow | Noncommutative symmetric functions of type B[END_REF] (63)

X = (X + Y ) # = sec # + tan # = sec # (1 + sin # ) = m≥0 (R # (2 m ) + R # (2 m 1) ).
5.1.2. Quasi-differential equations. Let d be the linear map acting on G π as follows:

(64)

dG π = G uv if π = unv, G uv if π = unv.
This map lifts to FQSym (2) the derivation ∂ of ( 23), although it is not itself a derivation. We then have Theorem 5.1. The series X satisfies the quasi-differential equation

(65) dX = 1 + X 2 .
Proof -Indeed, let us compute what happens when applying d to R # (2 m ) , the property being the same with dR # (2 m 1) . Let us fix a permutation σ of shape (2 m ). If n appears in σ, let us write σ = unv. Then dG σ appears in the product G Std(u) G Std(v) and u and v are of respective shapes (2 n 1) and (2 m-n-1 ). If n appears in σ, let us write again σ = unv. Then dG σ appears in the product G Std(u) G Std(v) and u and v are of respective shapes (2 n ) and (2 m-n-1 1). Conversely, any permutation belonging to u * v with u and v of shapes (2 n 1) and (2 m-n-1 ) has a shape (2 m ) if one adds n in position 2n + 2. The same holds for the other product, hence proving the statement. This is not enough to characterize X but we have the analog of fixed point equation (26) (66) Solving this equation by iterations gives back the results of [START_REF] Josuat-Vergès | Enumeration of snakes and cycle-alternating permutations[END_REF]Section 4]. Indeed, the iteration of Equation (66) yields the solution

X = 1 + G 1 + B(X, X), where (67) B(G α , G β ) = γ=u(n+1)v, Std(u)=α, Std(v)=β G γ if |α| is odd, γ=u(n+1)v, Std(u)=α, Std(v)=β G γ if |α| is even. Indeed,
(68) X = T ∈CBT B T (G 0 = 1, G 1 ),
where, for a tree T , B T (a, b) is the result of the evaluation of all expressions formed by labeling by a or b the leaves of T and by B its internal nodes. This is indeed the same as the polynomials P n defined in [12, Section 4] since one can interpret the G 0 leaves as empty leaves in this setting, the remaining nodes then corresponding to all increasing trees of the same shape, as can be seen on the definition of the operator B.

t m(π) = sec((1 + t)z) + tan((1 + t)z).
But another immediate interpretation of the series in the right-hand side is

(73) n z n π s.t. |π| is alternating in An t m(π) = sec((1 + t)z) + tan((1 + t)z).
It is thus in order to give a bijection proving the equality of the generating functions. Let π be an alternating signed permutation. We can associate with π the pair (std(π), ǫ) where ǫ is the sign vector such that ǫ i = 1 if π -1 (i) > 0 and ǫ i = -1 otherwise. The image of {1, . . . , n} by π is {ǫ i i : 1 ≤ i ≤ n}. Since π can be recovered from std(π) and the image of {1, . . . , n}, this map is a bijection between signed alternating permutations and pairs (σ, ǫ) where σ is alternating and ǫ is a sign vector.

Then, with such a pair (σ, ǫ), one can associate a signed permutation τ such that |τ | is alternating simply by taking τ i = σ i ǫ i . The composition π → (σ, ǫ) → τ gives the desired bijection.

For example, here follow the 16 permutations obtained by applying the bijection to the 16 alternating permutations of size 3 (see Equation (61)):

(74) [START_REF] Stanley | A survey of alternating permutations[END_REF]

(76) Y = (cos + sin) • sec # = k≥0 (-1) k (S 2k + S 2k+1 ) • n≥0 R # 2 n .
Now, Y lives in BSym and expands in the ribbon basis R of BSym as

Y = k≥0 (-1) k ( R2k + R2k+1 ) n≥0 R # 2 n = n≥0 (R # 2 n + R12 n + R32 n ) + k≥1;n≥0 (-1) k ( R2k2 n + R2k+22 n-1 + R2k+12 n + R2k+32 n-1 ) = n≥0 (R # 2 n + R12 n + R32 n ) - n≥0 ( R2 n+1 + R32 n ) (77) which simplifies into (78) Y = 1 + n≥0 ( R12 n + R02 n+1 ).
In FQSym (2) , this is the sum of all G π such that

(79) 0 > π 1 < π 2 > . . . if n is even, 0 < π 1 > π 2 < . . . if n is odd.
Thus, for n odd, π is exactly a B n -snake in the sense of [START_REF] Arnol | The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF], and for n even, π is a B n -snake. Clearly, the number of sign changes or of minus signs in snakes and in these modified snakes are related in a trivial way so we have generating series for both statistics in all cases.

Here are these modified snakes for n ≤ 4:

(80)

Y = cos • sec # + sin • sec # ,
where f → f is the involution of FQSym (2) inverting the signs of permutations.

Expanding Y in the R basis, one gets

(84) Y = 1 + n≥0 ( R02 n 1 + R02 n+1 ).
As for type B alternating permutations (see Equation ( 65)), the series Y satisfies a differential equation with the same linear map d as before (see Equation (64)):

(85) dY = Y X.
It is then easy to see that Y also satisfies a fixed point equation similar to (26):

(86)

Y = 1 + B(Y, X).
The iteration of (86) brings up a solution close to (68):

(87) Y = T ∈CBT B T (G 0 = 1, G 1 ),
where, for a tree T , B T (a, b) is now the result of the evaluation of all expressions formed by labeling by a or b the leaves of T and by B its internal nodes. Note that in this case, the first leaf needs to have label a. This is the same as the trees defined in [12, Section 4] since one can again interpret the G 0 leaves as empty leaves in this setting, the remaining nodes then corresponding to all increasing trees of the same shape.

5.2.3.

Snakes from [START_REF] Arnol | The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF]. The generating series of the snakes of [START_REF] Arnol | The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF], also in BSym is

(88) cos • sec # + sin • sec # ,
and can be written as

(89) Y = 1 + n≥0 ( R12 n + R12 n 1 )
on the ribbon basis.

The lift of the differential equation for y(1) is given by a map δ similar to d, with δunv = ūv and δunv = uv. Then for an appropriate bilinear map B.

6. Another combinatorial model 6.

1. An analogue of cos z -sin z in FQSym (2) . Definition 6.1. A signed permutation π ∈ B n is a valley-signed permutation if, for any i ∈ [n], π(i) < 0 implies that • either i > 2, and π i-1 > 0, and

|π i-2 | > π i-1 < |π i |,
• or i = 2, and 0 < π 1 < |π 2 |. We denote by V n the set of valley-signed permutations of size n.

Here are these signed permutations, up to n = 4:

(92) 1, 12, 1 2, 21, (93) 123
The terminology is explained by the following remark. Let σ ∈ S n , and let us examine how to build a valley-signed permutation π so that π i = ±σ i . It turns out that for each valley σ(i -1) > σ(i) < σ(i + 1), we can choose independently the sign of π(i + 1) (here 1 ≤ i < n and 1 is a valley if σ(1) < σ(2)).

The goal of this section is to obtain the noncommutative generating functions for the sets V n . Theorem 6.2. The following series

(95) U = 1 -[G 1 + G 1 2 -G 12 3 -G 1 23 4 + G 12 34 5 + G 1 23 45 6 + . . . ]
is again a lift of cos z -sin z in FQSym (2) . It satisfies

(96) U -1 = n≥0 π∈Vn G π .
Hence the π occuring in this expansion are in bijection with snakes of type B.

This result is a consequence of the next two propositions. Definition 6.3. Let R 2n ⊂ B 2n be the set of signed permutations π of size 2n such that |π| is of shape 2 n , and for any 1 ≤ i ≤ n, we have π(i) > 0 iff i is odd. Let

(97) V = n≥0 π∈R 2n G π = G ǫ + G 1 2 + G 1 32 4 + G 1 42 3 + . . .
Let R 2n+1 ⊂ B 2n+1 be the set of signed permutations π of size 2n + 1 such that |π| is of shape 12 n , π 1 > 0, and for any 2 ≤ i ≤ n, we have π(i) > 0 iff i is even. Let

(98) W = n≥0 π∈R 2n+1 G π = G 1 + G 21 3 + G 31 2 + G 21 43 5 + . . . Note that R n ⊂ V n .
Clearly, #R n is the number of alternating permutations of S n since, given |π|, there is only one possible choice for the signs of each π i . So V and W respectively lift sec and tan in FQSym (2) . Now, given that the product rule of the G σ does not affect the signs, a simple adaptation of the proof of the A n case shows: Proposition 6.4. We have

V -1 = 1 -G 1 2 + G 1 23 4 -G 1 23 45 6 + . . . , (99) W V -1 = G 1 -G 12 3 + G 12 34 5 -G 12 34 56 7 + . . . ( 100
)
Note that U = (1 -W )V -1 . So, to complete the proof of the theorem, it remains to show: Proposition 6.5. We have

(101) V (1 -W ) -1 = n≥0 π∈Vn G π .
Proof -We can write V (1 -W ) -1 = V + V W + V W 2 + . . . , and expand everything in terms of the G π , using their product rule (see Equation ( 53)). We obtain a sum of G u 1 ...u k where Std(u 1 ) ∈ R 2 * and Std(u i ) ∈ R 2 * +1 for any i ≥ 2 (where * is any integer). The sum is a priori over lists (u 1 , . . . , u k ) such that u = u 1 . . . u k ∈ B n . Actually, if the words u 1 , . . . , u k satisfy the previous conditions, then u is in V n . Indeed, the first two letters of each u i are not signed, each u i is a valley-signed permutation, which implies that u itself is a valley-signed permutation. Conversely, it remains to show that this factorization exists and is unique for any u ∈ V n . First, observe that in u = u 1 . . . u k , u k is the only suffix of odd length having the same signs as an element of R 2 * +1 (since the first two letters are positive and the other alternate in signs, it cannot be itself a strict suffix of an element of R 2 * +1 ). So the factorization can be obtained by scanning u from right to left.

Let (102)

Z := G1 -G1 2 -G1 2 3 + G1 23 4 + G1 2 34 5 -G1 23 45 6 + . . .

Precisely, the n-th term in this expansion is the permutation σ of B n such that, |σ| = id, σ(1) = 1, σ(2) = 2 and, for 3 ≤ i ≤ n, σ(i) < 0 iff n -i is even. The sign corresponds to the sign of z n in the expansion of cos z + sin z -1, so that it is a lift of cos z + sin z -1 in FQSym (2) .

Theorem 6.6. The series Z U -1 is a sum of G π without multiplicities in the Hopf algebra FQSym (2) . Hence the π occuring in this expansion are in bijection with snakes of type D (see Section 9). Moreover, the series (1 + Z) U -1 is also a sum of G π without multiplicities in the Hopf algebra FQSym (2) . Hence the π occuring in this expansion are in bijection with alternating permutations of type B.

Here are the elements of Z U -1 , up to n = 4: Proof -Let ε i be the linear operator sending a word w to the word w ′ where w ′ is obtained from w by sending its ith letter to its opposite and not changing the other letters.

(
Then if one writes 1 + Z = E + O as a sum of an even and an odd series, one has

(106) E = ε 1 ε 2 V -1 O = ǫ 1 (W V -1 ).
Since ε i (ST ) = ε i (S)T if S contains only terms of size at least i, an easy rewriting shows that

(107) (1 + Z)V = V + ε 1 (W ) + ε 1 ε 2 (1 -V ).
Then, one gets

(108) (1 + Z)V (1 -W ) -1 = U -1 + ε 1 (W + ε 2 (1 -V ))(1 -W ) -1 .

So it only remains to prove that

Q = ε 1 (W + ε 2 (1 -V ))(1 -W ) -1
has only positive terms and has no term in common with U -1 . This last fact follows from the fact that all terms in Q have a negative number as first value. Let us now prove that Q has only positive terms. First note that W + ε 2 (1 -V ) is an alternating sum of permutations of shapes 2 n and 12 n . Hence, any permutation of shape 2 n can be associated with a permutation of shape 12 n-1 by removing its first entry and standardizing the corresponding word. Now, all negative terms -G v G w come from -ε 2 (V )(1 -W ) -1 and are annihilated by the term G v ′ G 1 G w where v ′ is obtained from v by the removal-and-standardization process described before.

6.2. Another proof of Theorem 6.2. Let Sg n be the group algebra of {±1} n . We identify a tuple of signs with a word in the two symbols 1, 1, and the direct sum of the Sg n with the free associative algebra on these symbols.

We can now define the algebra of signed noncommutative symmetric functions as

(109) sSym := n≥0 Sym n ⊗ Sg n endowed with the product (110) (f ⊗ u) • (g ⊗ v) = f g ⊗ uv .
It is naturally embedded in FQSym (2) by ( 111)

R I ⊗ u = C(σ)=I G σ,u .
With this at hand, writing

U = P -Q with (112) P = m≥0 (-1) m R 2m ⊗ (1 1) m and Q = m≥0 (-1) m R 2m+1 ⊗ 1(1 1) m , it is clear that (113) P -1 = m≥0 R (2 m ) ⊗ (1 1) m = V and W = m≥0 R (12 m ) ⊗ 1(1 1) m = QV, so that U = (1 -W )V -1 , and U -1 = V (1 -W ) -1 can now be computed by observing that (114) (1 -W ) -1 = I R I ⊗ p I (1, 1)
where p I is the sum of words in 1, 1 obtained by associating with each tiling of the ribbon shape of I by tiles of shapes (1, 2 m 1 , . . . , 1, 2 m k ) the word 1(1 1) m 1 . . . 1(1 1) m k . For example, p 12 = 111 + 11 1, for there are two tilings, one by three shapes (1) and one by [START_REF] Josuat-Vergès | Enumeration of snakes and cycle-alternating permutations[END_REF]. The proof of Theorem 6.6 can be reformulated in the same way.

6.3. Some new identities in BSym. Let us have a closer look at the map Ā → tA. By definition, R I (A|tA) = R I ((1 -q)A)| q=-t , so that the generating series for one-part compositions is

(115) n≥0 R n ((1 -q)A)x n = σ x ((1 -q)A) = λ -qx (A)σ x (A) .
One can now expand this formula in different bases. Tables are given in Section 10.

6.3.1.

Image of the R in the S basis of Sym. The first identity gives the image of a ribbon in the S basis:

(116) R I (A|tA) = J (-1) l(I)+l(J) (1 -(-t) jr ) (-t) A(I,J ) j k S J
where A(I, J) = {p|j 1 + • • • + j p ∈ Des(I)}. Indeed, expanding λ -qx (A) on the basis S J , one finds

(117) n≥0 R n ((1 -q)A)x n = n≥0 x n k+m=n (-q) k K k (-1) k-ℓ(K) S K S m
Each composition of a given n occurs twice in the sum, so that

(118) R n ((1 -q)A) = J n (-1) 1-ℓ(J) (q n-jr -q n )S J .
Hence, Equation ( 116) is true for one-part compositions. The general case follows by induction from the product formula

(119) R I R j = R Ij + R I⊲j .
Now, as for the R, we have Proposition 6.7. Let I be a type-B composition and set I =: (i 0 , I ′ ). Then the expansion of the RI (A, tA) on the

S J (A) is (120)        (-1) ℓ(I ′ )+n t n S n + J∈C 1 (-1) ℓ(I)+ℓ(J) (1 -(-t) jr ) (-t) A(I,J ) j k S J if i 0 = 0, ( -1) ℓ
(I)+1 S n + J∈C 2 (-1) ℓ(I)+ℓ(J) (1 -(-t) jr ) (-t) A(I,J ) j k S J otherwise,
where C 2 is the set of compositions of n different from (n) whose first part is a sum of any prefix of I, and C 1 the set complementary to C 2 in all compositions of n different from (n).

For example, with I = (1321), C 2 (I) is the set of compositions of 7 whose first part is either 1, 4, or 6.

Proof -By induction on the length of

I. First, R n (A, tA) = R n (A) = S n (A) and (121) Rn (A, tA) = R n (A) and R0n (A, tA) = R n (A|tA) -R n (A).
Now, the formula RI R j = RIj + RI⊲j together with Equation (116) implies the general case.

Note that this also means that one can compute the matrices recursively. Indeed, if one denotes by K 0 (n) (resp. K 1 (n)) the matrix expanding the RI (A, tA) where i 0 = 0 (resp. i 0 = 0) on the S J , one has the following structure: (122)

(K 0 (n+1) K 1 (n+1)) = -tK 0 (n) tK 0 (n) K 1 (n) -K 1 (n) t(K 0 (n)+K 1 (n)) 0 0 K 0 (n)+K 1 (n) 6.3.2.
Image of the R in the Λ basis of Sym. Expanding Equation (115) on the basis Λ J , the same reasoning gives as well

(123) R I (A|tA) = J (-1) n+1+l(I)+l(J) (1 -(-t) j 1 ) (-t) k∈A ′ (I,J ) j k Λ J where A ′ (I, J) = {ℓ|j 1 + • • • + j ℓ-1 ∈ Des(I)}.
Now, as for the R, we have Proposition 6.8. Let I be a type-B composition and set I =: (i 0 , I ′ ). Then the expansion of the RI (A, tA) on the Λ J (A) is

(124)        J (-1) n+l(I ′ )+l(J) (-t) j 1 + k∈A ′ (I ′ ,J ) j k Λ J if i 0 = 0, J (-1) n+1+l(I ′ )+l(J) (-t) k∈A ′ (I ′ ,J ) j k Λ J otherwise.
Note that this is coherent with the fact that 0 ∈ Des(I) if i 0 = 0.

Proof -The proof is again by induction of the length of I following the same steps as in the expansion on the S.

Again, one can compute the matrices recursively. If one denotes by L 0 (n) (resp. L 1 (n)) the matrix expanding the RI (A, tA) where i 0 = 0 (resp. i 0 = 0) on the Λ J , one has the following structure:

(125) (L 0 (n+1) L 1 (n+1)) = tL 0 (n) -tL 0 (n) -L 1 (n) L 1 (n) tL 1 (n) tL 0 (n) L 1 (n) L 0 (n) .
6.3.3. Image of the R in the R basis of Sym. The expansion of R I (A|tA) has been discussed in [START_REF] Krob | Noncommutative symmetric functions II: Transformations of alphabets[END_REF] and [START_REF] Novelli | Superization and (q, t)-specialization in combinatorial Hopf algebras[END_REF]. Recall that a peak of a composition is a cell of its ribbon diagram having no cell to its right nor on its top (compositions with one part have by convention no peaks) and that a valley is a cell having no cell to its left nor at its bottom.

The formula is the following:

(126) R I (A|tA) = J (1 + t) v(J) t b(I,J) R J (A),
where the sum is over all compositions J such that I has either a peak or a valley at each peak of J. Here v(J) is the number of valleys of J and b(I, J) is the number of values d such that, either d is a descent of J and not a descent of I, or d -1 is a descent of I and not a descent of J.

In the case of the R, the matrices satisfy a simple induction. If one denotes by M 0 (n) (resp. M 1 (n)) the matrix expanding the RI (A, tA) where i 0 = 0 (resp. i 0 = 0) on the R, one has the following structure which follows directly from the interpretation in terms of signed permutations: (127)

(M 0 (n+1) M 1 (n+1)) = tM 1 (n) tM 0 (n) M 1 (n) M 0 (n) t(M 0 (n)+M 1 (n)) 0 0 M 0 (n)+M 1 (n) .
For example, one can check this result on Figure 3. One then recovers the matrix of R I (A|tA) on the R as M 0 + M 1 .

7. Euler-Bernoulli triangles 7.1. Alternating permutations of type B. Counting ordinary (type A) alternating permutations according to their last value yields the Euler-Bernoulli triangle, sequence A010094 or A008281 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF] depending on whether one requires a rise or a descent at the first position.

The same can be done in type B for alternating permutations and snakes. Since usual snakes begin with a descent, we shall count type B permutations of ribbon shape 2 m or 2 m 1 according to their last value. We then get the table Proof -Let S(n, p) be the set of alternating permutations of B n ending with p.

(128) n\p -6 -5 -4 -3 -2 -
The proof is almost exactly the same as for type A, with one exception: it is obvious that S(n, 1) = S(n, -1). Since the reading order changes from odd rows to even rows, let us assume that n is even and consider both sets S(n, p) and S(n, p -1). The natural injective map of S(n, p -1) into S(n, p) is simple: exchange p -1 with p while leaving the possible sign in place. The elements of S(n, p) that were not obtained previously are the permutations ending by p -1 followed by p. Now, removing p -1 and relabeling the remaining elements in order to get a type B permutation, one gets elements that are in bijection with elements of either S(n -1, p) or S(n -1, p -1), depending on the sign of p.

Snakes of type B.

The classical algorithm computing the number of type B snakes (also known as Springer numbers, see Sequence A001586 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]) makes use of the double Euler-Bernoulli triangle.

Proposition 7.2. The table counting snakes of type B by their last value is obtained by the following algorithm: first separate the picture by the column p = 0 and then compute two triangles. Put 1 at the top of the left triangle and 0 at the top of the right one and compute the rest as follows: fill the second row of the left (resp. right) triangle as the sum of the elements of the first row (resp. strictly) to their left. Then fill the third row of the right (resp. left) triangle as the sum of the elements of the previous row (resp. strictly) to their right. Compute all rows successively by reading from left to right and right to left alternatively.

Here are the first rows of both triangles: Proof -The proof is essentially the same as in the case of alternating permutations of type B: it amounts to a bijection between a set of snakes on the one side and two sets of snakes on the other side.

(129) n\p -6 -5 -4 -3 -2 -
One also sees that each row of the triangles of the alternating type B permutations presented in Equation (128) can be obtained, up to reversal, by adding or subtracting the mirror image of the left triangle to the right triangle. For example, on the fifth row, the sums are 40 + 40 = 80, then 48 + 32 = 80, then 54 + 22 = 76, then 57 + 11 = 68, and 57 + 0 = 57; the differences are 57 -0 = 57, then 57 -11 = 46, then 54 -22 = 32, then 48 -32 = 16, and 40 -40 = 0. These properties follow from the induction patterns.

These numerical properties indicate that one can split alternating permutations ending with (-1) n-1 i into two sets and obtain alternating permutations beginning with (-1) n i by somehow taking the "difference" of these two sets. On the alternating permutations, the construction can be as follows: assume that n is even. If p > 1, the set S(n, p) has a natural involution I without fixed points: change the sign of ±1 in permutations.

Then define two subsets of S(n, p) by

S ′ (n, p) = {σ ∈ S(n, p)|σ n-1 < -p or -1 ∈ σ}, S ′′ (n, p) = {σ ∈ S(n, p)|σ n-1 > -p and -1 ∈ σ}. (130)
Then S ′ (n, p) ∪ S ′′ (n, p) is S(n, p) and S ′ (n, p)/I(S ′′ (n, p)) is S(n, -p) up to the sign of the first letter of each element. In the special case p = -1, both properties still hold, even without the involution since S ′′ is empty.

Let us illustrate this with the example n = 4 and p = 2. We then have:

S(4, 2) = {13
A = A (0) ⊔ A (1) ⊔ • • • ⊔ A (r-1) = A × C,
with C = {0, . . . , r -1} be an r-colored alphabet. We assume that A (i) = A × {i} is linearly ordered and that (136) 1) .

A (0) > A (1) > • • • > A (r-
Colored words can be represented by pairs w = (w, u) where w ∈ A n and u ∈ C n . We define r-colored alternating permutations σ = (σ, u) by the condition (137)

σ 1 < σ 2 > σ 3 < . . .
hence, as permutations of shape 2 n or 2 n 1 as words over A. Let A

n be the set of such permutations. Their noncommutative generating series in FQSym (r) is then

(138) n≥0 σ∈A (r) n G σ (A) = X(A) = m≥0 R 2 m (A) + R 2 m 1 (A).
Thus, if we send A (i) to q i E, the exponential generating function of the polynomials (139)

α n (q 0 , . . . , q r-1 ) =

σ∈A (r) n n i=1 q u i is (140) α(z; q 0 , . . . , q r-1 ) = sin(q 0 + • • • + q r-1 )z + 1 cos(q 0 + • • • + q r-1 )z .
Iterating the previous constructions, we can define generalized snakes as colored alternating permutations such that σ 1 ∈ A (0) , or, more generally σ 1) , we have for these permutations the noncommutative generating series

1 ∈ A (0) ⊔• • •⊔A (i) . Setting B i = A (0) ⊔ • • • ⊔ A (i) and B i = A (i+1) ⊔ • • • ⊔ A (r-
(141) Y(B i , B i ) = (cos + sin)(B i ) sec(B i |B i )
which under the previous specialization yields the exponential generating series (142) y i (t; q 0 , . . . , q r-1 ) = cos(q 0 + • • • + q i )t + sin(q i+1 + • • • + q r-1 )t cos(q 0 + • • • + q r-1 )t .

Setting all the q i equal to 1, we recover sequences A007286 and A007289 for r = 3 and sequence A006873 for r = 4 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF], counting what the authors of [START_REF] Ehrenborg | Sheffer posets and r-signed permutations[END_REF] Proposition 8.1. The table counting alternating permutations with r colors by their last value is obtained by the following algorithm: first separate the picture by the column p = 0 and then compute r triangles. Put 1 at the top of each triangle and compute the rest as follows: fill the second row of all triangles as the sum of the elements of the first row strictly to their left. Then fill the third row of all triangles as the sum of the elements of the previous row to their right. Compute all rows successively by reading from left to right and right to left alternatively.

Proof -Same argument as for Propositions 7.1 and 7.2.

Applying the same rules to the construction of three triangles but with only one 1 at the top of one triangle gives the following three tables. Note that this amounts to split the alternating permutations, first by the number of bars of their first element, then, inside the triangle, by their last value. Arnol'd [START_REF] Arnol | The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF] has found remarkable arithmetical properties of the Euler-Bernoulli triangles. The study of the properties of these new triangles remains to be done. 9. Snakes of type D 9.1. The triangle of type D snakes. The Springer numbers of type D (Sequence A007836 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]) are given by exactly the same process as for type B Springer numbers, but starting with 0 at the top of the left triangle and 1 at the top of the right triangle. Since all operations computing the rows of the triangles are linear in the first entries, we have in particular that the sum of the number of snakes of type D n and the number of snakes on type B n is equal to the number of alternating permutations of type B.

We have even more information related to the triangles: both B and D triangles can be computed by taking the difference between the triangle of Equation (128) and of Equation (129). We obtain In other words, our first sort of type D snakes corresponds to permutations of ribbon shape 2 n 1 or 2 n whose first letter is positive. Since both alternating permutations and snakes of type B can be interpreted as solutions of a differential equation and a fixed point solution involving the same bilinear form, one then concludes that these snakes of type D satisfy It is easy to go from these last elements to the other type D snakes: change all values into their opposite and then change the first element s to -|s|. Conversely, change (resp. do not change) the sign of the first element depending whether it is not (resp. it is) in D n and then change all values into their opposite.

Tables

Here follow the tables of the maps A → tA from BSym to Sym. All tables represent in columns the image of ribbons indexed by type-B compositions, where the first half begins with a 0 and the other half does not. So, with N = 3, compositions are in the following order: Note that the zero entries have been represented by dots to enhance readability.

(159)

-

(- 1 )(- 1 )

 11 n id 2n and S = n≥0 n id 2n+1

2. 3 .

 3 Operations on alphabets. If B is another totally ordered alphabet, we denote by A + B the ordinal sum of A and B. This allows to define noncommutative symmetric functions of A + B, and

4. 1 .

 1 The Mantaci-Reutenauer algebra of type B. The most straightforward definition of Sym in type B is to generalize the combinatorial objects involved in the definition: change compositions into signed compositions.

5 . 5 . 1 .

 551 Algebraic theory in type B Alternating permutations of type B. 5.1.1. Alternating shapes. Let us say that a signed permutation π ∈ B n is alternating if π 1 < π 2 > π 3 < . . . (shape 2 m or 2 m 1).

  applying d to the fixed point equation brings back Equation (65) and it is clear from the definition of B that all terms in B(G α , G β ) are alternating signed permutations.

5. 1 . 3 .

 13 Alternating signed permutations counted by number of signs. Under the specialization Ā = tA, X goes to the series (69)X(t; A) = I   π alternating, C(std(π))=I t m(π)   R I (A)where m(π) is the number of negative letters of π. If we further set A = zE, we obtain (70) x(t, z) = 1 + sin((1 + t)z) cos((1 + t)z) sin z cos z -sin z for t = 1, thus giving a t-analogue different from the one of [12]. 5.1.4. A simple bijection. From (70), we have

  first separate the picture by the column p = 0 and then compute two triangles. Put 1 at the top of each triangle and compute the rest as follows: fill the second row of the left (resp. right) triangle as the sum of the elements of the first row (resp. strictly) to their left. Then fill the third row of the right (resp. left) triangle as the sum of the elements of the previous row (resp. strictly) to their right. Compute all rows successively by reading from left to right and right to left alternatively. This is the analogue for alternating permutations of Arnol'd's construction for snakes of type B[START_REF] Arnol | The calculus of snakes and the combinatorics of Bernoulli, Euler, and Springer numbers for Coxeter groups[END_REF].

1 .( R02 n 1 +

 11 Snakes of type D. From our other sets having the same cardinality as type B snakes, we can deduce combinatorial objects having same cardinality as type D snakes by taking the complement in the alternating permutations of type B.Since the generating series of type B alternating permutations is) + R # (2 m 1) ).and the generating series of type B snakes defined in Section 5.2R02 n+1 ), we easily get one definition of the generating series type D snakes:(150) D = X -Y = n≥0 ( R2 n 1 + R2 n+1 ).

G 1 +B 9 . 1 . 2 .

 1912 B(D, X).The iteration of (154) brings up a solution close to (68) and (87): T (G 0 , G 1 ), where, for a tree T , B T (a, b) is the result of the evaluation of all expressions formed by labeling by a or b the leaves of T and by B its internal nodes. Note that in this case, the first leaf needs to have label b. The usual snakes of type D. The previous type D snakes are not satisfactory since, even if they fit into the desired triangle, they do not belong to D n . The classical snakes of type D of Arnol'd belong to D n and are easily defined: select among permutations of ribbon shape 12 n and 12 n 1 the elements with an even number of negative signs and such that σ 1 + σ 2 < 0.

  , 12 43, 12 43 , 12 43, 12 43 , 1324, 13 24, 1324, 13 24, 13 42, 13 42 , 13 42, 13 42 , 1423, 14 23, 1423, 14 23, 14 32, 14 32 , 14 32, 14 32 , 21 34, 213 4, 21 43, 21 43 , 214 3, 2143 , 2314, 23 14, 2314, 23 14, 23 41, 23 41 , 23 41, 23 41 ,

	(62)	12 34, 12 342413, 24 13, 2413, 24 13, 24 31, 24 31 , 24 31, 24 31 , 31 24, 312 4, 31 42, 31 42 ,
		314 2, 3142 , 3214, 32 14, 32 41, 32 41 , 324 1, 3241 , 3412, 34 12, 3412, 34 12,
		34 21, 34 21 , 34 21, 34 21 , 41 23, 412 3, 41 32, 41 32 , 413 2, 4132 , 4213, 42 13,
		42 31, 42 31 , 423 1, 4231 , 4312, 43 12, 43 21, 43 21
		1, 1, 12, 12, 21, 21
	(61)	12 3, 12 3, 132, 13 2, 132, 13 2, 21 3, 213 , 231, 23 1, 231, 23 1, 31 2, 312 , 321, 32 1,

  1, 23 1, 132, 2 31, 132, 23 1, 2 31 , 231 , 231, 231, 1 32, 13 2, 1 32 , 132 , 13 2, 13 2.

	5.2. Type B snakes.
	5.2.1. An alternative version. The above considerations suggest a new definition of
	type B snakes, which is a slight variation of the definition of [2]. We want to end up
	with the generating series
	(75)	y(1, z) =	1 cos z -sin z	=	cos z + sin z cos 2z
	after the same sequence of specializations. A natural choice, simple enough and given
	by a series in BSym, is to set

  The table counting type B alternating permutations by their last value is obtained by the following algorithm:

					1 0 1	2	3	4	5	6
	1				1 0 1
	2			0	1 0 1	2
	3		4	4	3 0 3	2	0
	4	0	4	8	11 0 11 14 16 16
	5	80 80 76 68 57 0 57 46 32 16	0
	6	0 80 160 236 304 361 0 361 418 464 496 512 512
	Proposition 7.1.

  called augmented alternating permutations.8.2.Triangles of alternating permutations with r colors. One can now count alternating permutations of shapes 2 k and 2 k 1 by their last value. With r = 3, the following tables present the result:

		n	1	2	3	4	5	1	2	3	4	5	1	2	3	4 5
		1	1					1					1
	(143)	2 3	0 9	1 9	8			1 8	2 7	5			2 5	3 3	0
		4	0	9	18	26		26	34	41	46		46	51	54 54
		5 405 405 396 378 352	352 326 292 251 205	205 159 108 54 0

  Here are these elements for n ≤ 4: (151) 12, 12 3, 132, 231, 13 2, 23 1 12 34, 12 43, 12 43 , 1324, 13 24, 13 42, 13 42 , 1423, 14 23, 14 32, 14 32 , 2314, 23 14, 23 41, 23 41 , 2413, 24 13, 24 31, 24 31 , 3412, 34 12, 34 21, 34 21 .

	(152)

  One then gets the following elements for n ≤ 4: (156) 1 12 , 12 3, 1 32 , 13 2, 2 31 , 23 1, 1 23 4, 1 24 3, 12 43, 1 32 4, 1324 , 1 34 2, 13 42, 1 42 3, 1423 , 1 43 2, 14 32, 2 31 4, 2314 , 2 34 1, 23 41, 2 41 3, 2413 , 2 43 1, 24 31, 3 41 2, 3412 , 3 42 1, 34 21. (157)

  t 2 t 2 1 -1 t 2 + t . . t + 1 Figure 1. Matrices of RI (A, tA) on the S basis for n = 2, 3. -t 3 -t 3 t 3 1 -1 -1 1 t 2 t 3 -t 2 -t 3 -1 -t 1 t -t t t 3 -t 3 -1 1 t 2 -t 2Figure 2. Matrices of RI (A, tA) on the Λ basis for n = 2, 3. + t t 3 + t 2 . . t + 1 t 2 + t . t 2 + t t 3 + t 2Figure 3. Matrices of RI (A, tA) on the R basis for n = 2, 3.

				t 3		-t 3	-t 3 t 3 1 -1 -1		1	
				-t 3 -t 2	.	t 3 +t 2 . . t+1	.	-t-1	
			 	t-t 3 t 3 -t	.		. .	.	1-t 2 t 2 -1	 
				t 3 +t 2 t 2 +t	.		. .	.	t 2 +t t+1
	(160)	t 2 -t 2 -1 1 t t 2 1 t	   	t 3 t	t 2	t 2	t 3	1	t	t	t 2	   
	(161)
				t		t 2	t 2		t 3 1	t	t		t 2	
	t t 2 + t . . t + 1 t 2 1 t	  	.		t 2 .		. .	.	t + 1 t 2 + t	  
			t 3 + t 2 t 2 + t	.		. .	.	t 2 + t t + 1

This differs from the convention used in some references.

. M. Josuat-Vergès was supported by the Austrian Science Foundation (FWF) via the grant Y463. 1


Jérémy Parriaux

Gilles Millérioux

Nilpotent semigroups for the characterization of flat outputs of discrete-time switched linear and LPV systems

This paper addresses the problem of flat output characterization for switched linear systems along with an extension to LPV systems. A condition which has a polynomial complexity with respect to the dimension of the system and a practical approach for checking this condition are provided.

I. INTRODUCTION

Flatness is an important control-theoretical concept introduced in [START_REF] Fliess | Flatness and defect of non-linear systems: introductory theory and examples[END_REF]. For a flat discrete-time system (linear or nonlinear), the state variable as well as the input to the system can be written as some function of the output (including forward and backward shifts in the output). Such a property is especially interesting both for state reconstruction and for control perspectives. As for the state reconstruction context, it is clear from the definition that flatness provides a generic way of reconstructing the state vector despite possibly unknown inputs. Even more is true, flatness is a structural property of a dynamical system and so provides conditions for the existence of an unknown input observer without any a priori structure of the observer. For control purposes, flatness is also relevant insofar as, from the definition again, it provides a constructive way of designing a feedforward control to track a prescribed trajectory of the plant output. An overview along with applications can be found in the book [START_REF] Sira-Ramirez | Differentially Flat Systems[END_REF]. This being the case, an important issue related to flatness is the problem of checking whether a given output of a dynamical system is flat or not. An interesting approach has been proposed in [START_REF] Levine | Flat output characterization for linear systems using polynomial matrices[END_REF] for continuous linear systems. Flat output characterization has been addressed for the first time for discrete-time switched linear systems in [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF]. However, the condition was not, in general, tractable. The purpose of this paper is to give a new criterion for discrete-time switched linear systems with better tractability. It is based on the notion of nilpotent semigroups. The corresponding algorithm for checking the conditions is given. Furthermore, an extension to LPV systems is proposed. The layout is the following. In Section II, we recall some basics on flatness for switched linear systems. Section III is devoted to flat output characterization as well as the corresponding algorithm. An extension to LPV systems is proposed in Section IV. Finally, Section V is devoted to illustrative examples.

II. PRELIMINARIES AND DEFINITIONS

We shall examine throughout this paper switched linear systems in the form

x k+1 = A σ(k) x k + B σ(k) u k y k = C σ(k) x k + D σ(k) u k (1)
The state vector is

x k ∈ R n , the input is u k ∈ R m and the output is y k ∈ R p . All the matrices, namely A σ(k) ∈ R n×n , B σ(k) ∈ R n×m , C σ(k) ∈ R p×n and D σ(k) ∈ R p×m
belong to the respective finite sets of cardinality J:

A = {A 1 , . . . , A J }, B = {B 1 , . . . , B J }, C = {C 1 , . . . , C J } and D = {D 1 , . . . , D J }. At a given time k, the mode is delivered by a switching function σ : k ∈ N -→ σ(k) ∈ {1, . . . , J} = J . A sequence of modes (also called path) over an interval of time [k 1 , k 2 ], that is {σ(k 1 ), . . . , σ(k 2 )},
is denoted by {σ} k1:k2 . For a given switching rule σ, the set of corresponding mode sequences over an interval of time of length T + 1 belongs to J T +1 . This set has cardinality J T +1 if σ is arbitrary since, in this case, it is composed of all the possible mode sequences. Otherwise, the cardinality is lower because there may exist some forbidden patterns.

Let U be the space of input sequences over the time interval [0, ∞) and Y the corresponding output space. At time k, for each initial state x k ∈ R n , when the system (1) is driven by the input sequence {u} k:k+T = {u k , . . . , u k+T } ∈ U, for a mode sequence {σ} k:k+T , {x(x k , σ, u)} k:k+T refers to the solution of (1) in the interval of time [k, k + T ] starting from

x k and {y(x k , σ, u)} k:k+T ∈ Y refers to the corresponding output sequence in the same interval of time

[k, k + T ].
We introduce the subsequent vectors and matrices. For any integer n, 1 n refers to the n-dimensional identity matrix and 0 n×m stands for the n × m zero matrix. If irrelevant, the dimension of the zero matrix will be omitted and we shall merely write 0.

u k:k+i =      u k u k+1 . . . u k+i      , y k:k+i =      y k y k+1 . . . y k+i      (2)
I m×r = 1 m 0 m×(m•r) O σ(k:k+i) =      C σ(k) C σ(k+1) A σ(k) . . . C σ(k+i) A σ(k+i-1) σ(k)      (3)
The matrix O σ(k:k+i) involves the transition matrix

A σ(k1) σ(k0) = A σ(k1) A σ(k1-1) • • • A σ(k0) if k 1 ≥ k 0 = 1 n if k 1 < k 0
Finally, we recursively define the matrix

M σ(k:k+i) = D σ(k) 0 O σ(k:k+i) B σ(k) M σ(k+1:k+i) (4) with M σ(k:k) = D σ(k)
Let us notice that the notation σ(k : k + i), which points out that the related matrix depends on the sequence {σ(k), . . . , σ(k + i)} is somehow abusive since σ is defined over N and not over N i+1 . However, since it does not induce confusion, such a notation will be used accordingly. Flatness is closely related to the notion of left invertibility. Left invertibility for switched linear systems has been addressed in [START_REF] Vu | Invertibility of switched linear systems[END_REF] for continuous-time systems and in [START_REF] Sundaram | Designing stable inverters and state observers for switched linear systems with unknown inputs[END_REF], [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF] for discrete-time systems.

Definition 1 ([6], [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF]): A system is a left r-delay inverse for (1) if, under identical initial conditions x 0 and identical sequences {σ} 0:∞ , there exists a non negative integer r such that, when driven by y k:k+r , the equalities x k+r = x k and u k+r = u k hold for all k ≥ 0, u k being its output at time k. The non negative integer r is called the inherent delay.

Theorem 1 ([6], [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF]): The system

      
x k+r+1 = P σ(k:k+r) x k+r +B σ(k) I m×r (M σ(k:k+r) ) † y k:k+r u k+r = -I m×r (M σ(k:k+r) ) † O σ(k:k+r) x k+r +I m×r (M σ(k:k+r) ) † y k:k+r (5) with

P σ(k:k+r) = A σ(k) -B σ(k) I m×r (M σ(k:k+r) ) † O σ(k:k+r) (6)
is a left r-delay inverse system for (1). The matrix (M σ(k:k+r) ) † is the classical Moore-Penrose generalized inverse of M σ(k:k+r) . The matrices P σ(k:k+r) are called the left-inverse dynamical matrices.

Remark 1: In Definition 1, the initial condition is considered at the particular discrete time k = 0 but can be replaced by any other initial condition x k considered at time k.

A. Flatness Definition 2 ([4]

): A square (p = m) dynamical system is said to be flat if there exists a set of independent variables y k , referred to as flat outputs, such that all system variables can be expressed as a function of the flat output and a finite number of its backward and/or forward shifts. In particular, there exist two functions F and G which obey

x k = F(y k+k F , . . . , y k+k F ) u k = G(y k+k G , . . . , y k+k G ) (7)
where k F , k F , k G and k G are Z-valued integers.

Considering the expression of u k in [START_REF] Radjavi | Simultaneous Triangularization[END_REF], it is clear that left invertibility is a necessary condition for flatness.

The issue of flat output characterization consists in checking whether a given output of a dynamical system is flat. Theorem 2 stated in [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF] and recalled below gives a characterization by considering the left-inverse dynamical matrices. Theorem 2 ( [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF]): An output y k of the system (1) assumed to be square, with left inherent delay r, is a flat output if there exists a positive integer K < ∞ such that, for all sequences in J r+K , the following equality, involving the product of left-inverse dynamical matrices, applies for all k ≥ 0:

P σ(k+K-1:k+K-1+r) P σ(k+K-2:k+K-2+r) • • • P σ(k:k+r) = 0 ( 8
)
The point is that the computational cost of the test ( 8) grows exponentially with respect to the number K of matrices involved in [START_REF] Dubi | An algorithmic approach to simultaneous triangularization[END_REF]. Besides, no upper bound for K is given.

The first objective of the paper is to propose an alternative condition with a reduction of the computational cost. As the condition only involves the left-inverse dynamical matrices of the left r-delay inverse system, we define below an auxiliary system and rewrite Theorem 2.

B. Auxiliary system

Let us define the auxiliary system of (1) as the switched linear system given by

q k+1 = Q σ (k) q k (9)
with q k ∈ R n and σ a switching rule defined as follows.

Consider the mapping φ : J r+1 → H = {1, . . . , J r+1 } that assigns to each possible sequence {σ(k), . . . , σ(k + r)} an integer h from the set H which uniquely identifies the sequence. Then, the switching rule σ is defined as the function from N to H which associates to each integer k ∈ N the quantity σ (k) = φ(σ(k), . . . , σ(k + r)) ∈ H. The value σ (k) is the mode of the auxiliary switched linear system (9) and Q σ (k) = P σ(k:k+r) . We denote by Q the set of all the matrices Q h (h ∈ H).

By considering the auxiliary system (9), we are now in position of reformulating Theorem 2 which turns into Theorem 3: An output y k of the system (1) assumed to be square, with left inherent delay r, is a flat output if there exists a positive integer K < ∞ such that, for all admissible sequences {σ (k), . . . , σ (k + K -1)} ∈ H K , the following equality, involving the product of the dynamical matrices of the auxiliary system (9), applies for all k ≥ 0:

Q σ (k+K-1) Q σ (k+K-2) • • • Q σ (k) = 0 (10) Proof:
The proof is a straightforward consequence of the definition of the auxiliary system. We are now in position to give an alternative condition to [START_REF] Dubi | An algorithmic approach to simultaneous triangularization[END_REF]. It is based on the consideration of (10) and the notion of nilpotent semigroups as presented in the next section.

III. FLAT OUTPUT CHARACTERIZATION AND NILPOTENT

SEMIGROUPS

A. Main result

Basics related to nilpotent semigroups are first recalled. Definition 3 (Semigroup): A semigroup S is a set together with an associative internal law. S is said to be finite if it has a finite number of elements. If S is a set of matrices, the associative internal law is the matrix multiplication. We denote by 0 the absorbing element of a semigroup when it exists.

Definition 4 (Nilpotent semigroup): A semigroup S with an absorbing element 0 is said to be nilpotent if there is an integer t ∈ N * such that the internal law applied to any t elements of S is always equal to 0. The smallest integer t is called the nilpotency class of S. If S is a set of matrices, applying the internal law to any t elements of S amounts to performing the product of t matrices of S. The absorbing element is, in this case, the null matrix. Here, the elements of S are the matrices of Q.

Theorem 4: If the matrices of Q of the auxiliary system (9) generate a nilpotent semigroup, then y k is a flat output.

Proof: If the matrices of Q of the auxiliary system (9) generate a nilpotent semigroup, by definition, for any t-uple (h 1 , . . . , h t ) ∈ H t , t being the class of nilpotency of Q, one has

t i=1 Q hi = 0 (11)
Hence, (10) is fulfilled with K = t. As a result, Theorem 3 holds and means that y k is a flat output. Corollary 1: If the of Q generate a nilpotent semigroup, the integer K is finite and is upper bounded by the dimension n of the system [START_REF] Fliess | Flatness and defect of non-linear systems: introductory theory and examples[END_REF].

Proof: If the matrices of Q generate a nilpotent semigroup, the integer K is equal to the class of nilpotency t of the semigroup. The class of nilpotency being actually bounded by the dimension of the matrices involved in the semigroup, K is bounded by the dimension of the matrices of Q, that is precisely n, the dimension of the system (1).

Remark 2: A necessary condition for the matrices of Q to generate a nilpotent semigroup is that all the matrices of Q are nilpotent, that is all their eigenvalues are zero. Indeed, (11) must hold in particular for the t-uples (h 1 , . . . , h t ) with h i = h l for all i, l ∈ {1, . . . , t}.

Remark 3: It is worth pointing out that different sequences {σ(k), . . . , σ(k + r)} of (1) and so different modes σ (k) = φ(σ(k), . . . , σ(k + r)) of (9) might lead to identical matrices Q σ (k) . As a result, Q is a multiset 1 and we should consider only distinct matrices of Q to reduce the computational cost. We denote by Z the set of distinct matrices of Q and by L its cardinality. Its elements are denoted by Z l (l = 1, . . . , L). Clearly, Z ⊆ Q, L ≤ J r+1 and Theorem 4 still applies by considering Z instead of Q. 1 The notion of multiset is a generalization of the notion of set in which elements are allowed to appear more than once.

B. Equivalence on conditions

Let us first point out that the switching rule σ of the auxiliary system (9) is constrained. Indeed, since σ (k) = φ(σ(k), . . . , σ(k+r)) and σ (k+1) = φ(σ(k+1), . . . , σ(k+ r + 1)), σ (k) and σ (k + 1) depend on the common subsequence {σ(k+1), . . . , σ(k+r)} and thereby are related one another. Hence, even in the case when the switching rule σ of (1) is arbitrary, given a matrix Q σ (k) = P σ(k:k+r) , the matrix Q σ (k+1) = P σ(k+1:k+1+r) is constrained. To formalize this constraint, it is convenient to introduce a socalled set of feasible transitions.

Definition 5: The set Γ(σ (k)) of feasible transitions from mode σ (k) is the set defined by

Γ(σ (k)) = {h ∈ H : h = φ(σ(k + 1), . . . , σ(k + r + 1)), ∀σ(k + r + 1) ∈ J } (12)
In other words, Γ(σ (k)) is the set h ∈ H which can be reached when σ(k + r + 1) varies over the whole range J , σ (k) and so the sequence {σ(k + 1), . . . , σ(k + r)} being imposed. One has Γ(σ (k)) ⊆ H which clearly formalizes that σ is constrained. It is clear that Γ(σ (k)) can never be the empty set.

Definition 6:

A sequence {h 1 , h 2 , . . .} is said admissible if for any i ≥ 0 h i+1 ∈ Γ(h i ) (13) Let us introduce the map µ : H → Q which assigns to each integer h ∈ H the matrix Q h ∈ Q. The restriction of µ to a particular subset Γ(h) of H is denoted by µ Γ(h) . Definition 7: A sequence of matrices {Q h1 , Q h2 , . . .} (h i ∈ H) is said admissible if for any h i ∈ H Q hi+1 ∈ R(µ Γ(hi) ) (14)
where the notation R denotes the range of the function. The following proposition applies: Proposition 1: The conditions (10) and (11) are equivalent if and only if

∀h i ∈ H, R(µ Γ(hi) ) = Q (15) Proof:
The statement (11) ⇒ (10) is always true regardless of the condition (15). Still, it must be shown that (10) implies (11) provided that (15) is fulfilled. The condition ∀h i , R(µ Γ(hi) ) = Q means that, for any arbitrary mode h i ∈ H, Q hi+1 can be any matrix in Q. Hence, for any t-uple (h 1 , . . . , h t ), the sequence {Q h1 , . . . , Q ht } is an admissible sequence for (9). Finally, the set of products Q h1 • • • Q ht for all t-uples (h 1 , . . . , h t ) coincides with the set of products (10) for all k ≥ 0. That completes the proof.

Similarly to Remark 3, if different sequences {σ(k), . . . , σ(k + r)} and so different σ (k) = φ(σ(k), . . . , σ(k + r)) lead to identical matrices Q σ (k) , Proposition 1 still can be applied with a lower computational cost if the multiset Q is replaced by the set Z of distinct elements of Q. Hence, we will consider hereafter the set Z.

Remark 4: It can be easily seen that ( 15) is always satisfied for at least two particular cases: when the inherent delay r is equal to zero or if it is equal to one and that C does not depend on σ. These two cases encompass a large class of systems and we will illustrate in Section V that (15) also applies in other cases.

C. Computational issues

In this section, we propose an algorithm that allows to check whether or not a set of matrices generates a nilpotent semigroup that is, if Theorem 4 is fulfilled. It is shown that it has a polynomial complexity and is theoretically motivated by Levitsky's theorem (Theorem 2.1.7 stated in [START_REF] Radjavi | Simultaneous Triangularization[END_REF]).

Theorem 5 (Levitsky's theorem): Any semigroup of nilpotent matrices can be triangularized. In other words, all the matrices of a same nilpotent semigroup can be rewritten as upper triangular matrices with zeros on the diagonal up to a common change of basis. The consequence of this theorem is central for our purpose. Indeed, determining whether or not the matrices of Z generate a nilpotent semigroup amounts to checking whether or not Z can be simultaneously triangularized. It is a necessary and sufficient condition. The approach we propose to check Theorem 5 is inspired from the general triangularization method provided in [START_REF] Dubi | An algorithmic approach to simultaneous triangularization[END_REF] and corresponds to Algorithm 1. Next, some peculiarities that apply to our special case will be addressed to provide a fully-specified algorithm for flat output characterization. The algorithm is expected to return a change of basis S that simultaneously triangularizes the set Z composed of the L matrices Z l , l ∈ {1, . . . , L} of dimension n. According to Remark 2, Z l , l ∈ {1, . . . , L} are assumed to be nilpotent.

Algorithm 1: 1: Initialization 2: for l=1 to L do

w i ← S 2 • v i 14: S 1 ← S 1 w i 15:
S 2 ← matrix whose column vectors are vectors that extend S 1 to a basis 16: S ← (S 1 S 2 ) 17:

I 1 ← 0 i 1 n-i 18: I 2 ← 0 i 1 n-i 19:
S -1 ← inverse of S 20:

for l ← 1 to L do 21:

T l ← I 1 S -1 Z l SI 2 22:
end for 23: end for 24: return S

The following comments are in order:

• Line 1 to Line 5 corresponds to the initialization.

Matrices T l (l = 1, . . . , L) play the role of the auxiliary variables and are initialized at the beginning with the matrices Z l of the set Z. • At most n -1 successive loops from Line 7 to Line 23 are performed as stressed by Corollary 1. • Line 8 corresponds to the first step of a given loop i. It consists in finding out a eigenvector v i which is common to the matrices T l (l = 1, . . . , L). Consequently, in the first loop, v 1 is a common eigenvector of the matrices Z l of Z. It is worth pointing out that if this step fails in the loop i, it means that the matrices T l (l = 1, . . . , L) do not have any common eigenvector v i and the algorithm stops. Levitsky's theorem stating a necessary and sufficient condition, it can be concluded that Z does not generate a nilpotent semigroup and Theorem 4 is not fulfilled. • Line 14 describes the fact that the final change of basis S is built column after column. Each new vector v i carried out in the loop v i is added (actually after a change of basis notified at Line 13) resulting in a matrix

S 1 = (v 1 • • • v i ). When i = n then S = (S 1 S 2 ), S 1
and S 2 resulting from the loop n -1. • At Line 15, S 1 must be extended to a basis. By extension, it is meant a set of n -i vectors w j so that

S = (S 1 w 1 • • • w n-i ) is full rank. The matrix S 2 is precisely S 2 = (w 1 • • • w n-i ).
• Line 21 performs the current change of basis S to the matrices Z l . The multiplications by I 1 and I 2 merely corresponds to the extraction of a square matrix of dimension n -i from the matrix S -1 Z l S, that the first i rows and columns of S -1 Z l S are removed. A new set of matrices T l is thereby obtained. A new loop can restart from Line 7.

Such an algorithm is quite general. However, the determination of a common eigenvector at Line 8 and the extension to a basis at Line 15 can be particularized to our special context. 1) Determination of a common eigenvector: According to Remark 2, a necessary condition for the set Z to generate a nilpotent semigroup is that all the matrices Z l of Z are nilpotent, that is all their eigenvalues are zero. The set T = {T l }, l = 1, . . . , L corresponds exactly to Z at the initialization and it is updated at each loop i through a linear change of basis S at Line 21 which preserves the eigenvalues. Hence, the eigenvalues of the T l 's are all zero whatever the loop i ≥ 0 is. Consequently, for any v i (i = 1, . . . , n) and ∀T l ∈ T , T l v i = 0 holds. Hence, v i is a non zero solution of

Rv i = 0 with R =    T 1 . . . T L    (16)
As a result, v i is a non zero vector of the null space of R denoted ker(R).

2) Extension to a basis: At Line 15, S 1 must be extended to a basis. We must thereby find out a set of n -i vectors w j so that S = S 1 w 1 • • • w n-i is full rank. It can be obtained by determining a basis of the kernel of the transpose of S 1 . In other words, S 2 = (w 1 • • • w n-i ) can be any basis of ker(S 1 ) where the symbol stands for transposition.

D. Complexity

All the operations can easily be performed by software involving usual built-in functions. The complexity of the condition ( 8) is O(J r+K Kn 3 ). The point is that the complexity is exponential with respect to the number of matrices K involved in the product [START_REF] Dubi | An algorithmic approach to simultaneous triangularization[END_REF], which can be large. On the other hand, let us assess the computational cost of the flat output characterization approach based on nilpotent semigroups by examining Algorithm 1. Considering a given loop, the most complex operations are performed at Lines 8, 15, 19 and 21. Lines 8 and 15 consist in determining the kernel of a matrix. It is usually based on singular value decomposition of a R a×b matrix for which known algorithms with complexity O(4ab 2 + 8b 3 ) exist. Line 19 has complexity O(n 3 ) when considering usual inversion algorithms. Line 21 is a change of basis. The multiplications by I 1 and I 2 can be avoided since its purpose is merely to extract a square matrix of dimension n -i from the matrix S -1 Z l S. Therefore, the two operations to be considered are the two matrix multiplications of Z l by S and S . Matrix multiplications have complexity at most O(n 3 ). Therefore, the complexity of Lines 20 to 22 is O(Ln 3 ) or O(J r+1 n 3 ) due to the inequality L ≤ J r+1 (recall Remark 3). This part of the code is the one with the largest complexity. The operations are repeated over at most n loops. Therefore, the global complexity of Algorithm 1 is O(J r+1 n 4 ). There is no more exponential complexity with respect to the number of matrices involved in the product [START_REF] Dubi | An algorithmic approach to simultaneous triangularization[END_REF].

It is an improvement insofar as the complexity is no longer exponential with respect to the parameter K.

IV. EXTENSION TO LPV SYSTEMS

The results stated in the previous sections can be interestingly extended in a rather straightforward way to LPV systems. Indeed, the system (1) can be viewed as an LPV system as soon as we consider that the switching rule σ is replaced by a function which takes values in a continuum. If so, the sets J , H, Γ(σ (k)), Q and Z must be considered as uncountable sets. The r-delay inverse system (5), the auxiliary system (9) together with the mapping φ still make sense as soon as σ is considered as a function, similarly to σ, taking values in a continuum. Besides and most importantly, it turns out that both semigroups (Definition 3) and the nilpotent semigroups (Definition 4) are still well defined for an uncountable set S. As a result, Theorem 4 still applies.

On the other hand, Levitsky's theorem, which allows for checking whether Theorem 4 is fulfilled, applies for any semigroup, including semigroups with infinite cardinality, which is precisely the case here. It is recalled that Levitsky's theorem asserts that "Z generates a nilpotent semigroup if the matrices of Z can be simultaneously triangularized". The key point is that, considering Z as an uncoutable set of matrices, it can be reformulated in a strictly equivalent way stating that "the matrices Z σ (k) must be simultaneously triangularized with a change of basis that does not depend on σ (k)". Taking into acount the aforementionned considerations and combining Theorem 4 and Theorem 5, the following theorem holds for characterizing flat outputs of LPV systems Theorem 6: If the matrices of Z of the auxiliary system (9) can be simultaneously triangularized independently of σ (k), then y k is a flat output. Algorithm 1 still applies up to some minor modifications. The loops at Line 2 and Line 20 can be removed or equivalently, L can be set to L = 1. Besides, the determination of a common eigenvector at Line 8, that is the search for a non zero vector v i of ker(R) as explained in Subsection III-C.1 turns into the search for a non zero vector v i of ker(T 1 ) (since L = 1 and so R = T 1 ) independent of σ (k). Line 8 has to be replaced by 8: v i ← One eigenvector of T 1 independent of σ (k) The flat output characterization based on nilpotent semigroups for LPV systems is valuable for two major reasons. First, flat outputs characterization of LPV systems has never been addressed so far in the literature. Secondly, the characterization through [START_REF] Dubi | An algorithmic approach to simultaneous triangularization[END_REF] or equivalently (3) cannot be done for LPV systems since that requires to check an infinite number of possible products. Indeed, σ taking values in a continuum, the number of sequences {σ} in Theorem 2 or sequences {σ } in Theorem 3 would be infinite.

V. ILLUSTRATIVE EXAMPLES

A. Example 1: switching systems

Consider the SISO switched linear system of the form (1). The dimension is n = 4, the switching rule σ, not detailed here, is assumed to deliver arbitrary sequences and the number of modes is J = 3. According to the mode, the state space matrices numerically read

A 1 =    -1 -0.5 -0.5 0 1 1.5 1.5 0 1 0.5 0.5 1 1 0 1 0    , A 2 =    -1 -1 -1 -0.5 1 2 2 0.5 1 1 1 1.5 1 0 1 0    , A 3 =    -1 -2.5 -2.5 -2 1 3.5 3.5 2 1 2.5 2.5 3 1 0 1 0    B 1 = B 2 = B 3 = 0 0 0 1 C 1 = C 2 = C 3 = 2 1 1 0 D 1 = D 2 = D 3 = 0
Since it is a SISO system, that for all i ∈ J , D i = 0, for all (i, j) ∈ J 2 , C i B j = 0 and that for all (i, j, l) ∈ J 3 , C i A j B l = 0, the inherent delay is r = 2. Let us derive the corresponding auxiliary system as defined in Section II-B. To this end, we must define the mapping φ. The number of possible sequences over any interval of time

[k : k + r] is J r+1 = 3 2+1 = 27 and φ({1, 1, 1}) = 1 • • • φ({1, 1, 2}) = 2 φ({3, 3, 1}) = 25 φ({1, 1, 3}) = 3 φ({3, 3, 2}) = 26 • • • φ({3, 3, 3}) = 27
The set Γ of feasible transitions obeys

Γ(1) = {1, 2, 3} • • • Γ(2) = {4, 5, 6} Γ(26) = {23, 24, 25} • • • Γ(27) = {25, 26, 27}
It turns out that the multiset Q has L = 3 distinct matrices and the matrices Z l of the corresponding set Z numerically read As a consequence, based on Theorem 4 and Theorem 5, we conclude that y k is a flat output.

Z 1 =    -1 -0.5 -0.5 0 1 1.5 1.5 0 1 0.5 0.5 1 -2 -2 -2 -1    , Z 2 =    -1 -1 -1 -0.5 1 2 2 0.5 1 1 1 1.5 -2 -3 -3 -2    , Z 3 =    -1 -2.5 -2.5 -2 1 3.5 3.5 2 1 2.5 2.5 3 -2 -6 -6 -5    One has µ(Γ(1)) = • • • = µ(Γ(27)) = {Z 1 , Z 2 , Z 3 } Hence, condition (

B. Example 2: LPV systems

We investigate an LPV system given by the following form 2 x k+1 = A σ(k)

x k + B σ(k) u k y k = C σ(k) x k + D σ(k) u k (17)
where x k ∈ R 4 , u k ∈ R, y k ∈ R and the state space matrices numerically read 2 In the framework of LPV systems, the notation X(ρ k ) is often used and refers to matrices which depend on a time-varying parameter ρ k . Hence here, by X σ(k) , it must be understood a matrix X which depends on a time-varying parameter σ(k) with σ(k) taking values in a continuum. σ As stressed in Section IV, σ must be considered here as a function which takes values in a continuum. Since it is a SISO system, that D σ(k) = 0 for all k and that C σ(k+1) B σ(k) = 1 independently of σ, the inherent delay is 1. The set Q of the dynamical matrices of the left-inverse system [START_REF] Vu | Invertibility of switched linear systems[END_REF] Finally, since Q σ (k) only depends on σ at time k, it is clear that condition (15) of Proposition 1 is fulfilled, guaranteeing that conditions (10) and (11) are equivalent. The interest of the result stated in this paper is that (11) provides an alternative to (10), hence solving the intractability of (10) for LPV systems.

A σ(k) =     0 1 0 0 1 0 1 0 0 0 0 1 σ (1) k σ (2) k 1 0     , B σ(k) =     0 0 1 0     ,

VI. CONCLUSION

We have provided a condition to characterize flat outputs of switched linear discrete-time systems. Then, the condition is extended to LPV discrete-time systems. The condition is based on the notion of nilpotent semigroups. A tractable fully-specified algorithm, with polynomial complexity with respect to the dimension of the system, has been provided to check the condition.

3 :Triangularization 7 :

 37 T l ← Z l 4: end for 5: S 2 ← 1 n ; S 1 ← 0 n×0 6: for i ← 1 to n -1 do 8:v i ← One eigenvector common to the matrices {T l }, l = 1, . . . , L 9: if v i does not exist then

  15) of Proposition 1 is fulfilled and so applies beyond the particular cases mentioned in Remark 4. Finally, it turns out that Algorithm 1 succeeds and returns the following change of basis S

  (i) k will denote the i-th component of σ(k) C σ(k) = 1 0 1 0 , D σ(k) = 0

  are the matrices Q σ (k) = P σ(k:k+1) which read for all σ (k) = {σ(k), σ(k + 1)} Q σ (k)It turns out that Theorem 6 is fulfilled with a triangularization basis S which numerically reads

  This work was partially supported by the CPER Région Lorraine (AOC Project), Fédération Charles Hermite, and INRIA

1 Université de Lorraine, CRAN, UMR 7039, ESSTIN, 2 rue Jean Lamour, Vandoeuvre-lès-Nancy Cedex, 54506, France 2 CNRS, CRAN, UMR 7039, France