# A bijection between irreducible k-shapes and surjective pistols of height $k-1$

Ange Bigeni*

Institut Camille Jordan, Université Claude Benard Lyon 1, France

**Abstract.** 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}$.

**Résumé.** On construit une bijection entre les k-formes irréductibles et les pistolets surjectifs de hauteur $k-1$, qui envoie les "k-sites libres" sur les points fixes des pistolets. Cette bijection démontre une conjecture de Hivert et Mallet (FPSAC 2011), selon laquelle les k-formes irréductibles sont comptées par les nombres de Genocchi $G_{2k}$.

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

## 1 Introduction

The study of k-shapes arises naturally in the combinatorics of k-Schur functions (see [LLMS13]). In a 2011 FPSAC paper, Hivert and Mallet showed that the generating function of all k-shapes 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 \ge 1}$ seemed to be the sequence of Genocchi numbers $(G_{2k})_{k \ge 1} = (1, 1, 3, 17, 155, 2073, \dots)$ [OEI], which may be defined by $G_{2k} = Q_{2k-2}(1)$ for all $k \ge 2$ (see [Car71, RS73]) 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)). \qquad (1)$$

Hivert and Mallet defined a statistic $fr(\lambda)$ counting the so-called free k-sites on the partitions $\lambda$ in the set of irreducible k-shapes $IS_k$, and conjectured that

$$Q_{2k-2}(x) = \sum_{\lambda \in IS_k} x^{fr(\lambda)+2}. \qquad (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

<footnote>*Email: bigeni@math.univ-lyon1.fr.</footnote>
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 $\varphi$ (in Subsection 4.1) and $\phi$ (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.

# 2 Definitions and main result

## 2.1 Surjective pistols

For all positive integer $n$, we denote by $[n]$ the set $\{1, 2, \dots, n\}$. A surjective pistol of height $k$ is a surjective map $f: [2k] \to \{2, 4, \dots, 2k\}$ such that $f(j) \ge j$ for all $j \in [2k]$. We denote by $SP_k$ the set of surjective pistols of height $k$. By abuse of notation, we assimilate a surjective pistol $f \in SP_k$ into the sequence $(f(1), f(2), \dots, f(2k))$. A fixed point of $f \in SP_k$ is an integer $j \in [2k]$ such that $f(j) = j$. We denote by $fix(f)$ the number of fixed points different from $2k$ (which is always a fixed point). The following result is due to Dumont.

**Theorem 2.1 ([Dum74])** For all $k \ge 2$, the Gandhi polynomial $Q_{2k}(x)$ has the following combinatorial interpretation:

$$Q_{2k}(x) = \sum_{f \in SP_k} x^{fix(f)+2}.$$

## 2.2 Partitions, skew partitions, k-shapes

A partition is a finite sequence of positive integers $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_m)$ such that $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_m$. We consider that a partition may be empty (corresponding to $m=0$). A convenient way to visualize a partition $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_m)$ is to consider its Ferrers diagram (denoted by $[\lambda]$), which is composed of cells organized in left-justified rows such that the $i$-th row (from bottom to top) contains $\lambda_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 $\lambda = (4, 2, 2, 1)$ is represented in Figure 1, in which every cell is labeled by its own hook length.

<figure><img src="image_1.png" /><figcaption>**Fig. 1:** Ferrers diagram of the partition $\lambda = (4, 2, 2, 1)$.</figcaption></figure>

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** Skew partition $\lambda \setminus \mu$.</figcaption></figure>
We will sometimes assimilate partitions with their Ferrers diagrams. If two partitions $\lambda = (\lambda_1, \dots, \lambda_p)$ and $\mu = (\mu_1, \dots, \mu_q)$ (with $q \le p$) are such that $\mu_i \le \lambda_i$ for all $i \le q$, then we write $\mu \subseteq \lambda$ and we define the skew partition $s = \lambda/\mu$ as the diagram $[\lambda]\setminus[\mu]$, the Ferrers diagram $[\mu]$ appearing naturally in $[\lambda]$. For example, if $\lambda = (4, 2, 2, 1)$ and $\mu = (2, 1, 1)$, then $\mu \subseteq \lambda$ and the skew partition $\lambda\setminus\mu$ is the diagram depicted in Figure 2. 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 2, 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 $
$ 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 2, the lower border of $s$ is drawn as a thin red line which is continuous, and $
$ is simply the original partition $\lambda = (4, 2, 2, 1)$.

Now, consider a positive integer $k$. For all partition $\lambda$, it is easy to see that the diagram composed of the cells of $[\lambda]$ whose hook length does not exceed $k$, is a skew partition, that we name $k$-boundary of $\lambda$ and denote by $\partial^k(\lambda)$. Incidentally, we name $k$-rim of $\lambda$ the lower border of $\partial^k(\lambda)$ (which may be fragmented), and we denote by $rs^k(\lambda)$ (respectively $cs^k(\lambda)$) the sequence $rs(\partial^k(\lambda))$ (resp. the sequence $cs(\partial^k(\lambda))$). For example, the 2-boundary of the partition $\lambda = (4, 2, 2, 1)$ depicted in Figure 1, is in fact the skew partition of Figure 2. Note that if the $k$-rim of $\lambda$ is continuous, then the partition $<\partial^k(\lambda)>$ is simply $\lambda$.

**Definition 2.1 ([LLMS13]** A $k$-shape is a partition $\lambda$ such that the sequences $rs^k(\lambda)$ and $cs^k(\lambda)$ are also partitions.

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

## 2.3 Irreducible $k$-shapes

Let $\lambda$ be a $k$-shape and $(u, v)$ a pair of positive integers. Following [HM11], we denote by $H_u(\lambda)$ (respectively $V_u(\lambda)$) the set of the cells of the skew partition $\partial^k(\lambda)$ that are contained in a row of length $u$ (resp. the set of all cells of $\partial^k(\lambda)$ that are contained in a column of height $v$). For example, consider the 5-shape $\lambda = (4, 2, 2, 1)$. The sets $(H_u(\lambda))_{u \ge 1}$ and $(V_u(\lambda))_{v \ge 1}$ are outlined in Figure 3 (in this example

<figure><img src="image_3.png" /><figcaption>**Fig. 3:** Skew partition $\partial^5(\lambda)$ with $\lambda = (4, 2, 2, 1)$.</figcaption></figure>

the set $V_2(\lambda)$ is empty). Note that for all $k$-shape $\lambda$ and for all pair of positive integers $(u, v)$, if the
set $H_u(\lambda) \cap V_v(\lambda)$ is not empty, then there exists a cell in $V_v(\lambda)$ hook lengthed by at least $u + v - 1$. Consequently, if $u + v > k + 1$, then by definition of $\partial^k(\lambda)$, the set $H_u(\lambda) \cap V_v(\lambda)$ must be empty. Hivert and Mallet [HM11] 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 \in \{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 Proposition 3.8 of [HM11].

**Definition 2.2 ([HM11])** An irreducible $k$-shape is a $k$-shape $\lambda$ such that the sets $H_i(\lambda) \cap V_{k-i}(\lambda)$ and $H_i(\lambda) \cap V_{k+1-i}(\lambda)$ contain at most $i-1$ horizontal steps of the $k$-rim of $\lambda$ for all $i \in [k]$. We denote by $IS_k$ the set of irreducible $k$-shapes.

For example, the 5-shape $\lambda = (4, 2, 2, 1)$ (see Figure 3) is irreducible: the sets $H_i(\lambda) \cap V_{5-i}(\lambda)$ and $H_j(\lambda) \cap V_{6-j}(\lambda)$ are empty if $i \neq 2$ and $j \neq 3$, and the two sets $H_2(\lambda) \cap V_3(\lambda)$ and $H_3(\lambda) \cap V_3(\lambda)$ contain respectively $1 < 2$ and $1 < 3$ horizontal steps of the $k$-rim of $\lambda$.

In general, it is easy to see that for any $k$-shape $\lambda$ to be irreducible, the sets $H_1(\lambda) \cap V_k(\lambda)$ and $H_k(\lambda) \cap V_1(\lambda)$ must be empty, and by definition the set $H_1(\lambda) \cap V_{k-1}(\lambda)$ must contain no horizontal step of the $k$-rim of $\lambda$. In particular, for $k=1$ or $2$ there is only one irreducible $k$-shape: the empty partition.

**Definition 2.3 ([HM11, Mal11])** Let $\lambda$ be an irreducible $k$-shape with $k \ge 3$. For all $i \in [k-2]$, we say that the integer $2i$ is a free $k$-site of $\lambda$ if the set $H_{k-i}(\lambda) \cap V_{i+1}(\lambda)$ is empty. We define $\overrightarrow{fr}(\lambda)$ as the vector $(t_1, t_2, \dots, t_{k-2}) \in \{0, 1\}^{k-2}$ where $t_i = 1$ if and only if $2i$ is a free $k$-site of $\lambda$. We also define $fr(\lambda)$ as $\sum_{i=1}^{k-2} t_i$ (the quantity of free $k$-sites of $\lambda$).

For example, the irreducible 5-shape $\lambda = (4, 2, 2, 1)$ depicted in Figure 3 is such that $\overrightarrow{fr}(\lambda) = (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 $\phi : IS_k \to SP_{k-1}$ such that $fix(\phi(\lambda)) = fr(\lambda)$ for all $\lambda$. Mallet [Mal11] refined the conjecture by introducing a vectorial version of the statistic of fixed points: for all $f \in SP_{k-1}$, we define $\overrightarrow{fix}(f)$ as the vector $(t_1, \dots, t_{k-2}) \in \{0, 1\}^{k-2}$ where $t_i = 1$ if and only if $f(2i) = 2i$ (in particular $fix(f) = \sum_i t_i$).

**Conjecture 2.1 ([Mal11])** For all $k \ge 3$ and $\vec{v} = (v_1, v_2, \dots, v_{k-2}) \in \{0, 1\}^{k-2}$, the number of irreducible $k$-shapes $\lambda$ such that $\overrightarrow{fr}(\lambda) = \vec{v}$ is the number of surjective pistols $f \in SP_{k-1}$ such that $\overrightarrow{fix}(f) = \vec{v}$.

The main result of this paper is the following theorem, which implies immediately Conjecture 2.1.

**Theorem 2.2** There exists a bijection $\phi : IS_k \to SP_{k-1}$ such that $\overrightarrow{fix}(\phi(\lambda)) = \overrightarrow{fr}(\lambda)$ for all $\lambda \in IS_k$.

We intend to demonstrate Theorem 2.2 in the following two sections 3 and 4.

# 3 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 (resp. by 2), we say that $s$ is a partial $k$-shape.
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 \in [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 4 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 example 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 \ge 1$ such that the height of every column of $s$ is at least $\lceil (j+2)/2 \rceil$ (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 $\tilde{s}$ obtained by gluing right on the last column of $s$, the amount of $z$ columns of height $\lceil (j+1)/2 \rceil$ (see Figure 6) labeled by the integer $t(j)$.

<figure><img src="image_4.png" /><figcaption>Fig. 4: Partial 6-shape $s$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 5: Partial 6-shape $s \oplus_1^6$</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 6: Gluing of the rectangle $\lceil (j+1)/2 \rceil^{z_j}$ to $s$.</figcaption></figure>

We apply the following algorithm on $\tilde{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 $\tilde{s}$ such that the bottom cell $c_0$ of $C_0$ is a corner of $\tilde{s}$ (a cell of $\tilde{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 7).

2. If there exists a column $C_0$ of height $i_0 + 1$ (with $i_0 \in [k-2]$) and labeled by 1 in $\tilde{s}$, such that the bottom cell $c_0$ of $C_0$ is 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 8).

3. If there exists a column $C_0$ of height $i_0 + 1$ (with $i_0 \in [k-2]$) and labeled by 1 in $\tilde{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 $\tilde{s}$ whose length is $k - i_0 - l < k - i_0$ for some $l \ge 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 last column (from left to right) intersecting $R_0$, in such a way the hook length of $c_0$ becomes $k$ again in $\tilde{s}$ (see Figure 9).
<figure><img src="image_7.png" /><figcaption>Fig. 7:</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 8:</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 9:</figcaption></figure>

It is easy to see that this algorithm is finite and that the final version of $\tilde{s}$ is a partial k-shape, that we define as the $t(j)$-sum of the partial k-shape $s$ with the rectangle $\lceil (j+1)/2 \rceil^z$ (the partition whose Ferrers diagram is a rectangle of length $z$ and height $\lceil (j+1)/2 \rceil$), and which we denote by

$$s \oplus_{t(j)}^k \lceil (j+1)/2 \rceil^z.$$

For example, the $1$-sum $s \oplus_1^6 3^2$ of the partial 6-shape $s$ represented in Figure 4, with the rectangle composed of 2 columns of height 3 and label 1, is the partial 6-shape depicted in Figure 5.

**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 \oplus_{t(j)}^k \lceil (j+1)/2 \rceil^z$. In particular, if $s$ is saturated in $i \in [k-2]$, then $s \oplus_{t(j)}^k \lceil (j+1)/2 \rceil^z$ is also saturated in $i$.

The two following lemmas deal with the saturation of a partial k-shape which is not saturated in some particular $i_0$ with conditions.

**Lemma 3.1** Let $s$ be a partial k-shape, let $j \in [2k-4]$ such that every column of $s$ is at least $\lceil (j+2)/2 \rceil$ cells high, and let $z \in \{0, 1, \dots, k-1 - \lceil j/2 \rceil\}$. 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. If $C_2$ has been lifted at the same level as $C_1$ in $s \oplus_{t(j)}^k \lceil (j+1)/2 \rceil^z$, then it is not in the context (1) of Definition 3.2.

**Lemma 3.2** Let $s$ be a partial k-shape and $j \ge 1$ such that the height of every column of $s$ is at least $\lceil (j+2)/2 \rceil$, and such that the quantity of integers $i \in [k-2]$ in which $s$ is not saturated (which implies $s$ has columns whose height is $i+1$) is at most $\lceil j/2 \rceil$. Then, if $s$ is not saturated in $i_0 \in [k-2]$, there exists a unique integer $z \in [k-1 - \lceil j/2 \rceil]$ such that the partial k-shape $s \oplus_{t(j)}^k \lceil (j+1)/2 \rceil^z$ is saturated in $i_0$.

# 4 Proof of Theorem 2.2

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

## 4.1 Algorithm $\varphi: SP_{k-1} \to IS_k$

**Definition 4.1 (Algorithm $\varphi$)** Let $f \in SP_{k-1}$. We define $s^{2k-3}(f)$ as the empty skew partition. For $j$ from $2k-4$ downto 1, let $i \in [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 $\lceil (j+2)/2 \rceil$, and the number of integers $i$ in which $s^{j+1}(f)$ is not saturated is at most $\lceil j/2 \rceil$" is true (in particular $H(2k-3)$ is true so we can initiate the algorithm).
1. If $f(2i) > 2i$, if $j = \min\{j' \in [2k-4], f(j') = 2i\}$ 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) \oplus_{t(j)}^{k} \lceil(j+1)/2\rceil z_j(f)$ where $z_j(f)$ is the unique element of $[k-1 - \lceil j/2 \rceil]$ such that $s^{j+1}(f) \oplus_{t(j)}^{k} \lceil(j+1)/2\rceil 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) \oplus_{t(j)}^k \lceil(j+1)/2\rceil z_j(f)$ where $f(j) = 2(\lceil j/2 \rceil + z_j(f))$ (notice that $z_j(f) \in \{0, 1, \dots, k-1 - \lceil j/2 \rceil\}$ 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 $\lceil(j+1)/2\rceil$. Also, suppose there exist at least $\lceil(j-1)/2\rceil + 1$ different integers $i \in [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 $\lceil(j-1)/2\rceil + 1$ integers $j' \le j-1$ such that $f(j') \ge 2\lceil j/2 \rceil$. Also, since $f$ is surjective, there exist at least $\lceil j/2 \rceil - 1$ integers $j'' \le j-1$ such that $f(j') \le 2(\lceil j/2 \rceil - 1)$. Consequently, we obtain $(\lceil(j-1)/2\rceil + 1) + (\lceil j/2 \rceil - 1) \le j-1$, which is absurd because $\lceil(j-1)/2\rceil + \lceil j/2 \rceil = j$. So the hypothesis H($j$) is true and the algorithm goes on. Ultimately, we define $\varphi(f)$ as the partition $< s^1(f) >$.

**Proposition 4.1** For all $f \in SP_{k-1}$, the partition $\lambda = \varphi(f)$ is an irreducible $k$-shape such that $\partial^k(\lambda) = s^1(f)$ and $\overrightarrow{fr}(\lambda) = \overline{fix}(f)$.

For example, consider the surjective pistol $f = (2, 8, 4, 10, 10, 6, 8, 10, 10, 10) \in SP_5$. Apart from 10, the only fixed point of $f$ is 6, so $\overline{fix}(f) = (0, 0, 1, 0)$. Algorithm $\varphi$ provides the irreducible 6-shape $\lambda$ whose 6-boundary $\partial^6(\lambda) = s^1(f)$ is depicted in Figure 10, where we can see that $\overrightarrow{fr}(\lambda) = (0, 0, 1, 0) = \overline{fix}(f)$.

<figure><img src="image_10.png" /><figcaption>**Fig. 10:** 6-boundary $\partial^6(\lambda) = s^1(f)$ of the irreducible 6-shape $\lambda = \varphi(f)$.</figcaption></figure>

**Proof of Proposition 4.1.** The proof of $\partial^k(\lambda) = s^1(f)$ and $rs^k(\lambda)$ lies on Lemma 3.1 and a thorough analysis on the three cases of Definition 3.2 in which a column is lifted. Afterwards, let $n_i$ (resp. $m_i$) be the number of horizontal steps of the $k$-rim of $\lambda$ inside the set $H_{k-i}(\lambda) \cap V_{i+1}(\lambda)$ (resp. inside the set $H_{k-i}(\lambda) \cap V_i(\lambda)$). Recall that $\lambda$ is irreducible if and only if $(n_i, m_i) \in \{0, 1, \dots, k-1-i\}^2$ for all $i \in [k-2]$. Consider $i_0 \in [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) = \partial^k(\lambda)$. 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 \in [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 $\lambda$ is irreducible. Finally, for all $i \in [k-2]$, we have the equivalence $f(2i) = 2i \Leftrightarrow 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 $\overrightarrow{fix}(f) = \overrightarrow{fr}(\lambda)$. $\square$

## 4.2 Algorithm $\phi: IS_k \to SP_{k-1}$

**Definition 4.2** Let $\lambda$ be an irreducible $k$-shape. For all $i \in [k-2]$, we denote by $x_i(\lambda)$ the number of horizontal steps of the $k$-rim of $\lambda$ inside the set $H_{k-i}(\lambda) \cap V_{i+1}(\lambda)$, and by $y_i(\lambda)$ the number of horizontal steps inside the set $V_i(\lambda) \setminus H_{k+1-i}(\lambda) \cap V_i(\lambda) = \bigsqcup_{j=1}^{k-i} H_j(\lambda) \cap V_i(\lambda)$. Finally, for all $j \in [2k-4]$, we set

$$z_j(\lambda) = \begin{cases} y_i(\lambda) & \text{if } j = 2i - 1, \\ x_i(\lambda) & \text{if } j = 2i. \end{cases}$$

For example, if $\lambda$ is the irreducible $6$-shape represented in Figure 10, then $(z_j(\lambda))_{j \in [8]} = (3, 2, 1, 3, 2, 0, 0, 1)$. Note that in general, if $\lambda$ is an irreducible $k$-shape and $(t_1, t_2, \dots, t_{k-2}) = \overrightarrow{fr}(\lambda)$, then $t_i = 1$ if and only if $x_i(\lambda) = 0$.

**Lemma 4.1** For all $\lambda \in IS_k$ and for all $j \in [2k-4]$, we have

$$z_j(\lambda) \in \{0, 1, \dots, k - 1 - \lceil j/2 \rceil\}.$$

**Proof:** By definition of an irreducible $k$-shape, we automatically have $z_{2i}(\lambda) = x_{i+1}(\lambda) < k - i$ for all $i \in [k-2]$. The proof of $z_{2i-1}(\lambda) = y_i(\lambda) < k - i$ is less straightforward. The idea is to suppose there are at least $y_i(\lambda) \ge k - i$ horizontal steps of the $k$-rim of $\lambda$ inside $\bigsqcup_{j=1}^{k-i} H_j(\lambda) \cap V_i(\lambda)$ and show that at least $k - i$ of these $y_i(\lambda)$ steps appear inside $H_{k-i}(\lambda) \cap V_i(\lambda)$, contradicting the irreducibility of $\lambda$. $\square$

**Definition 4.3** Let $\lambda \in IS_k$. We define a sequence $(s^j(\lambda))_{j \in [2k-3]}$ of partial $k$-shapes by $s^{2k-3}(\lambda) = \emptyset$ and

$$s^j(\lambda) = s^{j+1}(\lambda) \oplus_{t(j)}^k \lceil (j+1)/2 \rceil z_j(\lambda).$$

**Lemma 4.2** We have $s^1(\lambda) = \partial^k(\lambda)$ for all $\lambda \in IS_k$.

**Proof:** Let $l$ be the number of columns of $[\lambda]$, which is obviously the same as for $\partial^k(\lambda)$ and $s^1(\lambda)$. For all $q \in [l]$, we define $\partial^k(\lambda)_q$ (respectively $s^1(\lambda)_q$) as the skew partition made of the $q$ first columns (from right to left) of $\partial^k(\lambda)$ (resp. $s^1(\lambda)$). By considering the three cases of Definition 3.2 in which a column is lifted, we can prove that $\partial^k(\lambda)_q = s^1(\lambda)_q$ for all $q \in [l]$ by induction (the statement being obvious for $q = 1$). In particular we obtain $\partial^k(\lambda) = \partial^k(\lambda)_l = s^1(\lambda)_l = s^1(\lambda)$. $\square$

Notice that Lemma 4.2 is obvious if we know that $\lambda = \varphi(f)$ for some surjective pistol $f \in SP_{k-1}$, because in that case $s^j(\lambda) = s^j(f)$ for all $j$.
**Definition 4.4 (Algorithm $\phi$)** Let $\lambda \in IS_k$. We define $m(\lambda) \in \{0, 1, \dots, k-2\}$ and

$$1 \le i_1(\lambda) < i_2(\lambda) < \dots < i_m(\lambda) \le k-2$$

such that

$$\{i_1(\lambda), i_2(\lambda), \dots, i_{m(\lambda)}(\lambda)\} = \{i \in [k-2], x_i(\lambda) > 0\}$$

(this set may be empty). For all $p \in [m(\lambda)]$, let

$$j_p(\lambda) = \max\{j \in [2i_p(\lambda) - 1], s^j(\lambda) \text{ is saturated in } i_p(\lambda)\}.$$

Let $L(\lambda) = [2k-4]$. For $j$ from 1 to $2k-4$, if $j = j_p(\lambda)$ for some $p \in [m(\lambda)]$, and if there is no $j' \in L(\lambda)$ such that $j' < j$ and $\lceil j'/2 \rceil + z_{j'} = i_p(\lambda)$, then we set $L(\lambda) := L(\lambda) \setminus \{j_p(\lambda)\}$. Now we define $\phi(\lambda) \in \mathbb{N}^{[2k-2]}$ as the following: the integers $\phi(\lambda)(2k-2)$ and $\phi(\lambda)(2k-3)$ are defined as $2k-2$; afterwards, let $j \in [2k-4]$.

* If $j \in L(\lambda)$ then $\phi(\lambda)(j)$ is defined as $2(\lceil j/2 \rceil + z_j(\lambda))$.

* Else there exists a unique $p \in [m(\lambda)]$ such that $j = j_p(\lambda)$, and we define $\phi(\lambda)(j)$ as $2i_p(\lambda)$.

**Proposition 4.2** For all $\lambda \in IS_k$, the map $\phi(\lambda)$ is an element of $SP_{k-1}$ such that $\overrightarrow{fix}(\phi(\lambda)) = \overrightarrow{fr}(\lambda)$.

For example, consider the irreducible 6-shape $\lambda = \varphi(f)$ (with $f = (2, 8, 4, 10, 10, 6, 8, 10, 10, 10)$) of Figure 10, such that $(z_j(\lambda))_{j \in [8]} = (3, 2, 1, 3, 2, 0, 0, 1)$. In particular $(x_1(\lambda), x_2(\lambda), x_3(\lambda), x_4(\lambda)) = (2, 3, 0, 1)$ so $m(\lambda) = 3$ and $(i_1(\lambda), i_2(\lambda), i_3(\lambda)) = (1, 2, 4)$. Moreover, by considering the sequence of partial 6-shapes $(s^8(\lambda), \dots, s^1(\lambda))$, we obtain $(j_2(\lambda), j_3(\lambda), j_1(\lambda)) = (3, 2, 1)$. Applying the algorithm of Definition 4.4 on $L(\lambda) = [8]$, we quickly obtain $L(\lambda) = \{4, 5, 6, 7, 8\}$. Consequently, if $g = \phi(\lambda)$, then automatically $g(10) = g(9) = 10$, afterwards $(g(1), g(2), g(3)) = (g(j_1(\lambda)), g(j_3(\lambda)), g(j_2(\lambda))) = (2i_1(\lambda), 2i_3(\lambda), 2i_2(\lambda)) = (2, 8, 4)$ since $j_p(\lambda) \notin L(\lambda)$ for all $p \in [3]$, and $g(j) = 2(\lceil j/2 \rceil + z_j(\lambda))$ for all $j \in L(\lambda)$. Finally, we obtain $g = (2, 8, 4, 10, 10, 6, 8, 10, 10, 10) = f$ (and $\overrightarrow{fix}(g) = \overrightarrow{fr}(\lambda)$).

**Proof of Proposition 4.2.** Let $\lambda \in IS_k$ and $f = \phi(\lambda)$. We know that $f(2k-2) = f(2k-3) = 2k-4$. Consider $j \in [2k-4]$.

1. If $j = j_p(\lambda)$ for some $p \in [m(\lambda)]$ and if $j \notin L(\lambda)$, then $f(j) = 2i_p(\lambda) > j_p(\lambda)$ by definition, we obtain $2k-2 \ge f(j) > j$.

2. Else $f(j) = 2(\lceil j/2 \rceil + z_j(\lambda))$, so $2k-2 \ge f(j) \ge j$ in view of Lemma 4.1.

Consequently $f$ is a map $[2k-2] \to \{2, 4, \dots, 2k-2\}$ such that $f(j) \ge j$ for all $j \in [2k-2]$. Now, we prove that $f$ is surjective. We know that $2k-2 = f(2k-2)$. Let $i \in [k-2]$.

* If $i = i_p(\lambda)$ for some $p \in [m(\lambda)]$, then either $j_p(\lambda) \notin L(\lambda)$, in which case $2i = f(j_p(\lambda))$, or there exists $j < j_p(\lambda)$ in $L(\lambda)$ such that $\lceil j/2 \rceil + z_j = i$, in which case $2i = f(j)$.

* Else $z_{2i}(\lambda) = 0$, which implies that $2i$ cannot be equal to any $j_p(\lambda)$ because $s^{2i}(\lambda) = s^{2i+1}(\lambda) \oplus_1^k (i+1)z_j(\lambda) = s^{2i+1}(\lambda)$. Consequently $2i \in L(\lambda)$, thence $f(2i) = 2(i + z_{2i}(\lambda)) = 2i$.

Therefore $f \in SP_{k-1}$. Finally, for all $i \in [k-2]$, we have just proved that $z_{2i}(\lambda) = 0$ implies $f(2i) = 2i$. Reciprocally, if $f(2i) = 2i$, then necessarily $2i \in L(\lambda)$ (otherwise $2i$ would be $j_p(\lambda)$ for some $p$ and $f(2i)$ would be $2i_p(\lambda) > j_p(\lambda) = 2i$), meaning $2i = f(2i) = 2(i + z_{2i}(\lambda))$ thence $z_{2i}(\lambda) = 0$. The equivalence $z_{2i}(\lambda) = 0 \Leftrightarrow f(2i) = 2i$ for all $i \in [k-2]$ exactly translates into $\overrightarrow{fr}(\lambda) = \overrightarrow{fix}(f)$. $\square$
## 4.3 Proof of Theorem 2.2

At this stage, we know that $\varphi$ is a map $SP_{k-1} \to IS_k$ which transforms the statistic $\overrightarrow{fix}$ into the statistic $\overrightarrow{fr}$. The bijectivity of $\varphi$ is a consequence of the following proposition.

**Proposition 4.3** The maps $\varphi: SP_{k-1} \to IS_k$ and $\phi: IS_k \to SP_{k-1}$ are inverse maps.

**Lemma 4.3** Let $(f, \lambda) \in SP_{k-1} \times IS_k$ such that $\lambda = \varphi(f)$ or $f = \phi(\lambda)$. Let $p \in [m(\lambda)]$ and $j^p(\lambda) := \min\{j \in [2k-4], f(j) = 2i_p(\lambda)\}$. The two following assertions are equivalent.

1. $j_p(\lambda) \notin L(\lambda)$.

2. $j_p(\lambda) = j^p(\lambda)$.

**Proof of Proposition 4.3:** The map $\phi(\varphi(f))$ being $f$ for all $f \in SP_{k-1}$ comes from Lemma 4.3 with $\lambda = \varphi(f)$. Reciprocally, if $\mu = \varphi(\phi(\lambda))$ for some $\lambda \in IS_k$, we show by induction on $j$ from $2k-4$ to $1$ that $s^j(\mu) = s^j(\lambda)$ for all $j \in [2k-4]$, mainly from Lemma 4.3 with $f = \phi(\lambda)$. In particular, we obtain $\mu = <s^1(\mu) >= <s^1(\lambda) >= \lambda$. $\square$

# 5 Extensions

Dumont and Foata [DF76] introduced a refinement of Gandhi polynomials $(Q_{2k}(x))_{k \ge 1}$ through the polynomial sequence $(F_k(x, y, z))_{k \ge 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 $Q_{2k}(x) = x^2 F_k(x, 1, 1)$ in view of Formula 1. Now, for all $k \ge 2$ and $f \in SP_k$, let $max(f)$ be the number of maximal points of $f$ (integers $j \in [2k-2]$ such that $f(j) = 2k$) and $pro(f)$ the number of prominent points (integers $j \in [2k-2]$ such that $f(i) < f(j)$ for all $i \in [j-1]$). For example, if $f$ is the surjective pistol $(2, 4, 4, 8, 8, 6, 8, 8) \in SP_4$, 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 \ge 2$, the Dumont-Foata polynomial $F_k(x, y, z)$ is symmetrical, and is generated by $SP_k$:

$$F_k(x, y, z) = \sum_{f \in SP_k} x^{max(f)} y^{fix(f)} z^{pro(f)}.$$

In 1996, Han [Han96] gave another interpretation by introducing the statistic $sur(f)$ defined as the number of surfixed points of $f \in SP_k$ (points $j \in [2k-2]$ such that $f(j) = j+1$; for example, the surfixed points of the surjective pistol $f = (2, 4, 4, 8, 8, 6, 8, 8) \in SP_4$ are $\{1, 3\}$).

**Theorem 5.2 ([Han96])** For all $k \ge 2$, the Dumont-Foata polynomial $F_k(x, y, z)$ has the following combinatorial interpretation:

$$F_k(x, y, z) = \sum_{f \in SP_k} x^{max(f)} y^{fix(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 \in SP_k$ and $j \in [2k-2]$, we say that $j$ is a *lined* point of $f$ if there exists $j' \in [2k-2] \setminus \{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 $fl(f)$ (resp. $fnl(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 [Dum95] defined generalized Dumont-Foata polynomials $(\Gamma_k(x, y, z, \bar{x}, \bar{y}, \bar{z}))_{k \ge 1}$ by

$$ \Gamma_k(x, y, z, \bar{x}, \bar{y}, \bar{z}) = \sum_{f \in SP_k} x^{mo(f)} y^{fl(f)} z^{snl(f)} \bar{x}^{me(f)} \bar{y}^{fnl(f)} \bar{z}^{sl(f)}. $$

This a refinement of Dumont-Foata polynomials, considering $\Gamma_k(x, y, z, x, y, z) = F_k(x, y, z)$. Dumont conjectured the following induction formula: $\Gamma_1(x, y, z, \bar{x}, \bar{y}, \bar{z}) = 1$ and

$$ \Gamma_{k+1}(x, y, z, \bar{x}, \bar{y}, \bar{z}) = (x + \bar{z})(y + \bar{x})\Gamma_k(x + 1, y, z, \bar{x} + 1, \bar{y}, \bar{z}) \\ + (x(\bar{y} - y) + \bar{x}(z - \bar{z}) - x\bar{x})\Gamma_k(x, y, z, \bar{x}, \bar{y}, \bar{z}). \quad (3) $$

This was proven independently by Randrianarivony [Ran94] and Zeng [Zen96]. See also [JV11] for a new combinatorial interpretation of $\Gamma_k(x, y, z, \bar{x}, \bar{y}, \bar{z})$.

Now, let $f \in SP_{k-1}$ and $\lambda = \varphi(f) \in IS_k$. For all $j \in [2k-4]$, we say that $j$ is a *chained k-site* of $\lambda$ if $j \notin L(\lambda)$. Else, we say that it is an *unchained k-site*. In view of Lemma 4.3, an integer $j \in [2k-4]$ is a chained k-site if and only if $j = j_p(\lambda) = j^p(\lambda)$ for some $p \in [m(\lambda)]$, in which case $f(j) = 2i_p(\lambda)$ (the integer $j$ is forced to be mapped to $2i_p(\lambda)$). If $j$ is an unchained k-site, by definition $f(j) = 2([j/2] + z_j(\lambda))$. 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 \in [k-2]$, the integer $2i$ is a fixed point of $f$ if and only if $2i$ is a free k-site of $\lambda$, which is also equivalent to $z_{2i}(\lambda) = 0$. We extend the notion of free k-site to any $j \in [2k-4]$ : the integer $j$ is said to be a free k-site if $z_j(\lambda) = 0$. Notice that free k-sites of $\lambda$ are necessarily unchained because $z_j(\lambda) = 0$ implies $s^j(\lambda) = s^{j+1}(\lambda)$ thence $j \neq j_p(\lambda)$ for all $p \in [m(\lambda)]$. We denote by $fro(\lambda)$ the quantity of odd free sites of $\lambda$. We denote by $ful(\lambda)$ the quantity of full k-site of $\lambda$ (namely, unchained k-sites $j \in L(\lambda)$ such that $z_j(\lambda) = k-1 - [j/2]$), and by $sch(\lambda)$ the quantity of *surchained k-sites* (chained k-sites $j \in [2k-4]$ such that $j = j_p(\lambda)$ for some $p \in [m(\lambda)]$ with $2i_p(\lambda) = j+1$). Theorem 5.2 can now be reformulated as follows.

**Theorem 5.3** For all $k \ge 2$, the Dumont-Foata polynomial $F_k(x, y, z)$ has the following combinatorial interpretation:

$$ F_k(x, y, z) = \sum_{\lambda \in IS_{k+1}} x^{ful(\lambda)} y^{fr(\lambda)} z^{fro(\lambda)} + sch(\lambda). $$

## Acknowledgement

I thank Jiang Zeng for his comments and useful references.
References

[Car71] Leonard Carlitz. A conjecture concerning Genocchi numbers. *Norske Vid. Selsk. Skr. (Trondheim)*, 9:4, 1971.

[DF76] Dominique Dumont and Dominique Foata. Une propriété de symétrie des nombres de genocchi. *Bull. Soc. Math. France*, 104:433–451, 1976.

[DR94] Dominique Dumont and Arthur Randrianarivony. Dérangements et nombres de Genocchi. *Disc. Math.*, 132:37–49, 1994.

[Dum72] Dominique Dumont. Sur une conjecture de Gandhi concernant les nombres de Genocchi. *Disc. Math.*, 1:321–327, 1972.

[Dum74] Dominique Dumont. Interprétations combinatoires des nombres de Genocchi. *Duke Math. J.*, 41:305–318, 1974.

[Dum95] Dominique Dumont. Conjectures sur des symétries ternaires liées aux nombres de Genocchi. In FPSAC 1992, editor, *Discrete Math.*, number 139, pages 469–472, 1995.

[Han96] Guo Niu Han. Symétries trivariées sur les nombres de genocchi. *Europ. J. Combinatorics*, 17:397–407, 1996.

[HM11] Florent Hivert and Olivier Mallet. Combinatorics of *k*-shape and Genocchi numbers. In FPSAC 2011, editor, *Discrete Math. Theor. Comput. Sci. Proc.*, pages 493–504, Nancy, 2011.

[JV11] Matthieu Josuat-Vergès. Dumont-Foata polynomials and alternative tableaux. Sém. Lothar. Combin. 64, Art. B64b, 17pp, 2011.

[LLMS13] Thomas Lam, Luc Lapointe, Jennifer Morse, and Marc Shimozono. The poset of *k*-shapes and branching rules for *k*-schur functions. *Mem. Amer. Math. Soc.*, 223(1050), 2013.

[Mal11] Olivier Mallet. Combinatoire des *k*-formes et nombres de Genocchi. Séminaire de combina-toire et théorie des nombres de l'ICJ, may 2011.

[OEI] OEIS Foundation Inc. (2011). The On-Line Encyclopedia of Integer Sequences. http://oeis.org/A110501.

[Ran94] Arthur Randrianarivony. Polynômes de Dumont-Foata généralisés. Sém. Lothar. Combin. 32, Art. B32d, 12pp, 1994.

[RS73] John Riordan and Paul R. Stein. Proof of a conjecture on Genocchi numbers. *Discrete Math.*, 5:381–388, 1973.

[Sta99] R.P. Stanley. *Enumerative Combinatorics*, volume 2. Cambridge University Press, Cambridge, 1999.

[Zen96] Jiang Zeng. Sur quelques propriétés de symétrie des nombres de Genocchi. *Disc. Math.*, 153:319–333, 1996.