Alin Bostan

Jordan Tirrell
email: jtirrell2@washcoll.edu

Bruce W Westbury
email: bruce.westbury@gmail.com

Y I Zhang
email: yi.zhang03@xjtlu.edu.cn

ON SOME COMBINATORIAL SEQUENCES ASSOCIATED TO INVARIANT THEORY

Keywords: representation theory, Lie algebra, binomial transform, algebraic residues, computer algebra, creative telescoping

We study the enumerative and analytic properties of some sequences constructed using tensor invariant theory. The octant sequences are constructed from the exceptional Lie group G 2 and the quadrant sequences from the special linear group SL(3). In each case we show that the corresponding sequences are related by binomial transforms. The first three octant sequences and the first four quadrant sequences are listed in the On-Line Encyclopedia of Integer Sequences (OEIS). These sequences all have interpretations as enumerating two-dimensional lattice walks but for the octant sequences the boundary conditions are unconventional. These sequences are all P-recursive and we give the corresponding recurrence relations. In all cases the associated differential operators are of third order and have the remarkable property that they can be solved to give closed formulae for the ordinary generating functions in terms of classical Gaussian hypergeometric functions. Moreover, we show that the octant sequences and the quadrant sequences are related by the branching rules for the inclusion of SL(3) in G 2 .

We study two families of sequences, each of them constructed using tensor invariant theory. The theory is summarised in §2. The first family contains the octant sequences. The first octant sequence is constructed from the seven-dimensional fundamental representation of the exceptional simple algebraic group G 2 . This sequence was studied initially by Kuperberg in [START_REF] Kuperberg | Spiders for rank 2 Lie algebras[END_REF] and subsequently by Westbury in [START_REF] Westbury | Enumeration of non-positive planar trivalent graphs[END_REF]. We will refer to this sequence as T 3 . The second family contains the quadrant sequences. The first quadrant sequence is constructed from the direct sum of the three-dimensional vector representation of SL(3) and its dual. The sequences are defined as the dimension of the subspace of invariant tensors in the tensor powers of the representation. In both cases we extend to a family of sequences by adding copies of the trivial representation to the initial representation. Combinatorially, it means that each family consists of the iterated binomial transforms of the first sequence.

The first three sequences of the octant family have entries in the On-Line Encyclopedia of Integer Sequences (OEIS). They are displayed in Figure 1. The sequence A059710 is the first octant sequence T 3 . To our knowledge, the sequence T 3 has not appeared previously in the combinatorics literature. In §3 we prove the following combinatorial interpretations of this sequence.

Theorem 1.1. The sequence T 3 enumerates:

• hesitating tableaux of height 2, empty shape, and no singleton;

• set partitions with no singleton and no enhanced 3-crossing;

• sequences (x 1 , x 2 , . . . , x n ) such that 1 x i < i with no weakly decreasing subsequence of length 3. These all follow from known combinatorial interpretations of the binomial transform of T 3 ; they are corollaries to Theorem 3.1 in §3.

The starting point for Theorem 1.1 is the interpretation of the sequences in the first family as lattice walks in the plane. This interpretation is used in [START_REF] Westbury | Enumeration of non-positive planar trivalent graphs[END_REF]. These lattice walks have six nonzero steps and one zero step corresponding to the seven weights of the representation. These walks are restricted to the region 0 y x. There is an additional constraint which is unusual from the standard theory of lattice walks, namely, that the zero step is forbidden on the line x = y.

Let E 3 be the second octant sequence A108307 in Figure 1. Using this interpretation, we have the following theorem.

Theorem 1.2. The sequence E 3 is the binomial transform of the sequence T 3 , i.e., for n ≥ 0,

E 3 (n) = n i=0 n i T 3 (i).
This result provides an unexpected connection between the invariant theory of G 2 and the combinatorics of set partitions.

In §3. [START_REF] Bonichon | Baxter permutations and plane bipolar orientations[END_REF] we study the ordinary generating functions of these sequences. First we derive the following recurrence relation for T 3 .

Theorem 1.3. The sequence T 3 is determined by the initial conditions T 3 (0) = 1, T 3 (1) = 0, T 3 (2) = 1 and the recurrence relation The recurrence relation in Theorem 1.3 was conjectured by Mihailovs [42, §3] and we give three independent proofs in §3. [START_REF] Bonichon | Baxter permutations and plane bipolar orientations[END_REF]. The corresponding linear differential equation, satisfied by the generating function T (t) = n≥0 T 3 (n)t n , can be solved to give a closed formula for T (t) in terms of the Gaussian hypergeometric function 2 F 1 . The differential equations and recurrence relations for the other two sequences in Figure 1 are derived in [START_REF] Bousquet | On partitions avoiding 3-crossings[END_REF] and closed formulae are given in the OEIS.

The first four sequences of the quadrant sequences also have entries in the OEIS; they are shown in Figure 2. The most well-known of these sequences is the third one, which enumerates Baxter permutations [START_REF] Baxter | On fixed points of the composite of commuting functions[END_REF].

These sequences also have interpretations as lattice walks. These walks are restricted to the quadrant 0 x, y. These are walks in six weights of the representation. This interpretation follows from the Pieri rule. For GL [START_REF] Bonichon | Baxter permutations and plane bipolar orientations[END_REF], representations are indexed by partitions with three rows. Then applying the Pieri rule gives:

V [1] ⊗ V λ ∼ = ⊕ µ V µ V [1,1] ⊗ V λ ∼ = ⊕ ν V ν
where the first sum is over all partitions µ obtained by adding a single box to λ and the second sum is over all partitions ν obtained by adding two boxes in different rows to λ. Then the restriction to SL(3) is given by mapping the partition [λ 1 , λ 2 , λ 3 ] to the lattice point in the plane (λ 1 -λ 2 , λ 2 -λ 3 ). The first sequence is studied in [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF], where it is defined in terms of lattice walks. The identification of the third sequence with the sequence enumerating Baxter permutations can be proved by several methods. One method is to show that they both satisfy the same recurrence relation and initial conditions. Another method is to prove that they both enumerate axis walks in the octant, using [START_REF] Courtiel | Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods[END_REF], [START_REF] Burrill | Tableau sequences, open diagrams, and Baxter families[END_REF], [START_REF] Burrill | A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape[END_REF] or our derivation utilizing branching rules. The fourth sequence was introduced by Marberg in [START_REF] Marberg | Crossings and nestings in colored set partitions[END_REF]. It is defined as the number of noncrossing 2-coloured set partitions; a lattice path interpretation is given in [START_REF] Marberg | Crossings and nestings in colored set partitions[END_REF], where a differential equation and a recurrence relation can also be found. The second sequence does not have a published reference, but it is known to enumerate a family of unlabelled graphs called planar st-graphs [START_REF] Cranch | Representing and enumerating two-dimensional pasting diagrams[END_REF]. We identify this sequence with the OEIS entry by giving a combinatorial interpretation and by showing that the binomial transform is the third sequence in §4. Moreover, the second and fourth sequences are both given by axis walks in the corresponding octant. The ordinary generating functions for these sequences are studied in §4.4. We give a recurrence relation for the k-th quadrant sequence, which includes k as a parameter. A closed formula for the generating function of the Baxter sequence is given in the OEIS without a reference. We give a different, but equivalent, closed formula.

These two families of (octant and quadrant) sequences are related since SL(3) is a maximal subgroup of G 2 . Furthermore, the restriction of the seven-dimensional fundamental representation is the direct sum of the two three-dimensional representations and one copy of the trivial representation. More generally, the restriction of the representation for the k-th sequence in octant family is the (k + 1)-st sequence in the quadrant family. It means that these two sequences are related by the branching rules for the inclusion of SL(3) in G 2 . It has been observed several times that the Baxter numbers enumerate walks which end on an axis and bijections which establish this are given in [START_REF] Burrill | Tableau sequences, open diagrams, and Baxter families[END_REF]Proposition 23], [START_REF] Courtiel | Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods[END_REF]Theorem 3], [START_REF] Sherry | Pattern-avoiding inversion sequences and open partition diagrams[END_REF]Theorem 1.2]. In the last section we give an interpretation of this result using representation theory. It gives a new proof that these sets are equinumerous but it is not bijective. However, this proof does extend the result. First, the analogous result relates the k-th quadrant sequence and the k-th octant sequence. It also follows combinatorially from the known result using the binomial transforms. Second, our proof also extends this result by giving an analogous result for walks ending at a point other than the origin. This is an expanded version of [START_REF] Bostan | On sequences associated to the invariant theory of rank two simple lie algebras[END_REF]. The abbreviated version was used in [START_REF] Scherer | A Criterion for Sharpness in Tree Enumeration and the Asymptotic Number of Triangulations in Kuperberg's G2 Spider[END_REF] to find the radius of convergence of sequence A060049 and proving [START_REF] Kuperberg | Spiders for rank 2 Lie algebras[END_REF]Conjecture 8.2].

Invariant theory

In this section we describe the way in which the representation theory of algebraic groups gives rise to combinatorially interesting sequences. For the basic notions in the theory of linear algebraic groups, the reader is invited to consult the book [START_REF] Fulton | Representation theory[END_REF].

Let G be a reductive complex algebraic group, i.e., G has a trivial unipotent radical. Let V λ be the irreducible representation of G with highest weight λ. Definition 2.1. Let V be a (finite-dimensional) representation of G and λ a dominant weight. The sequence associated to (G, V, λ), denoted a V,λ , is the sequence whose n-th term is the multiplicity of V λ in the tensor power ⊗ n V .

Our main interest is in the case λ = 0. In this case V λ is the trivial representation and the n-th term of the sequence a V,λ is the dimension of the subspace of invariant tensors in ⊗ n V . The sequence a V,0 is denoted by a V .

Example 2.2. The simplest example is to take G = SL(2) and V to be the two-dimensional defining representation. The odd terms of the sequence a V are zero and the even terms are the Catalan numbers

C n = 1 n+1 2n n .
It is very classical that the generating function for the sequence of Catalan numbers is algebraic. In our context, this can be seen as a special case of the following general result. Proposition 2.3. Take G = SL(2) and V to be any representation. Then the generating function of the sequence a V is algebraic.

Proof. The character χ(V ) of V is a Laurent polynomial in x invariant under x ↔ x -1 . Then the n-th term of the sequence a V is the constant term of the Laurent polynomial χ(V ) n (1 -x 2 ). Equivalently, the generating function of the sequence a V is the diagonal of the bivariate rational function x-x -1

1-tx χ(V ) . The result now follows by applying the Pólya-Furstenberg theorem [START_REF] Pólya | Sur les séries entières, dont la somme est une fonction algébrique[END_REF][START_REF] Furstenberg | Algebraic functions over finite fields[END_REF], see also [START_REF] Stanley | Enumerative combinatorics[END_REF]Theorem 6.3.3].

Next we discuss the case where V is a fundamental representation of a classical simple Lie algebra of rank two. These sequences have all been studied and are known to be P-recursive, or holonomic: they satisfy linear recurrences with polynomial coefficients (in the index n).

Example 2.4. Take G = SL(3) and V to be the three-dimensional defining representation. In the sequence a V every third term is nonzero and the other terms are zero. Taking every third term gives the sequence of three-dimensional Catalan numbers (A005789), whose n-th term is given by 2 (3n)!/(n! (n + 1)! (n + 2)!) and matches the number of standard tableaux of rectangular shape (n, n, n).

This can be seen as follows. Let V be the vector representation of GL(n). Then Schur-Weyl duality gives the decomposition of ⊗ r V as ⊕ λ S λ ⊗ V λ where λ is a partition of size r with at most n non-zero parts and S λ is an irreducible representation of the symmetric group on r points. There are several constructions (due to Young) of S λ , which take the vector space with basis the set of standard tableaux of shape λ and give an action of the symmetric group. Now restrict from GL(n) to SL(n). The restriction of the representation V λ is trivial if λ has rectangular shape and is non-trivial otherwise.

Example 2.5. Take G = Sp(4) of type C 2 and V to be the fourdimensional defining representation. Under the isomorphism Sp(4) ∼ = Spin(5), we see that V is the spin representation of the spin group Spin [START_REF] Bostan | Creative telescoping for rational functions using the Griffiths-Dwork method[END_REF]. The odd terms in the sequence a V are zero and the even terms are those of the sequence C n C n+2 -C 2 n+1 (A005700). This sequence counts 3-noncrossing perfect matchings on 2n points and also nested pairs of Dyck paths of length 2n.

The theory of Kashiwara crystals (see [START_REF] Malle | Linear algebraic groups and finite groups of Lie type[END_REF]Ch. 2], or [START_REF] Hong | Introduction to quantum groups and crystal bases[END_REF]Ch. 4]) gives combinatorial interpretations of these sequences. There is a crystal associated to each representation. The crystal associated to the irreducible representation V λ is denoted by C λ . These are the connected crystals. Crystals have a tensor product with the property that the crystal associated to the tensor product of representations is the tensor product of the crystals associated to the representations. The trivial crystal is C 0 and has one element. Moreover, the crystal associated to the direct sum of representations is the disjoint union of the crystals associated to the representations.

Let C be a crystal. The elements of ⊗ n C are words of length n in the elements of C. The analogue of the subspace of invariant tensors is the subset of invariant words in ⊗ n C.

The crystal version of Definition 2.1 is:

Definition 2.6. Let C be a (finite) crystal of G and λ a dominant weight. The sequence associated to (G, C, λ), denoted a C,λ , is the sequence whose n-th term is the multiplicity of the crystal C λ in the tensor power ⊗ n C.

Proposition 2.7. If C is the crystal of the representation V then a C,λ = a V,λ for all dominant weights λ.

In this paper we only apply this to the sum of the two fundamental representations of SL(3) and to the seven-dimensional fundamental representation of G 2 . For the fundamental representations of SL(3) this follows from classical results by interpreting a standard or semistandard tableau as a sequence of partitions. For the G 2 case this result has been used in [START_REF] Kuperberg | Spiders for rank 2 Lie algebras[END_REF] and [START_REF] Westbury | Enumeration of non-positive planar trivalent graphs[END_REF]. We give an outline of the general case which is an application of the tensor product rule for crystals. This is [START_REF] Grabiner | Random walks in Weyl chambers and the decomposition of tensor powers[END_REF]Theorem 2].

Proof. A tensor product of highest weight representations has a canonical vector space decomposition as

V λ ⊗ V µ ∼ = ⊕ ν A ν λ,µ ⊗ V ν .
Similarly the tensor product of crystals has a set decomposition

C λ ⊗ C µ ∼ = ν B ν λ,µ ⊗ C ν .
The decomposition rule of [START_REF] Littelmann | A littlewood-richardson rule for symmetrizable kac-moody algebras[END_REF] asserts that dim A ν λ,µ = |B ν λ,µ |. Then the n-th terms of the two sequences are equal. This is proved by induction on n using the above for the inductive step.

Binomial transform.

In this subsection we recall some basic properties of the binomial transform. Identities associated to the binomial transform are given for instance in [START_REF] Khristo | Notes on the binomial transform[END_REF].

The binomial transform operator is denoted by B. This is a linear operator acting on sequences. Given the sequence a with n-th term a(n), the binomial transform of a is the sequence, denoted Ba, whose n-th term is

n i=0 n i a(i).
Binomial transforms arise naturally for sequences associated to the representations of reductive complex algebraic groups.

Lemma 2.8. Assume that a V,λ is the sequence associated to (G, V, λ) as specified in Definition 2.1. Then a V ⊕C,λ = Ba V,λ .

Proof. Expanding the tensor product gives

⊗ n (V ⊕ C) ∼ = ⊕ n i=0 C ( n i ) ⊗ (⊗ i V
). This can be proved by induction on n as in the binomial theorem. Now comparing invariant tensors on both sides gives the result.

The binomial transform also arises naturally for lattice walks restricted to a domain. Lemma 2.9. Assume that a sequence a enumerates walks in a lattice, confined to a domain D, using a set of steps S. Then Ba is given by adding a new step corresponding to the zero element of the lattice; that is, S is replaced by the disjoint union S {0} without changing the domain.

Proof. A path of length n with steps S {0} has i steps S and j steps 0 with i + j = n. Taking the steps in S and ignoring the 0 steps gives a path of length i in S. Each path of length i in S appears n j times corresponding to the partitions of a set of size n into two disjoint subsets of size i and j.

The following is a corollary to both Lemma 2.8 and Lemma 2.9.

Corollary 2.10. Assume that a C,λ is the sequence associated to (G, C, λ) as specified in Definition 2.6. Let * be the trivial crystal. Then

a C * = Ba C,λ .
We can also consider iterations of the binomial transform.

Lemma 2.11. Given the sequence a with n-th term a(n). For k ∈ Z, the k-th binomial transform of a is given by

(B k a)(n) = n i=0 k n-i n i a(i) for each n ∈ N.
The binomial transform can also be regarded as an operator on the generating function of a sequence. Let G(t) = ∞ n=0 a(n)t n be the generating function of the sequence a. We denote the generating function of B k a by B k G. Then we have the following immediate lemma. Lemma 2.12. For k ∈ Z, the k-th binomial transform of G(t) is

(B k G)(t) = 1 1 -k t G t 1 -k t .

Octant sequences

In this section we consider a sequence associated to the representation theory of the exceptional simple algebraic group G 2 by the construction in Definition 2.1. Then we relate this sequence and its binomial transforms to known sequences of hesitating tableaux of height 2 and vacillating tableaux of height 2. These were introduced in [START_REF] William | Crossings and nestings of matchings and partitions[END_REF].

The algebraic group G 2 has dimension 14 and rank 2. It can be constructed as the automorphism group of the (complex) octonions. By construction, the octonions are then an eight-dimensional representation of G 2 . The unit spans a one-dimensional invariant subspace and the imaginary octonions are an invariant complementary subspace. This seven-dimensional representation of G 2 is a fundamental representation. Lecture 22]) is shown in Figure 3 with the fundamental chamber shaded. The two simple roots are α and β with α short and β long. The two fundamental weights are λ and θ. The highest weight representation with highest weight λ is the seven-dimensional representation we are interested in. The highest weight representation with highest weight θ is the adjoint representation, so θ is the highest root.

β α λ θ Figure 3. G 2 root system 3.1. Root systems. The root system of G 2 (see [20,
These are related by

λ = 2 α + β, θ = 3 α + 2 β.
The element ρ is defined in terms of the roots as half the sum of the positive roots. The six positive roots are

α, β, α + β, 2 α + β, 3 α + β, 3 α + 2 β.
This gives ρ = 5 α + 3 β.

The element ρ is also defined in terms of the weights as the sum of the fundamental weights. This gives ρ = λ + θ.

Lattice walks.

In this subsection, we give a combinatorial proof of Theorem 1.2. Let G be G 2 , let V be the seven-dimensional fundamental representation, and C be the associated crystal. We now apply the general theory of §2 to this case.

The highest weight words in tensor powers of C correspond to lattice walks in the weight lattice of G 2 restricted to the dominant chamber. These lattice walks are studied by Kuperberg [START_REF] Kuperberg | Spiders for rank 2 Lie algebras[END_REF] and by Westbury [START_REF] Westbury | Enumeration of non-positive planar trivalent graphs[END_REF]. Since V has dimension 7, C has cardinality 7, and the seven steps are shown in Figure 4, where the coordinates are with respect to the basis of fundamental weights. One can make it more explicit by taking the

(1,0) (-1,1) (-2,1) (-1,0) (1,-1) (2,-1) (0,0) Figure 4.
Steps in weight lattice

(1,0) (0,1) (-1,1) (-1,0) (0,-1) (1,-1) (0,0) Figure 5.
Steps in octant intersection of the Euclidean lattice in three-dimensional space with the plane x + y + z = 0. Then, we can take the short simple root α = (0, 1, -1), the long simple root β = (1, -2, 1), the fundamental weight λ = (1, 0, -1), and the fundamental weight θ = (2, -1, -1).

The highest weight words correspond with these steps, restricted to the dominant chamber and with the extra condition that the step (0, 0) is not permitted at a weight (0, k) for k 0.

A hesitating tableau of semilength n is a walk in the Young lattice with n steps. Each step is one of the following pairs of moves on the Young lattice:

• do nothing, add a cell • remove a cell, do nothing • add a cell, remove a cell The shape is the final partition.

A hesitating tableau of height h is a hesitating tableau such that every partition in the sequence has height at most h.

There is a lattice walk interpretation of hesitating tableaux of height 2 given by Bousquet-Mélou and Xin in [START_REF] Bousquet | On partitions avoiding 3-crossings[END_REF].

A hesitating tableau of height 2 can be interpreted as a walk in Z 2 by identifying partitions with at most two nonzero rows with the set

{(x, y) ∈ Z 2 |x y 0}.
There are 8 steps which are shown in Figure 5. There are eight steps since there are:

• two ways to do nothing then add a cell,

• two ways to remove a cell then do nothing • four ways to remove a cell then add a cell Two of the four ways to remove a cell then add a cell give the step (0, 0), namely add a cell on the first row then remove this cell and add a cell on the second row then remove this cell. It is always allowed to add and then remove a cell on the first row. The step which adds and removes a cell on the second row is not permitted on the line x = y.

Proof of Theorem 1.2. We compare the two descriptions of the walks. The steps of the walks for the sequence T 3 are shown in Figure 4 and the steps of the walks for the sequence E 3 are shown in Figure 5.

In order to compare these, we first make the change of coordinates (x, y) → (x + y, x), which maps the steps from Figure 4 to those of Figure 5. This identifies the six non-zero steps, as well as the two domains.

By Lemma 2.9, it remains to compare the zero steps. There is one zero step in the T 3 case and two in the E 3 case. In the E 3 case we have the zero step which adds and then removes a cell on the second row. The boundary condition is that this step is not allowed on the line x = y. After the change of coordinates, this is the same boundary condition as the zero step in the T 3 case. The second zero step in the E 3 case adds and then removes a cell in the first row. This is always allowed.

Theorem 3.1. For each n 0 and r, s 0 there is a correspondence between highest weight words of weight (r, s) and length n in the crystal C * and hesitating tableaux of height 2, semilength n and shape (r + s, s).

Proof. The proof is the observation that the two descriptions of the lattice walks agree under a simple change of coordinates. The point (r, s) in the weight lattice is dominant if r, s 0. This point corresponds to the two part partition (r + s, s).

It is straightforward to check that under this change of coordinates, the eight steps correspond, the two domains correspond, and the extra condition on a step of weight (0, 0) also corresponds.

There is a variation of Theorem 3.1 for vacillating tableaux. A vacillating tableau of semilength n is an excursion in the Young lattice with n steps. Each step is one of the following pairs of moves on the Young lattice:

• do nothing twice • do nothing, add a cell

j 1 i 1 j 2 i 2 j 3 i 3 i 3 = j 1 i 1 j 2 i 2 j 3
Figure 6. A 3-crossing and an enhanced 3-crossing

• remove a cell, do nothing • remove a cell, add a cell A vacillating tableau of height h is a vacillating tableau such that every partition in the sequence has height at most h.

There is a lattice walk interpretation of vacillating tableaux of height 2 also given in [START_REF] Bousquet | On partitions avoiding 3-crossings[END_REF]. There are nine steps since there are six steps which change the shape and three steps which leave the shape unaltered.

Vacillating tableaux were introduced in [START_REF] William | Crossings and nestings of matchings and partitions[END_REF] in the context of set partitions. A set partition will mean a partition of the ordered set

[n] = {1, 2, . . . , n} into non-empty pairwise disjoint subsets. The standard representation of a set partition is a graph with vertex set [n]. The edges are arcs connecting pairs of elements in a block which are adjacent in the numerical order on the block.

A singleton in a set partition is a block with one element. A k-crossing in a set partition is a k-subset of arcs, (i 1 , j 1 ), . . . , (i k , j k ) such that

i 1 < i 2 • • • < i k < j 1 < j 2 • • • < j k
An enhanced k-crossing in a set partition is a k-subset of arcs, (i 1 , j 1 ), . . . , (i k , j k ) such that

i 1 < i 2 • • • < i k j 1 < j 2 • • • < j k Theorem 3.2.
For each n 0 and r, s 0 there is a correspondence between highest weight words of weight (r, s) and length n in the crystal C * * and vacillating tableaux of height 2, semilength n and shape (r + s, s).

Proof. The proof is essentially the same as the proof of Theorem 3.1.

The main innovation in [START_REF] William | Crossings and nestings of matchings and partitions[END_REF] is the construction of a bijection between set partitions of [n] and vacillating tableaux of semilength n and empty shape. The set partition has a k-crossing if and only if some partition in the vacillating tableau has length at least k. In particular, for k = 3, this is a bijection between 3-noncrossing set partitions and vacillating tableaux of height 2 and empty shape.

There is a correspondence between hesitating tableaux of semilength n, empty shape and height h and set partitions of n with no enhanced h + 1-crossing. This is proved by Lin in [START_REF] Lin | Restricted inversion sequences and enhanced 3-noncrossing partitions[END_REF] and by Marberg in [37, Proposition 5.8]. In [START_REF] Gil | A simple bijection for enhanced, classical, and 2-distant k-noncrossing partitions[END_REF] the sequence A108307 is called NC 0,3 , the sequence A108304 is called NC 1,3 ; the binomial transform relation between them is given in [START_REF] Lin | Restricted inversion sequences and enhanced 3-noncrossing partitions[END_REF][START_REF] Gil | A simple bijection for enhanced, classical, and 2-distant k-noncrossing partitions[END_REF].

A corollary is that there is a correspondence between invariant words of length n in C and set partitions of [n] with no singleton and no enhanced 3-crossing.

There is another combinatorial interpretation based on [START_REF] Sherry | Ascent sequences and 3-nonnesting set partitions[END_REF] and [START_REF] Lin | Restricted inversion sequences and enhanced 3-noncrossing partitions[END_REF].

Definition 3.3. An inversion sequence of length n is a sequence (x 1 , x 2 , . . . , x n ) such that 1 x i i.
A singleton in the inversion sequence (x 1 , x 2 , . . . , x n ) is an i ∈ [n] such that x i = i. Proposition 3.4. For n 0 there is a bijection between set partitions of [n] with no enhanced 3-crossing and no singletons and inversion sequences of length n with no weakly decreasing subsequence of length 3 and no singletons.

Proof. There is a bijection in [START_REF] Sherry | Ascent sequences and 3-nonnesting set partitions[END_REF] between set partitions of [n] with no enhanced 3-crossing and inversion sequences of length n with no weakly decreasing subsequence of length 3. This bijection preserves singletons.

3.3. Algebra. In this subsection, we give three proofs of Theorem 1.3, with different flavors. The first two proofs utilize Theorem 1.2 and a result of Bousquet-Mélou and Xin [START_REF] Bousquet | On partitions avoiding 3-crossings[END_REF] on partitions that avoid 3crossings. The last one is a direct proof which relies on the connection with G 2 walks.

The first proof is based on Theorem 1.2, on Proposition 2 in [START_REF] Bousquet | On partitions avoiding 3-crossings[END_REF] and on the method of creative telescoping [START_REF] Zeilberger | The method of creative telescoping[END_REF][START_REF] Koutschan | Advanced applications of the holonomic systems approach[END_REF] for the summation of (bivariate) holonomic sequences. Proposition 3.5. [9, Proposition 2] The number E 3 (n) of partitions of [n] having no enhanced 3-crossing is given by E 3 (0) = E 3 (1) = 1, and for n ≥ 0, (2) 8 (n + 3) (n + 1) E 3 (n) + 7n 2 + 53n + 88 E 3 (n + 1)

-(n + 8) (n + 7) E 3 (n + 2) = 0.
Equivalently, the associated generating function

E(t) = n≥0 E 3 (n)t n satisfies t 2 (1 + t) (1 -8t) d 2 dt 2 E(t) + 2t 6 -23t -20t 2 d dt E(t) + 6 5 -7t -4t 2 E(t) -30 = 0.
First Proof of Theorem 1.3. By Theorem 1.2, we have

T 3 (n) = n k=0 (-1) n-k n k E 3 (k). Set f (n, k) = (-1) n-k n k E 3 (k)
. By Proposition 3.5, and by the closure properties for holonomic functions, it follows that f (n, k) is holonomic. Thus, we can apply Chyzak's algorithm [START_REF] Koutschan | Advanced applications of the holonomic systems approach[END_REF] for creative telescoping to derive a recurrence relation for T 3 . In particular, using Koutschan's Mathematica package HolonomicFunctions.m [START_REF] Koutschan | holonomicfunctions (user's guide)[END_REF] that implements Chyzak's algorithm, we find exactly the recurrence equation in Theorem 1.3.

The detailed calculation involved in the above proof can be found in [START_REF] Bostan | Supplementary electronic material to the article "on sequences associated to invariant theory[END_REF].

The second proof is also based on Proposition 3.5 and on Theorem 1.2, namely on the relation between the generating functions of T 3 (n) and of E 3 (n) implied by Theorem 1.2.

Second Proof of Theorem 1.3. Let T (t) = n≥0 T 3 (n)t n
. By Theorem 1.2 and Lemma 2.12,

T (t) = 1 1 + t • E t 1 + t .
We know from Proposition 3.5 a differential equation for E (t). By (univariate) closure properties of D-finite functions, we deduce a differential equation for T (t), and convert it into a linear recurrence for T 3 (n), which is exactly the recurrence in Theorem 1.3.

Let G be a reductive complex algebraic group and V be a representation of G. If G is connected then the sequence a V associated to (G, V ) can sometimes be written as an algebraic residue. The general principle is discussed by Gessel and Zeilberger in [START_REF] Gessel | Random walk in a Weyl chamber[END_REF] and in detail by Grabiner and Magyar in [START_REF] Grabiner | Random walks in Weyl chambers and the decomposition of tensor powers[END_REF].

Let K be the character of V and let ∆ be given by

∆ = w∈W ε(w) [w(ρ) -ρ] .
Here W is the Weyl group, ε : W → {±1} is the sign character and ρ is half the sum of the positive roots. These are both elements of the group ring of the root lattice of G. If we choose a basis of the root lattice then these become Laurent polynomials where the number of indeterminates is the rank of G.

For the representations that appear in this paper, the n-th term of the sequence a V is the constant term in the Laurent polynomial ∆ K n and the generating function is the algebraic residue of the rational function ∆/(xy -txyK).

Example 3.6. In Example 2.2, the Laurent polynomials are

∆ = (1 -x -2 ), K = (x -x -1 ).
Then the constant term of the Laurent polynomial

(1 -x -2 )(x -x -1 ) 2n is 2n n - 2n n + 2 ,
which is a well known expression for the n-th Catalan number C n . This can be proved directly using the reflection principle.

It is a general result that an algebraic residue is D-finite, see [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF]. This shows that the generating functions of these sequences are D-finite and hence the sequences are P-recursive.

The third proof of Theorem 1.3 relies on G 2 walks and the method in [START_REF] Bostan | Hypergeometric expressions for generating functions of walks with small steps in the quarter plane[END_REF].

The following definition is given in [START_REF] Kuperberg | The quantum G 2 link invariant[END_REF] in the paragraph following Conjecture 3.3. Definition 3.7. The n-th term T 3 (n) is the constant term of the Laurent polynomial ∆ K n , where

K = 1 + x + y + x y + x -1 + y -1 + (xy) -1 ,
and ∆ is the Laurent polynomial

∆ = x -2 y -3 (x 2 y 3 -xy 3 + x -1 y 2 -x -2 y + x -3 y -1 -x -3 y -2 + x -2 y -3 -x -1 y -3 + xy -2 -x 2 y -1 + x 3 y -x 3 y 2 ).
Third Proof of Theorem 1.3. Let T (t) = n≥0 T 3 (n)t n . By Definition 3.7, T (t) is the constant coefficient [x 0 y 0 ] of ∆/(1 -tK). In other words, T (t) is equal to the algebraic residue of ∆/(xy -txyK), and thus it is D-finite [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF] and is annihilated by a linear differential operator that cancels the contour integral of ∆/(xy -txyK) over a cycle. Using the integration algorithm for multivariate rational functions in [START_REF] Bostan | Creative telescoping for rational functions using the Griffiths-Dwork method[END_REF] we compute the following operator of order 6, that cancels T (t): Clearly, the operator L 1 has a basis of solutions formed of {P/t 5 }. Let {f 1 , f 2 } be a basis of solutions of L 2 . Then one can show that the solution T (t) of L 3 is

L 6 = t 5 (t + 1) (7 t -1) (2 t + 1) 2 ∂ 6 + 3 t 4 (2 t
P t 5 • (C 1 f 1 + C 2 f 2 ) t 5 P dt,
for some constants C 1 and C 2 to be determined.

Using algorithms for solving second order differential equations, as described in [START_REF] Bostan | Hypergeometric expressions for generating functions of walks with small steps in the quarter plane[END_REF], one deduces that f 1 and f 2 have hypergeometric expressions. After identifying the constants C 1 and C 2 , we derive the following explicit formula for T (t). Define the polynomials: (1 -t) 3 .

S = (7 t -1) (t + 1) (2 t + 1)
Then the generating function T (t) is equal to

P 30 t 5 S P 2 (t -1) 2 U 2 F 1 1 3 2 3 1 ; φ + V (1 -t) 3 2 F 1 4 3 5 3

2

; φ dt.

Note that the above indefinite integrals have no constant term. This expression can be further simplified by introducing the additional rational functions Then the simpler expression for T (t) is

R 1 = (t + 1)
T (t) = 1 30 t 5 R 1 • 2 F 1 1 3 2 3 2 ; φ + R 2 • 2 F 1 2 3 4 3 3 ; φ + 5 P .
Following the approach in [4, §3.3], one can obtain an alternative expression for T (t) by using an approach with a more geometric flavor. The key point is that the denominator of W/(xy -txyK) is a family of elliptic curves, thus integrating W/(xy -txyK) over a small torus amounts to computing the periods of the two forms (of the first and second kind). Working out the details, this approach yields an expression for T (t) in terms of the Weierstrass invariant g 2 = (t -1) 25 t 3 + 21 t 2 + 3 t -1 and of the j-invariant J = (t -1) 3 (25 t 3 + 21 t 2 + 3 t -1) of our family of curves. As in [START_REF] Bostan | Hypergeometric expressions for generating functions of walks with small steps in the quarter plane[END_REF], we introduce the expression Moreover, one can use the methods in [START_REF] Bostan | Hypergeometric expressions for generating functions of walks with small steps in the quarter plane[END_REF] to deduce that the generating function T (t) is a transcendental power series and that the asymptotic behavior of its n-th coefficient T 3 (n) is

H(t) = 1 g 2 1/4
T 3 (n) ∼ C • 7 n n 7
, where C = 4117715 864

√ 3 π ≈ 2627.6.

Quadrant sequences

In this section we consider a family of sequences associated to the representation theory of the simple algebraic group SL(3) by the construction Definition 2.1. The algebraic group SL(3) has dimension 8 and rank 2. Let V be the three-dimensional vector representation and V * be the dual representation. These are the two fundamental representations of SL(3). By Lemma 2.8, those sequences are also related by binomial transforms.

By the general theory in Proposition 2.7 these sequences enumerate walks in the weight lattice of SL(3). Equivalently, these are walks in the positive quadrant which is our reason for calling them quadrant sequences.

The n-th term of the sequence S 0 enumerates A 2 -webs with n boundary points, see [START_REF] Kuperberg | Spiders for rank 2 Lie algebras[END_REF]. If we use the representation theory of GL(3) (instead of SL( 3)) then we can translate this to a combinatorial interpretation in terms of rectangular semistandard tableaux with three rows.

Let SST(λ; α) be the set of semistandard tableaux of shape λ and weight α. Here λ is a partition, α is a composition and |λ| = |α|. Proposition 4.2. The first three quadrant sequences have the following interpretations in terms of rectangular semistandard tableaux.

(1) The n-th term of the sequence S 0 is the number of rectangular semistandard tableaux with three rows whose weight, α, is a composition of length n such that α i ∈ {1, 2} for 1 i n.

(2) The n-th term of the sequence S 1 is the number of rectangular semistandard tableaux with three rows whose weight, α, is a composition of length n such that α i ∈ {0, 1, 2} for 1 i n.

(3) The n-th term of the sequence S 1 is the number of rectangular semistandard tableaux with three rows whose weight, α, is a composition of length n such that α i ∈ {1, 2, 3} for 1 i n. (4) The n-th term of the sequence S 2 is the number of rectangular semistandard tableaux with three rows whose weight, α, is a composition of length n such that α i ∈ {0, 1, 2, 3} for 1 i n.

Proof. There are easy bijections with the respective walks. A semistandard tableaux can be regarded as a sequence of partitions where the i-th partition is the shape given by taking the cells whose entry is at most i. For a semistandard tableau with (at most) three rows this gives a sequence of vectors (λ 1 , λ 2 , λ 3 ) such that λ 1 λ 2 λ 3 0. Each such vector maps to the point (λ 1 -λ 2 , λ 2 -λ 3 ). This constructs a map from semistandard tableaux with three rows to walks in the two-dimensional lattice which stay in the non-negative quadrant. This map gives all bijections.

Proposition 4.3. The first three quadrant sequences have the following expressions.

(1) The n-th term of the sequence S 0 is

m 0 a,b,c 0 a+b=n a+2b=3m n a, b SST(3 m ; 1 a 2 b ) (2) The n-th term of the sequence S 1 is m 0 a,b,c 0 a+b+c=n b+2c=3m n a, b, c SST(3 m ; 0 a 1 b 2 c ) (3) The n-th term of the sequence S 1 is m 0 a,b,c 0 a+b+c=n a+2b+3c=3m n a, b, c SST(3 m ; 1 a 2 b 3 c ) (4) The n-th term of the sequence S 2 is m 0 a,b,c,d 0 a+b+c=n b+2c+3d=3m n a, b, c, d SST(3 m ; 1 b 2 c 3 d )
Proof. These follow directly from Proposition 4.2 together with the result that |SST(λ;

α)| = |SST(λ; α ′ )| if α ′ is a reordering of α.
Note that it is clear from these expressions that S 1 is the binomial transform of S 0 and that S 2 is the binomial transform of S 1 . This uses the observation that SST(3 m ; 1 a 2 b ) = SST(3 m+c ; 1 a 2 b 3 c ) for all a, b, c, m 0 such that a + 2b = m. Theorem 4.4. The quadrant sequences S 0 , S 1 , S 2 , S 3 are identical to the sequences in the second family specified in Figure 2.

Proof. The sequence S 0 appears as sequence A151366. This sequence is defined in [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF] using lattice walks.

The sequence S 1 appears as sequence A236408. There is no published reference for this sequence and we discuss this sequence in § 4.2 below.

The sequence S 2 appears as sequence A001181. This is the sequence of Baxter permutations. These two sequences can be seen to be the same by noting that Proposition 4.3 together with the known formula for the number of rectangular partitions agrees with the formula in [START_REF] Fan | The number of Baxter permutations[END_REF] for the number of Baxter permutations. Alternatively one can check that both sequences satisfy the same recurrence relation and initial conditions. A bijective proof is given by noting that there is an easy bijection using the combinatorial interpretation in Proposition 4.2 and [18, Theorem 2]. Alternative proofs are given in [START_REF] Burrill | Tableau sequences, open diagrams, and Baxter families[END_REF]Proposition 23], and [START_REF] Courtiel | Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods[END_REF]Theorem 3].

The sequence S 3 appears as sequence A216947. This sequence is defined in [START_REF] Marberg | Crossings and nestings in colored set partitions[END_REF] using 2-colored noncrossing set partitions. This paper also gives an easy bijection with the lattice paths. Definition 2.1 generalises to give sequences a V ⊕V * ⊕k C,λ . Here λ = (r, s) for r, s 0 and the sequence enumerates lattice walks which start at (0, 0) and end at (r, s).

4.1. Root systems. The root system of SL(3) is shown in Figure 7 with the fundamental chamber shaded. The two simple roots are α and α ′ . The two fundamental weights are λ and λ ′ . The fundamental representations are the three-dimensional vector representation and its dual.

The element ρ is

ρ = α + α ′ = λ + λ ′ .
All four entries in the OEIS give a recurrence relation for each quadrant sequence. These recurrence relations all agree with, or are consequences of, the recurrence relations in §4.4. If the recurrence relation in the OEIS has a proof then we can check that the initial terms agree and so we have an alternative proof that the two sequences agree. If the recurrence relation in the OEIS is conjectural then our results prove that these recurrence relations are satisfied by the sequence.

As a consequence of the identification of S 2 with the Baxter sequence we can give a formula for the terms of S k . This formula is obtained by

α ′ α λ λ ′ Figure 7
. A 2 root system substituting the formula (1) in [START_REF] Fan | The number of Baxter permutations[END_REF] for the terms in the Baxter sequence into the formula in Lemma 2.11 for iterated binomial transforms.

Other known results that are consequences are: A bijective proof of the following is given in [START_REF] Burrill | Tableau sequences, open diagrams, and Baxter families[END_REF]Proposition 23] and [START_REF] Courtiel | Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods[END_REF]Theorem 3], and in a recent paper by Yan [START_REF] Sherry | Bijections for inversion sequences, ascent sequences and 3nonnesting set partitions[END_REF]. 4.2. Increasing maps. In this subsection we give a combinatorial interpretation of the sequence S 1 . This depends on the closely related combinatorial interpretations of the Baxter sequence in [START_REF] Ackerman | A bijection between permutations and floorplans, and its applications[END_REF] (mosaic floor plans), [START_REF] Bonichon | Baxter permutations and plane bipolar orientations[END_REF] (plane bipolar orientations), and [START_REF] Law | The hopf algebra of diagonal rectangulations[END_REF] (diagonal rectangulations). All three of these interpretations are equivalent to oriented st-maps.

A map is a connected graph embedded in the plane with no edgecrossings, considered up to isotopy. The vertices and edges of the map are those of the graph. The faces of the map are the connected components of the complement of the graph in the plane. The outer face is unbounded, the inner faces are bounded.

An oriented map is a map together with an orientation of each edge. An oriented map is an st-map if it has a unique source, s, and a unique sink, t, both on the outer face.

An increasing map is an oriented map together with an increasing labelling of the vertices. If the map has r vertices then the labelling, ℓ, is a bijection between the vertices and the set {1, 2, . . . , r}. A labelling is increasing if whenever there is a directed path from vertex v to vertex w then ℓ(v) < ℓ(w). Let O be an increasing st-map. Then ℓ(s) = 1 and ℓ(t) = r.

A simple increasing st-map is a increasing st-map whose underlying graph has no multiple edges. Proposition 4.7. Let a(n) be the number of increasing st-maps with n edges and let a S (n) be the number of simple increasing st-maps with n edges. Then

a(n + 1) = n k=0 n k a S (k + 1)
Proof. There is a bijection between simple increasing st-maps with each edge labelled by a positive integer and increasing st-maps since we can replace each edge labelled by m with m copies of the same edge. This is a bijection between increasing st-maps with n edges and pairs consisting of a simple increasing st-map with k edges and a labelling of the edges by positive integers whose sum is n. The result follows from the observation that the number of sequences of positive integers of length k with sum n is n+1 k+1 .

One corollary of Proposition 4.7 is that the conjectured recurrence relation for A236408 is correct.

Plane bipolar orientations arise in the unpublished notes by James Cranch, Pasting Diagrams, as the morphisms in a strict monoidal category.

First we construct the category. The set of objects is N so we have an object [n] for each n ∈ N. Let O be an oriented st-map. One of the oriented paths going from s to t has the outer face on its right: this path is the right border of O, and its length is the right outer degree of O. The left border and left outer degree is defined similarly. An oriented st-map, O, is a morphism [l] → [r] where l is the left outer degree of O and r is the right outer degree. Composition of O and O ′ is only defined if the right outer degree of O is the left outer degree of O ′ . In this case, the composite O • O ′ is the oriented st-map given by identifying the right border of O with the left border of O ′ . The identity morphism of [n] is a path with n edges.

This category has a tensor product. On objects this is just [n] ⊗ [m] = [n + m] so the monoid of objects is N. The tensor product O ⊗ O ′ is always defined and is the plane bipolar orientation given by identifying the sink of O with the source of O ′ . It is straightforward to check that this tensor product is strictly associative and that these are compatible in the sense that they satisfy the interchange condition

(O • O ′ ) ⊗(P • P ′ ) = (O ⊗P ) • (O ′ ⊗P ′ ).
Hence this is a strict monoidal category, P. Simple plane bipolar orientations are the morphisms of a strict monoidal subcategory, P S .

The monoidal category P is the free strict monoidal category whose monoid of objects is N with a morphism α(n, m) : [n] → [m] for n, m > 0. The monoidal subcategory P S is the free strict monoidal category whose monoid of objects is N with a morphism α(n, m) : [n] → [m] for n, m > 0 with α(1, 1) omitted. The morphism α(n, m) consists of a single inner face with n edges on the left border and m edges on the right border.

Branching rules.

In this subsection we use the branching rules for the inclusion of SL(3) in G 2 to relate the two families of sequences.

The interpretation using invariant theory gives a connection between the octant sequences and the quadrant sequences. This uses the fact that SL(3) is a subgroup of G 2 , in fact, a maximal subgroup. Then the restriction of the representation V ⊕ kC from G 2 to SL(3) is the representation V ⊕ V * ⊕ (k + 1)C. This implies that each quadrant sequence a V ⊕k C,λ can be written as a linear combination of the octant sequences a V ⊕k C,µ with coefficients which are independent of k. These coefficients are the branching rules for the inclusion of SL(3) in G 2 . A combinatorial description of the branching rules for the inclusion

SL(3) → G 2
is given in [START_REF] King | The evaluation of weight multiplicities of G 2[END_REF] and [START_REF] Richter | Splints of classical root systems[END_REF].

A special case of this is the result that walks in the quadrant which end at (0, 0) correspond to walks in the octant which end on the x-axis, see [START_REF] Burrill | Tableau sequences, open diagrams, and Baxter families[END_REF], [START_REF] Courtiel | Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods[END_REF], [START_REF] Burrill | Tableau sequences, open diagrams, and Baxter families[END_REF], [START_REF] Burrill | A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape[END_REF], [START_REF] Sherry | Pattern-avoiding inversion sequences and open partition diagrams[END_REF].

The generating function for the branching rules for the inclusion of the maximal subgroup SL(3) → G 2 are given by Gaskell and Sharp in [22, (2.3)]. Let V (r, s) be a highest weight representation of G 2 with highest weight (r, s) and let U(p, q) be a highest weight representation of SL(3) with highest weight (p, q). Denote the multiplicity of U(p, q) in the restriction of V (r, s) to SL(3) by m (r,s) (p,q) . Proposition 4.8. The generating function r,s,p,q 0 m (r,s) (p,q) x p y q X r Y s is the rational function

(4) (1 -X) -1 -xyY (1 -xyY ) -1 (1 -x X)(1 -y X)(1 -x Y )(1 -y Y )
Theorem 4.9. Let V be a representation of G 2 and V ↓ the restriction to SL(3). Then the number of axis-walks of length n for V is the number of excursions for V ↓.

Proof. Putting x = 0, y = 0 in the generating function (4) gives r,s,p,q 0 m (r,s) (0,0) X r Y s . Putting x = 0, y = 0 in the rational function gives (1 -X) -1 . This shows that m (r,s) (0,0) = 1 if s = 0, 0 otherwise. Example 4.10. First we extend each octant sequence to a sequence of functions on the dominant weights of G 2 , or, equivalently, on the octant y 0, x y. It follows from Lemma 2.11 that these can be written as polynomials in k.

Then the octant sequences are given by

1 k 1 1 1 + k 2 1 + 2 k 1 2 + 2 k 2 1 + 3 k + k 3 4 + 3 k + 3 k 2 3 + 3 k 1
Then summing the entries on the bottom row gives the sequence

1, 1 + k, 3 + 2 k + k 2 , 9 + 9 k + 3 k 2 + k 3 .
This proves Proposition 4.5 and Proposition 4.6.

≥ 0. Then G k is the constant coefficient [x 0 y 0 ] of W/(1 -tK), where (5)
K = k + x + y + x -1 + y -1 + x y + y x and (6) W = 1 - x 2 y + x 3 -x 2 y 2 + y 3 - y 2 x .
Let C 2 (n) be the n-th term of the sequence A216947 in the second family. Marberg [START_REF] Marberg | Crossings and nestings in colored set partitions[END_REF]Theorem 1.7] showed that C 2 (n) is the constant term [x 0 y 0 ] of W Kn , where K = K| k=3 , the Laurent polynomials K and W are specified in [START_REF] Bostan | Creative telescoping for rational functions using the Griffiths-Dwork method[END_REF] and [START_REF] Bostan | On sequences associated to the invariant theory of rank two simple lie algebras[END_REF]. By Lemma 4.11, the sequence S 3 is identical to the sequence A216947. Therefore, we have: dt 4 G 3 (t) = 0. Next, for k = 0, 1, 2, 3, we prove a uniform recurrence equation for the sequence S k . It is given by a single formula with k as a parameter. Moreover, we show that S 0 , S 1 , S 2 , S 3 are identical to the sequences in the second family. Theorem 4.13. For k = 0, 1, 2, 3, the n-th term a(n) of the sequence S k satisfies the following recurrence equation: Proof. By Lemma 2.8, sequences S 2 , S 1 , S 0 are the first, second, and third inverse binomial transforms of S 3 , respectively. Thus, it follows from Lemma 2.12 that the generating function of S k is

G k (t) = 1 1 + (3 -k)t • G 3 t 1 + (3 -k)t
for k = 0, 1, 2, 3, where G 3 (t) is the generating function of S 3 . Regarding k as a parameter in the above expression, we deduce the differential equation for G k (t) by using Proposition 4.12 and closure properties of D-finite functions. By converting the differential equation for G k (t), we get the corresponding recurrence equation for the sequence a(n), which is exactly the recurrence equation in the claim.

The argument of [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF]Proposition 10] gives rise to a proof for the recurrence relation of A151366 stated in the OEIS. For the Baxter sequence A001181, the recurrence relation can be verified by utilizing its explicit formula in terms of binomial coefficients and the creative telescoping method. The details for the verification can be found in [START_REF] Bostan | Supplementary electronic material to the article "on sequences associated to invariant theory[END_REF]. The recurrence equation for A216947 is proven in [START_REF] Marberg | Crossings and nestings in colored set partitions[END_REF]. As far as we know, the stated recurrence relation in the OEIS for A236408 is only conjectured. Next, we give a unified proof for all those recurrence relations.

Corollary 4.14. The recurrence relations stated in the OEIS for the sequences in the second family specified in Figure 2 are true. Moreover, the sequences in the second family are related by binomial transforms.

Proof. By Theorem 4.4, we see that the quadrant sequences S 0 , S 1 , S 2 and S 3 are identical to the sequences in the second family specified in Figure 2. In [START_REF] Bostan | Supplementary electronic material to the article "on sequences associated to invariant theory[END_REF], by setting k to 0, 1, 2, 3, we find that the corresponding recurrence operators are left multiples [13, page 618] of those of A216947, A001181, A236408, and A151366 specified in the OEIS, respectively. To verify that they satisfies those recurrence relations, we just need to check finitely many initial terms. The details of the verification can be found in [START_REF] Bostan | Supplementary electronic material to the article "on sequences associated to invariant theory[END_REF]. Since S k 's are related by binomial transforms, so are sequences in the second family.

Closed formulae for these sequences can be obtained by the same methods as in Section 3.4.

Define the function

H(x) = 2 F 1 1 3 2 3 1 ; 27x 2 (1 -2x) 3 .
Then the ordinary generating function of S 2 is equal to

(x + 1) 2 (1 -8x) 3x 2 (1 -2x) 2 H + 12(1 + 20x -8x 2 )(1 -2x) (x + 1) H ′ - (3x 2 -x + 1) (3x 2 )
The above formula is equivalent to the following formula for A001181 in the OEIS.

-

1 + 1 3x 2 (x -1) + (1 -2x) 2 F 1 -2 3 2 3 1 ; 27x 2 (1 -2x) 3 - (8x 3 -11x 2 -x) (1 -2x) 2 2 F 1 1 3 2 3
2 ; 27x 2 (1 -2x) 3 .

A closed formula for the generating function of S k follows by substitution in Lemma 2.12.

The asymptotics is stated in [START_REF] Fan | The number of Baxter permutations[END_REF] and a detailed account is given in [19, Theorem 1].

Figure 1 .

 1 Figure 1. The first sequences of the family of octant sequences, their OEIS tags and their first ten terms.

( 1 )

 1 14 (n + 1) (n + 2) T 3 (n) + (n + 2) (19n + 75) T 3 (n + 1) + 2 (n + 2) (2n + 11) T 3 (n + 2) -(n + 8) (n + 9) T 3 (n + 3) = 0 satisfied for all n ≥ 0.

Figure 2 .

 2 Figure 2. The first four quadrant sequences, their OEIS tags and their first nine terms.

Definition 4 . 1 .

 41 For k 0, the quadrant sequences S k are the sequence associated to (SL(3), V ⊕ V * ⊕ k C).

Proposition 4 . 5 .Proposition 4 . 6 .

 4546 The set of hesitating tableaux of length n which end with a single row partition is equinumerous with the set of Baxter permutations on [n].A bijective proof of the following can be found in[START_REF] Courtiel | Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods[END_REF] Corollary 14]. The set of vacillating tableaux of length n which end with a single row partition is equinumerous with the set of 2-coloured noncrossing set partitions of [n].

4. 4 .

 4 Recurrence equations. In this subsection we give recurrence relations for the sequences S k . A recurrence relation for S 3 is given by Marberg in [37, § 4]. Lemma 4.11. Let G k be the generating function of S k , where k

Proposition 4 .

 4 [START_REF] Burrill | A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape[END_REF].[START_REF] Marberg | Crossings and nestings in colored set partitions[END_REF] Theorem 1.7] The n-th term C 2 (n) of the sequence S 3 is given by C 2 (0) = 1, C 2 (1) = 3 and for n ≥ 0:(n + 5)(n + 6) • C 2 (n + 2) -2(5n 2 + 36n + 61) • C 2 (n + 1) + 9(n + 1)(n + 4) • C 2 (n) = 0, Equivalently, the associated generating function G 3 (t) = n≥0 C 2 (n)t n satisfies 72G 3 (t) + 4(-61 + 117t) d dt G 3 (t) + 2(15 -184t + 234t 2 ) d 2 dt 2 G 3 (t) + 2t(-6 + 7t)(-1 + 9t) d 3 dt 3 G 3 (t) + (-1 + t)t 2 (-1 + 9t) d 4

( 7 )

 7 (-3 + k) 2 (-2 + k)(6 + k)(1 + n)(2 + n)a(n)+ -2(-3 + k)(2 + n)(-60 + 8k + 8k 2 -18n + 3kn + 2k 2 n)a(n + 1)+ (-342-174k+114k 2 -195n-70kn+54k 2 n-27n 2 -6kn 2 +6k 2 n 2 )a(n+2)+ 2(57 -70k + 16n -24kn + n 2 -2kn 2 )a(n + 3) + (n + 7)(n + 8)a(n + 4) = 0.

  + 1) 168 t 3 + 211 t 2 + 40 t -11 ∂ 5 + 6 t 3 2100 t 4 + 3475 t 3 + 1616 t 2 + 79 t -61 ∂ 4 + 6 t 2 11200 t 4 + 17400 t 3 + 7556 t 2 + 268 t -273 ∂ 3 + 36 t 4200 t 4 + 6100 t 3 + 2442 t 2 + 54 t -77 ∂ 2 + 36 3360 t 4 + 4540 t 3 + 1646 t 2 + 16 t -35 ∂+ 20160 t 3 + 25200 t 2 + 8064 t, The operator L 6 factors as L 6 = QL 3 , where Q = (2 t + 1) t 3 ∂ 3 + (24 t + 13) t 2 ∂ 2 + 6 (12 t + 7) t∂ + 48 t + 30, + 338 t 2 + 36 t -42 ∂ + 28 t (3 t + 4) . P 2 = 131712 t 11 + 719712 t 10 + 1626800 t 9 + 2014088 t 8 + 1498264 t 7 + 665620 t 6 + 146508 t 5 -4560 t 4 -11138 t 3 -2663 t 2 -244 t -7 and P = 28 t 4 + 66 t 3 + 46 t 2 + 15 t + 1.

	and
	(3) L 3 = t 2 (2 t + 1) (7 t -1) (t + 1) ∂ 3 + 2 t (t + 1) 63 t 2 + 22 t -7 ∂ 2 + 252 t 3 This shows that f (t) := L 3 (T (t)) is a solution of the differential oper-ator Q. Hence, by denoting f (t) = n≥0 f n t n , one deduces that for all n ≥ 0 we have 2 (n + 2) f 2 + t(t + 1)P 1 P ∂ + P 2 P 2 ,
	and
	L 1 = ∂ -	d dt (P/t 5 ) P/t 5

where ∂ = ∂ ∂t denotes the derivation operator with respect to t. n + (n + 6) f n+1 = 0.

One the other hand, from T (t) = 1 + t 2 + O(t 3 ), it follows that f 0 = 0, therefore f (t) = 0, in other words T (t) is also a solution of L 3 . From there, deducing the recurrence relation of Theorem 1.3 is immediate. 3.4. Closed formulae. In this subsection, we give two closed formulae for the generating function T (t) of sequence T 3 (A059710) in terms of classical Gaussian hypergeometric functions 2 F 1 . The operator L 3 in (3) factors as L 3 = L 2 L 1 , where L 2 = t 2 (2 t + 1) (7 t -1) (t + 1) ∂ with P 1 = 3136 t 6 + 7560 t 5 + 5744 t 4 + 1592 t 3 -90 t 2 -131 t -9,

  2 , U = (11 t -1) (46 t 3 -78 t 2 + 15 t -1), and V = 11870 t 7 -6934 t 6 -13371 t 5 + 1115 t 4 + 1112 t 3 -300 t 2 + 29 t -1,

	as well as the rational function
	φ =	27 (t + 1) t 2

  • 2 F 1

	1 12	1	5 12	;	1728 J	.
	Then the generating function T (t) is equal to P 6 t 5 + (7 t -1) (2 t + 1) (t + 1) 360 t 5 155 t 2 + 182 t + 59 (11 t + 1) H (t) +
	341 t 3 + 507 t 2 + 231 t + 1 (5 t + 1) H

′ (t) .

t[START_REF] Bostan | On sequences associated to the invariant theory of rank two simple lie algebras[END_REF] (1 -7 t) (2 t + 1) 2 (t + 1)[START_REF] Bonichon | Baxter permutations and plane bipolar orientations[END_REF]

A. Bostan was supported in part by DeRerumNatura ANR-19-CE40-0018. The work of Y. Zhang was supported by XJTLU Research Development Funding No. RDF-20-01-12, the NSFC Young Scientist Fund No. 12101506 and the Natural Science Foundation of the Jiangsu Higher Education Institutions of China No. 21KJB110032.


Gaël Loubet

Alassane Sidibe

Alexandru Takacs

Daniela Dragomirescu

This paper presents a Bluetooth Low Energy sensing node, part of a wireless sensor network dedicated to the deployment of a cyber-physical system for the structural health monitoring of reinforced concretes throughout their life. This fully wireless sensing node is designed to measure temperature and relative humidity, and wirelessly transmit the collected data in its network, as well as to be energy autonomous. For that, it is battery-free, able to cold-start, and wirelessly and remotely powered -and controlledover several meters by communicating nodes (other part of the network, assuring the connection to the digital world) via a radiative electromagnetic power transfer system.

INTRODUCTION

For several years, electronic embedded systems have played an increasingly important role in our societies. Numerous and always more diversified wireless communication technologies have been developed with various features and performances, both for human-to-human and machine-to-machine (M2M) communications. These technologies are employed to deploy Wireless Sensor Networks (WSN) for different applications, such as Structural Health Monitoring (SHM) of various structures (e.g. vehicles, buildings, etc.).

Nevertheless, one of the main limitations to the deployment of WSN is their energy need. To date, these are essentially powered by the use of the mains supply or batteries. But these two solutions are expensive, required a lot of maintenance, and limit the mobility and the scalability. To assure the energy autonomy of the WSN, both the ambient energy harvesting and the Wireless Power Transfer (WPT) solutions are investigated [START_REF] Peruzzi | A review of energy harvesting techniques for Low Power Wide Area Networks (LPWANs)[END_REF]. However, these latter are highly dependent on the deployment environment and on the targeted application.

In this context, and in the framework of the McBIM project (Material communicating with the Building Information Modelling (BIM)) [START_REF] Derigent | Materials communicating with the BIM: aims and first results of the McBIM project[END_REF], wireless, batteryfree and wirelessly powered sensing nodes (SN) based on the Bluetooth Low Energy _____________ (BLE) technology have been developed, implemented and tested. These SN are devoted to the design and implementation of a WSN embedded in a reinforced concrete to make it communicating and thus, to obtain a Cyber-Physical System (CPS) dedicated to the SHM in the civil engineering industry [START_REF] Loubet | Implementation of a Wireless Sensor Network Designed to be Embedded in Reinforced Concrete[END_REF][START_REF] Loubet | LoRaWAN Battery-Free Wireless Sensors Network Designed for Structural Health Monitoring in the Construction Domain[END_REF].

In this paper, the design and implementation of the BLE battery-free and wirelessly powered SN will be presented. Then, their characterization and some experimental results will be provided and discussed. Next, the positioning, the current limitations and perspectives will be explained. Before concluding, a comparison with similar SN based on the LoRaWAN wireless communication technology will be carried out.

DESIGN AND IMPLEMENTATION OF THE SENSING NODES

The McBIM project targets the design and implementation of a communicating reinforced concrete, according to the 'Communicating Materials' paradigm [START_REF] Kubler | Problem definition methodology for the "Communicating Material" paradigm[END_REF], and dedicated to the SHM of concrete structures throughout their life. To achieve this objective, we choose to embed a WSN inside the reinforced concrete, which must be able to sense various parameters (from the reinforced concrete itself and/or from its environment), to process, store and share wirelessly the collected data with the physical and digital worlds [START_REF] Loubet | Implementation of a Wireless Sensor Network Designed to be Embedded in Reinforced Concrete[END_REF][START_REF] Loubet | LoRaWAN Battery-Free Wireless Sensors Network Designed for Structural Health Monitoring in the Construction Domain[END_REF]. This WSN is composed of a meshed network of communicating nodes (CN) gathering information from a star network of SN fully embedded in the reinforced concrete (used to generate, pre-process and transmit data). This paper is focused on the SN based on the BLE. Complementary information is available in [START_REF] Derigent | Materials communicating with the BIM: aims and first results of the McBIM project[END_REF][START_REF] Loubet | Implementation of a Wireless Sensor Network Designed to be Embedded in Reinforced Concrete[END_REF][START_REF] Loubet | LoRaWAN Battery-Free Wireless Sensors Network Designed for Structural Health Monitoring in the Construction Domain[END_REF].

Architecture of the Sensing Nodes

The SN will be embedded into the reinforced concrete, and thus, become inaccessible. Thus, two main constraints must be overcome in their design:

 these must be able to wirelessly transmit the measured data to the CN through the reinforced concrete.

 their energy autonomy and reconfigurability must be ensured during all their lifespan.

To meet these requirements, the architecture presented in Fig. 1 has been chosen. It is composed of two distinct but interconnected parts, respectively dedicated to the data and the uplink, and to the energy and the downlink.

A specific package must be considered for the deployment in order to protect the electronics from the concrete, while allowing accurate measurements. The current prototype of the SN is presented in Fig. 2.

Data Measurement, Pre-Processing and Transmission

In order to assure the SHM of the reinforced concrete throughout its lifetime (expressed in decades), the SN must measure relevant data from the monitored structure and/or its environment such as temperature, relative humidity, mechanical deformations, corrosion rate, etc. The collected data can be formatted before being wirelessly transmitted to the CN and becoming accessible for the whole CPS.

The BLE technology is interesting for our application as it provides the next specifications:  unidirectional communications without connection or acknowledgement, due to the notification mode in the broadcaster/observer configuration;  low power consumption;  low to medium data-rate;  medium range of use: at least ten meters from a reinforced concrete element;  large availability and included in all general-purpose wireless devices.

The data acquisition and transmission part of the SN is printed or soldered on a 0.8 mm FR4 substrate and is composed of:  a low-power temperature and relative humidity sensor (Texas Instruments HDC2080 [START_REF]HDC2080 Low-Power Humidity and Temperature Digital Sensor[END_REF]) with accuracies of respectively 0.2 °C and 2 %, and ranges of -40 °C to +125 °C, and of 0 to 100 %;  a low-power BLE transceiver embedding a microcontroller unit (NXP QN9080 [START_REF] Nxp | QN908x Ultra low power Bluetooth 5 system-on-chip solution[END_REF]) which will drive the sensor, collect and format the measured data, and manage the BLE stack. The 3 bytes data will be wirelessly transmitted in an advertising broadcasting frame of 19 bytes. To assure the reliability, this frame will be transmitted 4 times on 3 different 2 MHz-channels on the 2.45 GHz ISM frequency band;

 a printed meandered inverted-f antenna (MIFA) [START_REF] Nxp | AN11994 QN908x BLE Antenna Design Guide[END_REF]. The data downlink is not implemented, and even not desired, for reasons of hardware security and power consumption. The power consumption is reduced by deleting the time dedicated to the listening of the medium for receiving acknowledgement, data or firmware update. The security is increased by imposing a fixed firmware and by blocking all accesses required to alter or update it.

Power Harvesting and Energy Management for Long-Term Autonomy, and Reconfigurability

In order to assure their energy autonomy for reliable long-term operations and because inaccessible once installed, the SN have been designed as simple as possible, low-power battery-free, able to cold-start, wirelessly powered and remotely controlled, over several meters even through the reinforced concrete.

A radiative electromagnetic WPT system controlled by the CN has been chosen to power the SN. This provides a generic long-term solution, for all possible use cases, and The energy part of the SN is composed of:  a rectenna (rectifying antenna): a printed folded quart-wavelength dipole antenna with capacitive arms, connected to a full-wave RF-to-DC rectifier, with a 14 cm x 9 cm metallic reflector plane located at 6 cm achieving a good trade-off between compactness and radiation efficiency [START_REF] Sidibe | Compact Antenna in 3D Configuration for Rectenna Wireless power transfer Applications[END_REF]. It will harvest the +33 dBm (or 2 W) radiative electromagnetic power generated by the CN through a continuous wave in the ISM 868 MHz frequency band and convert it in DC power;

 a Power Management Unit (PMU) (Texas Instruments bq25570 [START_REF]BQ225570[END_REF]) to store efficiently the energy in a supercapacitor and to supply the data part of the SN each time enough energy is available;

 a 100 µF aluminum electrolytic capacitor (Panasonic EEEFK0J101P 100 [START_REF] Panasonic | Aluminum electrolytic capacitors surface mount type FK series[END_REF]) to store the scavenged energy with low losses.

When the CN transmit radiative electromagnetic power, the rectenna of each SN located around converts the available RF power in DC power and provides it to the PMU; this stores it in the capacitor, thanks to its cold-start ability if this one is completely empty, and in an MPPT optimized way when enough energy is available to power this hardware function; once enough energy is stored, the PMU discharges the capacitor to power the data part of the SN; once a full process is achieved (id est when the energy stored for it is fully consumed), this cycle begin again (with a capacitor not empty) as long as the CN provide a radiative electromagnetic power. Thus, a "store then use" strategy is employed.

By tuning the radiative electromagnetic power source of the CN in terms of output power, waveform or duty cycle, it is possible to wirelessly and remotely control the behavior of the SN in terms of periodicity of data measurement and transmission without altering either their hardware or software. This power approach is the only way to reconfigure the current SN for which no data downlink is available.

CHARACTERIZATION AND EXPERIMENTAL RESULTS

Characterization of the Power Consumption

As shown in Fig. 3, nearly 1 second is required by the SN to achieve a full process: power-up, initialization, temperature and relative humidity measurement, and 4 times frame transmission (frame length: 19 bytes including 3 data bytes) with a +0 dBm power and to be powered-off again. 780 ms are needed for frame transmission. The broadcasting frames are separate by 250 ms period of deep-sleep mode. Around 920 µJ are required with a 3 V supply voltage, which means around 1.5 µJ is consumed per transmitted bit (for the 4 iterations) and 38 µJ per data bit (or 307 µJ per data byte).

In order to store enough energy in the 100 µF capacitor, the activation threshold voltage is set to 5.3 V and the deactivation one to 2.2 V, that allows to store around 1.16 mJ, enough for a full process and for the compensation of the disparity and ageing of the components.

Temporal Characterization of the First Charges and the Recharges

The periodicity of measurement and transmission of the SN are wirelessly and remotely controlled by the CN through the WPT. Thus, the characterization of the times required for a first charge (from an empty capacitor) and for recharges (between two process, with the same input power) in function of the input radiative electromagnetic power is a relevant information, and gives an important information of the possible ranges of use and frequencies of data collection. For an input power of the rectifier of +1 dBm, around 17 s are required for the first charge, and around 4 s for a recharge. For an input power of the rectifier of -16 dBm, 28 min and 17 s are necessary for the first charge, and 3 min 15 s for a recharge.

Wireless Communication Performances and Qualitative Tests

Several qualitative tests have been achieved in several configurations, in the air and/or from a reinforced concrete beam (with at least 10 cm of reinforced concrete around the SN). A unique CN can wirelessly power and collect data of several SN in its neighborhood (tested for 3 SN). If the SN are embedded in a reinforced concrete beam, the maximal range tested if 2 meters. If the SN is not embedded (only the sensor will be embedded) the maximal transmission range tested goes up to 7 meters in the air. In the both cases, the communication and power transmission work in almost omnidirectional way, no need of directive antennas. Moreover, by tuning their power source, the CN can remotely control the periodicity of functioning of the SN.

The impact of the reinforced concrete is highly visible in the performances of both the WPT and wireless communications. For one SN embedded in reinforced concrete powered wirelessly by an electromagnetic power of + 33 dBm at a distance of 2 m the first-time charge is of 1 min 15 s and the recharge time is 33 s. For the same SN placed outside the concrete beam powered by the same source of +33 dBm at 2 m distance the first-time charge is only 17 s and the recharge time goes down to only 4 s. For the wireless communications, the first packet losses appear for distance around 11 m for a SN embedded in the reinforced concrete beam, against more than 20 m for the SN placed on the concrete beam. Moreover, it must be noted that the WPT and the wireless communications have a similar range of use, expressed in meters and with expected maximum ranges over 10 m.

WORK IN PROGRESS ON THE BLE SENSING NODES

There are in the academic literature some recent works concerning the BLE nodes for WSN powered by the ambient energy harvesting or WPT. Some harvest ambient light [START_REF] Fraternali | Pible: battery-free mote for perpetual indoor BLE applications[END_REF][START_REF] Zhang | Design of a hybrid power system based on solar cell and vibration energy harvester[END_REF], mechanical vibrations [START_REF] Zhang | Design of a hybrid power system based on solar cell and vibration energy harvester[END_REF][START_REF] Rodriguez | A vibration energy harvester and power management solution for battery-free operation of wireless sensor nodes[END_REF], temperature gradient [START_REF] Rösch | Fully printed origami thermoelectric generators for energy-harvesting[END_REF], electromagnetic inductive field [START_REF] Maharjan | An indoor power line based magnetic field energy harvester for self-powered wireless sensors in smart home applications[END_REF], electromagnetic radiative waves [START_REF] Jung | A wideband, quasi-isotropic, kilometer-range fm energy harvester for perpetual IoT[END_REF], or multiple sources [START_REF] Zhang | Design of a hybrid power system based on solar cell and vibration energy harvester[END_REF], while others are based on the radiative electromagnetic WPT [START_REF] Rosa | RF energy scavenger for battery-free Wireless Sensor Nodes[END_REF][START_REF] Janhunen | Wireless energy transfer powered wireless sensor node for green IoT: Design, implementation and evaluation[END_REF], but all power a BLE node, battery-free [START_REF] Fraternali | Pible: battery-free mote for perpetual indoor BLE applications[END_REF][START_REF] Rodriguez | A vibration energy harvester and power management solution for battery-free operation of wireless sensor nodes[END_REF][START_REF] Rösch | Fully printed origami thermoelectric generators for energy-harvesting[END_REF][START_REF] Maharjan | An indoor power line based magnetic field energy harvester for self-powered wireless sensors in smart home applications[END_REF][START_REF] Jung | A wideband, quasi-isotropic, kilometer-range fm energy harvester for perpetual IoT[END_REF][START_REF] Rosa | RF energy scavenger for battery-free Wireless Sensor Nodes[END_REF][START_REF] Janhunen | Wireless energy transfer powered wireless sensor node for green IoT: Design, implementation and evaluation[END_REF] or not [START_REF] Zhang | Design of a hybrid power system based on solar cell and vibration energy harvester[END_REF][START_REF] Maharjan | An indoor power line based magnetic field energy harvester for self-powered wireless sensors in smart home applications[END_REF], and with [START_REF] Fraternali | Pible: battery-free mote for perpetual indoor BLE applications[END_REF][START_REF] Zhang | Design of a hybrid power system based on solar cell and vibration energy harvester[END_REF][START_REF] Rodriguez | A vibration energy harvester and power management solution for battery-free operation of wireless sensor nodes[END_REF][START_REF] Maharjan | An indoor power line based magnetic field energy harvester for self-powered wireless sensors in smart home applications[END_REF][START_REF] Jung | A wideband, quasi-isotropic, kilometer-range fm energy harvester for perpetual IoT[END_REF][START_REF] Rosa | RF energy scavenger for battery-free Wireless Sensor Nodes[END_REF][START_REF] Janhunen | Wireless energy transfer powered wireless sensor node for green IoT: Design, implementation and evaluation[END_REF] or without sensor [START_REF] Rösch | Fully printed origami thermoelectric generators for energy-harvesting[END_REF]. Those based on ambient energy harvesting are highly dependent of their environment and of their application, while those based on the WPT have limited range of use in the air (tested up to 2 m), are based on a "direct consumption" strategy, and their periodicity of data measurement and transmission is configured by software.

Our first BLE SN prototypes still have some limitations and some improvements (both hardware and software) can be carried out.

Concerning the data part, other low power sensors must be implemented with the aim of monitoring reinforced concretes and the data communication protocol can be optimized to further reduce the required energy, while ensuring reliable communications. It could be relevant to characterize the energy required and efficiency versus the supply voltage, the wireless communication transmitting power, the datarate, the time intervals between advertising frames, the number of frames sent, the number of channels used, always by considering the impact on the reliability of the wireless communications. By reducing the needed energy, the times required for the first charge and recharges will be reduced too. The capacity of the storage element and the activation threshold of the PMU could also be decreased.

Concerning the energy part, its optimization must improve the energy efficiency of the SN and allow wider ranges of use for the WPT. This optimization concerns especially the reduction of the minimum required input power, which is highly correlated to the rectenna efficiency (related to both antenna and rectifier performances, especially with the reinforced concrete as propagation medium for the electromagnetic waves), the power required by the PMU and the losses of the capacitor.

Concerning the global implementation, its size is mainly constrained by the antenna, a specifically designed package must be used, and further tests and characterizations must be performed.

COMPARISON WITH SENSING NODES BASED ON THE LORAWAN WIRELESS COMMUNICATION TECHNOLOGY

The presented implementation of the SN based on the BLE technology can be compared with those described in [START_REF] Loubet | Implementation of a Wireless Sensor Network Designed to be Embedded in Reinforced Concrete[END_REF][START_REF] Loubet | LoRaWAN Battery-Free Wireless Sensors Network Designed for Structural Health Monitoring in the Construction Domain[END_REF] and based on the LoRaWAN technology. However, these do not have the same maturity level.

The two are based on the same architecture, the same functioning in a "store then use" strategy (power-up, initialization, data measurement, formatting and wireless transmission to the CN, power-off), and are dedicated to the same application: the design and implementation of a communicating reinforced concrete and its long-term SHM. Also, their energy parts are similar: the same rectenna is used (with different metallic reflector plane), the supercapacitor and capacitor have similar losses despite different capacities (2.2 mF for LoRaWAN SN versus 100 µF for BLE SN), and only the PMU are different, which allows minor improvements in the BLE version with theoretically a lower minimal required input power. Thus, their ranges of use for the WPT part are almost the same. These are battery-free, able to cold-start and wirelessly powered (and wirelessly and remotely controlled) by the CN through a radiative electromagnetic WPT.

The main differences are related to the available sensors, the energy required for the data part and the wireless communication performances. The LoRaWAN implementation provides a reliable medium to high range wireless communications even through the reinforced concrete, while the BLE one is limited to a ten of meters with a high impact due to the reinforced concrete and potential packet losses. Nevertheless, the BLE requires very little energy to operate, less than 1 mJ, while the LoRaWAN one needs at least 20 mJ. The lower the stored energy, the faster the time to a first charge or a recharge. The BLE is more efficient than the LoRaWAN one in terms of energy per byte of data transmitted, with 307 µJ per data byte against up to 5 mJ per data byte. Thus, a trade-off between the reliability of the wireless communications, its range and its energy consumption must be done.

These two implementations meet the requirements of the simultaneous wireless information and power transmission (SWIPT) paradigm, both without temporal multiplexing and power splitting; and without frequency and spatial multiplexing for the LoRaWAN one.

CONCLUSION

This paper proposes an innovative low-cost, low power, fully wireless, battery-free and wirelessly powered by radiative electromagnetic waves BLE sensing nodes embedded into reinforced concrete to ensure its SHM throughout its lifetime, but which can be easily employed for other applications. Due to its design, the BLE sensing node is reliable and completely autonomous for decades. It is wirelessly powered over 7 meters and it is able to transmit data with an energy efficiency of only 307 µJ per data byte for a range up to 7 meters. Moreover, by tuning the power source used by the WPT system, the BLE SN can be wirelessly and remotely reconfigured in terms of periodicity of use (temperature and relative measurement, and data wireless communication), without altering either its hardware or software.

Figure 1 .

 1 Figure 1. Bloc diagram of the architecture of the sensing nodes.

Figure 2 .

 2 Figure 2. Photograph of a prototype of the sensing nodes.

Figure 3 .

 3 Figure 3. Power consumption of the sensing nodes powered by a 3 V supply voltage.

ACKNOWLEDGMENT

This research has been funded by the French National Research Agency (ANR) under the McBIM project, grant number ANR-17-CE10-0014. The authors would like to thank Mohamed ABO KASSEM for his valuable help during the design and the test of the BLE prototypes, as well as all their French partners in the McBIM project: CRAN (Nancy), LIB (Dijon), and FINAO SAS / 360SmartConnect (Trans-en-Provence).