Diala Naboulsi
email: diala.naboulsi@insa-lyon.fr

Marco Fiore
email: marco.fiore@ieiit.cnr.it

Carla-Fabiana Chiasserini
email: chiasserini@polito.it

Assessment of Practical Energy Savings in Cellular Networks

Keywords: cellular networks, energy consumptions, reduce consumptions

In this work, we tackle the problem of on-grid energy saving in cellular networks based on switch-on/off techniques for base stations and the usage of renewable energy. We aim to evaluate how much power can be saved in the network and dimension the renewable energy system according to the consumptions in real-world networks.

Evaluation des Economies d'Energie Pratiques dans les Réseaux Cellulaires

Résumé : Dans ce travail, nous abordons le problème d'économisation des consommations d'énergie dans les réseaux cellulaires sur le réseau électrique en appliquant des techniques d'endormissement pour les stations de bases et en utilisant de l'énergie renouvelable. On vise à évaluer combien de puissance on peut économiser dans le réseau et à dimensionner le système d'énergie renouvelable en fonction des consommations dans les réseaux réels.

Mots-clés : réseaux cellulaires, consommation d'énergie, réduction de consommation

Introduction

The last few years have witnessed a tremendous growth in cellular traffic. Currently, more than 4 million base stations (BSs) are deployed to fulfill users demands in the world, consuming very large amounts of energy. Alongside environmental concerns, the growing fuel prices are amplifying the expenses on the operator side, making the reduction of energy consumption an inevitable step. BSs are responsible for more than 50% of the total power of a wireless cellular network, they are switched on during all times and consume a lot of energy even when they are underutilized.

Our work focuses on reducing the energy consumption in cellular networks over the electrical grid by using BSs powered by renewable energy, and applying at the same time a switch on/off strategy for BSs. Such a solution is expected to be very convenient especially in regions where significant amounts of renewable energy can be produced. This approach is starting to be explored, as in [START_REF] Han | On Optimizing Green Energy Utilization for Cellular Networks with Hybrid Energy Supplies[END_REF]. However, the study in [START_REF] Han | On Optimizing Green Energy Utilization for Cellular Networks with Hybrid Energy Supplies[END_REF] only considers the coverage of users appearing in the network at a specific snapshot and does not propose techniques that allow to detect them. In our work, instead, we focus on providing geographical coverage of the network. Moreover, the evaluations in [START_REF] Han | On Optimizing Green Energy Utilization for Cellular Networks with Hybrid Energy Supplies[END_REF] are conducted over a simplistic scenario, whereas in our work, we use real-world data including a real deployment of BSs and real users consumptions data.

Clearly, our problem is constrained not just by the full coverage but also by the limitations on the radio resources. Accounting for both kinds of constraints simulataneously results in an NP-hard optimization problem, thus, we split it into two sub-problems, one for each kind of constraints. We conduct our work over three steps: i) we first evaluate the minimum required energy to provide a geographical coverage over the studied region; ii) we check the time intervals of a day when such a solution allows us to fulfill users demands; iii) we dimension the green energy system according to the daily energy needs of the BSs. In the following section, we detail steps i) and ii).

Model

Geographical coverage subproblem

We define A = {1, ..., m} as the set of areas that should be covered in the studied region, and B = {1, ..., n} as the set of deployed BSs. We denote the power consumption of a BS j by P c j . If BS j is off, P c j is equal to 0; while, if the BS is on, P c j accounts for the constant consumption due to the electronics plus a term related to the transmission power. P c ij is a constant representing the minimum required consumed power by BS j that permits it to provide coverage to a user at the farthest edge of area i. To derive the power consumption thresholds P c ij , we first evaluate the required transmission power P t ij of the BS j to serve area i, by applying the Walfish-Ikegami empirical propagation model [START_REF]Cost 231 Final Report[END_REF], and then computing P c ij by applying the power consumption model proposed in [START_REF] Arnold | Power consumption modeling of different BS types in heterogeneous cellular networks[END_REF]. Both models are briefly presented in the next section. We use x ij to represent the association between area i and BS j, such that x ij is equal to 1 if area i is covered by BS j, and 0 otherwise. We calculate the minimum consumed power needed to provide a full coverage of the network by solving the following optimization problem. Our decision variables are the continuous variables, P c j ∀j ∈ B, and the binary variables x ij ∀i ∈ A, ∀j ∈ B.

min j∈B P c j P c j ≥ P c ij x ij ∀i ∈ A, ∀j ∈ B (1) j∈B x ij ≥ 1 ∀i ∈ A (2)
P c j ≤ P c max ∀j ∈ B (3)
Constraint (1) allows an area i ∈ A to be covered by a BS j ∈ B, if the power consumed by the BS is higher than the constant P c ij . Constraint [START_REF]Cost 231 Final Report[END_REF] imposes that each area should be covered by at least one BS. Constraint (3) sets an upper bound P c max on the consumed power, such that the maximum possible transmit power is not exceeded.

Resource allocation subproblem

Once we obtain the BSs power configuration from the previous step, we check the time intervals for which the solution allows us to handle the expected user demand. We do so by solving the following subproblem, in which we aim to optimize the allocation of resources. The set of y ij is the set of integer decision variables each representing the number of radio resources that shall be allocated by BS j to serve users in area i. y ij are time-dependent, and we consider them over a meaningful time interval. For simplicity we drop the time notation in the model.

min j∈B i∈Aj y ij i∈Aj y ij ≤ R j ∀j ∈ B ( 4
) j∈Bi y ij W Log 2 (1 + SN R ij ) ≥ f i ∀i ∈ A (5)
Constraint (4) insures that the limit on the number of radio resources for each BS, R j , is not exceeded. A j is the set of areas covered by BS j. Equation (5) imposes the constraint on the radio resources allocated for each area, according to Shannon's theorem, such that the demand in the area can be managed. B i is the set of BSs that can cover area i. W is the bandwidth for one radio resource, for simplicity it is considered constant. f i represents the total throughput demands in area i. SN R ij is the Signal-to-noise ratio perceived by a user in area i with respect to the signal received from BS j. The left part of constraint (5) provides the sum of theoretical throughputs that can be attained, based on Shannon's formula in area i. Constraint (5) can be modified depending on the technology. As introduced, it holds for the case of 4G networks, where we can consider that Shannon's capacity can be reached.

Our subproblems still suffer from complexity, due to the high number of integer and binary variables, especially in large-scale evaluations. However, as interactions occur on a local level, we approximate the solution by solving the subproblems on clusters of areas.

Scenario and results

Scenario

We derive our results over the 2G network of Orange in Abidjan. Abidjan is divided into ten neighborhoods, known as communes. Fig. 1(a) shows the position of BSs, together with the communes. These communes have highly different building characteristics that affect the signal propagation: As an example very tall buildings dominate over the commune of Plateau, while the commune of Abobo is mostly formed by buildings of one or two floors. This led us to parameterize, in our evaluations, each commune separately.

For the signal propagation, we adopt the Walfish-Ikegami model [START_REF]Cost 231 Final Report[END_REF], which provides the average path loss, taking into account the properties of the vertical plane between the transmitter and the receiver. We assume that a region i can be associated to a transmitting BS j, if the user at the farthest edge of the area receives a minimum power of -100 dBm. The parameters of the model are chosen adequately for each commune according to the average characteristics of the environment. Concerning the power consumption, we apply the model for macro base stations from [START_REF] Arnold | Power consumption modeling of different BS types in heterogeneous cellular networks[END_REF]. Moreover, the values of P

Results

In this poster, we provide early results on the geographical coverage subproblem, in subsection 2.1. We present in Fig. 1(b) the results derived over the scenario described above. In this figure, we represent the BSs that can be switched-off with red points, while the switched-on BSs are drawn with green circles whose radius is proportional to their consumed power. We can see that different communes require different densities of switched-on BSs, resulting from the characteristics of the signal propagation and the initial density of BSs. We compare the total consumed power when the switch-on/off strategy is applied, to the total consumed power when all BSs are on, obtained by solving the same optimization problem, as before, with the additional constraint: P c j ≥ P 1 , ∀j ∈ B. This constraint imposes that each BS is switched on. We note that we respectively refer to the strategies as "on-off" and "all-on". Fig. 2 shows the normalized gain G in the power consumption for each commune, together with the absolute power value for both strategies. The gain we obtain in each commune varies from 39% to 72%.

Conclusions

Our results show how much energy can be saved in a real-world cellular network with a switch-on/off technique for BSs under geographical coverage constraints. Energy savings of more than 70% can be reached, when very low traffic demands exist. Also, we observed that this value changes with respect to the BSs density and the signal propagation environment characteristics. We are currently extending our The obtained gain (G) when switch on/off strategy is applied, with respect to the all-on strategy, and the total power consumption per commune for each case.

results by focusing on the resource allocation optimization subproblem and the renewable energy system dimensioning. In the future, we would also like to consider other scenarios.

Figure 1 :

 1 Figure 1: (a): Geographical distribution of BSs over the communes of Abidjan. (b): Geographical distribution of switched-on/off BSs.

Figure 2 :

 2 Figure2: The obtained gain (G) when switch on/off strategy is applied, with respect to the all-on strategy, and the total power consumption per commune for each case.

RT n°

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-0803

grant from the Rhône-Alpes Region.


Ange Bigeni

A BIJECTION BETWEEN IRREDUCIBLE k-SHAPES THE SURJECTIVE PISTOLS OF HEIGHT k -1

Keywords: Genocchi numbers, Gandhi polynomials, (irreducible) k-shapes, surjective pistols

This paper constructs a bijection between irreducible k-shapes and surjective pistols of height k -1, which carries the "free k-sites" to the fixed points of surjective pistols. The bijection confirms a conjecture of Hivert and Mallet (FPSAC 2011) that the number of irreducible k-shape is counted by the Genocchi number G 2k .

Introduction

The study of k-shapes arises naturally in the combinatorics of k-Schur functions (see [START_REF] Lam | The poset of k-shapes and branching rules for k-schur functions[END_REF]). In a 2011 FPSAC paper, Hivert and Mallet showed that the generating function of all kshapes was a rational function whose numerator P k (t) was defined in terms of what they called irreducible k-shapes. The sequence of numbers of irreducible k-shapes (P k (1)) k≥1 seemed to be the sequence of Genocchi numbers (G 2k ) k≥1 = (1, 1, 3, 17, 155, 2073, . . .) [OEI], which may be defined by G 2k = Q 2k-2 (1) for all k ≥ 2 (see [START_REF] Carlitz | A conjecture concerning Genocchi numbers[END_REF][START_REF] Riordan | Proof of a conjecture on Genocchi numbers[END_REF]) where Q 2n (x) is the Gandhi polynomial defined by the recursion Q 2 (x) = x 2 and

Q 2k+2 (x) = x 2 (Q 2k (x + 1) -Q 2k (x)). (1)
Hivert and Mallet defined a statistic f r(λ) counting the so-called free k-sites on the partitions λ in the set of irreducible k-shapes IS k , and conjectured that

Q 2k-2 (x) = λ∈IS k x f r(λ)+2 . (2)
The goal of this paper is to construct a bijection between irreducible k-shapes and surjective pistols of height k -1, such that every free k-site of an irreducible k-shape is carried to a fixed point of the corresponding surjective pistol. Since the surjective pistols are known to generate the Gandhi polynomials with respect to the fixed points (see Theorem 2.1), this bijection will imply Formula (2). The rest of this paper is organized as follows. In Section 2, we give some background about surjective pistols (in Subsection 2.1), partitions, skew partitions and k-shapes (in Subsection 2.2), then we focus on irreducible k-shapes (in Subsection 2.3) and enounce Conjecture 2.1 raised by Mallet (which implies Formula 2), and the main result of this paper, Theorem 2.2, whose latter conjecture is a straight corollary. In Section 3, we give preliminaries of the proof of Theorem 2.2 by introducing the notion of partial k-shapes. In Section 4, we demonstrate Theorem 2.2 by defining two inverse maps ϕ (in Subsection 4.1) and φ (in Subsection 4.2) which connect irreducible k-shapes and surjective pistols and keep track of the two statistics. Finally, in Section 5, we explore the corresponding interpretations of some generalizations of the Gandhi polynomials, generated by the surjective pistols with respect to refined statistics, on the irreducible k-shapes.

Definitions and main result

2.1. Surjective pistols. For all positive integer n, we denote by [n] the set {1, 2, . . . , n}. A surjective pistol of height k is a surjective map f : [2k] → {2, 4, . . . , 2k} such that f (j) ≥ j for all j ∈ [2k]. We denote by SP k the set of surjective pistols of height k. By abuse of notation, we assimilate a surjective pistol f ∈ SP k into the sequence (f (1), f (2), . . . , f (2k)). A fixed point of f ∈ SP k is an integer j ∈ [2k] such that f (j) = j. We denote by f ix(f ) the number of fixed points different from 2k (which is always a fixed point). A surjective pistol of height k can also be seen as a tableau made of k right-justified rows of length 2, 4, 6, . . . , 2k (from top to bottom), such that each row contains at least one dot, and each column contains exactly one dot. The map f corresponding to such a tableau would be defined as f (j) = 2( j/2 + z j ) where the j-th column of the tableau contains a dot in its (1 + z j )-th cell (from top to bottom) for all j ∈ [2k]. For example, if f = (2, 4, 4, 8, 8, 6, 8, 8) ∈ SP 4 , the tableau corresponding to f is depicted in Figure 1. In particular, an integer j = 2i is a fixed point of f if and only if the dot of the 2i-th column of the corresponding tableau is at the top of the column. For example, the surjective pistol f of Figure 1 has 2 fixed points 6 and 8, but f ix(f ) = 1 (because the fixed point 2k = 8 is not counted by the statistic). The following result is due to Dumont.

Theorem 2.1 ( [START_REF] Dumont | Interprétations combinatoires des nombres de Genocchi[END_REF]). For all k ≥ 2, the Gandhi polynomial Q 2k (x) has the following combinatorial interpretation:

Q 2k (x) = f ∈SP k x f ix(f )+2 .
2.2. Partitions, skew partitions, k-shapes. A partition is a a finite sequence of positive integers λ = (λ 1 , λ 2 , . . . , λ m ) such that λ 1 ≥ λ 2 ≥ . . . ≥ λ m . By abuse of definition, we consider that a partition may be empty (corresponding to m = 0). A convenient way to visualize a partition λ = (λ 1 , λ 2 , . . . , λ m ) is to consider its Ferrers diagram (denoted by [λ]), which is composed of cells organized in left-justified rows such that the i-th row (from bottom to top) contains λ i cells. The hook length of a cell c is defined as the number of cells located to its right in the same row (including c itself) or above it in the same column. If the hook length of a cell c equals h, we say that c is hook lengthed by the integer h. For example, the Ferrers diagram of the partition λ = (4, 2, 2, 1) is represented in Figure 2, in which every cell is labeled by its own hook length. We will sometimes assimilate partitions with their Ferrers diagrams. If two partitions λ = (λ 1 , . . . , λ p ) and µ = (µ 1 , . . . , µ q ) (with q ≤ p) are such that µ i ≤ λ i for all i ≤ q, then we write µ ⊆ λ and we define the skew partition s = λ/µ as the diagram

[λ]\[µ], the Ferrers diagram [µ] appearing naturally in [λ].
For example, if λ = (4, 2, 2, 1) and µ = (2, 1, 1), then µ ⊆ λ and the skew partition λ\µ is the diagram depicted in Figure 3. For all skew partition s, we name row shape (respectively column shape) of s, and we denote by rs(s) (resp. cs(s)), the sequence of the lengths of the rows from bottom to top (resp. the sequence of the heights of the columns from left to right) of s. Those sequences are not necessarily partitions. For example, if s is the skew partition depicted in Figure 3, then rs(s) = (2, 1, 1, 1) and cs(s) = (1, 2, 1, 1) (in particular cs(s) is not a partition). If the lower border of s is continuous, i.e., if it is not fragmented into several pieces" we also define a canonical partition < s > obtained by inserting cells in the empty space beneath every column and on the left of every row of s. For example, if s is the skew partition depicted in Figure 3, the lower border of s is drawed as a thin red line which is continuous, and < s > is simply the original partition λ = (4, 2, 2, 1). Now, consider a positive integer k. For all partition λ, it is easy to see that the diagram composed of the cells of [λ] whose hook length does not exceed k, is a skew partition, that we name k-boundary of λ and denote by ∂ k (λ). Incidentally, we name k-rim of λ the lower border of ∂ k (λ) (which may be fragmented), and we denote by rs k (λ) (respectively cs k (λ)) the sequence rs(∂ k (λ)) (resp. the sequence cs(∂ k (λ)). For example, the 2-boundary of the partition λ = (4, 2, 2, 1) depicted in Figure 2, is in fact the skew partition of Figure 3. Note that if the k-rim of λ is continuous, then the partition < ∂ k (λ) > is simply λ.

Definition 2.1 ([LLMS13]

). A k-shape is a partition λ such that the sequences rs k (λ) and cs k (λ) are also partitions.

For example, the partition λ = (4, 2, 2, 1) depicted in Figure 2 is not a 2-shape since cs 2 (λ) = (1, 2, 1, 1) is not a partition, but it is a k-shape for any k ≥ 4 (for instance cs 5 (λ) = (3, 3, 1, 1) and rs 5 (λ) = (3, 2, 2, 1) are partitions, so λ is a 5-shape, see Figure 4). Note that the k-rim of a k-shape λ is necessarily continuous, thence λ =< ∂ k (λ) >. Consequently, we will sometimes assimilate a k-shape into its k-boundary.

2.3.

Irreducible k-shapes. Let λ be a k-shape and (u, v) a pair of positive integers. Following [START_REF] Hivert | Combinatorics of k-shape and Genocchi numbers[END_REF], we denote by H u (λ) (respectively V v (λ)) the set of all cells of the skew partition ∂ k (λ) that are contained in a row of length u (resp. the set of all cells of ∂ k (λ) that are contained in a column of height v). For example, consider the 5-shape λ = (4, 2, 2, 1). The sets (H u (λ)) u≥1

Definition 2.2 ([HM11]

). An irreducible k-shape is a k-shape λ such that the sets

H i (λ) ∩ V k-i (λ) and H i (λ) ∩ V k+1-i (λ) contain at most i -1 horizontal steps of the k-rim of λ for all i ∈ [k].
We denote by IS k the set of irreducible k-shapes.

For example, the 5-shape λ = (4, 2, 2, 1) (see Figure 4) is irreducible: the sets H i (λ) ∩ V 5-i (λ) and H j (λ) ∩ V 6-j (λ) are empty if i = 2 and j = 3, and the two sets H 2 (λ) ∩ V 3 (λ) and H 3 (λ) ∩ V 3 (λ) contain respectively 1 < 2 and 1 < 3 horizontal steps of the k-rim of λ.

In general, it is easy to see that for any k-shape λ to be irreducible, the sets H 1 (λ) ∩ V k (λ) and H k (λ) ∩ V 1 (λ) must be empty, and by definition the set H 1 (λ) ∩ V k-1 (λ) must contain no horizontal step of the k-rim of λ. In particular, for k = 1 or 2 there is only one irreducible k-shape: the empty partition. [START_REF] Hivert | Combinatorics of k-shape and Genocchi numbers[END_REF][START_REF] Mallet | Combinatoire des k-formes et nombres de Genocchi[END_REF]). Let λ be an irreducible k-shape with k ≥ 3. For all i ∈ [k-2], we say that the integer i is a free k-site of λ if the set H k-i (λ) ∩ V i+1 (λ) is empty. We define -→ f r(λ) as the vector (t 1 , t 2 , . . . , t k-2 ) ∈ {0, 1} k-2 where t i = 1 if and only if i is a free k-site of λ. We also define f r(λ) as k-2 i=1 t i (the quantity of free k-sites of λ).

Definition 2.3 ([
For example, the irreducible 5-shape λ = (4, 2, 2, 1) depicted in Figure 4 is such that -→ f r(λ) = (1, 0, 1). In order to prove the conjecture of Formula 2, and in view of Theorem 2.1, Hivert and Mallet proposed to construct a bijection φ : IS k → SP k-1 such that f ix(φ(λ)) = f r(λ) for all λ. Mallet [START_REF] Mallet | Combinatoire des k-formes et nombres de Genocchi[END_REF] refined the conjecture by introducing a vectorial version of the statistic of fixed points: for all f ∈ SP k-1 , we define -→ f ix(f ) as the vector (t 1 , . . . , t k-2 ) ∈ {0, 1} k-2 where

t i = 1 if and only if f (2i) = 2i (in particular f ix(f ) = i t i ). Conjecture 2.1 ([Mal11]). For all k ≥ 3 and - → v = (v 1 , v 2 , . . . , v k-2 ) ∈ {0, 1} k-2 , the number of irreducible k-shapes λ such that -→ f r(λ) = - → v is the number of surjective pistols f ∈ SP k-1 such that -→ f ix(f ) = - → v .
The main result of this paper is the following theorem, which implies immediately Conjecture 2.1.

Theorem 2.2. There exists a bijection ϕ :

SP k-1 → IS k such that -→ f r(ϕ(f )) = -→ f ix(f ) for all f ∈ SP k-1 .
We intend to demonstrate Theorem 2.2 in the following two sections §3 and §4.

Partial k-shapes

Definition 3.1 (Labeled skew partitions, partial k-shapes and saturation property). A labeled skew partition is a skew partition s whose columns are labeled by the integer 1 or 2. If cs(s) is a partition and if the hook length of every cell of s doesn't exceed k (resp. k -1) when the cell is located in a column labeled by 1 (resp. by 2), we say that s is a partial k-shape. In that case, if C 0 is a column labeled by 1 which is rooted in a row R 0 (i.e., whose bottom cell is located in R 0 ) whose top left cell is hook lengthed by k, we say that C 0 is saturated. For all i ∈ [k -1], if every column of height i + 1 and label 1 is saturated in s, we say that s is saturated in i. If s is saturated in i for all i, we say that s is saturated.

We represent labeled skew partitions by painting in dark blue columns labeled by 1, and in light blue columns labeled by 2. For example, the skew partition depicted in Figure 5 is a partial 6-shape, which is not saturated because its unique column C labeled by 1 is rooted in a row whose top left cell (which is in this exemple the own bottom cell of C) is hook lengthed by 5 instead of 6. Definition 3.2 (Sum of partial k-shapes with rectangles). Let s be a partial k-shape, and j ≥ 1 such that the height of every column of s is at least (j + 2)/2 (if s is the empty skew partition we impose no condition on j). Let z be a nonnegative integer and t(j) the integer defined as 1 if j is even and 2 if j is odd. We consider the labeled skew partition s obtained by gluing right on the last column of s, the amount of z columns of height (j + 1)/2 (see Figure 6. Partial 6-shape s ⊕ 6 1 3 2 .

Figure 7. Gluing of the rectangle (j + 1)/2 z j to s.

Figure 7) labeled by the integer t(j). We apply the following algorithm on s as long as one of the three corresponding conditions is satisfied.

(1) If there exists a column C 0 labeled by 1 (respectively by 2) in s such that the bottom cell c 0 of C 0 is a corner of s (a cell of s with no other cell beneath it or on the left of it) whose hook length h exceeds k (resp. k -1), then we lift the column C 0 , i.e., we erase c 0 and we draw a cell on the top of C 0 (see Figure 8). (2) If there exists a column C 0 of height i 0 + 1 (with i 0 ∈ [k -2]) and labeled by 1 in s, such that the bottom cell c 0 of C 0 is on on the right of the bottom cell of a column whose height is not i 0 + 1 or whose label is not 1, then we lift every column on the left of C 0 whose bottom cell is located in the same row as c 0 , i.e., we erase every cell on the left of c 0 and we draw a cell on every corresponding column (see Figure 9). (3) If there exists a column C 0 of height i 0 + 1 (with i 0 ∈ [k -2]) and labeled by 1 in s, such that the bottom cell c 0 of C 0 is a corner whose hook length h doesn't equal k (which means it is rooted in a row R 0 of s whose length is k -i 0 -l < k -i 0 for some l ≥ 1), whereas this hook length was exactly k in the partial k-shape s, then we lift every column rooted in the same row as the l last columns (from left to right) intersecting R 0 , in such a way the hook length of c 0 becomes k again in s (see Figure 10). It is easy to see that this algorithm is finite and that the final version of s is a partial k-shape, that we define as the t(j)-sum of the partial k-shape s with the rectangle (j + 1)/2 z (the partition whose Ferrers diagram is a rectangle of length z and height (j + 1)/2 ), and which we denote by

s ⊕ k t(j) (j + 1)/2 z .
For example, the 1-sum s ⊕ 6 1 3 2 of the partial 6-shape s represented in Figure 5, with the rectangle composed of 2 columns of height 3 and label 1, is the partial 6-shape depicted in Figure 6.

Remark 3.1. In the context of Definition 3.2, the rule (3) of the latter definition guarantees that any saturated column of s is still saturated in s ⊕ k t(j) (j + 1)/2 z . In particular, if s is saturated in i ∈ [k -2], then s ⊕ k t(j) (j + 1)/2 z is also saturated in i. Lemma 3.1. Let s be a partial k-shape, let j ∈ [2k -4] such that every column of s is at least (j + 2)/2 cells high, and let z ∈ {0, 1, . . . , k -1 -j/2 }. We consider two consecutive columns (from left to right) of s, which we denote by C 1 and C 2 , with the same height and the same label but not the same level, and such that C 1 has been lifted in the context (1) of Definition 3.2 (note that it cannot be in the context (2)). If C 2 has been lifted at the same level as C 1 in s ⊕ k t(j) (j + 1)/2 z , then it is not in the context (1) of Definition 3.2. Proof. Let R 1 (resp. R 2 ) be the row in which C 1 (resp. C 2 ) is rooted, and let R be the row beneath R 1 . Let l be the length of R. Since C 1 and C 2 have the same height and the same label, and since C 1 has been lifted in the context (1) of Definition 3.2, then it is necessary that the length of R 2 equals l as well. Consequently, the partial k-shape s is like depicted in Figure 11. We also consider the last column C 3 to be rooted in R 2 , and the column C 4 on the right of C 3 . Now, suppose that, in s ⊕ k t(j) (j + 1)/2 z , the column C 2 has been lifed at the same level as C 1 in the context (1) of Definition 3.2. To do so, it is necessary that the row R gains cells between s and s ⊕ k t(j) (j + 1)/2 z , i.e., that the column C 4 is lifted at the same level as C 3 . By hypothesis, it means that C 4 must be lifted down to at least (j + 2)/2 cells between s and s ⊕ k t(j) (j + 1)/2 z . Obviously, every column of s ⊕ k t(j) (j + 1)/2 z has been lifted up to at most (j + 1)/2 cells, so (j + 1)/2 = (j + 2)/2 , i.e., there exists p ∈ [k -2] such that j = 2p. Consequently, the partial k-shape s ⊕ k t(j) (j + 1)/2 z is obtained by adding z columns of height p + 1 and label 1 to s. However, according to the rule (3) of Definition 3.2, only the p top cells of those z columns may lift the columns of s in the context (1), i.e., the columns of s are lifted up to at most p cells in this context, thence C 4 cannot be lifted at the same level as C 3 , which is absurd.

Remark 3.2. Here, we give precisions about context (3) of Definition 3.2. Using the same notations, consider the column C 1 of s which contains the last cell (from left to right) of R 0 , and C 2 the column which follows C 1 (see Figure 12). Since C 0 loses (momentarily) its saturation during the computation of s ⊕ k t(j) (j + 1)/2 z , it is necessary that the columns C 1 and C 2 have the same height and the same label in order to obtain the situation depicted in Figure 13. Consequently, the lifting of C 1 in Figure 12 comes from rule (1) of Definition 3.2 (it cannot be prompted by rule (3) because C 0 has not lost its saturation yet). Also, if the label of C 1 and C 2 is 1, then the hook length h 2 of the bottom cell c 2 of C 2 equals k in Figure 13 Figure 12. Partial k-shape s.

Figure 13. Between s and s ⊕ k t(j) (j + 1)/2 z .

(because C 1 has been lifted in the context (1)), implying the situation depicted in Figure 13 cannot be reached because, as noticed in Remark 3.1, the hook length h 2 of c 2 still equals k in Figure 13, forcing C 1 to be lifted by the rule (1). So, the label of C 1 and C 2 must be 2, and

h 2 = k -1.
Finally, according to Lemma 3.1, the lifting of C 2 in Figure 13 must be done in the context (2) of Definition 3.2: indeed, if it was context (3), there would exist a column C 0 labeled by 1 between C 0 and C 2 , which would be lifted so that its bottom cell ends up in the row R 0 (in order for C 2 to be lifted at the same level). But then, since C 0 has not lost its saturation yet at this time (because C 2 has not been lifted yet), the column C 0 would be rooted in R 0 thus would be saturated, which is absurd because by hypothesis C 0 is supposed to lose momentarily its saturation. Thus, the column C 3 depicted in Figure 13 is labeled by 1.

Lemma 3.2. Let s be a partial k-shape and j ≥ 1 such that the height of every column of s is at least (j + 2)/2 , and such that the quantity of integers i

∈ [k -2] in which s is not saturated is at most j/2 . Then, if s is not saturated in i 0 ∈ [k -2],
there exists a unique integer z ∈ [k -1 -j/2 ] such that the partial k-shape s ⊕ k t(j) (j + 1)/2 z is saturated in i 0 . Proof. According to Remark 3.2, columns labeled by 1 cannot be lifted in the context (3) of Definition 3.2. Consequently, in the partial k-shape s, the columns of height i 0 + 1 and label 1 are organized in m ≥ 1 groups of columns rooted in a same row, such that the m -1 first groups from right to left are made of saturated columns, i.e., such that the columns of these groups are rooted in rows whose top left cell is hook lengthed by k, and such that the m-th group is made of non-saturated columns, i.e., such that the columns C 1 , C 2 , . . . , C q of this group (from left to right) are rooted in a row whose top left cell (which is the bottom cell c 1 of C 1 ) is hook lengthed by some integer h < k (see Figure 14). Now, for all p ∈ [k -j/2 ], let s p be the partial k-shape s ⊕ k t(j) (j + 1)/2 p . For all p ≥ 2, the partial k-shape s p is obtained by gluing a column of height (j + 1)/2 and label t(j) right next to the last column of s p-1 , then by applying the 3 rules of Definition 3.2 so as to obtain a partial k-shape. We now focus on s k-j/2 . Let C be a column of s. Since the height of C is at least (j + 2)/2 , if the bottom cell c of C is located in the same row as one of the cells of the rectangle (j + 1)/2 k-j/2 during the computation of s k-j/2 , then the hook length of c will be at least (j + 2)/2 + k -j/2 ≥ k + 1. Consequently, according to the rule (1) of Definition 3.2, the column C is lifted as long as its bottom cell is in the same row as one of the cell of the rectangle (j + 1)/2 k-j/2 , and since this holds for every column C of s, then the partial k-shape s k-j/2 is obtained by drawing the rectangle (j + 1)/2 k-j/2 in the bottom right Figure 15. Partial k-shape s k-j/2 . hand corner of s (see Figure 15). In particular, the columns C 1 , C 2 , . . . , C q must have been been lifted (j + 1)/2 times between s and s k-j/2 . The idea is to prove there exists a unique p 0 ∈ [k -1 -j/2 ] such that C 1 has been lifted in the context (1) of Definition 3.2 in s p 0 +1 , implying the hook length h of c 1 equals k in s p 0 , which means s p 0 is saturated in i 0 according to Remark 3.1. Note that the columns C 1 , C 2 , . . . , C q cannot be lifted in the context (3) of Definition 3.2 because their label is 1 (see Remark 3.2). If m ≥ 2, the columns C 1 , C 2 , . . . , C q cannot be lifted in the context (2), hence they are lifted in the context (1), so the existence and unicity of the integer p 0 is obvious. If m = 1, suppose C 1 is never lifted in the context (1), i.e., that it is lifted (j + 1)/2 times in the context (2) between s and s k-j/2 . Each of these (j + 1)/2 times, the first column labeled by 1 (from right to left) prompting the chain reaction of liftings in the context (2) (which leads to the lifting of C 1 ), must be different from the others. Also, the columns labeled by 1 responsible for these liftings cannot be saturated, because from Remark 3.1 they would still be saturated when glued to the columns of different height or label that are lifted, meaning their bottom cell would be hooked lengthed by k and that the lifting would be in the context (1), which is absurd. As a conclusion, it is necessary that in addition to i 0 , there would exist (j + 1)/2 ≥ j/2 different integers i < i 0 such that s is not saturated in i, which is absurd by hypothesis.

Proof of Theorem 2.2

We first construct two key algorithms in the first two subsections.

4.1. Algorithm ϕ : SP k-1 → IS k . Definition 4.1 (Algorithm ϕ). Let f ∈ SP k-1 .
We define s 2k-3 (f ) as the empty skew partition.

For

j from 2k -4 downto 1, let i ∈ [k -1] such that f (j) = 2i
, and suppose that the hypothesis H(j + 1) defined as "if s j+1 (f ) is not empty, the height of every column of s j+1 (f ) is at least (j + 2)/2 , and the number of integers i in which s j+1 (f ) is not saturated is at most j/2 " is true (in particular H(2k -3) is true so we can initiate the algorithm).

(

) If f (2i) > 2i, if j = min{j ∈ [2k -4], f (j ) = 2i} 1
and if the partial k-shape s j+1 is not saturated in i, then we define s j (f ) as s j+1 (f ) ⊕ k t(j) (j + 1)/2 z j (f ) where z j (f ) is the unique element of [k -1 -j/2 ] such that s j+1 (f ) ⊕ k t(j) (j + 1)/2 z j (f ) is saturated in i (see Lemma 3.2 in view of Hypothesis H(j + 1)).

(2) Else, we define s j (f ) as s j+1 (f ) ⊕ k t(j) (j + 1)/2 z j (f ) where f (j) = 2( j/2 + z j (f )) (notice that z j (f ) ∈ {0, 1, . . . , k -1 -j/2 } by definition of a surjective pistol). In either case, if s j (f ) is not empty, then the height of every column is at least (j + 1)/2 . Also, suppose there exists at least (j -1)/2 + 1 different integers i ∈ [k -2] in which s j (f ) is not saturated. In view of the rule (1) of the present algorithm, this implies there are at least (j -1)/2 + 1 integers j ≤ j -1 such that f (j ) ≥ 2 j/2 . Also, since f is surjective, there exist at least j/2 -1 integers j ≤ j -1 such that f (j ) ≤ 2( j/2 -1). Consequently, we obtain ( (j -1)/2 + 1)+( j/2 -1) ≤ j -1, which cannot be because (j -1)/2 + j/2 = j. So the hypothesis H(j) is true and the algorithm goes on. Ultimately, we define ϕ(f ) as the partition < s 1 (f ) >.

Proposition 4.1. For all f ∈ SP k-1 , the partition λ = ϕ(f ) is an irreducible k-shape such that ∂ k (λ) = s 1 (f ) and -→ f r(λ) = -→ f ix(f ).
For example, consider the surjective pistol f = (2, 8, 4, 10, 10, 6, 8, 10, 10, 10) ∈ SP 5 whose tableau is depicted in Figure 16. Apart from 10, the only fixed point of f is 6, so -→ f ix(f ) = (0, 0, 1, 0). Algorithm ϕ provides the sequence (s 8 (f ), s 7 (f ), . . . , s 1 (f )) depicted in Figure 17

(note that s 8 (f ) = s 7 (f ) = s 6 (f ) because z 7 (f ) = z 6 (f ) = 0). j ∈ {8; 7; 6} j = 5 j = 4 j = 3 j = 2 j = 1 Figure 17. Sequence (s j (f )) j∈[8] .
Thus, we obtain s 1 (f ) = ∂ 6 (λ) where λ = ϕ(f ) =< s 1 (f ) >. In particular, the sequences rs 6 (λ) = (5, 4, 4, 3, . . . , 1) and cs 6 (λ) = (5, 3, 3, 3, . . . , 1) are partitions, so λ is a 6-shape.

Finally, we can see in Figure 18 that λ is irreducible and Proof. By construction, the skew partition s 1 (f ) is a saturated partial k-shape (the saturation is guaranteed by Hypothesis H(1)). As a partial k-shape, the hook length of every cell doesn't exceed k. Consequently, to prove that ∂ k (ϕ(f )) = s 1 (f ), we only need to show that the hook length h 1 of every anticoin of s 1 (f ) (namely, cells glued simultaneously to the left of a row of s 1 (f ) and beneath a column of s 1 (f ), see Figure 19) is such that h 1 > k.

-→ f r(λ) = (0, 0, 1, 0) = -→ f ix(f ).
Figure 19. Anticoin labeled by its hook length h 1 .

Figure 20

Anticoins of s 1 (f ) are created by lifting columns in one of the three contexts (1),(2) or (3) of Definition 3.2. Let x 1 (resp. y 1 ) be the length of the row R 1 (resp. the height of the column C 1 ).

(1) If C 1 has been lifted in the context (1), then

x 1 + y 1 > k (if c 1 is labeled by 1) or x 1 + y 1 > k -1 (if C 2 is labeled by 2).
In either case, we obtain h 1 = 1 + x 1 + y 1 > k.

(2) If C 1 has been lifed in the context (2), then the first cell (from left to right) of the row R 1 is a corner, and it is the bottom cell of a column C 2 labeled by 1 (see Figure 20). Let y 2 be the height of C 2 . Since C 2 is saturated, then the hook length h 2 = x 1 + y 2 -1 of its bottom cell equals k. Consequently, since y 1 ≥ y 2 , we obtain h 1 = x 1 + y 1 -1 > k.

(3) Else C 1 has been lifted in the context (3). Let C 0 be the saturated column of s 1 (f ) such that C 1 is the column that contains the last cell (from left to right) of the row R 0 in which C 0 is rooted (see Figure 21). Let j ∈ [2k -4] such that C 0 is saturated in the partial k-shape s j+1 (f ) and such that C 0 loses its saturation at some point of the computation of s j (f ) (recall that C 0 is saturated at the end of this computation by the rule (3) of Definition 3.2). The partial k-shape s j+1 (f ) then presents the situation depicted in Figure 22. Following Remark 3.2, the columns C 1 and C 2 have the same height and the same label 2 (and h 2 = k -1), and in order for C 0 to lose temporarily its saturation between s j+1 (f ) and s j (f ), there exists a column C 3 labeled by 1 on the right of C 2 such that C 2 is lifted at the same level as C 1 in the context (2) of Definition 3.2, with C 3 being the column responsible for this lifting (see Figure 23). Now, the rule (3) of Definition 3.2 yields the situation depicted in Figure 24, in which h 2 = h 2 -l where l ≥ 1 is the number of gray cells. Finally, in order to saturate C 3 (every column labeled by 1 being saturated in s 1 (f )), it is necessary to lift the l gray cells. Indeed, otherwise, the column C 3 would become saturated by lifting columns C 5 , C 6 , . . . , C m whose top cells would be glued to the right of the last gray cells, meaning those columns have the same height y and the same label t as the l columns whose top cells are the gray cells. Obviously, since C 3 is not saturated yet at that moment, the columns C 5 , C 6 , . . . , C m are not lifted in the context (3) of Definition 3.2. In view of Lemma 3.1, these columns must have been lifted in the context (2), which implies every column of height y and label t are lifted to the same level as the last gray cell. But then it would lift the column C 3 in the context (1) of Definition 3.2 instead of saturating it, which is absurd. So the l gray cells are necessarily lifted in s 1 (f ) (see Figure 25), in which h 2 has become h 2 again).

In particular, the hook length h 2 = h 2 equals k -1 and we obtain

h 1 = h 2 + 2 > k. Lemma 4.2. For all f ∈ SP k-1 , the partition λ = ϕ(f ) is a k-shape.
Proof. From Lemma 4.1 we know that s 1 (f ) = ∂ k (λ), and since s 1 (f ) is a partial k-shape by construction, the sequence cs k (λ) = cs(s 1 (f )) is a partition. To prove that λ is a k-shape, it remains to show that the sequence rs k (λ) = rs(s 1 (f )) is a partition. Let R and R be two consecutive rows (from bottom to top) of s 1 (f ) (see Figure 26). Let x, x be the respective lengths of R, R and y 1 ≥ y 2 ≥ y 3 the respective heights of the columns C 1 , C 2 , C 3 introduced by the picture. Since s 1 (f ) = ∂ k (λ), we know that the quantity h = y 2 + x + 1 (which is the hook length of the cell glued to C 2 and R) exceeds k. Also, the hook length h 1 of the bottom cell

c 1 of C 1 doesn't exceed k, so x = h 1 -y 1 +1 ≤ k -y 1 +1 ≤ k -y 2 +1 ≤ x+1. Now suppose that x = x + 1. Then h 1 = y 1 + x -1 = y 1 + x ≥ y 2 + x = h -1 ≥ k, so h 1 = k (which implies y 1 = y 2 ).
Consequently C 1 and C 2 are two columns of height y 1 = y 2 , and labeled by 1 because As a conclusion, it is necessary that x ≥ x , then rs k (λ) is a partition and λ is a k-shape.

Lemma 4.3. For all f ∈ SP k-1 , the k-shape λ = ϕ(f ) is irreducible and

-→ f r(λ) = -→ f ix(f ).
Proof. For all i ∈ [k -2], let n i (resp. m i ) be the number of horizontal steps of the k-rim of λ that appear inside the set

H k-i (λ) ∩ V i+1 (λ) (resp. inside the set H k-i (λ) ∩ V i (λ)). Recall that λ is irreducible if and only if (n i , m i ) ∈ {0, 1, . . . , k -1 -i} 2 for all i ∈ [k -2]. Consider i 0 ∈ [k -2].
The number n i 0 is precisely the number of saturated columns of height i 0 + 1 of the partial k-shape s 1 (f ) = ∂ k (λ). Since s 1 (f ) is saturated by construction, this number is the quantity z 2i 0 (f ) < k -i 0 according to Definition 4.1. This statement being true for any i 0 ∈ [k -2], in particular, if i 0 > 1, there are n i 0 -1 = z 2i 0 -2 (f ) columns of height i 0 and label 1 in s 1 (f ), thence the quantity m i 0 is precisely the number z 2i 0 -1 (f ) < k -i 0 of columns of height i 0 and label 2. Also, the columns of height 1 are necessarily labeled by 2, so

m 1 = z 1 (f ) < k -1.
Consequently, the k-shape λ is irreducible. Finally, for all i ∈ [k -2], we have the equivalence

f (2i) = 2i ⇔ z 2i (f ) = 0. Indeed, if f (2i) = 2i then by definition z 2i (f ) = f (2i)/2 -i = 0. Reciprocally, if f (2i) > 2i, then either z 2i (f ) is defined in the context (1) of Definition 4.1, in which case z 2i (f ) > 0, or z 2i (f ) = f (2i)/2 -i > 0.
Therefore, the equivalence is true and exactly translates into

-→ f ix(f ) = -→ f r(λ). 4.2. Algorithm φ : IS k → SP k-1 .
Definition 4.2. Let λ be an irreducible k-shape. For all i ∈ [k -2], we denote by x i (λ) the number of horizontal steps of the k-rim of λ inside the set H k-i (λ) ∩ V i+1 (λ), and by y i (λ) the number of horizontal steps inside the set

V i (λ)\H k+1-i (λ) ∩ V i (λ) = k-i j=1 H j (λ) ∩ V i (λ).
Finally, for all j ∈ [2k -4], we set

z j (λ) = y i (λ) if j = 2i -1, x i (λ) if j = 2i.
For example, if λ is the irreducible 6-shape represented in Figure 18, then (z j (λ)) j∈[8] = (3, 2, 1, 3, 2, 0, 0, 1). Note that in general, if λ is an irreducible k-shape and (t 1 , t 2 , . . . , t k-2 ) = -→ f r(λ), then t i = 1 if and only if x i (λ) = 0, for all i.

Lemma 4.4. For all λ ∈ IS k and for all j ∈ [2k -4], we have

z j (λ) ∈ {0, 1, . . . , k -1 -j/2 }.
Proof. By definition of an irreducible k-shape, we automatically have

z 2i (λ) = x i (λ) < k -i for all i ∈ [k -2].
The proof of z 2i-1 (λ) = y i (λ) < k -i is less straightforward. Suppose that y i (λ) ≥ k -i. Let C 0 be the first column (from left to right) of k-i j=1 H j (λ) ∩ V i (λ), let R 0 the row in which C 0 is rooted, and let R 1 be the row beneath R 1 . We denote by l ∈ [y i (λ)] the number of consecutive columns of k-i j=1 H j (λ) ∩ V i (λ) whose bottom cells are located R 0 , and l the length of R 1 (see Figure 27).

Figure 27

Figure 28 Figure 29 The hook cell h = i + l + 1 of the cell glued to the left of R 1 exceeds k, thence l ≥ k -i. Now suppose that l ≥ k -i: then, the hook length

h ≤ k -1 of the bottom cell c 0 of C 0 is such that h ≥ i + l -1 ≥ k -1 hence h = k -1.
As a result, the first l columns of

k-i j=1 H j (λ)∩V i (λ) are in fact located in H k-i (λ)∩V i (λ), therefore |H k-i (λ)∩V i (λ)| ≥ l ≥ k -i, which contradicts the irreducibility of λ. So l ≤ k -i -1 < y i (λ).
As a consequence, there exists a column of k-i j=1 H j (λ) ∩ V i (λ) which intersects R 1 ; in particular, consider the first column C 1 that does so, then its bottom cell c 1 is located in a row R 2 (whose length is denoted by l ≥ l ) and c 1 is hooked lengthed by

h = i + l -1 < k, thence k -i ≤ l ≤ l ≤ k -i, which implies l = l = k -i. Now, let l ∈ {0, 1, . . . , k -i} be the number of columns of k-i j=1 H j (λ) ∩ V i (λ) intersecting R 1 but whose top cells are not located in R 1 (see Figure 28). Since h = i -1 + l + l ≤ k -1, we obtain l + l ≤ k -i. With precision, we must have l + l ≤ k -i -1: otherwise, we would have l + l = k -i and h = k -1 which implies the first l + l = k -i columns of k-i j=1 H j (λ) ∩ V i (λ) are located in H k-i (λ) ∩ V i (λ), which cannot be because λ is irreducible. So l + l < k -i ≤ y i (λ). It means there exists a column C 2 of k-i j=1 H j (λ) ∩ V i (λ) whose top box is located in R 1 ,
which forces its bottom cell to be located in a row R 3 of length k -i (see Figure 29) because rs(λ) is a partition. But then the bottom cell of every column intersecting R 1 is located in a row of length k -i, therefore the bottom cells of those k -i columns are elements of the set H k-i (λ) ∩ V i (λ), which cannot be because λ is irreducible and the length of R 1 is k -i. As a conclusion, it is necessary that y i (λ) < k -i.

Definition 4.3. Let λ ∈ IS k . We define a sequence (s j (λ)) j∈[2k-3] of partial k-shapes by s 2k-3 (λ) = ∅ and s j (λ) = s j+1 (λ) ⊕ k t(j) (j + 1)/2 z j (λ) .
Lemma 4.5. We have

s 1 (λ) = ∂ k (λ) for all λ ∈ IS k .
Proof. Let n be the number of columns of [λ], which is obviously the same as for ∂ k (λ) and s 1 (λ). For all q ∈ [n], we define ∂ k (λ) q (respectively s 1 (λ) q ) as the skew partition (resp. labeled skew partition) obtained by considering the q first columns (from right to left) of ∂ k (λ) (resp. s 1 (λ)). The idea is to prove that ∂ k (λ) q = s 1 (λ) q for all q ∈ [n] by induction (the statement being obvious for q = 1). In particular, for q = n, we will obtain ∂ k (λ) = s 1 (λ). Suppose that ∂ k (λ) q = s 1 (λ) q for some q ≥ 1. The (q + 1)-th column C q+1 (whose bottom cell is denoted by c q+1 ) of ∂ k (λ) q+1 (from right to left) is glued to the left of ∂ k (λ) q , at the unique level such that the hook length h of c q+1 doesn't exceed k, and the hook length x of the cell beneath c q+1 exceeds k. Since the hook length of every cell of s 1 (λ) doesn't exceed k, the (q + 1)-th column C q+1 (whose bottom cell is denoted by c q+1 ) of s 1 (λ) q+1 is necessarily positionned above or at the same level as C q+1 (see Figure 30 where C q+1 [resp. C q+1 ] has been drawed in black [resp.

in red] and whose bottom cell is labeled by its hook length h [resp. h ]). Now, suppose that the columns C q+1 and C q+1 are not at the same level. In particular, the hook length x of the cell beneath c q+1 is such that x ≤ h ≤ k. Also, the bottom cell c q of the q-th column C q of s 1 (λ) q+1 is a corner.

(1) If C q+1 has been lifted in the context (1) of Definition 3.2, then since x ≤ k, the label of C q+1 is necessarily 2, and x = k. Consequently, the cell c q+1 is in fact the cell labeled by x , and h = x = k. In particular, this implies C q+1 is labeled by 1, which is absurd because C q+1 and C q+1 must have the same label.

(2) If C q+1 has been lifted in the context (2) of Definition 3.2, then in particular C q is a column labeled by 1. Consequently, the hook length of c q , which is the same as c q because s 1 (λ) q = ∂ k (λ) q , is the integer h = k. Since rs k (λ) and cs k (λ) are partitions, this implies h > h = k, which is absurd. (3) Therefore, the column C q+1 has necessarily been lifted in the context (3) of Definition 3.2. According to Remark 3.2, it implies : (a) C q+1 and C q have the same height and the same label 2 (and h = k -1); (b) C q+1 is located one cell higher than C q .

In particular, from (b), since C q+1 is supposed to be located at a higher level than C q+1 , then the cell c q+1 is glued to the left of the cell c q . Since h = k -1, we obtain h = k, which is in contradiction with C q+1 being labeled by 2.

So C q+1 and C q+1 are located at the same level, thence

∂ k (λ) q+1 = s 1 (λ) q+1 .
Notice that Lemma 4.5 is obvious if we know that λ = ϕ(f ) for some surjective pistol f ∈ SP k-1 , because in that case s j (λ) = s j (f ) for all j.

Definition 4.4 (Algorithm φ). Let λ ∈ IS k . We define m(λ) ∈ {0, 1, . . . , k -2} and

1 ≤ i 1 (λ) < i 2 (λ) < . . . i m (λ) ≤ k -2 such that {i 1 (λ), i 2 (λ), . . . , i m(λ) (λ)} = {i ∈ [k -2], x i (λ) > 0} (this set may be empty). For all p ∈ [m(λ)], let j p (λ) = max{j ∈ [2i p (λ) -1], s j (λ) is saturated in i p (λ)}. Let L(λ) = [2k -4]. For j from 1 to 2k -4, if j = j p (λ) for some p ∈ [m(λ)],
and if there is no j ∈ L(λ) such that j < j and j /2 + z j = i p (λ), then we set L(λ) := L(λ)\{j p (λ)}. Now we define φ(λ) ∈ N [2k-2] as the following: the integers φ(λ)(2k -2) and φ(λ)(2k -3) are defined as 2k -2; afterwards, let j ∈ [2k -4].

• If j ∈ L(λ) then φ(λ)(j) is defined as 2( j/2 + z j (λ)).

• Else there exists a unique p ∈ [m(λ)] such that j = j p (λ), and we define φ(λ)(j) as 2i p (λ).

Proposition 4.2. For all λ ∈ IS k , the map φ(λ) is a surjective pistol of height k -1, such that -→ f ix(φ(λ)) = -→ f r(λ).
For example, consider the irreducible 6-shape λ of Figure 18, such that (z j (λ)) j∈[8] = (3, 2, 1, 3, 2, 0, 0, 1). In particular (x 1 (λ), x 2 (λ), x 3 (λ), x 4 (λ)) = (2, 3, 0, 1) so m(λ) = 3 and (i 1 (λ), i 2 (λ), i 3 (λ)) = (1, 2, 4). Moreover, by considering the sequence of partial 6-shapes (s 8 (λ), . . . , s 1 (λ)), which is in fact the sequence (s 8 (f ), . . . , s 1 (f )) depicted in Figure 17 (with f = (2, 8, 4, 10, 10, 6, 8, 10, 10, 10) ∈ SP 5 ) because λ = ϕ(f ), we obtain (j 2 (λ), j 3 (λ), j 1 (λ)) = (3, 2, 1). Applying the algorithm of Definition 4.4 on L(λ) = [8], we quickly obtain L(λ) = {4, 5, 6, 7, 8}. Consequently, if g = φ(λ), then automatically g(10) = g(9) = 10, afterwards (g(1), g(2), g(3)) = (g(j 1 (λ)), g(j 3 (λ), g(j 2 (λ)) = (2i 1 (λ), 2i 3 (λ), 2i 2 (λ)) = (2, 8, 4) since j p (λ) ∈ L(λ) for all p ∈ [3], and g(j) = 2( j/2 + z j (λ)) for all j ∈ L(λ). Finally, we obtain g = (2, 8, 4, 10, 10, 6, 8, 10, 10, 10) = f (and

-→ f ix(g) = -→ f r(λ)).
Proof of Proposition 4.2. Let λ ∈ IS k and f = φ(λ). We know that f (2k

-2) = f (2k -3) = 2k -4. Consider j ∈ [2k -4].
(1) If j = j p (λ) for some p ∈ [m(λ)] and if j ∈ L(λ), then f (j) = 2i p (λ). By definition 2i p (λ) > j p (λ), so 2k -2 ≥ f (j) > j.

(2) Else f (j) = 2( j/2 + z j (λ)), so 2k -2 ≥ f (j) ≥ j following Lemma 4.4.

Consequently f is a map [2k -2] → {2, 4, . . . , 2k -2} such that f (j) ≥ j for all j ∈ [2k -2]. Now, we prove that f is surjective. We know that 2k -2 = f (2k -2). Let i ∈ [k -2].

• If i = i p (λ) for some p ∈ [m(λ)], then either j p (λ) ∈ L(λ), in which case 2i = f (j p (λ)), or there exists j < j p (λ) in L(λ) such that j/2 + z j = i, in which case 2i = f (j). • Else z 2i (λ) = 0, which implies that 2i cannot be equal to any j p (λ) because s 2i (λ) = s 2i+1 (λ)⊕ k 1 (i+1) z j (λ) = s 2i+1 (λ). Consequently 2i ∈ L(λ), thence f (2i) = 2(i+z 2i (λ)) = 2i. Therefore f ∈ SP k-1 . Finally, for all i ∈ [k -2], we have just proved that z 2i (λ) = 0 implies f (2i) = 2i. Reciprocally, if f (2i) = 2i, then necessarily 2i ∈ L(λ) (otherwise 2i would be j p (λ) for some p and f (2i) would be 2i p (λ) > j p (λ) = 2i),

meaning 2i = f (2i) = 2(i + z 2i (λ)) thence z 2i (λ) = 0. The equivalence z 2i (λ) = 0 ⇔ f (2i) = 2i for all i ∈ [k -2] exactly translates into -→ f r(λ) = -→ f ix(f ).
4.3. Proof of Theorem 2.2. At this stage, we know that ϕ is a map SP k-1 → IS k that transforms the statistic -→ f ix into the statistic -→ f r. The bijectivity of ϕ is a consequence of the following proposition. (1) j p (λ) ∈ L(λ).

(2) j p (λ) = j p (λ).

Proof. Let f ∈ SP k-1 and λ = ϕ(f ). In particular, we have s j (λ) = s j (f ) and z j (λ) = z j (f ) for all j ∈ [2k -4]. For all p ∈ [m(λ)], by Definition 4.1 the partial k-shape s j p (λ) (f ) = s j p (λ) (λ) is necessarily saturated in i p (λ), thence j p (λ) ≥ j p (λ).

(1) If j p (λ) ∈ L(λ), suppose that j p (λ) > j p (λ). Then, the partial k-shape s j p (λ)+1 (f ) = s j p (λ)+1 (λ) is saturated in i p (λ), meaning the integer z j p (λ) (f ) = z j p (λ) (λ) is defined as f (j p (λ))/2 -j p (λ)/2 = i p (λ) -j p (λ)/2 . Consequently, since j p (λ) ∈ L(λ) and j p (λ) < j p (λ), the integer j p (λ) cannot belong to L(λ) either. So j p (λ) = j p 1 (λ) for some p 1 = p because j p (λ) = j p (λ). Also, since f (j p 1 (λ)) = 2i p (λ) = 2i p 1 (λ) , then j p 1 (λ) > j p 1 (λ) (and j p 1 (λ) = j p (λ) ∈ L(λ)). By iterating, we build an infinite decreasing sequence (j p i (λ)) i≥1 of distinct elements of [2k -4], which is absurd. Therefore, it is necessary that j p (λ) = j p (λ).

(2) Reciprocally, if j p (λ) = j p (λ), suppose that j p (λ) ∈ L(λ). Then, there exists j ∈ L(λ) such that j < j p (λ) and z j (λ) = i p (λ) -j/2 . Let i ∈ [k -1] such that f (j) = 2i (since j < j p (λ) = j p (λ), we know that i = i p (λ)). Suppose s j (f ) is defined in the context (1) of Definition 4.1. In particular i = i p 1 (λ) for some

p 1 ∈ [m(λ)] (because f (2i) > 2i which implies z 2i (λ) = z 2i (f ) > 0)
, and j = j p 1 (λ) and s j+1 (f ) is not saturated in i.

Then, by definition the partial k-shape s j (f ) is the first partial k-shape to be saturated in i p 1 (λ) in the sequence (s 2k-4 (f ) = s 2k-4 (λ), . . . , s 1 (f ) = s 1 (λ)), meaning j = j p 1 (λ).

To sum up, the integer j = j p 1 (λ) = j p 1 (λ) doesn't belong to L(λ), and p 1 = p because f (j) = 2i p 1 (λ) and j < j p (λ) = j p (λ). By iterating, we build an infinite decreasing sequence (j p i (λ)) i≥1 of elements of [2k -4], which is absurd. So s j+1 (f ) is necessarily defined in the context (2) of Definition 4.1, meaning z j (f ) = f (j)/2 -j/2 ). Since z j (f ) = z j (λ) = i p (λ) -j/2 , we obtain f (j) = 2i p (λ), which is in contradiction with j p (λ) = j p (λ) > j. As a conclusion, it is necessary that j p (λ) ∈ L(λ). Now let λ ∈ IS k and f = φ(λ). We consider p ∈ [m(λ)].

(1) If j p (λ) ∈ L(λ), suppose that j p (λ) = j p (λ). Then, by definition f (j p (λ)) = 2i p (λ), meaning j p (λ) > j p (λ). Suppose now that j p (λ) ∈ L(λ), then 2i p (λ) = f (j p (λ)) = 2( j p (λ)/2 + z j p (λ) (λ)). As a result, we obtain z j p (λ) (λ) = i p (λ) -j p (λ)/2 , which is in contradiction with j p (λ) ∈ L(λ). So j p (λ) ∈ L(λ), which implies j p (λ) = j p 1 (λ) for some p 1 = p, and necessarily j p 1 (λ) = j p 1 (λ) since f (j p 1 (λ)) = 2i p (λ) = 2i p 1 (λ).

By iterating, we build a sequence (j p i (λ)) i≥1 of distinct elements of [2k -4], which is absurd. So j p (λ) = j p (λ).

(2) Reciprocally, if j p (λ) = j p (λ), suppose that j p (λ) ∈ L(λ). Then, there exists j ∈ L(λ) such that j < j p (λ) and z j (λ) = i p (λ) -j/2 . Let i ∈ [2k -4] such that f (j) = 2i. Because j p (λ) > j, we have i = i p (λ). And since j ∈ L(λ), we obtain 2i = f (j) = 2( j/2 + z j (λ)) = 2i p (λ), which is absurd. So j p (λ) ∈ L(λ).

Proof of Proposition 4.3.

Let f ∈ SP k-1 and λ = ϕ(f ) and g = φ(λ). Let j ∈ [2k -4] and i ∈ [k -1] such that f (j) = 2i.
(1) If s j (f ) is defined in the context (1) of Definition 4.1, then there exists p ∈ [m(λ)] such that i = i p (λ) and j = j p (λ) = j p (λ). Consequently, in view of Lemma 4.6 with λ = ϕ(f ), we know that j ∈ L(λ), implying g

(j) = g(j p (λ)) = 2i p (λ) = 2i = f (j). (2) If s j (f ) is defined in the context (2) of Definition 4.1, then z j (f ) = f (j)/2 -j/2 = i -j/2 . Now it is necessary that j ∈ L(λ): otherwise j = j p (λ) for some p ∈ [m(λ)],
and from Lemma 4.6 we would have j = j p (λ) = j p (λ), which is impossible because we are in the context (2) of Definition 4.1. So j ∈ L(λ), implying g

(j) = 2( j/2 +z j (λ)) = 2( j/2 + z j (f )) = 2i = f (j).
As a conclusion, we obtain g = f so φ • ϕ is the identity map of SP k-1 . Reciprocally, let µ ∈ IS k and h = φ(µ). We are going to prove by induction that s j (µ) = s j (h) for all j ∈ [2k -3]. By definition s 2k-3 (µ) = s 2k-3 (h) = ∅. Suppose that s j+1 (µ) = s j+1 (h) for some j ∈ [2k -4].

(1) If s j (h) is defined in the context (1) of Definition 4.1, then there exists p ∈ [m(λ)] such that h(j) = 2i p (µ), such that j = j p (µ) and such that s j+1 (h) is not saturated in i p (µ).

Since the partial k-shape s j+1 (µ) = s j+1 (h) is not saturated in i p (µ), by definition j ≥ j p (µ). Suppose that j > j p (µ). Since j = j p (µ), we know from Lemma 4.6 (with λ = µ and f = φ(λ) = h) that j p (µ) ∈ L(µ). It means there exists j < j p (µ) < j such that j ∈ L(µ) and j /2 + z j (µ) = i p (µ), implying h(j ) = 2i p (µ) = h(j), wich contradicts j = j p (µ). So j = j p (µ), therefore s j (µ) is saturated in i p (µ). But since we are in the context (1) of Definition 4.1, the partial k-shape s j (h) is defined as

s j+1 (h) ⊕ k t(j) ( (j + 1)/2 z j (h) where z j (h) is the unique integer z ∈ [k -1 -j/2 ] such that s j+1 (h) ⊕ k t(j) ( (j + 1)/2 z is saturated in i p (µ). Since the partial k-shape s j (µ) = s j+1 (µ) ⊕ k t(j) ( (j + 1)/2 z j (µ) = s j+1 (h) ⊕ k t(j) ( (j + 1)/2 z j (µ)
is saturated in i p (µ), we obtain z j (µ) = z j (h) and s j (µ) = s j (h).

(2) If s j (h) is defined in the context (2) of Definition 4.1, then s j (h) = s j+1 (µ) ⊕ k t(j) (j + 1)/2 z j (h) with z j (h) = h(j)/2 -j/2 . Now either h(j) = 2( j/2 + z j (µ)), in which case we obtain z j (h) = z j (µ), or h(j) = 2i p (µ) for some p ∈ [m(µ)] such that j = j p (µ) ∈ L(µ)). In view of Lemma 4.6, it means j = j p (µ), which cannot happen because otherwise we would be in the context (1) of Definition 4.1. So z j (h) = z j (µ) and s j (h) = s j (µ).

By induction, we obtain s 1 (µ) = s 1 (h), thence µ = ϕ(h). Consequently, the map ϕ • φ is the identity map of IS k .

Extensions

Dumont and Foata [START_REF] Dumont | Une propriété de symétrie des nombres de genocchi[END_REF] introduced a refinement of Gandhi polynomials (Q 2k (x)) k≥1 through the polynomial sequence (F k (x, y, z)) k≥1 defined by F 1 (x, y, z) = 1 and

F k+1 (x, y, z) = (x + y)(x + z)F k (x + 1, y, z) -x 2 F k (x, y, z).
Note that x 2 F k (x, 1, 1) = Q 2k (x) for all k ≥ 1 in view of Formula 1. Now, for all k ≥ 2 and f ∈ SP k , let max(f ) be the number of maximal points of f (points j ∈ [2k -2] such that f (j) = 2k) and pro(f ) the number of prominent points (points j ∈ [2k-2] such that f (i) < f (j) for all i ∈ [j -1]). For example, if f is the surjective pistol (2, 4, 4, 8, 8, 6, 8, 8) ∈ SP 4 depicted in Figure 1, then the maximal points of f are {4, 5}, and its prominent points are {2, 4}. Dumont and Foata gave a combinatorial interpretation of F k (x, y, z) in terms of surjective pistols.

Theorem 5.1 ([DF76]

). For all k ≥ 2, the Dumont-Foata polynomial F k (x, y, z) is symmetrical, and is generated by SP k :

F k (x, y, z) = f ∈SP k x max(f ) y f ix(f ) z pro(f ) .
In 1996, Han [START_REF] Niu | Symétries trivariées sur les nombres de genocchi[END_REF] gave another interpretation by introducing the statistic sur(f ) defined as the number of surfixed points of f ∈ SP k (points j ∈ [2k -2] such that f (j) = j + 1; for example, the surfixed points of the surjective pistol f ∈ SP 4 of Figure 1 are {1, 3}).

Theorem 5.2 ([Han96]

). For all k ≥ 2, the Dumont-Foata polynomial F k (x, y, z) has the following combinatorial interpretation:

F k (x, y, z) = f ∈SP k x max(f ) y f ix(f ) z sur(f ) .
Theorem 2.1 then appears as a particular case of Theorem 5.1 or Theorem 5.2 by setting x = z = 1 (and by applying the symmetry of F k (x, y, z)). Furthermore, for all f ∈ SP k and j ∈ [2k -2], we say that j is a lined point of f if there exists j ∈ [2k -2]\{j} such that f (j) = f (j ). We define mo(f ) (resp. me(f )) as the number of odd (resp. even) maximal points of f , and f l(f ) (resp. f nl(f )) as the number of lined (resp. non lined) fixed points of f , and sl(f ) (resp. snl(f )) as the number of lined (resp. non lined) surfixed points of f . Dumont [START_REF] Dumont | Conjectures sur des symétries ternaires liées aux nombres de Genocchi[END_REF] defined generalized Dumont-Foata polynomials (Γ k (x, y, z, x, ȳ, z)) k≥1 by Γ k (x, y, z, x, ȳ, z) = f ∈SP k x mo(f ) y f l(f ) z snl(f ) xme(f) ȳfnl(f) zsl(f) . This a refinement of Dumont-Foata polynomials, considering Γ k (x, y, z, x, y, z) = F k (x, y, z). Dumont conjectured the following induction formula: Γ 1 (x, y, z, x, ȳ, z) = 1 and Γ k+1 (x, y, z, x, ȳ, z) = (x + z)(y + x)Γ k (x + 1, y, z, x + 1, ȳ, z) + (x(ȳ -y) + x(z -z) -xx)Γ k (x, y, z, x, ȳ, z). (3) This was proven independently by Randrianarivony [START_REF] Randrianarivony | Polynômes de Dumont-Foata généralisés[END_REF] and Zeng [START_REF] Zeng | Sur quelques propriétés de symétrie des nombres de Genocchi[END_REF]. See also [START_REF] Josuat-Vergès | Dumont-Foata polynomials and alternative tableaux[END_REF] for a new combinatorial interpretation of Γ k (x, y, z, x, ȳ, z). Now, let f ∈ SP k-1 and λ = ϕ(f ) ∈ IS k . For all j ∈ [2k -4], we say that j is a chained k-site of λ if j ∈ L(λ). Else, we say that it is an unchained k-site. In view of Lemma 4.6, an integer j ∈ [2k -4] is a chained k-site if and only if j = j p (λ) = j p (λ) for some p ∈ [m(λ)], in which case f (j) = 2i p (λ) (the integer j is forced to be mapped to 2i p (λ), thence the use of the word chained ). If j is an unchained k-site, by definition f (j) = 2( j/2 + z j (λ)). Consequently, every statistic of Theorems 5.1, 5.2 and Formula 3 has its own equivalent among irreducible k-shapes. However, the objects counted by these statistics are not always easily pictured or formalized. We only give the irreducible k-shapes version of Theorem 5.2. Recall that for all i ∈ [k -2], the integer 2i is a fixed point of f if and only if 2i is a free k-site of λ, which is also equivalent to z 2i (λ) = 0. We extend the notion of free k-site to any j ∈ [2k -4]: the integer j is said to be a free k-site if z j (λ) = 0. Notice that free k-sites of λ are necessarily unchained because z j (λ) = 0 implies s j (λ) = s j+1 (λ) thence j = j p (λ) for all p ∈ [m(λ)]. We denote by f ro(λ) the quantity of odd free sites of λ. We denote by f ul(λ) the quantity of full k-site of λ (namely, unchained k-sites j ∈ L(λ) such that z j (λ) = k -1 -j/2 ), and by sch(λ) the quantity of surchained k-sites (chained k-sites j ∈ [2k -4] such that j = j p (λ) for some p ∈ [m(λ)] such that 2i p (λ) = j + 1). Theorem 5.2 can now be reformulated as follows.

Theorem 5.3. For all k ≥ 2, the Dumont-Foata polynomial F k (x, y, z) has the following combinatorial interpretation:

F k (x, y, z) = λ∈IS k+1
x f ul(λ) y f r(λ) z f ro(λ)+sch(λ) .

Proof. First of all, maximal points of f are full k-sites of λ: if f (j) = 2k -2 then z j (f ) is necessarily defined in the context (2) of Definition 4.1, thence z j (λ) = z j (f ) = f (j)/2-j/2 = k -1 -j/2 , and j ∈ L(λ) because otherwise f (j) would equal 2i p (λ) < 2k -2 for some p ∈ [m(λ)]. So j is a full k-site of λ. Reciprocally, if j ∈ L(λ) is such that z j (λ) = k -1-j/2 , then f (j) = 2( j/2 + z j (λ)) = 2k -2 so j is a maximal point of f . Afterwards, surfixed points of f are odd free k-sites and surchained k-sites of λ: if f (j) = j + 1, then j = 2i -1 for some i ∈ [k -1] and either j ∈ L(λ), in which case f (j) = 2(i + z j (λ)) = 2i thence j is an odd free k-site, or j = j p (λ) = j p (λ) for some p ∈ [m(λ)] such that 2i p (λ) = 2i = j + 1, i.e., the integer j is a surchained k-site. Reciprocally, if j is an odd free k-site then f (j) = 2( j/2 + z j (λ)) = 2( j/2 ) = j + 1, and if j is a surchained k-site then in particular f (j) = 2i p (λ) = j + 1 for some p ∈ [m(λ)]. As a conclusion, the result comes from Theorem 2.2.

Aknowledgement

I thank Jiang Zeng for his comments and useful references.

Figure 1 .

 1 Figure 1. Tableau corresponding to f = (2, 4, 4, 8, 8, 6, 8, 8) ∈ SP 4 .

Figure 2 .

 2 Figure 2. Ferrers diagram of the partition λ = (4, 2, 2, 1).Figure 3. Skew partition λ\µ.

Figure 3 .

 3 Figure 2. Ferrers diagram of the partition λ = (4, 2, 2, 1).Figure 3. Skew partition λ\µ.

Figure 4 .

 4 Figure 4. Skew partition ∂ 5 (λ) with λ = (4, 2, 2, 1).and (V v (λ)) v≥1 are outlined in Figure4(in this example the set V 2 (λ) is empty). Note that for all k-shape λ and for all pair of positive integers (u, v), if the set H u (λ) ∩ V v (λ) is not empty, then there exists a cell in V v (λ) hook lengthed by at least u + v -1. Consequently, if u + v > k + 1, then by definition of ∂ k (λ) the set H u (λ) ∩ V v (λ) must be empty. Hivert and Mallet[START_REF] Hivert | Combinatorics of k-shape and Genocchi numbers[END_REF] defined an operation which consists in inserting, in a k-shape, a l-rectangle (namely, a partition whose Ferrers diagram is a rectangle and whose largest hook length is l) with l ∈ {k -1, k}, the result of the operation being a new k-shape. They defined irreducible k-shapes as k-shapes that cannot be obtained in such a way. In this paper, we use an equivalent definition in view of the Proposition 3.8 of[START_REF] Hivert | Combinatorics of k-shape and Genocchi numbers[END_REF].

Figure 5 .

 5 Figure 5. Partial 6-shape s.Figure 6. Partial 6-shape s ⊕ 6 1 3 2 .

  Figure 8Figure9Figure10

Figure 11 .

 11 Figure 11. Partial k-shape s.

Figure 14 .

 14 Figure 14. Partial k-shape s.Figure15. Partial k-shape s k-j/2 .

Figure 16 .

 16 Figure 16. Surjective pistol f = (2, 8, 4, 10, 10, 6, 8, 10, 10, 10) ∈ SP 5 .

Figure 18 .

 18 Figure 18. 6-boundary ∂ 6 (λ) = s 1 (f ) of the irreducible 6-shape λ = ϕ(f ). We split the proof of Proposition 4.1 into Lemmas 4.1, 4.2 and 4.3.

Figure 21 .

 21 Figure 21. s 1 (f ).Figure 22. s j+1 (f ).

Figure 22 .

 22 Figure 21. s 1 (f ).Figure 22. s j+1 (f ).

Figure 23 .

 23 Figure 23. Between s j+1 (f ) and s j (f ).Figure 24. s j (f )

Figure 24 .

 24 Figure 23. Between s j+1 (f ) and s j (f ).Figure 24. s j (f )

Figure 25 .

 25 Figure 25. s 1 (f ) Figure 26. s 1

Figure 30 .

 30 Figure 30. Skew partitions ∂ k (λ) q+1 and s 1 (λ) q+1 .

  Proposition 4.3. The maps ϕ :SP k-1 → IS k and φ : IS k → SP k-1 are inverse maps. Lemma 4.6. Let (f, λ) ∈ SP k-1 × IS k such that λ = ϕ(f ) or f = φ(λ). Let p ∈ [m(λ)] and j p (λ) := min{j ∈ [2k -4], f (j) = 2i p (λ)}.The two following assertions are equivalent.