Matthieu Heller

Measuring Elastic Scattering in the Coulomb Nuclear Interference (CNI) Region in ATLAS -Total Cross Sections and Luminosity

ATLAS is being complemented with detectors to measure elastic scattering at small angles. This will give a possibility both to measure the total cross section and make an absolute luminosity calibration of the Luminosity monitors of ATLAS. The principle of the measurement, the experimental requirements and the detector performances found in a 2008 test-beam are presented in this article.

Introduction

The Large Hadron Collider (LHC) will provide proton-proton collisions for the experiments installed at the interaction points (IP). The ATLAS detector is designed to detect high p t reactions and will focus on the discovery of the Higgs boson and new physics. However ATLAS is now also complemented by detectors in the very forward region to measure small angle elastic scattering. This will give a possibility to measure the total cross section and provide accurate luminosity calibration. The ultimate goal is to reach the Coulomb Nuclear Interference (CNI) region but even without reaching the CNI region precise luminosity calibration can be done. The detectors will be installed in so called "Roman Pots" 240 metres away from the ATLAS interaction point. The scattered particles at the IP will travel along the accelerator lattice and be detected by fiber trackers that are inserted in the Roman Pots. This measurement requires a special optics with very high beta at the interaction point and consequently will be done during dedicated runs.

Principle of the Measurement

The rate of elastic scattering is linked to the total interaction rate through the optical theorem, which states that the total cross section is directly proportional to the imaginary part of the nuclear forward elastic scattering amplitude extrapolated to zero momentum transfer:

σ tot ∝ [F n (t = 0)]
At very small scattering angle the four-momentum transfer can be written -t ≈ (pθ) 2 where p refers to the beam momentum and θ to the scattering angle at the IP.

EDS'09

1 Taking into account the optical theorem and the Coulomb term, the rate of elastic scattering at small t-values can be written as [START_REF]CERN/LHCC/2008-004[END_REF]:

dN dt = Lπ |f C + f N | 2 ≈ Lπ -2α |t| + σ tot 4π (i + ρ) e -b|t|/2 2 (1)
where the first term corresponds to the Coulomb and the second to the strong interaction amplitude and α is the fine structure constant, σ tot the total proton-proton cross section, b the nuclear slope and ρ the ratio of the real over the imaginary part of the forward elastic scattering amplitude. The formula is oversimplified, and there are also other corrections as the proton electromagnetic form factor and the relative phase between the Coulomb and the strong amplitude that are included in the final analysis. This expression allows to make the distinction between three terms as seen in Fig. 1. Fitting the rate of elastic scattering as a function of t allows to determine L, σ tot , b and ρ.

Experimental Framework

The best absolute accuracy on the luminosity measurement is obtained by approaching as close as possible the Coulomb region where the correlation between the luminosity and the total cross section gets smaller. However at the TeV scale, this means measuring scattering angles of a couple of micro-radians. At the nominal energy of the LHC (7 TeV) the strong amplitude is equal to the electromagnetic amplitude for -t = 6 10 -4 GeV 2 . This corresponds to a scattering angle of 3.5 µrad. A direct measurement of this angle would require to intercept these protons before the first magnetic element. This is in practice impossible because the separation between these protons and the beam core is less than 200 µm. It was found that the best solution was to use dedicated optics which will separate enough the beam core and the elastically scattered protons at 240 m from the IP (see Fig. 2). In this location Roman Pots (RPs) detectors will be inserted to tag the elastic protons.

2

EDS'09 The beam conditions required to reach the CNI region are a small emittance and special beam optics. This dedicated beam optics is characterized by a very large β * at the ATLAS IP, zero dispersion and a phase advance of the betatron function between the IP and the detectors of 90 degrees in the vertical plane to perform the parallel-to-point focussing which is sketched in Fig. 3. This has the consequence that particles scattered with the same angle arrive at the same position in the detector. An optics solution fulfilling the above requirements must be used in combination with rather few bunches of low intensity compared to nominal LHC settings. It will produce instantaneous luminosities in the range of 10 27 to 10 28 cm -2 s -1 . Using the expression of the scattering angle as a function of the position in the detector, the minimum t-value that we will be able to detect depends on the particle's momemtum (p), the distance to the beam centre expressed in terms of number of σ of the beam size (n min ), the emittance ( ), and the value of the betatron function at the IP (β IP ):

-t min = p 2 n 2 min β IP (2)
Assuming that we can approach the beam down to 12 σ, that we run at 7 TeV and that the normalised emittance is N = 1µm rad with a β IP = 2625 m, we obtain -t min = 3.7 10 -4 GeV 2 which is equivalent to θ IP,y = 3 µrad.

To intercept these protons, two Roman Pot stations are installed symmetrically in the forward direction on beam 1 and beam 2. Each station is made of an upper and a lower EDS'09 detector. The detectors inserted into the Roman Pots (RPs) are presented in the following section.

ALFA Detector

The ALFA detector 1 is made of a scintillating fiber tracker inserted in a Roman Pot (see Fig. 4). The tracker is made of 20 layers of 64 squared fibers each organised in a U-V geometry with 90 • between two consecutive layers (see Fig. 5). The scintillating fibers are 0.5×0.5 mm 2 and a staggering of 10 % is applied between two consecutive planes providing a theoretical resolution close to 15 µm. However as shown in Section 6, the assembling imperfections worsen this result. Each layer is read out by a Multi Anode PhotoMulTiplier (MAPMT) with 64 channels. The compact front-end electronics called 1 ALFA stands for Absolute Luminosity For ATLAS

4

EDS'09 PMF [START_REF] Pmf | the front end electronics of the ALFA detector[END_REF], are directly mounted on the back of the MAPMT. The MAROC2 ASIC [START_REF] Pmf | the front end electronics of the ALFA detector[END_REF] allows to correct the MAPMT gain non-uniformity and to discriminate the signal. An FPGA ensures the communication with the motherboard fixed on the pot. On top of that, the overlap detectors sketched in Fig. 6 are used to measure the relative position between the upper and the lower pot with a precision of 10 µm. Mechanically fixed to the main tracker, they provide essential information about the t-scale that cannot be extracted from the data. This measurement will be done reconstructing the halo particles passing at the same time through the upper and lower overlap detector.

The Simulation

The acceptance of the ALFA detector is a major issue and has to be computed by simulation. Indeed, one has to know as precisely as possible which protons will pass through the sensitive area of the detectors and which will go in between the upper and lower pot or will be lost during the transport from the IP to the RPs. This simulation therefore includes:

• a Monte-Carlo generator (Pythia [START_REF]Pythia website[END_REF]) to generate the event according to the differential elastic cross section,

• transport software (MadX [START_REF]MAD-X website[END_REF]) to track the protons along the magnetic lattice (see Fig. 7),

• reconstruction software to build the spectrum, correct it and fit it. Due to the optics settings, one t-value is seen as an ellipse in the detector. In Fig. 7 are sketched (x,y)-maps at the RP for three different t-ranges to give an idea of where the scattered protons will hit the detector. The inner ring represents t ∈ 7 10 -4 ; 13 10 -4 GeV 2 , the middle one t ∈ 7 10 -3 ; 13 10 -3 GeV 2 and the outer one t ∈ 7 10 -2 ; 13 10 -2 GeV 2 . The elastic protons detected allow to reconstruct the spectrum and to determine the acceptance. Fig. 8 shows the acceptance as a function of t for 7 TeV protons with the detectors at 12 σ from the beam center. One can observe two distinctive causes of acceptance losses. On the right of the red line, events are mainly lost in the accelerator due to the magnetic element aperture, and on EDS'09 the left, protons are passing between the two pots. The acceptance determination will allow to correct the detected spectrum to recover the underlying physics distribution.

[%] Beam properties 1. In Table 1 [START_REF]CERN/LHCC/2008-004[END_REF][START_REF]Luminosity calibration from elastic scattering[END_REF] are summarized the contributions to the precision on the luminosity measurement from various sources. In the so-called beam properties part, the major impact will be from the angular divergence as it mainly affects small values of t for which the fit is very sensitive. However the measurement of the optical parameters will also be an important issue. The detector properties will be dominated by the detector alignment with respect to the beam and acceptance corrections. Any error on this measurement will drastically affect the result of the fit. The background is composed of beam-gas events, particles surviving the LHC collimation system and all non-elastic processes such as single diffraction events. Its rejection is done using mainly the back-to-back topology of the elastic event. The simulation has shown that the 2-3 % claimed in [START_REF]CERN/LHCC/2008-004[END_REF] on absolute accuracy can be reached.

Detector Performances

The first complete tracker (20 planes of 64 fibers each) has been tested in August 2008 on the SPS test-beam line H8 at CERN. However, only half of the detector could be read out. The ALFA detector was coupled to a silicon strip telescope with a resolution of 10 µm. Using this setup we were able to determine the layer efficiency and the spatial resolution.

The layer efficiency has been computed using the telescope prediction. Indeed the accurate telescope resolution allows to point in each layer to the fiber where the particle went through. Comparing this prediction with the data allows us to determine the layer efficiency which has been found to be ≈90 %. Combining layers together this is enough to reach almost 100 % detection efficiency for the entire ALFA tracker.

The reconstruction method consist in projecting all fibers from all planes of the same orientation on a perpendicular plane. If a particle went through the detector, the hit fibers corresponding to the path will overlap on this projection. One can determine then the position of the center of the overlap region and its width. To accept a track in the reconstruction algorithm, a minimum of three fibers for half a detector must define the overlap region i.e. all layers do not have to be efficient, but only 60 % of them. For a full detector this limit is set to a minimum of 6 layers. This condition has a major impact on the resolution: the higher the number of fibers defining the track path is, the greater is the probability to have a small area of overlap providing a better resolution. This is exactly what we see in Fig. 9, which displays the resolution improving with a decreasing overlap region.

The spatial resolution obtained with half a detector is close to 52 µm in both directions. This results has been compared to a Monte Carlo simulation including layer efficiency and real geometry, and comparable results have been found. For a full detector, where the staggering configuration is optimal, the average overlap region width is lower than 100 µm. Judging by the Fig. 9 we can expect a resolution around 35 µm.

6

EDS'09

Conclusion

The studies of the systematics has shown that 2-3 % absolute accuracy on luminosity can be reached with the ALFA detector. All test-beam studies done so far have validated the technical choices made for the different parts of the ALFA detector. A new test-beam period is planned for October 2009 to definitely validate the electronics and the full tracker.

Figure 1 :

 1 Figure 1: Contribution to the differential elastic cross section of the three components at small t value with σ tot =100 mb, ρ=0.013 and b=18 GeV -2 .

Figure 2 :

 2 Figure 2: Location of the two stations (in red) on beam 1. Both other stations are on beam 2, on the opposite side with respect to ATLAS.

Figure 3 :

 3 Figure 3: Parallel-to-point focussing where the optics brings all particles scattered with the same angle at the IP to the same location in the detector.

Figure 4 :

 4 Figure 4: Schematic view of the ALFA detector.

Figure 5 :

 5 Figure 5: Schematic view of the main tracker. Only four U-V planes out of ten are represented on the picture.

Figure 6 :

 6 Figure 6: Schematic view of the detectors.

Figure 7 :

 7 Figure 7: Scattering picture at the RP. The black lines show the diamond shape of the active part of the detector.

Figure 8 :

 8 Figure 8: Acceptance obtained with the same parameters as define earlier.

Figure 9 :

 9 Figure 9: Resolution dependency on the overlap region width, #U and #V standing for the number of U-V layers used.

Table 1 :

 1 Summary of the different uncertainties obtained on integrated luminosity for L = 3.6 10 32 cm -2 .

	2


Dominique Foata
email: foata@math.u-strasbg.fr

Guo-Niu Han

THE q-TANGENT AND q-SECANT NUMBERS VIA BASIC EULERIAN POLYNOMIALS

Keywords: Mathematics Subject Classification. Primary 05A15, 05A30, 05E15 q-tangent numbers, q-secant numbers, q-Eulerian polynomials, excedances, derangements, desarrangements, alternating permutations

The classical identity that relates Eulerian polynomials to tangent numbers together with the parallel result dealing with secant numbers is given a q-extension, both analytically and combinatorially. The analytic proof is based on a recent result by Shareshian and Wachs and the combinatorial one on the geometry of alternating permutations.

Introduction

Let (A n (s, Y )) (n ≥ 0) be the sequence of polynomials in two variables defined by

(1.1) n≥0 u n n! A n (s, Y ) = 1 -s exp(su) -s exp(u) exp(Y u).
It is known (see, e.g. [START_REF] Foata | Théorie géométrique des polynômes eulériens[END_REF], chap. 4) that they are polynomials with positive integral coefficients. For Y = 1 we recover the Eulerian polynomials (A n (s, 1)) introduced by Euler [START_REF] Euler | Institutiones calculi differentialis cum eius usu in analysi finitorum ac Doctrina serierum[END_REF] for his evaluation of the alternating sum m i=1 (-1) i i n . Moreover, Euler derived the two identities The coefficients T 2n+1 (n ≥ 0), called tangent numbers, are positive integral numbers, and so are the secant numbers E 2n (n ≥ 1) (see, e.g., [START_REF] Nielsen | Traité élémentaire des nombres de Bernoulli[END_REF], p. 177) defined by the Taylor expansion of sec u:

sec u = 1 cos u = 1 + n≥1 u 2n (2n)! E 2n = 1 + u 2 2! 1 + u 4 4! 5 + u 6 6! 61 + u 8 8! 1385 + u 10 10! 50521 + • • • (1.4)
The parallel result to (1.2) involving secant numbers was obtained by Roselle [START_REF] Roselle | Permutations by number of rises and successions[END_REF] for the polynomials A n (s, 0) in the form

(1.5) A 2n-1 (-1, 0) = 0 (n ≥ 1); (-1) n A 2n (-1, 0) = E 2n (n ≥ 0). For each permutation σ = σ(1)σ(2) • • • σ(n) of 12 • •
• n the number of excedances exc σ, (resp. of descents, des σ,) of σ is defined to be the number of integers i such that 1 ≤ i ≤ n -1 and σ(i) > i (resp. σ(i) > σ(i + 1)). Also, fix σ designates the number of fixed points of σ and D n the subset of S n of the permutations without fixed points, called derangements. It is known that the two statistics "exc" and "des" have the same distributions over the symmetric group ( [START_REF] Alexander | Combinatory Analysis[END_REF], p. 186). As derived in [START_REF] Foata | Théorie géométrique des polynômes eulériens[END_REF], we have A n (s, Y ) = σ∈Sn s exc σ Y fix σ . The specializations are due to Riordan ([17], p. 214) for Y = 1 and to Roselle [START_REF] Roselle | Permutations by number of rises and successions[END_REF] for Y = 0.

The combinatorial counterparts of (1.2) and (1.5) can be expressed as

σ∈S2n (-1) exc σ = 0 (n ≥ 1); (1.6) σ∈S2n+1 (-1) n+exc σ = T 2n+1 (n ≥ 0); (1.7) σ∈D2n-1 (-1) exc σ = 0 (n ≥ 1); (1.8) σ∈D2n (-1) n+exc σ = E 2n (n ≥ 0). (1.9) Let (t; q) n = (1 -t)(1 -tq) • • • (1 -tq n-1
) for n ≥ 1 and (t; q) 0 = 1 denote the traditional q-ascending factorials. The purpose of this paper is to construct a q-analog of (1.6)-(1.9), as further stated in Theorem 1. This first means that two sequences of polynomials (T 2n+1 (q)), (E 2n (q)) with positive integral coefficients are to be introduced such that T 2n+1 (1) = T 2n+1 and E 2n (1) = E 2n . This is achieved by taking the q-tangent numbers T 2n+1 (q) and the q-secant numbers E 2n (q) (see [START_REF] Andrews | Congruences for the q-secant number[END_REF][START_REF] Andrews | Divisibility properties of the q-tangent numbers[END_REF][START_REF] Foata | Further divisibility properties of the q-tangent numbers[END_REF]) occurring in the two expansions: tan q (u) = n≥0 (-1) n u 2n+1 /(q; q) 2n+1 n≥0 (-1) n u 2n /(q; q) 2n = n≥0 u 2n+1 (q; q) 2n+1 T 2n+1 (q); sec q (u) = 1 n≥0 (-1) n u 2n /(q; q) 2n = n≥0 u 2n (q; q) 2n E 2n (q).

Note that tan q (u) (resp. sec q (u)) is simply the quotient of the q-sine and q-cosine (resp. the inverse of q-cosine), as introduced by Jackson [14] (also see [START_REF] Gasper | Basic hypergeometric series[END_REF], p. 23).

The first values are: T 1 (q) = 1; T 3 (q) = q + q 2 ; T 5 (q) = q 2 + 2q 3 + 3q 4 + 4q 5 + 3q 6 + 2q 7 + q 8 ; E 0 (q) = E 2 (q) = 1, E 4 (q) = q(1 + q) 2 + q 4 ; E 6 (q) = q 2 (1 + q) 2 (1 + q 2 + q 4 )(1 + q + q 2 + 2q 3 ) + q 12 . Second, another statistic on the symmetric group S n is to be associated with "exc," so that the left-hand sides of the four identities (1.6)-(1.9) will become true polynomial identities. The statistic that meets our expectations is the classical major index "maj," defined for each permutation σ = σ(1)σ(2) • • • σ(n) as the sum of all the i's such that σ(i) > σ(i + 1). The main result of the present paper is then the following theorem.

Theorem 1. We have:

σ∈S2n (-1) exc σ q (maj -exc)σ = 0 (n ≥ 1); (1.10) σ∈S2n+1 (-1) n+exc σ q (maj -exc)σ = T 2n+1 (q) (n ≥ 0); (1.11) σ∈D2n-1 (-1) exc σ q (maj -exc)σ = 0 (n ≥ 1); (1.12) σ∈D2n (-1) n+exc σ q (maj -exc)σ = E 2n (q) (n ≥ 0). (1.13)
We provide two proofs of Theorem 1. The analytic proof, given in Section 2, is based on a recent result due to Shareshian and Wachs [START_REF] Shareshian | q-Eulerian Polynomials: Excedance Number and Major Index[END_REF] who made an explicit study of the statistic "majexc". The combinatorial proof, given in Section 4, is based on the geometry of alternating permutations, as introduced by André [START_REF] André | Développement de sec x et tg x[END_REF][START_REF] André | Sur les permutations alternées[END_REF] and on an equidistribution property between two three-variable statistics (exc, fix, maj) and (lec, pix, inv) established in [START_REF] Foata | Fix-mahonian calculus III; a quadruple distribution[END_REF]. However, to make this paper self-contained, we give a new proof of that equidistribution property by directly calculating the distribution of the latter statistic (see Theorem 4, Section 3). Our combinatorial proof consists of reducing the four alternating sums (1.10)-(1.13) by means of two explicit sign-reversing involutions. In contrast to the combinatorial proofs of (1.6) and (1.7) given in [START_REF] Foata | Théorie géométrique des polynômes eulériens[END_REF], chap. 5, these involutions naturally lead to the alternating permutation model.

The analytic proof

The q-analogs of the Eulerian polynomials, which have been derived, are the generating polynomials for S n by the pair (des, maj) (Carlitz [START_REF] Carlitz | q-Bernoulli and Eulerian numbers[END_REF][START_REF] Carlitz | A combinatorial property of q-Eulerian numbers[END_REF]), by (des, inv) (Stanley [START_REF] Stanley | Binomial posets, Möbius inversion, and permutation enumeration[END_REF]) and by (exc, maj) (Shareshian and Wachs [START_REF] Shareshian | q-Eulerian Polynomials: Excedance Number and Major Index[END_REF]). Let us recall the latest q-extension.

Theorem 2 (Shareshian-Wachs). Let

A n (s, Y, q) = σ∈Sn s exc σ Y fix σ q maj σ . (2.1) Then n≥0 u n (q; q) n A n (s, Y, q) = 1 -sq e q (squ) -sqe q (u) e q (Y u), (2.2)
where e q (u) = n≥0 u n /(q; q) n is the first q-exponential.

To prove Theorem 1 it then suffices to establish the following equivalent theorem. Theorem 3. Let (A n (s, Y, q)) (n ≥ 0) be the sequence of polynomials defined by (2.1). Then

A 2n (-q -1 , 1, q) = 0 (n ≥ 1); (-1) n A 2n+1 (-q -1 , 1, q) = T 2n+1 (q) (n ≥ 0); A 2n-1 (-q -1 , 0, q) = 0 (n ≥ 1); (-1) n A 2n (-q -1 , 0, q) = E 2n (q) (n ≥ 0).
Proof. With the substitutions Y := 0 and s := -q -1 in (2.2) we get n≥0 u n (q; q) n A n (-q -1 , 0, q) = 1 + n≥1 u 2n (q; q) 2n -1

.

As the fraction on the right involves only even powers of u, we deduce:

A 2n-1 (-q -1 , 0, q) = 0 (n ≥ 1).
By replacing u by iu we obtain

n≥0 u 2n (q; q) 2n (-1) n A 2n (-q -1 , 0, q) = 1 + n≥1 (-1) n u 2n (q; q) 2n -1 = 1 cos q (u)
.

Consequently, (-1) n A 2n (-q -1 , 0, q) = E 2n (q) (n ≥ 0). From (2.2) we can write:

n≥0 u n (q; q) n A n (s, 1, q) = e q (u) n≥0 u n (q; q) n A n (s, 0, q)
so that by replacing s by -q -1 and u by iu n≥0 (iu) n (q; q) n A n (-q -1 , 1, q) = e q (iu) cos q (u) = cos q (u) + i sin q (u) cos q (u) .

By selecting the real and imaginary parts we get n even (iu) n (q; q) n A n (-q -1 , 1, q) = 1 and n≥0 u 2n+1 (q; q) 2n+1 (-1) n A 2n+1 (-q -1 , 1, q) = sin q (u) cos q (u) = tan q (u).

We then conclude:

A 2n (-q -1 , 1, q) = 0 (n ≥ 1), (-1) n A 2n+1 (-q -1 , 1, q) = T 2n+1 (q) (n ≥ 0).

A direct derivation

A word w = x 1 x 2 • • • x m is called a hook if x 1 > x 2
and either m = 2, or m ≥ 3 and x 2 < x 3 < • • • < x m . As proved by Gessel [START_REF] Gessel | A coloring problem[END_REF], each permutation σ = σ(1)σ(2) • • • σ(n) admits a unique factorization, called its hook factorization, pτ 1 τ 2 • • • τ k , where p is an increasing word and each factor τ 1 , τ 2 , . . . , τ k is a hook. To derive the hook factorization of a permutation, it suffices to start from the right and at each step determine the right factor which is a hook. For each i let inv τ i denote the number of inversions of τ i and define: Those two statistics have been introduced and used in [START_REF] Foata | Fix-mahonian calculus III; a quadruple distribution[END_REF]. Furthermore, let Desar n be the subset of S n of the permutations σ, called desarrangements, having the property that pix σ = 0 [START_REF] Désarménien | Une autre interprétation du nombre de dérangements[END_REF].

For instance, the hook factorization of the following permutation is indicated by vertical bars: σ = 1 3 4 14 | 12 2 5 11 15 | 8 6 7 | 13 9 10. We have p = 1 3 4 14, so that pix σ = 4, inv(12 2 5 11 15) = 3, inv(8 6 7) = 2, inv(13 9 10) = 2, so that lec σ = 7. The next theorem, already derived in [START_REF] Foata | Fix-mahonian calculus III; a quadruple distribution[END_REF], is given a new direct proof.

Theorem 4. Let A lec,pix,inv n (s, Y, q) := σ∈Sn s lec σ Y pix σ q inv σ . (3.3) Then n≥0 u n (q; q) n A lec,pix,inv n (s, Y, q) = 1 -sq e q (squ) -sqe q (u) e q (Y u). (3.4) Proof. Let pτ 1 τ 2 • • • τ r be the hook factorization of a permutation σ from S n . Let A 0 (resp. A i (1 ≤ i ≤ r))
denote the set of all letters in the word p (resp. in the hook τ i ) and call content of σ the sequence Cont σ = (A 0 , A 1 , . . . , A r ). Note that #A i ≥ 2 for i = 1, . . . , r and (A 0 , A 1 , . . . , A r ) is an ordered partition of [n] = {1, 2, . . . , n}. The statistic (invlec)σ is equal to the number of pairs (k, l) such that k ∈ A i , l ∈ A j , k > l and i < j, a number we shall denote by inv(A 0 , A 1 . . . , A r ).

If

A i = {a 1 < a 2 < • • • < a m }, then the hooks with content A i are the (m -1) words: w 1 = a m a 1 • • • a m-2 a m-1 , w 2 = a m-1 a 1 • • • a m-2 a m , . . . , w m-1 = a 2 a 1 a 3 • • • a m-1 a m ,
whose "lec" statistic and inversion number are both equal to (m -1), (m -2), . . . , 1, respectively. The generating polynomial for those (m -1) hooks by the pair (lec, inv) is then equal to (3.5) P m (s, q) := sq + (sq

) 2 + • • • + (sq) m-1 = sq -(sq) m 1 -sq .
The identity (A0,A1,... ,Ar) #Ai=ai q inv(A0,A1,... ,Ar) = n a0,a1,... ,ar q

, where the right-hand side is the q-multinomial coefficient (q; q) n /((q; q) a0 (q; q) a1 • • • (q; q) ar ) is easy to verify. We then have:

A lec,pix,inv n (s, Y, q) = σ∈Sn q (inv -lec)σ (sq) lec σ Y pix σ = (A0,A1,... ,Ar) q inv(A0,A1,... ,Ar) Y #A0 Cont σ=(A0,A1,... ,Ar) (sq) lec σ = (A0,A1,... ,Ar) q inv(A0,A1,... ,Ar) Y #A0 1≤i≤r P #Ai (s, q) = a0+a1+•••+ar =n ai≥2 (1≤i≤r) Y a0 1≤i≤r P ai (s, q) (A0,A1,... ,Ar) #Ai=ai q inv(A0,A1,... ,Ar) = a0+a1+•••+ar =n ai≥2 (1≤i≤r) n a 0 , a 1 , . . . , a r q Y a0 1≤i≤r P ai (s, q).
The rest of the calculation is routine:

n≥0 A lec,pix,inv n (s, Y, q) u n (q; q) n = n≥0 a0+a1+•••+ar=n ai≥2 (1≤i≤r)
Y a0 u a0 (q; q) a0 1≤i≤r P ai (s, q) u ai (q; q) ai = a0≥0 (Y u) a0 (q; q) a0 1

- b≥2 P b (s, q) u b (q; q) b -1 = e q (Y u) 1 - b≥2 sq -(sq) b 1 -sq u b (q; q) b -1 = e q (Y u)
1sq e q (squ)sqe q (u) .

In view of (2.1), (2.2), (3.3) and (3.4) the following identity holds

(3.6) σ∈Sn s exc σ Y fix σ q maj σ = σ∈Sn s lec σ Y pix σ q inv σ
and Theorem 1 is proved if we establish the four following identities: σ∈S2n (-1) lec σ q (inv -lec)σ = 0 (n ≥ 1); (3.7) σ∈S2n+1 (-1) n+lec σ q (inv -lec)σ = T 2n+1 (q) (n ≥ 0); (3.8) σ∈Desar2n-1 (-1) lec σ q (inv -lec)σ = 0 (n ≥ 1); (3.9) σ∈Desar2n (-1) n+lec σ q (inv -lec)σ = E 2n (q) (n ≥ 0). (3.10) This is the object of the next section.

The combinatorial proof

An alternating (resp. falling alternating) permutation is defined to be a permutation σ = σ(1) • • • σ(n) having the following properties: σ(1) < σ(2), σ(2) > σ(3), σ(3) < σ(4), etc. (resp. σ(1) > σ(2), σ(2) < σ(3), σ(3) > σ(4), etc.) in an alternating way. The set of alternating (resp. falling alternating) permutations of order n is denoted by T n (resp. by T ′ n ). The combinatorial interpretations #T 2n+1 = #T ′ 2n+1 = T 2n+1 , #T 2n = #T ′ 2n = E 2n are due to Désiré André [START_REF] André | Développement de sec x et tg x[END_REF][START_REF] André | Sur les permutations alternées[END_REF]. For each permutation σ let inv σ denote the number of its inversions. The following theorem is of common knowledge today, once we know how to q-transpose the calculation made by André in his memoirs (see, e.g., [START_REF] Andrews | Congruences for the q-secant number[END_REF], Proposition 4.1.) Theorem 5. For each n ≥ 0 we have σ∈T2n+1 q inv σ = σ∈T ′ 2n+1 q inv σ = T 2n+1 (q), and σ∈T2n q inv σ = E 2n (q). Next, consider the left-hand side LHS of (3.8) (resp. of (3.7)). The sum may be regarded as being over all hook factorizations pτ 1 τ 2 • • • τ r of permutations from S 2n+1 (resp. S 2n ). Let A 0 be the set of the letters in p and, as before, let A i be the set of all letters in τ i (1 ≤ i ≤ r). As above, we may apply the involution Ω → Ω ′ to all contents Ω = (A 1 , A 2 , . . . , A r ), remembering that this time Ω is an ordered partition of [2n + 1] \ A 0 (resp. of [2n] \ A 0 ). After applying Ω → Ω ′ we get (-1) n+r q inv(A0,A1,... ,Ar) , where the sum is over all ordered partitions Θ = (A 0 , A 1 , . . . , A r ) of [2n + 1] (resp. of [2n] with the convention that A 0 may be empty), having the property that (A 1 , . . . , A r ) is an ordered partition of a subset of [2n + 1] (resp. of [2n]) into blocks of cardinality 2 having no increase.

Another sign-reversing involution. Each ordered partition Θ = (A 0 , A 1 , . . . , A r ) of [2n+ 1] (resp. of [2n]) is said to be of type D, if max A 0 < min A 1 (by convention, max ∅ = -∞). It is of type D ′′ if max A 0 < min A 1 does not hold and #A 0 ≥ 2. If Θ is of type D, define Θ ′′ = (A 0 ∪ A 1 , A 2 , . . . , A r ). Then, Θ ′′ is of type D ′′ and inv Θ ′′ = inv Θ, so that (4.3) (-1) n+r q inv Θ + (-1) n+r-1 q inv Θ ′′ = 0.

Thus Θ → Θ ′′ is a sign-reversing involution.

After applying the transformation Θ → Θ ′′ to the summands in (4.2) there remains no term if the sum is made over the ordered partitions of [2n]. This proves identity (3.7). When making the sum over ordered partitions of [2n+1], the remaining terms correspond to the ordered partitions (A 0 , A 1 , . . . , A r ) having no increase and such that A 0 is a singleton. In particular, r = n. Such a partition is of the form ({a 0 }, {a 1 < b 1 }, {a 2 < b 2 }, . . . , {a n < b n }) having the property that a 0 > a 1 and for each i = 2, . . . , n the relation b i-1 > a i holds. Hence ω = a 0 a 1 b 1 a 2 b 2 • • • a n b n is a falling alternating permutation. We have then proved σ∈S2n+1 (-1) n+lec σ q (inv -lec)σ = ω∈T ′ 2n+1 q inv ω (n ≥ 0). This establishes (3.8) by Theorem 5.

(1. 2 )

 2 A 2n (-1, 1) = 0 (n ≥ 1); (-1) n A 2n+1 (-1, 1) = T 2n+1 (n ≥ 0);where T 2n+1 (n ≥ 0) are the coefficients of the Taylor expansion of tan u,

We first prove identities (3.9) and (3.10). With the notations of the previous section the content of each desarrangement is of the form (∅, A 1 , . . . , A r ), so that σ∈Desarn (-1) lec σ q (inv -lec)σ = A lec,pix,inv n (-q -1 , 0, q) = a1+•••+ar=n ai≥2 1≤i≤r

P ai (-q -1 , q) (A1,... ,Ar) #Ai=ai q inv(A1,... ,Ar) .

From the very definition of P m (s, q) we have:

Hence, if the ordered partition (A 1 , A 2 , . . . , A r ) has at least one block of odd cardinality and #A i = a i (1 ≤ i ≤ r), the product 1≤i≤r P ai (-q -1 , q) is null. As each desarrangement from S 2n-1 has at least one hook of odd length, the sum σ∈Desar2n-1 (-1) lec σ q (inv -lec)σ is zero. This already proves identity (3.9). Next, consider the even case. If all the blocks A 1 , A 2 , . . . , A r of the ordered partition (A 1 , A 2 , . . . , A r ) are of even cardinality, then σ∈Cont(A1,... ,Ar) (-1) n+lec σ q (inv -lec)σ = (-1) n+r q inv(A1,... ,Ar ) .

Hence, σ∈Desar2n (-1) n+lec σ q (inv -lec)σ = (A1,... ,Ar) #Ai even (-1) n+r q inv(A1,... ,Ar) . (4.1)

Sign-reversing involution. An ordered partition Ω = (A 1 , A 2 , . . . , A r ) is said to have an increase at i if 1 ≤ i ≤ r -1 and max A i < min A i+1 . If it has no increase and all its blocks A j are of cardinality 2, then r = n and the corresponding term in (4.1) is equal to q inv Ω . If it is not the case, let i be the integer with the following properties:

(ii) no increase at 1, 2, . . . , (i -1); (iii) either #A i ≥ 4, or (iv) #A i = 2 and there is an increase at i. Say that the partition Ω is of class C i (resp. C ′ i ) if (i), (ii) and (iii) (resp. and (iv

i , which is sign-reversing since inv Ω ′ = inv Ω and (-1) n+r q inv Ω + (-1) n+r+1 q inv Ω ′ = 0.

By applying the involution Ω → Ω ′ , the only partitions (A 1 , . . . , A r ) remaining in We have then proved σ∈Desar2n (-1) n+lec σ q (inv -lec)σ = ω q inv ω , where the sum is over all alternating permutations of order 2n, which establishes identity (3.10) by Theorem 5.


Dominique Foata

Guo-Niu Han

Doubloons and new q-tangent numbers

We introduce new q-tangent numbers based on the Carlitz q-analog of the Eulerian polynomial and the so-called doubloon combinatorial set-up. Those new q-tangent numbers are polynomials with positive integral coefficients. They are divisible by products of binomials of the form 1 + q i , the quotients being q-analogs of the reduced tangent numbers having an explicit combinatorial interpretation.

Introduction

In his search for an evaluation of the alternating sum m i=1 (-1) i i n Euler [Eu1755] introduced the sequence of now called Eulerian polynomials (A n (t)) (n ≥ 0) in the following two equivalent forms:

t -1 t -exp(u(t -1)) = n≥0 u n n! A n (t) (1.1) = 1 + u 1! + u 2 2! (t + 1) + u 3 3! (t 2 + 4t + 1) + u 4 4! (t 3 + 11t 2 + 11t + 1) + • • • m i=1 i n t i = n l=1
(-1) n+l n l t m+1 A n-l (t) (t -1) n-l+1 m l + (-1) n t(t m -1) (t -1) n+1 A n (t). (1.2)

The following infinite form of (1.2), also equivalent to both (1.1) and (1.2), (1.3)

i≥0 t i (i + 1) n = A n (t) (1 -t) n+1 (n ≥ 0)
is more of common usage today, while Euler's relation (1.2) seems to have been suprisingly forgotten. He also knew how to write the now called Taylor expansion of tan u as

tan u = n≥0 u 2n+1 (2n + 1)! T 2n+1 = u 1! + u 3 3! 2 + u 5 5! 16 + u 7 7! 272 + u 9 9! 7936 + u 11 11! 353792 + • • • (1.4) As tan u = 1 i 1 -e -2iu
1 + e -2iu , also equal to n≥1 u n n! i n-1 A n (-1) by (1.1), he derived the relations (1.5) A 2n (-1) = 0 (n ≥ 1); (-1) n A 2n+1 (-1) = T 2n+1 (n ≥ 0).

Since Euler both Eulerian polynomials A n (t) and tangent numbers T 2n+1 (n ≥ 0) have been given several combinatorial interpretations (see, e.g. [START_REF] Riordan | An Introduction to Combinatorial Analysis[END_REF], [START_REF] Stanley | Enumerative Combinatorics[END_REF] and [START_REF] Foata | Théorie géométrique des polynômes eulériens[END_REF], chap. 5 for a combinatorial proof of (1.5)). Also several q-analogs for both polynomials have been proposed, each of them having interesting geometric properties. The purpose of this paper is to derive a q-analog for (1.5). This means that a sequence of polynomials (A * n (t, q)) (n ≥ 0) is to be found having the following properties: (P 1) the coefficients of each polynomial A * n (t, q) are positive integers; (P 2) A * n (t, 1) = A n (t) (n ≥ 0); (P 3) A * 2n (-1, q) = 0 (n ≥ 1); (P 4) the coefficients of each polynomial (-1) n A * 2n+1 (-1, q) (n ≥ 0) are positive integers; (P 5) (-1) n A * 2n+1 (-1, 1) = T 2n+1 (n ≥ 0). Our second goal is to provide combinatorial interpretations for those two sequences of polynomials (A * n (t, q)), ((-1) n A * 2n+1 (-1, q)), compatible with what is already known for A n (t) and T 2n+1 . As we now see, the polynomials A * n (t, q), we have found, are slight variations of the classical qanalogs A n (t, q) of the Eulerian polynomials introduced by Carlitz [START_REF] Carlitz | q-Bernoulli and Eulerian numbers[END_REF]. The latter polynomials may be defined by the identity

(1.6) A n (t, q) (t; q) n+1 = j≥0 t j ([j + 1] q ) n (n ≥ 0), where (t; q) n+1 = (1-t)(1-tq) • • • (1-tq n ) and [j+1] q = 1+q+q 2 +• • •+q n
are the traditional q-ascending factorials and q-analogs of the positive integers. When q = 1, identity (1.6) is transformed into (1.3), so that

(1.7) A n (t, 1) = A n (t).
Let us reproduce the first values of the polynomials A n (t, q) (see [START_REF] Carlitz | q-Bernoulli and Eulerian numbers[END_REF], p. 336):

A 0 (t, q) = A 1 (t, q) = 1; A 2 (t, q) = 1 + tq; A 3 (t, q) = 1 + 2tq(q + 1) + t 2 q 3 ; A 4 (t, q) = 1 + tq(3q 2 + 5q + 3) + t 2 q 3 (3q 2 + 5q + 3) + t 3 q 6 ; A 5 (t, q) = 1 + tq(4q 3 + 9q 2 + 9q + 4) + t 2 q 3 (6q 4 + 16q 3 + 22q 2 + 16q + 6) + t 3 q 6 (4q 3 + 9q 2 + 9q + 4) + t 4 q 10 . Table 1.1. The Carlitz q-Eulerian Polynomials

The polynomials A * n (t, q) which meet our expectations are defined by:

A * 2n (t, q) = q ( n 2 ) A 2n (tq -n , q); (1.8) A * 2n+1 (t, q) = q ( n 2 ) A 2n+1 (tq -n , q); (1.9)
and our new q-tangent numbers by

T 2n+1 (q) = (-1) n A * 2n+1 (-1, q) = (-1) n q ( n 2 ) A 2n+1 (-q -n , q). (1.10)
The main result of this paper is the following theorem.

Theorem 1.1. Let T 2n+1 (q) be defined by (1.10). Then (a) T 2n+1 (q) is a polynomial; (b) its coefficients are positive integers;

(c) T 2n+1 (1) = T 2n+1 (the tangent number).

The proof of (a) is a consequence of Proposition 1.2 further stated. The proof of (b) is the most difficult part. It requires a long combinatorial development given in the next sections. The proof of (c) is easy:

T 2n+1 (1) = (-1) n A 2n+1 (-1, 1) [by (1.10)] = (-1) n A 2n+1 (-1) [by (1.7)] = T 2n+1 .
[by (1.5)]

Using Table 1.1 we can determine the first values of those new q-tangent numbers T 2n+1 (q): T 1 (q) = 1; T 3 (q) = 1 + q; T 5 (q) = 2 + 4q + 4q 2 + 4q 3 + 2q 4 ; T 7 (q) = 5 + 17q + 29q 2 + 39q 3 + 46q 4 + 46q 5 + 39q 6 + 29q 7 + 17q 8 + 5q 9 . Table 1.2. The new q-tangent numbers Of course, we recover the traditional tangent numbers: 1, 2, 16, 272, by replacing q by 1. They differ from the usual q-tangent numbers tan 2n+1 (q) occurring in the expansion of the ratio of the q-sine by the q-cosine introduced by Jackson [START_REF] Jackson | A basic-sine and cosine with symbolic solutions of certain differential equations[END_REF] (also see [START_REF] Andrews | Divisibility properties of the q-tangent numbers[END_REF], [START_REF] Foata | Further divisibility properties of the q-tangent numbers[END_REF], [START_REF] Gasper | Basic hypergeometric series[END_REF]p. 23

]) n≥0 u 2n+1 (q; q) 2n+1 tan 2n+1 (q) = n≥0 (-1) n u 2n+1 /(q; q) 2n+1 n≥0 (-1) n u 2n /(q; q) 2n ,
whose first values are tan 1 (q) = 1; tan 3 (q) = q + q 2 ; tan 5 (q) = q 2 + 2q 3 + 3q 4 + 4q 5 + 3q 6 + 2q 7 + q 8 ; tan 7 (q) = q 3 (1 + q) 2 (1 + q 2 )(1 + q 3 )(1 + q + 3q 2 + 2q 3 + 3q 4 + 2q 5 + 3q 6 + q 7 + q 8 ).

In a subsequent paper Carlitz [START_REF] Carlitz | A combinatorial property of q-Eulerian numbers[END_REF] obtained the following combinatorial interpretation for the polynomial A n (t, q). Let σ = σ(1)σ(2) • • • σ(n) be a permutation of 12 • • • n. The number of descents, des σ, (resp. major index, maj σ,) of the permutation σ is defined to be the number (resp. the sum) of all i's such that 1 ≤ i ≤ n -1 and σ(i) > σ(i + 1). The following result (1.11)

A n (t, q) = σ∈S n t des σ q maj σ (n ≥ 0) is due to him. From (1.11) and the definition of A * 2n+1 (t, q) given in (1.9) it follows that (1.12)

A * 2n+1 (t, q) = σ∈S 2n+1 t des σ q cmaj σ ,
where cmaj σ is the compressed major index of σ defined by

(1.13) cmaj σ = maj σ -n des σ + n(n -1)/2. Proposition 1.2. If σ ∈ S 2n+1 , then (1.14) 0 ≤ cmaj σ ≤ n 2 .
In particular, A * 2n+1 (t, q) is a polynomial of degree (n -1) in t and n 2 in q and T 2n+1 (q) is a polynomial (condition (a) of Theorem 1.1 holds).

Proof. We just verify:

min σ∈S 2n+1 (maj σ -n des σ) = min I={i 1 ,i 2 ,...,i d }⊂[2n] (i 1 + i 2 + • • • i d -nd) = min I={i 1 ,i 2 ,...,i d }⊂[2n] ((i 1 -n) + (i 2 -n) + • • • (i d -n)) = (1 -n) + (2 -n) + • • • (n -n) = -n(n -1)/2; max σ∈S 2n+1 (maj σ -n des σ) = max I={i 1 ,i 2 ,...,i d }⊂[2n] ((i 1 -n) + (i 2 -n) + • • • (i d -n)) = (n -n) + ((n + 1) -n) + • • • ((n + n) -n) = n(n + 1)/2.
Go back to the five properties (P 1)-(P 5) we wish to fulfill: (P 1) has been proved by Proposition 1.2. Also, (P 2) holds since A * n (t, 1) = A n (t, 1) = A n (t) by (1.7). (P 5) is condition (c) of Theorem 1.1 and has been proved. Let us deal with (P 3).

Proposition 1.3. For each n ≥ 1 we have: A * 2n (-1, q) = 0. Proof. One possibility is to go back to the other recurrence relations for the Carlitz polynomials A n (t, q) and extract an analytic proof. Feasible but cumbersome. We can instead use the following combinatorial argument based on (1.11). Let σ = σ(1)σ(2) • • • σ(2n) be a permutation of 12 • • • (2n) and let r σ be the reverse permutation r σ = σ(2n)

• • • σ(2)σ(1). If σ has j descents in positions d 1 , d 2 , . . . , d j (1 ≤ d 1 < d 2 < • • • < d j ≤ 2n -1), its major index, maj σ, is equal to d 1 + d 2 + • • • + d j .
Hence, the major index of r σ can be evaluated as maj

r σ = 1 + 2 + • • • + (2n -1) - (n -d 1 ) -(n -d 2 ) -• • • -(n -d j ). As des r σ = 2n -1 -j, we have -n des r σ + maj r σ = -n(2n -1 -j) + 1 + 2 + • • • + (2n -1) -(n -d 1 ) - (n -d 2 ) -• • • -(n -d j ) = -nj + d 1 + d 2 + • • • + d j = -n des σ + maj σ. Thus (-q -n ) des σ q maj σ = -(-q -n ) des r σ q maj r σ .
There remains to prove (P 4), that is, Theorem 1.1 (b). As a matter of fact, we will prove the following stronger result.

Theorem 1.4. The ratio d n (q) = T 2n+1 (q) (1 + q)(1 + q 2 ) • • • (1 + q n )
is a polynomial in q with positive integral coefficients.

Our proof will be of combinatorial nature, but the problem remains open for a true analytical one, which would use the very definition of the Carlitz q-Eulerian polynomials A n (t, q), in particular (1.6), from which we can derive:

A n (t, q) (t; q) n+1 = 1 (1 -q) n n k=0 n k (-1) k q k 1 -tq k , so that A * 2n+1 (t, q) (tq -n , q) 2n+1 = q n(n-1)/2 (1 -q) 2n+1 2n+1 k=0 2n + 1 k (-1) k q k 1 -tq -n q k . Hence T 2n+1 (q) (-q -n , q) 2n+1 = (-1) n q n(n-1)/2 (1 -q) 2n+1 2n+1 k=0 2n + 1 k (-1) k q k 1 + q -n q k .
and

T 2n+1 (q) (1 + q)(1 + q 2 ) • • • (1 + q n ) = (-1) n+1 (-1; q) n+2 (1 -q) 2n+1 2n+1 k=0 2n + 1 k (-1) k 1 + q k-n .
Theorem 1.4 asserts that the right-hand side of the last identity is a polynomial in q with integral positive coefficients. A direct proof would be welcome.

The first values of

d n (q) = T 2n+1 (q)/(1 + q)(1 + q 2 ) • • • (1 + q n ) are reproduced in Table 1.3. d 0 (q) = d 1 (q) = 1; d 2 (q) = 2 + 2q; d 3 (q) = 5 + 12q + 12q 2 + 5q 3 ; d 4 (q) = 14 + 56q + 110q 2 + 136q 3 + 110q 4 + 56q 5 + 14q 6 .
Table 1.3. The q-reduced tangent polynomials From Theorems 1.1 (c) and 1.4 it follows that d n (1) = T 2n+1 /2 n . Accordingly, the integers d n (1) are the reduced tangent numbers. Their exponential generating function is directly obtainable from (1.4) and reads:

√ 2 tan u √ 2 = n≥0 u 2n+1 (2n + 1)! d n (1) = u 1! 1 + u 3 3! 1 + u 5 5! 4 + u 7 7! 34 + u 9 9! 496 + u 11 11! 353792 + • • • (1.15)
The combinatorial set-up used in this paper is directly inspired from the models used in our previous statistical studies ( [START_REF] Han | Calcul Denertien[END_REF], [START_REF] Han | Une transformation fondamentale sur les réarrangements de mots[END_REF], [START_REF] Foata | Word straightening and q-Eulerian Calculus, Contemporary Mathematics, q-Series from a Contemporary Perspective[END_REF]). It can be described as follows. A doubloon of order (2n + 1) is a 2

× (n + 1)- matrix δ = a 0 a 1 ••• a n b 0 b 1 ••• b n such that the word a 0 a 1 • • • a n b n b n-1 • • • b 0 is a permutation of 012 • • • (2n + 1). Let D2n+1 (resp. D 0 2n+1 ) denote the set of all doubloons δ = a 0 a 1 ••• a n b 0 b 1 ••• b n of order (2n + 1) (resp. the subset of D2n+1 composed of all doubloons such that a 0 = 0). When δ = 0 a 1 ••• a n b 0 b 1 ••• b n belongs to D 0 2n+1 , the word ρ(δ) = a 1 • • • a n b n b n-1 • • • b 0 is called the reading of δ. Clearly, ρ provides a bijection of D 0 2n+1 onto S 2n+1 . When δ belongs to D 0 2n+1 , we simply define: des δ = des ρ(δ), maj δ = maj ρ(δ), cmaj δ = cmaj ρ(δ).
Now take advantage of the presentation of each doubloon as a two-row

matrix δ = a 0 a 1 ••• a n b 0 b 1 ••• b n for introducing the notions of interlacedness and normalizedness at each k (1 ≤ k ≤ n): the doubloon δ = a 0 a 1 ••• a n b 0 b 1 ••• b n is said to be interlaced (resp. normalized ) at k, if the sequence (a k-1 , a k , b k-1 , b k )
or one of its three cyclic rearrangements is monotonic increasing or decreasing (resp. decreasing). In the beginning of the next section it will be seen that out of the 4! = 24 possible orderings of the elements a k-1 , a k , b k-1 , b k there are four of them that make δ interlaced but not normalized at k (relations (I1)-(I4)) and four others that make δ normalized at k (relations (IN 1)-(IN 4)).

For instance, the doubloon δ = 0 2 4 3 5 7 1 6 of order 7 is interlaced (but not normalized) at 1, since 0 2 5 7 is increasing; interlaced (but not normalized) at 2, since the cyclic rearrangement 1 2 4 7 of 2 4 7 1 is increasing; normalized (and also interlaced) at 3, since the cyclic rearrangement 6 4 3 1 of 4 3 1 6 is decreasing.

When a doubloon of order (2n + 1) is interlaced (resp. normalized) at every k = 1, 2, . . . , n, we simply say that it is interlaced (resp. normalized ). Let I 0 2n+1 (resp. N 0 2n+1 ) denote the set of all doubloons from D 0 2n+1 , which are interlaced (resp. normalized).

Theorem 1.5. The polynomial T 2n+1 (q) is the generating function for the set I 0 2n+1 of interlaced doubloons by "cmaj":

(1.16) T 2n+1 (q) = δ∈I 0 2n+1 q cmaj δ .
Theorem 1.6. The following factorization holds

(1.17)

δ∈I 0 2n+1 q cmaj δ = (1 + q)(1 + q 2 ) • • • (1 + q n ) δ∈N 0 2n+1 q cmaj δ ,
so that the polynomial d n (q) is the generating function for the set N 0 2n+1 of normalized doubloons by "cmaj":

(1.18) d n (q) = δ∈N 0 2n+1 q cmaj δ .
The rest of the paper is devoted to proving the previous two theorems, which give combinatorial interpretations to T 2n+1 (q) and d n (q) and evidently imply Theorems 1.1 and 1.4.

There is one normalized doubloon of order 3, namely 03 21 , whose "cmaj" is null, the other interlaced doubloon being 0 1 2 3 with a "cmaj" equal to 1. Hence, d 1 (q) = 1 and T 3 (q) = 1 + q. In Table 1.4 are displayed the sixteen interlaced doubloons of order 5 with the values of their "cmaj" next to them. The top row contains the four normalized doubloons of order 5. Hence, d 2 (q) = 2 + 2q, T 5 (q) = (1 + q)(1 + q 2 )(2 + 2q). 0 5 3 4 2 1 , 0 0 4 2 3 1 5 , 1 0 5 4 3 2 1 , 0 0 4 3 2 1 5 , 1 0 5 1 4 2 3 , 1 0 4 5 3 1 2 , 2 0 5 1 3 2 4 , 1 0 4 5 2 1 3 , 2 0 2 3 4 5 1 , 3 0 1 2 3 4 5 , 4 0 2 4 3 5 1 , 3 0 1 3 2 4 5 , 4 0 2 1 4 5 3 , 2 0 1 5 3 4 2 , 3 0 2 1 3 5 4 , 2 0 1 5 2 4 3 , 3 Table 1.4. The set I 0 5 of interlaced doubloons of order 5

Geometry of doubloons

Let δ = a 0 a 1 ••• a n b 0 b 1 •••
b n be a doubloon and for each k = 1, 2, . . . , n write the four relations that make δ be normalized at k (conditions (IN 1)-(IN 4)), and the four relations making δ be interlaced but not normalized at k (conditions (I1)-(I4)):

(IN 1) b k < b k-1 < a k < a k-1 ; (I1) a k < b k-1 < b k < a k-1 ; (IN 2) b k-1 < a k < a k-1 < b k ; (I2) b k-1 < b k < a k-1 < a k ; (IN 3) a k < a k-1 < b k < b k-1 ; (I3) b k < a k-1 < a k < b k-1 ; (IN 4) a k-1 < b k < b k-1 < a k ; (I4) a k-1 < a k < b k-1 < b k .
We next introduce a class of transformations φ k (0 ≤ k ≤ n) on D2n+1 , called micro flips, which simply permute the entries in a given column. For 0 ≤ k ≤ n define:

φ k : a 0 • • • a k-1 a k a k+1 • • • a n b 0 • • • b k-1 b k b k+1 • • • b n → a 0 • • • a k-1 b k a k+1 • • • a n b 0 • • • b k-1 a k b k+1 • • • b n .
Two doubloons δ, δ ′ are said to be equivalent, if there is a sequence

φ i 1 , φ i 2 , . . . , φ i k of micro flips such that δ ′ = φ i 1 φ i 2 • • • φ i k (δ).
Proposition (e) Every doubloon equivalent to an interlaced doubloon is also interlaced.

(f ) Each equivalence class of interlaced doubloons contains one and only one normalized doubloon and there is an explicit algorithm for reaching it. Condition (e) is a consequence of (c) and (d). For (f ) let l be the smallest integer at which an interlaced doubloon δ = a 0 a 1 ••• a n b 0 b 1 ••• b n is not normalized. By (c) the doubloon φ l (δ) is normalized at 1, 2, . . . , l. Continue the process until reaching a doubloon normalized at all integers 1, 2, . . . , n. Finally, (g) follows from the fact that each equivalence class can be generated from an interlaced doubloon δ from the set I 0 2n+1 by applying the n involutions φ 1 , φ 2 , . . . , φ n to δ, independently.

For comparing two adjacent biletters

a k-1 b k-1 and a k b k (1 ≤ k ≤ n) of a doubloon δ = a 0 a 1 ••• a n b 0 b 1 ••• b n we define: shape k (δ) = > > (resp. > < , resp. < < , resp. < > ), if a k-1 > a k and b k-1 > b k (resp. a k-1 > a k and b k-1 < b k , resp. a k-1 < a k and b k-1 < b k , resp. a k-1 < a k and b k-1 > b k ).
We also define shape n+1 (δ) = ∨ or ∧ depending on whether a n > b n or a n < b n . The word shape 1 (δ) shape 2 (δ) • • • shape n (δ) is called the shape of δ and denoted by shape δ.

For example, if δ = 0 8 1 6 9 7 4 5 3 2 , then shape(δ) = < > < < > < > > and shape 5 (δ) = ∨. Now go back to the conditions (IN i)'s and (Ii)'s and determine shape k in each one of those eight cases. We obtain:

(IN 1) > > ; (IN 2) > < ; (IN 3) > > ; (IN 4) < > ; (I1) > < ; (I2) < < ; (I3) < > ; (I4) < < .
As (Ii) holds for δ whenever (IN i) does for φ k (δ), we can express the change of shape k when φ k is applied to δ by the diagram displayed in Fig. 2.1.

> > © > < d d d d d d s © < > d d d d d d s < <

Fig. 2.1. The interlaced case

The same study is to be done for each non interlaced doubloon. There are sixteen reorderings of the sequence (a k-1 , a k , b k-1 , b k ) that make the doubloon δ non-interlaced at k. In Fig. 2.2 only eight of them have been listed. As non-interlacedness is preserved under φ k by Proposition 2.1 (c), the other eight are indeed obtained by applying the micro flip φ k . Again, the content ot the table may be summarized by the diagram displayed in Fig. 2.3. Notice that each shape may be preserved under φ k (symbolized by the fixed point T ) and the only possible change occurs between the shapes > < and < > .

case : shape k (δ) shape k φ k (δ) b k < b k-1 < a k-1 < a k : < > > < a k-1 < a k < b k < b k-1 : < > < > b k-1 < b k < a k < a k-1 : > < > < a k < a k-1 < b k-1 < b k : > < < > b k < a k < b k-1 < a k-1 : > > > > a k < b k < a k-1 < b k-1 : > > > > b k-1 < a k-1 < b k < a k : < < < < a k-1 < b k-1 < a k < b k : < < < <

Fig. 2.2. The sixteen non interlaced orderings

Finally, we introduce the macro flip Φ k as

(2.1) Φ k (δ) = φ k φ k+1 • • • φ n (δ).
Again, the macro flip Φ k is an involution and also preserves interlacedness.

> > T T c > < < > T T < < T Fig. 2.3.
The non-interlaced case

Statistics on shapes

The next step is to study the action of the involution Φ k onto the pair of statistics (des, cmaj). As those two statistics essentially depend on the doubloon shapes, it is convenient to study the action on the shapes themselves. To that end we introduce the notion of full shape in the following manner. If δ belongs to I 0 2n+1 , its full shape is obtained by juxtaposing shape n+1 (δ) to the right of its shape, as defined just after the proof of Proposition 2.1. For example, the full shape of the interlaced doubloon δ = 0 8 1 6 9 7 4 5 3 2 is represented by

T = < > < < > < > > ∨ .
The full shape T of a doubloon δ from I 0 2n+1 has then n columns with two signs, followed by one single symbol. The statistics "des", "maj" and "cmaj" for the full shape T are defined by des T = des ρ(δ), maj T = maj ρ(δ) and cmaj T = cmaj ρ(δ).

If δ = 0 a 1 ... a n b 0 b 1 ... b n and if the k-th column of the full shape

T of δ is > < (1 ≤ k ≤ n), this means that a k-1 > a k and b k-1 < b k . Furthermore, b k is the (2n-k+1)-st term of the permutation ρ(δ) = a 1 • • • a k-1 a k • • • b k b k-1 • • • b 0 , so that the contribution of that k-th column to maj T is k-1+(2n-k+1) = 2n
. The remark will be used in the next lemmas.

Lemma 3.1. Let T be a full shape and S be obtained from T by permuting two symbols in the same column. Then (-1) des T = (-1) des S and cmaj T = cmaj S.

Proof. Only one case is to consider. Suppose that the k-th column of T (resp. of S) is > < (resp. < > ). Clearly, des T = des S + 2. Moreover, maj T = maj S + 2n. Hence, cmaj T = maj Tn des T + n(n -1)/2 = maj S + 2nn(des S + 2) + n(n -1)/2 = cmaj S. Lemma 3.2. Let T be a full shape and S be obtained from T by changing the value of the rightmost single symbol. Then (-1) des T = -(-1) des S and cmaj T = cmaj S.

Proof. Suppose that the rightmost single symbol of T (resp. of S) is ∨ (resp. ∧). Clearly, des T = des S + 1. Since

cmaj T = (• • • + n + • • •) -n des T + n(n -1)/2, cmaj S = (• • • + 0 + • • •) -n des S + n(n -1)/2, we have cmaj T = cmaj S.
Lemma 3.3. Let T be a full shape, whose k-th column is > < or < > . Let S be obtained from T by changing the k-th column into > > . Then

(-1) des T = -(-1) des S and cmaj T -cmaj S = n -i + 1.
Proof. If the k-th column of T is > < , then des T = des S + 1. Moreover, with j = 2nk + 1 we have:

cmaj T = (• • • + k -1 + • • • + j + • • •) -n des T + n(n -1)/2 = (• • • + k -1 + • • • + 0 + • • •) + j -n(des S + 1) + n(n -1)/2 = cmaj S + j -n = cmaj S + n -k + 1.
For the second case we just appeal to Lemma 3.1. Lemma 3.4. Let T be a full shape, whose k-th column is < < . Let S be obtained from T by changing the k-th column into > < or < > . Then

(-1) des T = -(-1) des S and cmaj T -cmaj S = n -k + 1. Proof. If the k-th column is changed into > < , then des T = des S -1. With j = 2n -k + 1 we have cmaj T = (• • • + 0 + • • • + j + • • •) -n des T + n(n -1)/2 = (• • • + k -1 + • • • + j + • • •) -k + 1 -n(des S -1) + n(n -1)/2 = cmaj S + n -k + 1.
Again it is sufficient to appeal to Lemma 3.1 to cover the second case.

The macro flips Φ k have been defined in (2.1). They are involutions and preserve the interlacedness. They play a crucial role in the next theorem.

Theorem 3.5. Let δ = 0 a 1 ... a n b 0 b 1 ... b n belong to D 0 2n+1 and 1 ≤ k ≤ n be an integer.

(1) If δ is normalized at k, then

(3.1) (-1) des Φ k (δ) = (-1) des δ ; cmaj Φ k (δ) -cmaj δ = n -k + 1; (2) If δ is non-interlaced at k, then (3.2) (-1) des Φ k (δ) = -(-1) des δ ; cmaj Φ k (δ) = cmaj δ.
Proof. Apply the macro flip Φ k = φ k • • • φ n to δ and compare the shapes of δ and Φ k (δ). First, φ n leaves "cmaj" invariant and changes the parity of "des" by Lemma 3.2. Next, φ n-1 , . . . , φ i+1 leave both "des" and "cmaj" invariant by Lemma 3.1, so that (-1) des Φ k+1 (δ) = -(-1) des δ and cmaj Φ k+1 (δ) = cmaj δ. Note that shape k δ = shape k φ k+1 • • • φ n (δ), as φ n , . . . , φ k+1 have no action on the columns of rank (k -1) and k (the k-th and (k + 1)-st columns). Also shape

k φ k (δ) = shape k φ k+1 • • • φ n φ k (δ) = shape k φ k φ k+1 • • • φ n (δ) = shape k Φ k (δ).
In case (1) there are two possibilities: either shape k δ = > > (cases (IN 1) and (IN 3)), or shape k φ k (δ) = < < (cases (IN 2) and (IN 4)). When shape k δ = > > (resp. shape k φ k (δ) = < < ), then shape k Φ k (δ) = shape k φ k (δ) = < > or > < according to Fig. 2.1 (resp. shape k Φ k (δ) = shape k φ k (δ) = < < ). By Lemma 3.3 (resp. Lemma 3.4) the parity of "des" is modified when going

from Φ k (δ) to φ k Φ k (δ) = Φ k+1 (δ) and cmaj Φ k (δ) -cmaj Φ k+1 (δ) = n - k+1. Hence (-1) des Φ k (δ) = -(-1) des Φ k+1 (δ) = (-1) des δ and cmaj Φ k (δ) = cmaj Φ k+1 (δ) + n -k + 1 = cmaj δ + n -k + 1.
In case 2 look at Fig. 2.3 and apply Lemmas 3.1 and 3.2. The only change is the parity of "des." 4. Proofs of Theorems 1.5 and 1.6 Let δ belong to D 0 2n+1 and σ = ρ(δ) be its reading. Recall that the statistics "des", "maj" and "cmaj" for δ are defined by (4.1) des δ = des σ, maj δ = maj σ and cmaj δ = cmaj σ.

From the definition of A * 2n+1 (t, q) (given in (1.12)) and the fact that ρ is a bijection of D 0 2n+1 onto S 2n+1 we can write:

A * 2n+1 (t, q) = δ∈D 0 2n+1 t des δ q cmaj δ = δ∈I 0 2n+1 t des δ q cmaj δ + δ∈D 0 2n+1 \I 0 2n+1
t des δ q cmaj δ , so that

T 2n+1 (q) = (-1) n A * 2n+1 (-1, q) = δ∈I 0 2n+1 (-1) n+des δ q cmaj δ + δ∈D 0 2n+1 \I 0 2n+1 (-1) n+des δ q cmaj δ . (4.2) Lemma 4.1. Let δ ∈ I 0 2n+1 . Then (4.3) (-1) des δ = (-1) n .
Proof. First, des 0 1 2 3 = des(0 1 3 2) = 1, so that (4.3) holds for n = 1. Let n ≥ 2 and δ = 0 ... From (4.2) and (4.3) we deduce:

(4.4) T 2n+1 (q) = δ∈I 0 2n+1 q cmaj δ + δ∈D 0 2n+1 \I 0 2n+1
(-1) n+des δ q cmaj δ .

Theorem 1.5 will be proved once we construct a sign-reversing involution on D 0 2n+1 \ I 0 2n+1 that makes the second sum vanish. The sign-reversing involution. For each doubloon δ = a 0 a 1 ... a n b 0 b 1 ... b n from the set D 0 2n+1 \ I 0 2n+1 there exists at least one integer k at which δ is noninterlaced. Let k(δ) be the smallest integer satisfying that condition.

Theorem 4.2. The mapping Φ k(δ) : δ → Φ k(δ) (δ) is a sign-reversing involution on D 0 2n+1 \ I 0 2n+1 . Proof. This is an immediate consequence of Theorem 3.5, formulas (3.2).

Proof of Theorem 1.6. Let δ be a normalized doubloon from N 0 2n+1 . By Proposition 2.1 the set of all the 2 n interlaced doubloons equivalent to δ may be expressed as

{Φ i 1 Φ i 2 • • • Φ i k (δ) : 1 ≤ i 1 < i 2 < • • • < i k ≤ n}. As Φ i k (δ) (resp. Φ i k-1 Φ i k (δ), . . . , resp. Φ i 2 • • • Φ i k-1 Φ i k (δ)) is normalized at i k-1 , (resp. at i k-2 , . . . , resp. at i 1 ), it follows from (3.2) that cmaj Φ i 1 Φ i 2 • • • Φ i k (δ) = cmaj Φ i 2 • • • Φ i k (δ) + n -i 1 + 1 = cmaj Φ i 3 • • • Φ i k (δ) + n -i 2 + 1 + n -i 1 + 1 = • • • = cmaj δ + n -i k + 1 + • • • + n -i 1 + 1. Hence α equiv δ q cmaj α = q cmaj Φ i 1 Φ i 2 •••Φ i k (δ) (1 ≤ i 1 < i 2 < • • • < i k ≤ n) = q cmaj δ q n-i k +1+•••+n-i 1 +1 (1 ≤ i 1 < • • • < i k ≤ n) = q cmaj δ (1 + q)(1 + q 2 ) • • • (1 + q n ).
By (4.4) we can write

T 2n+1 (q) = (-1) n A * 2n+1 (-1, q) = α∈I 0 2n+1 q cmaj α = δ∈N 0 2n+1 α equiv δ q cmaj α = (1 + q)(1 + q 2 ) • • • (1 + q n ) δ∈N 0 2n+1 q cmaj δ .

Constant terms and Catalan numbers

Referring to Table 1.2 we see that T 1 (0) = T 3 (0) = 1, T 5 (0) = 2, T 7 (0) = 5 and we would find T 9 (0) = 14. The sequence 1, 1, 2, 5, 14 is indeed the beginning of the sequence of Catalan numbers. This is true for all n as stated in the next theorem. Proof. From (1.16) T 2n+1 (0) = #{σ ∈ S 2n+1 , cmaj σ = 0}. Let {i 1 , i 2 , . . . , i d } be the descent set of a permutation σ from S 2n+1 . Then, maj σn des σ = (i

1 + i 2 + • • • i d -nd) = (i 1 -n) + (i 2 -n) + • • • (i d -n) = -n(n -1)/2 = (1 -n) + (2 -n) + • • • ((n -1) -n) + (n -n) (5.2) = (1 -n) + (2 -n) + • • • ((n -1) -n).
(5.3) Accordingly, the descent set of σ is either [n] = {1, 2, . . . , n} by (5.2), or [n -1] = {1, 2, . . . , n -1} by (5.3). The number of permutations of order 2n + 1 whose descent set is [n] (resp. [n -1]) is equal to 2n n (resp. 2n n-1 ). Hence,

T 2n+1 (0) = (-1) n σ∈S 2n+1 (-1) des σ 0 cmaj σ = 2n n - 2n n -1 = 1 n + 1 2n n .
As a summary we have:

> > ••• > > > > ••• > ∨ or < > > ••• > > > > ••• > ∧.
As δ is interlaced at every k = 1, 2, . . . , n, the following inequalities a 1 > b 0 > b 1 , a 1 > a 2 > b 1 > b 2 , . . . , a n-1 > a n > b n-1 > b n hold and may be represented by the poset:

n = a 1 > a 2 > • • • > a n ∨ ∨ • • • ∨ b 0 > b 1 > • • • > b n-1 = 1 .
This establishes a bijection between those doubloons and the above posets, which belong to the list of combinatorial models counted by the Catalan numbers [START_REF] Stanley | Enumerative Combinatorics[END_REF]p. 227].

Concluding remarks

Besides the traditional q-tangent number, tan 2n+1 (q), already mentioned in the Introduction, other q-analogs of the tangent have been proposed, in particular by Prodinger [START_REF] Prodinger | Combinatorics of geometrically distributed random variables: new q-tangent and q-secant numbers[END_REF][START_REF] Prodinger | A Continued Fraction Expansion for a q-Tangent Function: an Elementary Proof[END_REF] (also see [START_REF] Fulmek | A continued fraction expansion for a q-tangent function[END_REF]) and Han et al. [START_REF] Han | Un autre q-analogue des nombres d'Euler, The Andrews Festschrift[END_REF]. For those two cases the emphasis has been the search for adequate continued fraction expansions of those new functions.

In the Introduction each doubloon a 0 a 1 ••• a n b 0 b 1 ••• b n was said to be interlaced at k if the sequence (a k-1 , a k , b k-1 , b k ) or one of its three cyclic rearrangements was monotonic increasing or decreasing. Another equivalent definition that was successfully used in [START_REF] Han | Une transformation fondamentale sur les réarrangements de mots[END_REF] The doubloon model described in this paper serves to interpret the two q-analogs T 2n+1 (q) of T 2n+1 and d n (q) of t n . A refinement of the doubloon model will be proposed in our next paper [START_REF] Foata | The doubloon polynomial triangle[END_REF]; it will provide a refinement d n,j (q) of the polynomials d n (q), so that identities (5.5) and (5.6) will be extended to classical double-digit sequences of numbers: Catalan triangle [Sl07, sequence A009766] and Poupard triangle [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF].

  (g) Each equivalence class of interlaced doubloons from I 0 2n+1 contains 2 n doubloons. Proof. Conditions (a) and (b) are obvious. For (c) just observe that each doubloon δ satisfies (IN i) if and only if (Ii) holds for φ k (δ) (i = 1, 2, 3, 4). For (d) verify that condition (IN 1) (resp. (IN 2), resp. (IN 3), resp. (IN 4)), with (k + 1) replacing k, holds if and only if (I3) (resp. (I4), resp. (I1), resp. (I2)), with (k + 1) replacing k, holds for φ k (δ).

  a n-1 a n b 0 ... b n-1 b n ∈ I 0 2n+1 . Then δ ′ = 0 ... a n-1 b 0 ... b n-1 is an interlaced doubloon on the alphabet [0, 2n+1]\{a n , b n } (instead of [0, 2n-1]) and des δ ′ = (-1) n-1 by induction. As δ is interlaced at n, the eight orderings to consider for the sequence (a n-1 , a n , b n-1 , b n ) are the eight orderings (IN i), (Ii) (i = 1, 2, 3, 4) described in the beginning of Section 2. If a n-1 < b n-1 , then des δ = des δ ′ + des(a n-1 a n b n b n-1 ) = des δ ′ + 1. If a n-1 > b n-1 , then des δ = δ ′ -1 + des(a n-1 a n b n b n-1 ) = des δ ′ -1 + 2 = des δ ′ + 1.

Theorem 5. 1 .

 1 For all n ≥ 0 (5.1)T 2n+1 (0) = 1 n + 1 2n n(the Catalan number).

T

  2n+1 (1) = T 2n+1 (the tangent number);(5.4)T 2n+1 (0) = d n (0d n (1) = t n (the reduced tangent number). (5.6) Remark. Each doubloon δ = 0 a 1 ••• a n b 0 b 1 ••• b nsuch that cmaj δ = 0 has a full shape of the form <

  is based on the notion of cyclic interval.The cyclic interval [[a k-1 , b k-1 [[ is defined as the semi-open interval [a k-1 , b k-1 ) if a k-1 < b k-1 and as the union [a k-1 , +∞) ∪ (-∞, b k-1 )otherwise. It is readily seen that the doubloon is interlaced at k if and only if exactly one of the entries a k , b k belongs to the cyclic interval [[a k-1 , b k-1 [[.

  2.1. The following conditions hold: (a) Each micro flip is an involution. (b) The micro flips commute with each other. (c) Each doubloon δ is normalized at k if and only if φ k (δ) is interlaced but not normalized at k.

(d) Each doubloon δ is normalized at (k + 1) if and only if φ k (δ) is interlaced but not normalized at (k + 1).


Dominique Foata

Guo-Niu Han Dedicated

George Andrews

The doubloon polynomial triangle

Keywords: Doubloon polynomials, doubloon polynomial triangle, Poupard triangle, Catalan triangle, reduced tangent numbers. Mathematics Subject Classifications. 05A15, 05A30, 33B10

The doubloon polynomials are generating functions for a class of combinatorial objects called normalized doubloons by the compressed major index. They provide a refinement of the q-tangent numbers and also involve two major specializations: the Poupard triangle and the Catalan triangle.

Introduction

The doubloon ( * ) polynomials d n,j (q) (n ≥ 1, 2 ≤ j ≤ 2n) introduced in this paper serve to globalize the Poupard triangle [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF] and the classical Catalan triangle [START_REF] Sloane | On-line Encyclopedia of Integer Sequences[END_REF]. They also provide a refinement of the q-tangent numbers, fully studied in our previous paper [START_REF] Foata | Doubloons and new q-tangent numbers[END_REF]. Finally, as generating polynomials for the doubloon model, they constitute a common combinatorial set-up for the above integer triangles. They may be defined by the following recurrence: (D1) d 0,j (q) = δ 1,j (Kronecker symbol); (D2) d n,j (q) = 0 for n ≥ 1 and j ≤ 1 or j ≥ 2n + 1; (D3) d n,2 (q) = j q j-1 d n-1,j (q) for n ≥ 1;

(D4) d n,j (q) -2 d n,j-1 (q) + d n,j-2 (q) = -(1q) j-3 i=1 q n+i+1-j d n-1,i (q)

-(1 + q n-1 ) d n-1,j-2 (q) + (1q) 2n-1 i=j-1 q i-j+1 d n-1,i (q) for n ≥ 2 and 3 ≤ j ≤ 2n.

The polynomials d n,j (q) (n ≥ 1, 2 ≤ j ≤ 2n) are easily evaluated using (D1)-(D4) and form the doubloon polynomial triangle, as shown in Fig. 1.1 and 1.1 ′ . d 1,2 (q) d 2,2 (q) d 2,3 (q) d 2,4 (q) d 3,2 (q) d 3,3 (q) d 3,4 (q) d 3,5 (q) d 3,6 (q) d 4,2 (q) d 4,3 (q) d 4,4 (q) d 4,5 (q) d 4,6 (q) d 4,7 (q) d 4,8 (q) Fig. 1.1. The doubloon polynomial triangle d 1,2 (q) = 1; d 2,2 (q) = q; d 2,3 (q) = q + 1; d 2,4 (q) = 1; d 3,2 (q) = 2q 3 +2q 2 ; d 3,3 (q) = 2q 3 +4q 2 +2q; d 3,4 (q) = q 3 +4q 2 +4q+1; d 3,5 (q) = 2q 2 + 4q + 2; d 3,6 (q) = 2q + 2; d 4,2 (q) = 5q 6 +12q 5 +12q 4 +5q 3 ; d 4,3 (q) = 5q 6 +17q 5 +24q 4 +17q 3 +5q 2 ; d 4,4 (q) = 3q 6 + 15q 5 + 29q 4 + 29q 3 + 15q 2 + 3q; d 4,5 (q) = q 6 + 9q 5 + 25q 4 + 34q 3 + 25q 2 + 9q + 1; d 4,6 (q) = 3q 5 + 15q 4 + 29q 3 + 29q 2 + 15q + 3; d 4,7 (q) = 5q 4 + 17q 3 + 24q 2 + 17q + 5; d 4,8 (q) = 5q 3 + 12q 2 + 12q + 5. Notice the different symmetries of the coefficients of the polynomials d n,j (q), which will be fully exploited in Section 4 (Corollaries 4.3, 4.7, 4.8). Various specializations are displayed in Fig. 1.2 below, where C n = 1 2n+1 2n n stands for the celebrated Catalan number and t n for the reduced tangent number occurring in the Taylor expansion

√ 2 tan(u/ √ 2) = n≥0 u 2n+1 (2n + 1)! t n = u 1! 1 + u 3 3! 1 + u 5 5! 4 + u 7 7! 34 + u 9 9! 496 + u 11 11! 11056 + • • • (1.1)
The symbol Σ attached to each vertical arrow has the meaning "make the summation over j" and d n (q) is the polynomial further defined in (1.3).

When q = 1, the (D1)-(D4) recurrence becomes (P 1) d 0,j (1) = δ 0,j (Kronecker symbol); (P 2) d n,j (1) = 0 for n ≥ 1 and j ≤ 1 or j ≥ 2n + 1;

(P 3) d n,2 (1) = j d n-1,j (1) for n ≥ 1; (P 4) d n,j (1) -2 d n,j-1 (1) + d n,j-2 (1) = -2 d n-1,j-2 (1)
for n ≥ 2 and 3 ≤ j ≤ 2n, which is exactly the recurrence introduced by Christiane Poupard [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF]. The integers d n,j (1) are easily evaluated using (P 1)-(P 4) and form the Poupard triangle, as shown in Fig. 1.3. When q = 0, relation (D4) becomes:

d n,j (0) -2 d n,j-1 (0) + d n,j-2 (0) = -d n-1,j-2 (0) + d n-1,j-1 (0),
which can be rewritten as

d n,j (0) -d n,j-1 (0) -d n-1,j-1 (0) = d n,j-1 (0) -d n,j-2 (0) -d n-1,j-2 (0), so that by induction d n,j (0) -d n,j-1 (0) -d n-1,j-1 (0) = d n,2 (0) = j q j-1 d n-1,j | q=0 = 0
using (D2) and (D3) when n ≥ 2. Consequently, the integers d n,j (0) satisfy the recurrence relation

(C1) d n,j (0) = d n,j-1 (0) + d n-1,j-1 (0)
for n ≥ 2 and 3 ≤ j ≤ 2n with the initial conditions

d n,n+1 (0) = 1 (n ≥ 1); (C2) d n,j (0) = 0 (n ≥ 1 and j ≤ 1 or j ≥ 2n + 1); d n,2 (0) = d n,3 (0) = • • • = d n,n (0) = 0 (n ≥ 2).
In view of (C1) and (C2) the integers d n,j (0) (n ≥ 1, n + 1 ≤ j ≤ 2n) obey the rules of the classical Catalan triangle that has been studied by many authors (see the sequence A00976 in Sloane [START_REF] Sloane | On-line Encyclopedia of Integer Sequences[END_REF] and its abundant bibliography). They form the Catalan triangle displayed in Fig. 1.4. 1 0 1 1 0 0 1 2 2 0 0 0 1 3 5 5 0 0 0 0 1 4 9 14 14 0 0 0 0 0 1 5 14 28 42 42 For each n ≥ 0 let A n (t, q) be the Carlitz [START_REF] Carlitz | q-Bernoulli and Eulerian numbers[END_REF][START_REF] Carlitz | A combinatorial property of q-Eulerian numbers[END_REF] q-analog of the Eulerian polynomial defined by the identity

(1.2) A n (t, q) (t; q) n+1 = j≥0 t j ([j + 1] q ) n , where (t; q) n+1 = (1-t)(1-tq) • • • (1-tq n ) and [j+1] q = 1+q+q 2 +• • •+q n
are the traditional q-ascending factorials and q-analogs of the positive integers.

The polynomial d n (q) under study was introduced in [START_REF] Foata | Doubloons and new q-tangent numbers[END_REF]. It is defined by

(1.3) d n (q) = (-1) n q ( n 2 ) A 2n+1 (-q -n , q) (1 + q)(1 + q 2 ) • • • (1 + q n ) .
It was shown to be a polynomial of degree n-1 2 , with positive integral coefficients, having the following two properties:

d n (1) = t n ; (1.4) d n (0) = C n (n ≥ 0); (1.5) (see the bottom row in the diagram of Fig. 1.2.)
The first values of the polynomials d n (q) are: d 0 (q) = d 1 (q) = 1; d 2 (q) = 2 + 2q; d 3 (q) = 5 + 12q + 12q 2 + 5q 3 ; d 4 (q) = 14 + 56q + 110q 2 + 136q 3 + 110q 4 + 56q 5 + 14q 6 .

The main purpose of this paper is to prove the following theorem.

Theorem 1.1. Let (d n,j (q)) be the set of polynomials defined by (D1)-(D4) and d n (q) be defined by (1.3). Then, the following identity holds

(1.6) j d n,j (q) = d n (q).
In other words, the diagram in Fig. 1.2 is commutative.

Even for q = 1 identity (1.6), which then reads j d n,j (1) = t n , is not at all straightforward. It was elegantly proved by Christiane Poupard [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF] by means of the bivariable generating function

(1.7) Z(u, v) = 1 + n≥1 1≤l≤2n-1 u 2n-l (2n -l)! v l l! d n,l+1 (1).
She even obtained the following stronger result

Z(u, v) = cos((u -v)/ √ 2) cos((u + v)/ √ 2) , (1.8) so that ∂ ∂u Z(u, v) {v=0} = n≥1 u 2n-1 (2n -1)! d n,2 (1) = √ 2 tan(u/ √
2), (1.9) which proves j d n,j (1) = t n by appealing to (P 3).

Finally, she obtains a combinatorial interpretation for the polynomial (1.10) d n (s, 1) = j d n,j (1) s j in terms of strictly ordered binary trees, or in an equivalent manner, of André permutations which are also alternating (see, e.g. [START_REF] Foata | Nombres d'Euler et permutations alternantes[END_REF], [START_REF] Foata | Nombres d'Euler et permutations alternantes[END_REF], [START_REF] Foata | Euler numbers and variations of permutations[END_REF]).

For q = 0 identity (1.6) reads j d n,j (0

) = C n = 1 n+1 2n
n . This is a consequence of the identities

d n,2n (0) = j d n-1,j (0); (1.11) d n,j (0) = j -2 n -1 - j -2 n = 2n -j + 1 n j -2 n -1 ; (1.12) so that, in particular, d n,2n (0) = 1 n 2n -2 n -1 = C n-1 ; (1.13)
easily obtained from (C1) and (C2) by induction and iteration, as well as an expression for the generating function

(1.14) n≥1 u n j d n,j (0)v j = 1 1 -v -uv uv 2 - v 2 1 -1 -4uv 2 .
Again, the reader is referred to the excellent commented bibliography about the sequence A009766 in Sloane's On-Line Encyclopedia of Integer Sequences [START_REF] Sloane | On-line Encyclopedia of Integer Sequences[END_REF], in particular the contributions made by David Callan [START_REF] Callan | A reference given in On-Line Encyclopedia of Integer Sequences for the sequence A009766[END_REF] and Emeric Deutsch [START_REF] Deutsch | A reference given in On-Line Encyclopedia of Integer Sequences for the sequence A009766[END_REF], where identities (1.11)-(1.14) are actually derived with other initial conditions. The proof of Theorem 1.1 will be of combinatorial nature. In our previous paper [START_REF] Foata | Doubloons and new q-tangent numbers[END_REF] we proved that each polynomial d n (q) was a polynomial with positive integral coefficients by showing that it was the generating function for the class N 0 2n+1 of permutations called normalized doubloons, by an integral-valued statistic "cmaj" called the compressed major index:

(1.15) d n (q) = δ∈N 0 2n+1 q cmaj δ .
In particular, d n (1) = # N 0 2n+1 = t n by (1.4). Normalized doubloon and "cmaj" will be fully described in Section 2. Here we just recall that each normalized doubloon δ ∈ N 0 2n+1 is a two-row matrix δ =

a 0 a 1 ••• a n b 0 b 1 ••• b n , where the word ρ(δ) = a 0 a 1 • • • a n b n b n-1 • • • b 0 is a permuta- tion of 012 • • • (2n + 1
) having further properties that will be given shortly.

The set of all normalized doubloons

δ = a 0 a 1 ••• a n b 0 b 1 ••• b n such that b 0 = j is denoted by N 0 2n+1,j .
It will be shown that N 0 2n+1,j is an empty set for j = 0, 1 and 2n + 1, so that the subsets N 0 2n+1,j (j = 2, 3, . . . , 2n) form a partition of N 0 2n+1 . Consequently, the following identity holds:

(1.16)

d n (q) = 2n j=2 δ∈N 0 2n+1,j q cmaj δ .
Accorgingly, Theorem 1.1 is a simple corollary of the next theorem.

Theorem 1.2. Let (d n,j (q)) be the set of polynomials in one variable q defined by (D1)-(D4). Then d n,j (q) is the generating polynomial for N 0 2n+1,j by the compressed major index. In other words,

(1.17) d n,j (q) = δ∈N 0 2n+1,j q cmaj δ .
To prove that the polynomial d n,j (q), as expressed in (1.17), satisfies (D4), symmetry properties must be derived (see Corollaries 4.3, 4.7 and 4.8). This requires a careful geometric study of those doubloons and how the statistic "cmaj" evolves. All this is developed in Sections 3 and 4. The proof of the recurrence is completed in Section 5 and in the final Section concluding remarks are made.

Doubloons

A doubloon of order 2n + 1 is a 2 × (n + 1)-matrix δ = a 0 a 1 ••• a n b 0 b 1 ••• b n such that the word ρ(δ) = a 0 a 1 • • • a n b n b n-1 • • • b 0 , called the reading of δ, is a permutation of 012 • • • (2n + 1). Let D2n+1 (resp. D 0 2n+1 ) denote the set of all doubloons δ = a 0 a 1 ••• a n b 0 b 1 ••• b n of order (2n + 1) (resp. the subset of all doubloons such that a 0 = 0). Let 1 ≤ k ≤ n; each doubloon δ = a 0 a 1 ••• a n b 0 b 1 ••• b n
is said to be normalized at k, if the following two conditions are satisfied:

(N 1) exactly one of the two integers a k , b k lies between a k-1 and b k-1 (we also say that δ is interlaced at k);

(N 2) either a k-1 > a k and b k-1 > b k , or a k-1 < b k and b k-1 < a k .
In an equivalent manner, δ is normalized at k, if one of the four following orderings holds:

(2.1)

a k-1 < b k < b k-1 < a k ; b k < b k-1 < a k < a k-1 ; b k-1 < a k < a k-1 < b k ; a k < a k-1 < b k < b k-1 .
For each pair of distinct integers (i, j) the symbol N i 2n+1,j will denote the set of all doubloons δ = a 0 a

1 ••• a n b 0 b 1 ••• b n , normalized at every k = 1, 2, .
. . , n, such that a 0 = i and b 0 = j. The doubloons belonging to N 0 2n+1,j for some j are simply called normalized. Also N 0 2n+1 designates the union of the sets N 0 2n+1,j 's. For further results on permutations studied as two-row matrices see [START_REF] Han | Calcul Denertien[END_REF][START_REF] Han | Une transformation fondamentale sur les réarrangements de mots[END_REF][START_REF] Foata | Word straightening and q-Eulerian Calculus, Contemporary Mathematics, q-Series from a Contemporary Perspective[END_REF].

Let

δ = a 0 a 1 ••• a n b 0 b 1 ••• b n be a doubloon of order (2n+1) and h an integer. For each k = 0, 1, . . . , n let a ′ k = a k + h, b ′ k = b k + h be expressed as residues mod(2n + 2). The two-row matrix a ′ 0 a ′ 1 ••• a ′ n b ′ 0 b ′ 1 ••• b ′ n , denoted by δ + h, is still a doubloon. Let T h : δ → δ + h. Proposition 2.1. The map T h , restricted to N i 2n+1,j
, is a bijection onto N i+h 2n+1,j+h (superscript and subscript being taken mod(2n + 2)). Proof. The four orderings in (2.1) are cyclic rearrangements of each other, so that if δ is normalized at each i, the doubloon T h δ = δ + h has the same property.

The number of descents, des δ, (resp. the major index, maj δ)

of a doubloon δ = a 0 a 1 ••• a n b 0 b 1 ••• b n is defined to be the number of descents (resp. the major index) of the permutation ρ(δ) = a 0 a 1 • • • a n b n b n-1 • • • b 0 , so that if the descents (a i > a i+1 , or a n > b n , or still b i-1 > b i ) occur at positions l 1 , l 2 , . . . , l r in ρ(δ), then des δ = r and maj δ = l 1 + l 2 + • • • + l r . The compressed major index, cmaj δ, of δ is defined by (2.2) cmaj δ = maj δ -(n + 1) des δ + n 2 .
For example, there is one normalized doubloon of order 3 (n = 1): δ = 0 3 2 1 and cmaj δ = maj(0 3 1 2) -(1 + 1) des(0 3 1 2) + 1 2 = 0, so that d 1,2 (q) = 1. There are four normalized doubloons of order 5 (n = 2) and the partition of N 0 5 reads:

N 0 5,2 = 0 4 3 2 1 5 , N 0 5,3 = 0 5 4 3 2 1 , 0 4 2 3 1 5 , N 0 5,4 = 0 5 3 4 2 1 .
We have cmaj(043512) = maj(043512) -3 des(043512) + 2 2 = (2 + 4) -3 × 2 + 1 = 1, so that d 2,2 (q) = q. Furthermore, d 2,3 (q) = 1 + q and d 2,4 (q) = 1, as expected (see Fig. 1.2).

Operations on doubloons

In this section we study the actions of several operators on the statistic "cmaj." First, we recall the action of the dihedral group on the traditional statistics "des" and "maj," in particular characterize the images of

each permutation σ = σ(1)σ(2) • • • σ(n) under the reversal r (resp. comple- ment c) that maps σ onto its mirror image r σ = σ(n) • • • σ(2)σ(1) (resp. onto its complement c σ = (n + 1 -σ(1))(n + 1 -σ(2)) • • • (n + 1 -σ(n)) ).
The next properties are well-known (see, e.g., [START_REF] Foata | Major Index and Inversion number of Permutations[END_REF]): if σ belongs to S n , then des r σ = n -1des σ; maj r σ = maj σn des σ + n 2 ; (3.1)

des c σ = n -1 -des σ; maj c σ = n 2 -maj σ; (3.2) des r c σ = des σ; maj r c σ = n des σ -maj σ. (3.3)
Now let i, j be the two integers defined by σ(1) = nj, σ(n) = ni and σ ′ be the permutation mapping k onto

σ ′ (k) = σ(k) + i, if σ(k) + i ≤ n; σ(k) + i -n, if σ(k) + i > n.
The operation σ → σ ′ and Property (3.5) below already appear in [START_REF] Han | Une courte démonstration d'un résultat sur la Z-statistique[END_REF] for the study of the Z-statistic.

Lemma 3.1. We have:

des σ -des σ ′ = 0, if i < j; 1, if i > j; (3.4) maj σ -maj σ ′ = i. (3.5)
Proof. As σ(n) = n-i, we can factorize the word σ = σ(1)σ(2) • • • σ(n) as a product p 0 q 1 p 1 • • • q r p r (r ≥ 1), where the letters of all p k 's (resp. all q k 's) are smaller than or equal to (resp. greater than) ni. Also, let p ′ 0 q ′ 1 p ′ 1 • • • q ′ r p ′ r be the corresponding factorization of σ ′ such that λp ′ 0 = λp 0 , λq ′ 1 = λq 1 , . . . (λ being the word length). In particular, p r (and p ′ r ) is never empty since σ(n) = ni (and σ ′ (n) = n), but p 0 (resp. and p ′ 0 ) is non empty if and only if σ(1)

+ i = n -j + i ≤ n, that is, if i < j.
As the rightmost letter of each factor q k is larger than the leftmost letter of p k , we have des σ = des p 0 + des q 1 + 1 + des p 1 + • • • + des q r + 1 + des p r .

In σ ′ the rightmost letter of each p ′ k is greater than the leftmost letter of q ′ k+1 , so that, if i < j,

des σ ′ = des p ′ 0 + 1 + des q ′ 1 + • • • + des p ′ r-1 + 1 + des q ′ r + des p ′ r = des p 0 + des q 1 + 1 + • • • + des p r-1 + des q r + 1 + des p r = des σ,
while, if i > j, the factor p ′ 0 is empty and des

σ ′ = des q ′ 1 + • • • + des p ′ r-1 + 1 + des q ′ r + des p ′ r = des σ -1.
However, in both cases we have:

maj σ -maj σ ′ = λ(p 0 q 1 ) + λ(p 0 q 1 p 1 q 2 ) + • • • + λ(p 0 q 1 • • • p r-1 q r ) -(λ(p ′ 0 ) + λ(p ′ 0 q ′ 1 p ′ 1 ) + • • • + λ(p ′ 0 q ′ 1 • • • p ′ r-1 ) = λ(q 1 ) + λ(q 2 ) + • • • + λ(q r ) = #{k : σ(k) > n -i} = i. Lemma 3.2. Let δ = a 0 a 1 ••• a n b 0 b 1 ••• b n be a doubloon such that a 0 = i and b 0 = j. Also, let δ ′ = T -i (δ) = δ -i = 0 a 1 -i ••• a n -i j-i b 1 -i ••• b n -i . Then (3.6) cmaj δ -cmaj δ ′ = -i, if i < j; n + 1 -i, if i > j.
Proof. Add 1 to each letter of the reading ρ

(δ) = a 0 a 1 • • • a n b n b n-1 • • • b 0 of δ
and do the same for the reading ρ(δ ′ ) of δ ′ . We obtain two permutations σ, σ ′ of 12 • • • (2n + 2) of the form:

σ = (i + 1) σ(2) • • • σ(2n + 1) (j + 1); σ ′ = 1 σ ′ (2) • • • σ ′ (2n + 1) (j -i + 1).
When the transformation r c is applied to each of them, we get

r c σ = (2n + 2 -j) • • • (2n + 2 -i); r c σ ′ = (2n + 2 -j + i) • • • (2n + 2).
It follows from Lemma 3.1 (with (2n + 2) replacing n, r c σ instead of σ and r c σ ′ instead of σ ′ ) that des r c σdes r c σ ′ = 0, if i < j; 1, if i > j; maj r c σmaj r c σ ′ = i, so that by (3.3)

des σ -des σ ′ = 0, if i < j; 1, if i > j; maj σ -maj σ ′ = (2n + 2)(des σ -des σ ′ ) -(maj r c σ -maj r c σ ′ ) = (2n + 2)(des σ -des σ ′ ) -i. As cmaj δ = maj σ -(n + 1) des σ + n 2 , we get cmaj δ -cmaj δ ′ = (maj σ -maj σ ′ ) -(n + 1)(des σ -des σ ′ ) = (n + 1)(des σ -des σ ′ ) -i = -i, if i < j; n + 1 -i, if i > j. Lemma 3.3. Let δ = 0 a 1 ••• a n b 0 b 1 ••• b n → δ ′ = a ′ 0 a ′ 1 ••• a ′ n b ′ 0 b ′ 1 ••• b ′ n be the transforma- tion mapping δ ∈ D 0 2n+1 onto the doubloon δ ′ obtained from δ by replacing each entry a k (resp. b k ) by a ′ k = (2n + 1) -a k (resp. b ′ k = (2n + 1) -b k ). Then cmaj δ = n(n -1) -cmaj δ ′ .
Proof. Again, add 1 to each element of ρ(δ) and of ρ(δ ′ ) to obtain two permutations σ and σ ′ of 12 • • • (2n + 2). We have: σ ′ = c σ. By (3.2) des σ + des σ ′ = 2n + 1 and maj σ + maj σ ′ = 2n+2 2 = (n + 1)(2n + 1). Hence, cmaj δ+cmaj δ ′ = maj σ+maj σ ′ -(n+1)(des σ+des σ ′ )+n(n-1) = (n + 1)(2n + 1) -(n + 1)(2n + 1) + n(n -1) = n(n -1).

Let Γ :

0 a 1 ••• a n b 0 b 1 ••• b n → 0 2n+2-a 1 ••• 2n+2-a n 2n+2-b 0 2n+2-b 1 ••• 2n+2-b n [Γ : δ → δ ′′ in short] be the transformation mapping each doubloon δ = 0 a 1 ••• a n b 0 b 1 ••• b n ∈ D 0 2n+1 onto the doubloon δ ′′ = 0 a ′′ 1 ••• a ′′ n b ′′ 0 b ′′ 1 ••• b ′′ n obtained from δ by replacing each entry a k (resp. b k ) by the residue a ′′ k = (2n + 2) -a k (resp. b ′′ k = (2n + 2) -b k ).
Remark. If δ is interlaced at each k (condition (N 1) holds at each k), the same property holds for Γ(δ). However, if δ is normalized at each k, the property is not preserved under the transformation Γ.

Lemma 3.4. For each δ ∈ D 0 2n+1 we have:

cmaj δ + cmaj Γ(δ) = n 2 . Proof. First, transform δ into the doubloon δ ′ defined in Lemma 3.3, so that δ ′ = 2n+1 a ′ 1 ••• a ′ n 2n+1-j b ′ 1 ••• b ′ n
and cmaj δ = n(n -1)cmaj δ ′ . Next, apply Lemma 3.2 to δ ′ with i = 2n + 1, so that the new doubloon is of the form

δ ′′ = 0 a ′′ 1 ••• a ′′ n 2n+2-j b ′′ 1 ••• b ′′ n . Hence, cmaj δ ′ -cmaj δ ′′ = (n + 1) -(2n + 1) = -n and cmaj δ = n(n -1) -cmaj δ ′′ + n = n 2 -cmaj δ ′′ .

Further operations on doubloons

In our previous paper [FoHa08] we also introduced a class of transformations φ i (0 ≤ i ≤ n) on D2n+1 , called micro flips, which permute the entries in a given column. By definition,

φ i : a 0 • • • a i-1 a i a i+1 • • • a n b 0 • • • b i-1 b i b i+1 • • • b n → a 0 • • • a i-1 b i a i+1 • • • a n b 0 • • • b i-1 a i b i+1 • • • b n (0 ≤ i ≤ n).
Next, the macro flips Φ i are defined by

Φ i = φ i φ i+1 • • • φ n (1 ≤ i ≤ n).
Note that both φ i and Φ i are involutions of D2n+1 . In particular,

(4.1) Φ 1 Φ 2 • • • Φ i = j odd, j≤i φ j .
By means of the transformation Γ (see Lemma 3.4 above) and the involutions Φ i 's we now construct a bijection of N 0 2n+1,j onto N 0 2n+1,2n+2-j .

Lemma 4.1.

Let δ = 0 a 1 ••• a n b 0 b 1 ••• b n
be a normalized doubloon and let

Γ(δ) = δ ′′ = 0 a ′′ 1 ••• a ′′ n b ′′ 0 b ′′ 1 ••• b ′′ n .
Then, for each i = 1, 2, . . . , n the doubloon

Φ 1 Φ 2 • • • Φ i (δ ′′ ) is normalized at each integer 1, 2, . . . , i. In particular, Φ 1 Φ 2 • • • Φ n (δ ′′ ) is normalized.
Proof. Using (4.1) we have:

δ * = Φ 1 Φ 2 • • • Φ i (δ ′′ ) =    0 b ′′ 1 a ′′ 2 ••• a ′′ i-1 b ′′ i b ′′ 0 a ′′ 1 b ′′ 2 •••b ′′ i-1 a ′′ i , if i odd; 0 b ′′ 1 a ′′ 2 ••• b ′′ i-1 a ′′ i b ′′ 0 a ′′ 1 b ′′ 2 •••a ′′ i-1 b ′′ i , if i even.
The doubloon δ ′′ is not normalized (see the Remark before Lemma 3.4), but is interlaced at each i, so that the relations

a ′′ j-1 < a ′′ j , b ′′ j-1 < b ′′ j or a ′′ j-1 > a ′′ j , b ′′ j-1 > b ′′
j hold for all j. This shows that δ * is normalized whenever j is odd or even.

For the next Proposition we need the following property proved in our previous paper [FoHa08, Theorem 3.5]:

(4.2) Let δ = 0 a 1 ••• a n b 0 b 1 ••• b n be an interlaced doubloon, normalized at i. Then cmaj Φ i (δ) -cmaj δ = n -i + 1 (1 ≤ i ≤ n). Proposition 4.2. The transformation Φ 1 Φ 2 • • • Φ n Γ : δ → δ * is a bijec- tion of N 0
2n+1,j onto N 0 2n+1,2n+2-j having the property

(4.3) cmaj δ + cmaj δ * = n 2 . Proof. Let δ ′′ = Γ(δ). As Φ 1 Φ 2 • • • Φ i (δ ′′ ) is normalized at i, we have cmaj Φ i Φ 1 Φ 2 • • • Φ i (δ ′′ ) -cmaj Φ 1 Φ 2 • • • Φ i (δ ′′ ) = n -i + 1 by (4.2). Summing over all i = 1, 2, . . . , n we get n i=1 (cmaj Φ 1 Φ 2 • • • Φ i-1 (δ ′′ ) -cmaj Φ 1 Φ 2 • • • Φ i (δ ′′ )) = n i=1 (n -i + 1) cmaj δ ′′ -cmaj Φ 1 Φ 2 • • • Φ n (δ ′′ ) = n 2 -n 2 .
Using Lemma 3.4 we conclude that (n 2cmaj δ)cmaj δ * = n 2 -n 2 and then cmaj δ + cmaj δ * = n 2 . Example. For n = 2 we have Φ 1 Φ 2 = φ 1 . The four normalized doubloons of order 5 (n = 2) displayed at the end of Section 2 are mapped under Φ 1 Φ 2 Γ = φ 1 Γ as shown in Fig. 4.1. Next to each doubloon appears the value of its "cmaj".

 Γ  Γ  Γ 0 2 3 4 5 1 , 3 0 1 2 3 4 5 , 4 0 2 4 3 5 1 , 3 0 1 3 2 4 5 , 4  φ 1  φ 1  φ 1  φ 1 0 5 3 4 2 1 , 0 0 4 2 3 1 5 , 1 0 5 4 3 2 1 , 0 0 4 3 2 1 5 , 1 Fig. 4.1. The transformation Φ 1 Φ 2 • • • Φ n Γ Let d n,j (q) = δ∈N 0 2n+1,j q cmaj δ . The final purpose is to show that d n,j (q)
satisfies relations (D1) -(D4). This will be done in Section 5. In the rest of this section we state some symmetry properties of the d n,j (q)'s.

Corollary 4.3. For 2 ≤ j ≤ 2n we have:

(4.4) d n,j (q) = q ( n 2 ) d n,2n+2-j (q -1 ).
Proof. This follows from the previous proposition:

d n,j (q) = δ∈N 0 2n+1,j q cmaj δ = δ * ∈N 0 2n+1,2n+1-j q ( n 2 )-cmaj δ * = q ( n 2 ) d n,2n+2-j (q -1 ).
In the next lemma we study the action of the sole transposition φ 0 that permutes the leftmost entries of each doubloon.

Lemma 4.4. For each normalized doubloon δ

(4.5) cmaj δ -cmaj φ 0 (δ) = -n. Proof. Let ρ(δ) = 0a 1 • • • a n b n • • • b 1 b 0 be the reading of δ, so that ρ(φ 0 (δ)) = b 0 a 1 • • • a n b n • • • b 1 0.
As δ is normalized (and, in particular, interlaced), we have: 0 < b 1 < b 0 < a 1 . Thus, ρ(δ) starts and ends with a rise (0 < a 1 and b 1 < a 0 ), while ρ(φ 0 (δ)) starts with a rise b 0 < a 1 and ends with a descent b 1 > 0. Hence, des ρ(δ) = des ρ(φ 0 (δ)) -1 and maj ρ

(δ) = maj ρ(φ 0 (δ)) -(2n + 1) and cmaj δ -cmaj ρ(φ 0 (δ)) = -(2n + 1) -(n + 1) -1 = -n The involution φ 0 Φ 1 = Φ 1 φ 0 = φ 0 φ 1 • • • φ n transposes the two rows of each doubloon δ ∈ D2n+1 . Lemma 4.5. For each normalized doubloon δ (4.5) cmaj δ = cmaj φ 0 Φ 1 (δ).
Proof. First, cmaj δ = cmaj φ 0 (δ)n by the previous lemma. Furthermore, as φ 0 Φ 1 (δ) remains normalized at 1, relation (4.2) implies that cmaj Φ

1 (φ 0 Φ 1 (δ)) -cmaj φ 0 Φ 1 (δ) = n -1 + 1. Thus, cmaj φ 0 Φ 1 (δ) = cmaj φ 0 (δ) -n = cmaj δ + n -n = cmaj δ.
We next study the joint action of the operators T -j (introduced in Lemma. 3.2) φ 0 and Φ 1 .

Proposition 4.6. The transformation T -j φ 0 Φ 1 : δ → δ ′ is a bijection of N 0 2n+1,j onto N 0 2n+1,2n+2-j having the property that

(4.6) cmaj δ -cmaj δ ′ = n + 1 -j.
Proof. Let δ ∈ N 0 2n+1,j . Then, φ 0 Φ 1 (δ) is normalized at each i = 1, 2, . . . , n and also T -j φ 0 Φ 1 (δ) by the remark made before Lemma 3.2. Thus, δ ′ ∈ N 0 2n+1,2n+2-j and the map δ → δ ′ is bijective. Furthermore, cmaj δ = cmaj φ 0 Φ 1 (δ) by Lemma 4.5 and cmaj φ 0 Φ 1 (δ) = cmaj δ ′ + n + 1j by Lemma 3.2.

Example. Again consider the four normalized doubloons of order 5. We get the display of Fig. 4.2. with the value of "cmaj" next to each doubloon. 0 4 3 2 1 5 , 1 0 5 4 3 2 1 , 0 0 4 2 3 1 5 , 1 0 5 3 4 2 1 , 0

 φ 0 Φ 1  φ 0 Φ 1  φ 0 Φ 1  φ 0 Φ 1 2 1 5 0 4 3 , 1 3 2 1 0 5 4 , 0 3 1 5 0 4 2 , 1 4 2 1 0 5 3 , 0  T -2  T -3  T -3  T -4
0 5 3 4 2 1 , 0 0 5 4 3 2 1 , 0 0 4 2 3 1 5 , 1 0 4 3 2 1 5 , 1 Fig. 4.2. The transformation T -j φ 0 Φ 1 Corollary 4.7. For 2 ≤ j ≤ 2n we have:

(4.7) d n,j (q) = q n+1-j d n,2n+2-j (q).
The corollary immediately follows from Proposition 4.6. In its turn the next corollary is a consequence of both Corollaries 4.3 and 4.7.

Corollary 4.8. For 2 ≤ j ≤ 2n we have:

(4.8)
d n,j (q) = q ( n+1 2 )+1-j d n,j (q -1 ).

As could be seen in Fig. 1.2 for the first values, the polynomial d n,j (q) is a multiple of d n,2n+2-j (q) (Corollary 4.7) and Corollary 4.8 indicates a symmetry between its coefficients.

The recurrence itself

In this section we prove Theorem 1.2, that is, we show that relations (D1) -(D4) hold for d n,j (q) = δ∈N 0 2n+1,j q cmaj δ . The first two relations (D1) -(D2) are evidently true. For proving that relations (D3) -(D4) hold for such a d n,j (q) we start with a doubloon δ ∈ N 0 2n+1 , drop its leftmost column and compare the compressed major indices of δ and of the doubloon obtained after deletion. In so doing we get the following result.

Lemma 5.1. To each doubloon δ ∈ N 0 2n+1,j there corresponds a unique triplet (k, l, δ ′ ) such that k ≥ j -1, l ≤ j -2 and δ ′ ∈ N k 2n-1,l having the property that

(5.1) cmaj δ = cmaj δ ′ + (n -1). Proof. Let δ = 0 a 1 ••• a n j b 1 ••• b n ∈ N 0 2n+1,j and define a ′ i = a i -1, if a i < j; a i -2, if j < a i ≤ 2n + 1;
with an analogous definition for the b ′ i , the b's replacing the a's. Then,

δ ′ = a ′ 1 ... a ′ n b ′ 1 ... b ′ n
is a normalized doubloon of order (2n + 1), but its left-top corner a ′ 1 is not necessarily 0. Call it the reduction of δ. As a 1 > j > b 1 , we see that b

′ 1 = b 1 -1 < j -1 and a ′ 1 = a 1 -2 > j -2, that is, b ′ 1 ≤ j -2 < j -1 ≤ a ′ 1 . Thus δ ′ ∈ N k
2n-1,l with k ≥ j -1 and l ≤ j -2. Conversely, given the triplet (δ ′ , k, l) with the above properties, we can uniquely reconstruct the normalized doubloon δ.

As δ is normalized at 1, the inequalities 0 < b 1 < j < a 1 hold, so that ρ(δ) starts and ends with a rise: 0 < a 1 , b 1 < j. In particular, des ρ(δ) = des ρ(δ ′ ). However, maj ρ(δ) = maj ρ(δ ′ ) + des δ, as the first letter 0 is dropped when going from ρ(δ) to ρ(δ ′ ). Hence, cmaj δ-cmaj δ

′ = des δ -((n + 1) -n) des δ + n 2 -n-1 2 = n -1.
The previous Lemma yields the first passage from the generating polynomial d n,j (q) for the normalized doubloons δ ∈ N 0 2n+1,j by "cmaj" to the generating polynomial for doubloons of order (2n -1), as expressed in the next Corollary.

Corollary 5.2. For 2 ≤ j ≤ 2n we have:

(5.2) d n,j (q) = q n-1 k≥j-1, l≤j-2 q n-k d n-1,2n+l-k (q).
with k ranging over the interval defined in (5.4). The geometric sum over k is equal to q -max(2n-i,j-1)q -min(2n+j-i-2,2n-1)-1 1q -1 . Now, 2n-max(2n-i, j -1) = 2n+min(-2n+i, -j +1) = min(i, 2n-j +1) and 2n -1min(2n + ji -2, 2n -1) = max(0, -j + i + 1). Accordingly, q 2n-1 k subject to (5.4)

q -k = q max(0,i+1-j)q min(i,2n+1-j) 1q .

This proves (5.3) when reporting the latter expression into (5.5).

For getting rid of "max" and "min" from identity (5.3) we decompose the sum into four subsums, assuming j ≥ 3 (when j = 2 identity (5.3) gives back (D3)). We obtain:

(5.6) (1 -q)d n,j (q) = j-1 i=0 d n-1,i (q) + 2n+1 i=j q i+1-j d n-1,i (q) - 2n-j i=0 q i d n-1,i (q) - 2n+1 i=2n-j+1 q 2n+1-j d n-1,i (q).
By means of (5.6) we calculate d n,j (q)d n,j-1 (q) and then -d n,j-1 (q) + d n,j-2 (q), whose sum is the left-hand side of (D4). In the computation of (1q)(d n,j (q)d n,j-1 (q)) the contribution of the first subsum is simply d n-1,j-1 (q). Next, q 2n-j+1 d n-1,2n-j+1 (q) is the contribution of the second subsum. For the third subsum we get

-q d n-1,j-1 (q) + 2n+1 i=j q i-j+1 (1 -q)d n-1,i (q)
and for the fourth one

-q 2n+1-j d n-1,2n+1-j (q) + 2n+1 i=2n-j+2 q 2n+1-j (q -1)d n-1,i (q). Altogether (5.7) d n,j (q) -d n,j-1 (q) = d n-1,j-1 (q) + 2n+1 i=j q i-j+1 d n-1,i (q) - 2n+1 i=2n-j+2 q 2n+1-j d n-1,i (q); (5.8) -d n,j-1 (q) + d n,j-2 (q) = -d n-1,j-2 (q) - 2n+1 i=j-1 q i-j+2 d n-1,i (q) + 2n+1 i=2n-j+3 q 2n+2-j d n-1,i (q). δ ′ = φ i 1 φ i 2 • • • φ i k (δ). A doubloon δ = a 0 a 1 ••• a n b 0 b 1 ••• b n is said to be minimal, if a k < b k
holds for every k. Clearly, every equivalence class of doubloons contains one and only one minimal doubloon. Also, as proved in [START_REF] Foata | Doubloons and new q-tangent numbers[END_REF], each doubloon δ ∈ D 0 2n+1 is equivalent to one and only one normalized doubloon.

The link between split-pair arrangements and equivalence classes of interlaced doubloons is the following: start with a interlaced and minimal and there is exactly one letter equal to k, namely x l+1 between the two occurrences of (k-1), namely x m+1 and x m ′ +1 . Same conclusion if a k-1 < a k < b k-1 < b k . Those words w of length 2n having the property that exactly one letter equal to k lies between two occurrences of (k-1) for each k = 2, 3, . . . , n was called split-pair arrangements by Graham and Zang [START_REF] Graham | Enumerating split-pair arrangements[END_REF]. The mapping δ → w provides a bijection between equivalence classes of interlaced doubloons and those arrangements.

doubloon δ = a 0 a 1 ••• a n b 0 b ••• b n
A permutation σ = σ(1)σ(2) • • • σ(2n + 1) of 12 • • • (2n + 1) is said to be alternating if σ(2i) < σ(2i -1), σ(2i + 1) for each i = 1, 2, . . . , n. For each even integer 2i (1 ≤ i ≤ n) let w ′ i (resp. w ′′ i ) be the longest right factor of σ(1) • • • σ(2i -1) (resp. longest left factor of σ(2i + 1) • • • σ(2n + 1)), all letters of which are greater than σ(2i). Let min w ′ i (resp. min w ′′ i ) denote the minimum letter of w ′ i (resp. of w ′′ i ). Then σ is called an alternating André permutation if it is alternating and satifies min w ′ i > min w ′′ i for every i = 1, 2, . . . , n. The number of alternating André permutations of order (2n + 1) is equal to t n (see, e.g., [START_REF] Foata | Nombres d'Euler et permutations alternantes[END_REF], Property 2.6 and (5.4), or [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF], p. 370, also [FS74]). The alternating André permutations of order 5 are the following: 53412, 51423, 41523, 31524. Let A 2n+1,j denote the set of alternating André permutations of order (2n + 1) ending with j.

Thanks to the identity Three questions arise:

(1) Construct a natural (?) bijection of N 0 2n+1,j onto A 2n+1,j . (2) Find an adequate statistic "stat" on the alternating André permutation such that holds the identity d n,j (q) = σ∈A 2n+1,j q stat σ .

(3) As mentioned in the Introduction, we have an expression for the generating function for d n,j (1) (formula (1.8)) and for d n,j (0) (formula (1.14)). Find the exponential (or factorial) generating function for d n,j (q).

Fig. 1

 1 .1 ′ . The first doubloon polynomials

  Fig. 1.2. The specializations of d n,j (q)

Fig

  Fig. 1.3. The Poupard triangle (d n,j (1))

Fig. 1

 1 Fig. 1.4. The Catalan triangle (d n,j (0))

  and define the word w= x 1 x 2 • • • x 2n by x l+1 = l if and only if a k or b k is equal to l. For instance, δ is interlaced (condition (N 1)), exactly one of the integers a k , b k lies between a k-1 and b k-1 . If a k = l < l ′ = b k , then x l+1 = x l ′ +1 = k. If a k-1 = m < a k = l < b k-1 = m ′ < b k = l ′ , then x m+1 = x m ′ +1 = k -1

  i-1,k (1), valid for n ≥ 1, 2 ≤ j ≤ 2n -1 (d 0,j (1) = δ 0,j ) derived from the bivariable generating function (1.8), Christiane Poupard proved that (6.2) # A 2n+1,j = d n,j (1).

1 5 , 1 0 5 4

2 1 , 0 0

2 3 1

, 1 0 5 3 4 2 1 , 0  Γ

Proof. By the previous Lemma we can write: d n,j (q) = δ∈N 0 2n+1,j q cmaj δ = q n-1 k≥j-1, l≤j-2 δ ′ ∈N k 2n-1,l q cmaj δ ′ .

With each δ ′ ∈ N k 2n-1,l associate δ ′′ = T -k δ ′ = δ ′k. By Lemma 3.2 we get δ ′′ ∈ N 0 2n-1,2n+l-k (note that the residue mod(2n + 2) must be considered in the subscript for l < k) and cmaj δ ′cmaj δ ′′ = nk. Hence,

When j = 2 in (5.2), we get:

and also

[by using (4.7).]

Consequently, relation (D3) holds for the polynomial d n,j (q) = δ∈N 0 2n+1,j q cmaj δ . Using (5.2) it is also easy to derive the identity: q d n,3 (q) = (q + 1) d n,2 (q). Proposition 5.2. For 2 ≤ j ≤ 2n we have:

Taking the two relations keeping k within bounds into account we get the double inequality:

(5.4) max(2ni, j -1) ≤ k ≤ min(2n + ji -2, 2n -1).

Identity (5.2) may then be rewritten as

Summing (5.7) and (5.8) we get:

q 2n+1-j d n-1,i (q). Now, -q 2n+1-j d n-1,2n-j+2 (q) = -q n-1 d n-1,j-2 (q) by Corollary 4.7. Also

[by Corollary 4.7]

for n ≥ 2 and 3 ≤ j ≤ 2n, which is precisely relation (D4).

Concluding remarks

As mentioned in the Introduction, there has been a great number of papers dealing with the Catalan Triangle (the numbers d n,j (0)). The recurrence for the numbers d n,j (1), namely the set of conditions (P 1)-(P 4), is definitely due to Christiane Poupard [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF] and was recently rediscovered by Graham and Zang [START_REF] Graham | Enumerating split-pair arrangements[END_REF]. More exactly, the latter authors introduced the notion of split-pair arrangement. To show that the number of such arrangements of order n was equal to the reduced tangent number t n they set up an algebra for the coefficients d n,j (1) and again produced the recurrence (P 1)-(P 4), but their proof of the identity j d n,j (1) = t n was more elaborate than the original one made by Christiane Poupard [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF], shortly sketched in the Introduction.

Referring to Section 4 we say that two doubloons δ, δ ′ ∈ D2n+1 are equivalent if there is a sequence φ i 1 , φ i 2 , . . . , φ i k of micro flips such that