# Combinatorics of k-shapes and Genocchi numbers

Florent Hivert†and Olivier Mallet‡

LITIS, Université de Rouen, Saint-Étienne-du-Rouvray, France

**Abstract.** In this paper we present a work in progress on a conjectural new combinatorial model for the Genocchi numbers. This new model called irreducible k-shapes has a strong algebraic background in the theory of symmetric functions and leads to seemingly new features on the theory of Genocchi numbers. In particular, the natural q-analogue coming from the degree of symmetric functions seems to be unknown so far.

**Résumé.** Dans cet article, nous présentons un travail en cours sur un nouveau modèle combinatoire conjectural pour les nombres de Genocchi. Ce nouveau modèle est celui des k-formes irréductibles, qui repose sur de solides bases algébriques en lien avec la théorie des fonctions symétriques et qui conduit à des aspects apparemment nouveaux de la théorie des nombres de Genocchi. En particulier, le q-analogue naturel venant du degré des fonctions symétriques semble inconnu jusqu'ici.

**Keywords:** partitions, cores, symmetric functions

## Contents

<table><tr><td>1</td><td>Introduction</td><td>494</td></tr><tr><td>2</td><td>Background</td><td>495</td></tr><tr><td>2.1</td><td>Genocchi numbers</td><td>495</td></tr><tr><td>2.2</td><td>Integer partitions and skew partitions</td><td>495</td></tr><tr><td>2.3</td><td>k-cores and k-shapes</td><td>496</td></tr><tr><td>3</td><td>Irreducible k-shapes</td><td>497</td></tr><tr><td>3.1</td><td>Addition of rectangles</td><td>497</td></tr><tr><td>3.2</td><td>Main theorem</td><td>500</td></tr><tr><td>4</td><td>Work in progress</td><td>502</td></tr><tr><td>4.1</td><td>Main conjecture</td><td>502</td></tr><tr><td>4.2</td><td>Algebraic perspectives</td><td>502</td></tr><tr><td>5</td><td>Table</td><td>503</td></tr></table>

<footnote>†florent.hivert@univ-rouen.fr</footnote>

<footnote>‡olivier.mallet@univ-rouen.fr</footnote>
# 1 Introduction

The goal of this paper is to present some purely combinatorial results on certain partitions; these results are strongly motivated by the theory of symmetric functions. We define a still conjectural new model for the Genocchi numbers and Gandhi polynomials. We begin by explaining the root of this work, namely the k-Schur functions of Lapointe-Lascoux-Morse; however, the reader who is not familiar with the theory of symmetric functions can skip the following paragraphs without harm.

The fundamental theorem of symmetric functions states that their ring Sym is freely generated by the homogeneous symmetric functions $(h_i)_{i>0}$. It therefore makes sense to study the subring Sym$^{(k)}$ generated by the first $k$ homogeneous functions Sym$^{(k)}$ := $\mathbb{Q}[h_1, h_2, \dots, h_k]$. Say that a partition $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_l)$ is $k$-bounded if it has no part exceeding $k$ (i.e., $k \ge \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_l > 0$). Then, if we define $h_\lambda := h_{\lambda_1} h_{\lambda_2} \dots h_{\lambda_l}$, then $(h_\lambda)_\lambda$ where $\lambda$ is $k$-bounded is a natural basis for Sym$^{(k)}$. However, there exists another basis which plays the role of Schur functions; this basis is called atoms in [LLM03] and, with a different definition, $k$-Schur functions in [LM05, LM07]. It should be noted that those papers actually deal with a more general setting where homogeneous symmetric functions are replaced with their natural $q$-analogues (Hall-Littlewood functions) and $q$, $t$-analogues (Macdonald functions). From the combinatorial point of view, it seems that indexing $k$-Schur functions by $k$-bounded partitions is not the right approach. In [LM05], Lapointe and Morse showed that $k$-bounded partitions are in bijection with $k+1$-cores and that there is a natural tableau-like definition of $k$-Schur functions involving paths in the analogue of Young's lattice on $k+1$-cores.

An important question is to find a combinatorial way to expand the $k$-Schur function $s_\lambda^{(k)}$ in terms of the usual Schur functions $s_\lambda$. The strategy of [LLMS] is to inductively use a combinatorial way to expand $k$-Schur functions on $k+1$-Schur functions. In order to do that, they need to interpolate between $k$-cores and $k+1$-cores. They indeed define a certain partially ordered set of partitions they call $k$-shapes (see Definition 2.1) such that $k+1$-cores are the minimal elements and $k$-cores the maximal ones. The expansion of $s_\lambda^{(k)}$ is essentially described by counting paths from $k$-cores to $k+1$-cores in this poset up to some equivalence relation. The combinatorial study of these $k$-shapes is the main goal of our paper.

Our main result is the following theorem:

**Theorem 1.1** For $k \in \mathbb{N}$, the generating function for $k$-shapes is given by

$$f_k(t) = \frac{P_k(t)}{\prod_{u,v} (1 - t^{uv})} \qquad (1)$$

where the product is over the set of all couples $(u, v)$ of positive integers such that $u + v \in \{k, k+1\}$ and $P_k(t) \in \mathbb{N}[t]$ is a polynomial with nonnegative integer coefficients.

Using computer, we evaluated the numerator $P_k(t)$ up to $k = 9$ (see Section 5). Setting $t = 1$, one gets the following table

<table><tr><td>$k$</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td></tr><tr><td>$P_k(1)$</td><td>1</td><td>1</td><td>3</td><td>17</td><td>155</td><td>2073</td><td>38227</td><td>929569</td><td>28820619</td></tr></table>

which seems to be the sequence of Genocchi numbers (sequence A110501 of [Slo]):

**Conjecture 1.2** The polynomials appearing in Equation (1) are a $q$-analogue of the Genocchi numbers: $P_k(1)$ is the $k^{th}$ Genocchi number.
**Outline.** The paper is structured as follows: The first background section (Section 2) recalls the necessary definitions on Genocchi numbers (Subsection 2.1), partitions and skew partitions (Subsection 2.2), as well as k-cores and k-shapes (Subsection 2.3). Then, Section 3 is devoted to the operation of adding a rectangle to a k-shape and the construction of the main object of this paper, namely irreducible k-shapes. We finally conclude by stating our main conjecture (Subsection 4.1), as well as some algebraic perspectives (Subsection 4.2).

# 2 Background

## 2.1 Genocchi numbers

The unsigned Genocchi numbers $G_{2n}$ can be defined using the Bernoulli numbers $B_n$ by

$$G_{2n} = 2(2^{2n} - 1)|B_{2n}|$$

or via the generating function

$$\frac{2t}{1+e^t} = t + \sum_{n \ge 1} (-1)^n G_{2n} \frac{t^{2n}}{(2n)!}.$$

These numbers were named, apparently by Lucas [Luc91], after the 19th century Italian mathematician Angelo Genocchi; they appear in the latter's papers on the Bernoulli numbers [Gen52, Gen86]. However, Euler had already studied them in [Eul55].

The first combinatorial interpretation of the Genocchi numbers was given by Dumont in [Dum74]: $G_{2n+2}$ is the number of permutations $\sigma \in \mathfrak{S}_{2n}$ such that $\sigma_{2n}$ is odd and, for $i$ such that $1 \le i \le 2n - 1$, $\sigma_i$ is followed by a smaller number if it is even and by a greater number if it is odd. Such permutations are called *Dumont permutations of the first kind*. In the same paper, Dumont defined another family of permutations enumerated by the Genocchi numbers, which are now known as *Dumont permutations of the second kind*. Other families of Genocchi-enumerated permutations were subsequently introduced by Kitaev and Remmel [KR07] and Burstein and Stromquist [BS07].

## 2.2 Integer partitions and skew partitions

A partition $\lambda = (\lambda_1, \dots, \lambda_m)$ is a nonincreasing sequence of positive integers which are called the *parts* of the partition. We will sometimes also use the *exponential notation* for partitions: if $\lambda$ is a partition and $f_i$ is the number of occurrences of $i$ in $\lambda$, then we write $\lambda = (1^{f_1} 2^{f_2} \dots)$. The number of parts of $\lambda$ is denoted by $\ell(\lambda)$. The weight of $\lambda$ is $|\lambda| := \sum_{i=1}^m \lambda_i$. If the weight of $\lambda$ is $n$, we say that $\lambda$ is a *partition of n*. A sequence $c = (c_1, \dots, c_m)$ (not necessarily nonincreasing) of positive integers whose sum is $n$ is called a *composition of n*. We denote by $c \cdot c'$ the concatenation of the two compositions $c$ and $c'$.

A partition $\lambda$ is classically represented by a Ferrers diagram, which we denote by $[\lambda]$, where the $i^{th}$ row has $\lambda_i$ squares (also called cells). We use the French notation for Ferrers diagrams: the rows are counted from bottom to top. More precisely, $[\lambda]$ is formed by the unit cells $(x, y)$ with upper right corner at the point $(x, y)$, where $1 \le y \le \ell(\lambda)$ and $1 \le x \le \lambda_y$. An example is shown on Figure 1.

The union of two partitions $\lambda$ and $\mu$, which we denote by $\lambda \cup \mu$, is a partition that is obtained by gathering all the parts of $\lambda$ and $\mu$ and sorting them in nonincreasing order. For example, if $\lambda = (5, 4, 3, 3)$ and $\mu = (7, 6, 5, 3, 2, 1)$, we have $\lambda \cup \mu = (7, 6, 5, 5, 4, 3, 3, 3, 2, 1)$.

The notion of skew partition will be needed throughout the paper. Given two partitions $\lambda$ and $\mu$, we write $\mu \subseteq \lambda$ if $\mu_i \le \lambda_i$ for all $i$. If $\lambda$ and $\mu$ satisfy $\mu \subseteq \lambda$, we identify the skew partition $\lambda/\mu$ with its diagram, which is the set-theoretic difference $[\lambda] \setminus [\mu]$. The weight of $\lambda/\mu$ is $|\lambda/\mu| := |\lambda| - |\mu|$. For example, $\lambda/\mu = (4, 3, 2, 2, 1)/(2, 1, 1)$ has weight 8 and its diagram is shown on Figure 2.
<figure><img src="image_1.png" /><figcaption>**Figure 1:** The Ferrers diagram of (5, 4, 3, 3).</figcaption></figure>

<figure><img src="image_2.png" /><figcaption>**Figure 2:** The diagram of the skew partition $\lambda/\mu = (4, 3, 2, 2, 1)/(2, 1, 1)$. The dotted lines indicate the cells of $[\mu]$.</figcaption></figure>

## 2.3 k-cores and k-shapes

The hook of a cell $c$ in the Ferrers diagram of a partition is the set formed by $c$ and the cells that are located to its right in the same row or above it in the same column. The hook length of a cell is the number of cells in its hook. An example is shown on Figure 3, where we have encircled the hook of the dotted cell (2, 2); the hook length of this cell is 7.

<figure><img src="image_3.png" /><figcaption>**Figure 3:** The hook of the cell (2, 2) in the diagram of $\lambda = (7, 6, 4, 3)$.</figcaption></figure>

A partition is a *k*-core if its diagram contains no cells with hook length *k* [JK81]. See Figure 4 for an example.

It is not difficult to see that in every Ferrers diagram, the hook lengths decrease from left to right and from bottom to top. Consequently, the cells of a diagram $[\lambda]$ whose hook length is (strictly) larger than *k* form the diagram of a partition. Following [LLMS], we call this partition the *k*-interior of $\lambda$ and denote it by $\text{Int}^k(\lambda)$. As for the cells whose hook length does not exceed *k*, they form the diagram of a skew partition, which we call the *k*-boundary of $\lambda$ and denote by $\partial^k(\lambda)$. We also define the *k*-rim of $\lambda$ as the line that starts at the upper left corner of the diagram, goes down vertically until reaching the *k*-interior, follows the limit between the *k*-interior and the *k*-boundary and then goes horizontally to the lower right corner of the diagram. See Figure 5 for an example.

We call row shape of a skew partition $\lambda/\mu$ and denote by $\text{rs}(\lambda/\mu)$ the sequence of the lengths of the rows (from bottom to top) of $\lambda/\mu$. Likewise, we call column shape of $\lambda/\mu$ and denote by $\text{cs}(\lambda/\mu)$ the heights of the columns (from left to right) of $\lambda/\mu$. Both $\text{rs}(\lambda/\mu)$ and $\text{cs}(\lambda/\mu)$ are compositions of $|\lambda/\mu|$. For example, if we call $\lambda/\mu$ the 6-interior of the partition represented on Figure 5, we have $\text{rs}(\lambda/\mu) = (5, 4, 2, 1)$ and $\text{cs}(\lambda/\mu) = (2, 2, 1, 1, 2, 1, 1, 1)$. We also define $\text{rs}^k(\lambda) := \text{rs}(\partial^k(\lambda))$ and $\text{cs}^k(\lambda) := \text{cs}(\partial^k(\lambda))$.

**Definition 2.1 (Lam et al. [LLMS])** A partition $\lambda$ is a *k*-shape if $\text{rs}^k(\lambda)$ and $\text{cs}^k(\lambda)$ are both partitions.
<figure><img src="image_4.png" /><figcaption>**Figure 4:** The diagram of the 4-core (5, 3, 3, 1, 1) with its hook lengths.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 5:** The diagram of $\lambda = (9, 5, 2, 1)$ with its hook lengths. The bold line is the 6-rim. The cells below that line form the 6-interior of $\lambda$ and those above it form the 6-boundary.</figcaption></figure>

See Figure 6 for an example. Note that *k*-cores and *k* + 1-cores are *k*-shapes [LLMS, Proposition 10].

<figure><img src="image_6.png" /><figcaption>**Figure 6:** $\lambda = (9, 5, 2, 1)$ is a 4-shape.</figcaption></figure>

For legibility reasons, we will sometimes omit the *k*-interior when representing *k*-shapes graphically, since a *k*-shape is uniquely determined by its *k*-boundary.

# 3 Irreducible *k*-shapes

## 3.1 Addition of rectangles

This section deals with an operation that builds a *k*-shape from another *k*-shape and a *k*- or *k* − 1-rectangle. The definition of irreducible *k*-shapes and the proof of Theorem 1.1 rest on this operation. Note that it is a generalization of the construction presented in Theorem 10 of [LM04], which is equivalent, in our framework, to adding a *k*-rectangle to a *k* + 1-core.

**Definition 3.1 ([LLM03]** A *k*-rectangle is a partition of the form ($\ell^{k+1}-\ell$), where $\ell$ satisfies 1 ≤ $\ell$ ≤ *k*.

Evidently, *k*-rectangles are the partitions whose Ferrers diagram is a rectangle and whose largest hook length is *k*.

**Lemma 3.2** Let $r = (r_1, \dots, r_m)$ and $c = (c_1, \dots, c_p)$ be two compositions of the same integer $n$. Then there exists at most one skew partition $\lambda/\mu$ of weight $n$ such that $\mathrm{rs}(\lambda/\mu) = r$ and $\mathrm{cs}(\lambda/\mu) = c$.
**Proof:** We build the skew partition row by row, from top to bottom. At the $i^{th}$ step ($1 \le i \le m$), we try to insert a row of length $r_{m+1-i}$. The first $c_1$ rows must be left-justified so that the first column contains $c_1$ cells, as desired. The subsequent $c_1 - c_2$ rows must be shifted by one so that the first column does not contain more than $c_1$ cells and the second column contains $c_2$ cells, and so on. Therefore, the resulting skew partition is unique. □

It must be noted that a solution does not always exist. For example, if $r = (3)$ and $c = (2, 1)$, the two conditions are incompatible, because the row condition implies that the skew partition has three columns whereas the column condition implies that it has two columns.

**Definition 3.3** Let $\lambda$ be a k-shape, $r = \text{rs}^k(\lambda)$ and $c = \text{cs}^k(\lambda)$. For all $i \in \mathbb{N}^*$, let

$$ \mathbb{H}_i = [\max\{j | r_j > i\}, \min\{j | r_j < i\} - 1] \quad (2) $$

$$ \mathbb{V}_i = [\max\{j | c_j > i\}, \min\{j | c_j < i\} - 1] \quad (3) $$

We use the convention that if $\pi$ is a partition, we have $\pi_0 = \infty$ and $\pi_j = 0$ if $j > l(\pi)$.

The horizontal strip $H_i$ is the set $\{(x, y) \in \mathbb{R}^2 | y \in H_i\}$. Similarly, the vertical strip $V_i$ is the set $\{(x, y) \in \mathbb{R}^2 | x \in V_i\}$.

Note that the interval $H_i$ (resp. $V_i$) is reduced to a singleton if there is no integer $j$ such that $r_j = i$ (resp. $c_j = i$). In this case, the corresponding strip is a single line. An example is the vertical strip $V_2$ in the k-shape shown on Figure 7.

<figure><img src="image_7.png" /><figcaption>**Figure 7:** Horizontal and vertical strips in the diagram of the 4-shape (10, 7, 4, 2, 2, 2, 1, 1, 1, 1). Note that $V_2$ is reduced to a single line.</figcaption></figure>

**Proposition 3.4** Let $\lambda$ be a k-shape and $(u^v)$ be a k-rectangle or $k-1$-rectangle. Then there exists a point of the k-rim of $\lambda$ that belongs to $H_u \cap V_v$.

**Proof (sketch):** Using hook length considerations, we show that the upper right corner of the intersection $H_u \cap V_v$ belongs to the k-boundary while the lower left corner does not (see Figure 8). Consequently, a path between these two points must cross the k-rim. □
<figure><img src="image_8.png" /><figcaption>**Figure 8:** a is in the k-boundary and b in the k-interior; the k-rim therefore passes between these two points.</figcaption></figure>

**Proposition 3.5** Let $\lambda$ be a k-shape and $(u^v)$ be a k-rectangle or $k-1$-rectangle. Then there exists a unique k-shape, which we denote by $\lambda + (u^v)$, such that

$$rs^k(\lambda + (u^v)) = rs^k(\lambda) \cup (u^v) \qquad (4)$$

$$cs^k(\lambda + (u^v)) = cs^k(\lambda) \cup (v^u) \qquad (5)$$

**Proof:** We describe an algorithm that constructs $\partial^k(\lambda + (u^v))$ from $\partial^k(\lambda)$ by "inserting" the rectangle into the k-shape. Proposition 3.4 implies that we can decompose $\partial^k(\lambda)$ into three parts: the cells located to the right of $p$ and above it, which we call the foot (region $F$ in Figure 9), the cells to the left of the foot (region $A$) and the cells below the foot (region $B$).

<figure><img src="image_9.png" /><figcaption>**Figure 9:** The decomposition of the k-boundary of a k-shape used for inserting a rectangle. Here, $p$ is a point satisfying the conditions of Proposition 3.4.</figcaption></figure>

The insertion process then consists in transforming this k-boundary into the skew partition shown on Figure 10, from which the partition $\lambda + (u^v)$ is easily reconstructed, as said before.

<figure><img src="image_10.png" /><figcaption>**Figure 10:** Result of the insertion process. $F_2$ is a copy of $F$ and $\bar{F}$ is the complement of $F$ in $(u^v)$.</figcaption></figure>
We call this skew partition $\tilde{\lambda}/\tilde{\mu}$. First, we must prove that it satisfies (4) and (5). If $R_1$ and $R_2$ are two regions of the diagram, let $R_1 \lor R_2$ denote their set-theoretic union. We have that

$$ 
\begin{aligned}
\mathrm{rs}(\tilde{\lambda}/\tilde{\mu}) &= \mathrm{rs}(B) \cdot \mathrm{rs}(\bar{F} \lor F_2) \cdot \mathrm{rs}(A \lor F) \\
&= \mathrm{rs}(B) \cdot (u^v) \cdot \mathrm{rs}(A \lor F) \\
&= \mathrm{rs}(\lambda/\mu) \cup (u^v)
\end{aligned}
$$

because $\mathrm{rs}(B)$ is a partition into parts $\ge u$ and $\mathrm{rs}(A \lor F)$ is a partition into parts $\le u$, since $\lambda$ is a k-shape. Therefore, $\tilde{\lambda}/\tilde{\mu}$ satisfies (4); the proof that it satisfies (5) is similar.

We now need to check that $\tilde{\mu}$ is indeed the k-interior of $\tilde{\lambda}$, i.e. that the hook lengths of $\tilde{\lambda}/\tilde{\mu}$ do not exceed $k$ and those of $\tilde{\mu}$ are greater than $k$. To this end, we decompose $[\tilde{\lambda}]$ as shown on Figure 11.

<figure><img src="image_11.png" /><figcaption>**Figure 11:** Decomposition of $[\tilde{\lambda}]$ to check the hook length conditions. The regions $A'$, $C$ and $B'$ belong to the k-interior, the other regions belong to the k-boundary.</figcaption></figure>

The hook lengths of the cells that were above $p$ before the insertion (regions $A$, $A'$, and $F$ on Figure 11) have not been modified since no cells have been added or removed above those cells or to their right. The hook lengths of the cells that were to the right of $p$ (regions $B$, $B'$, and $F_2$) have not been modified either, for the same reason. A cell in the region $\bar{F}$ has at most $u-1$ cells to its right in the same row and at most $v-1$ cells above it in the same column: its hook length thus does not exceed $u+v-1 \le k$. Likewise, a cell in the region $C$ has at least $u$ cells to its right in the same row and $v$ cells above it in the same column, and therefore has hook length at least $u+v+1 \ge k+1$. All the hook lengths conditions are therefore satisfied.

The uniqueness is proved by Lemma 3.2. In particular, the result does not depend on the choice of $p$. $\square$

See Figure 12 for an example of the insertion process.

**Proposition 3.6** Let $\lambda$ be a k-shape and let $(u_1^{v_1})$ and $(u_2^{v_2})$ be two k- or $k-1$-rectangles. Then

$$ (\lambda + (u_1^{v_1})) + (u_2^{v_2}) = (\lambda + (u_2^{v_2})) + (u_1^{v_1}). $$

**Proof:** We have $\mathrm{rs}((\lambda + (u_1^{v_1})) + (u_2^{v_2})) = \mathrm{rs}(\lambda) \cup (u_1^{v_1}) \cup (u_2^{v_2}) = \mathrm{rs}((\lambda + (u_2^{v_2})) + (u_1^{v_1}))$ and likewise $\mathrm{cs}((\lambda + (u_1^{v_1})) + (u_2^{v_2})) = \mathrm{cs}((\lambda + (u_2^{v_2})) + (u_1^{v_1}))$. The proof is completed by using Lemma 3.2. $\square$

## 3.2 Main theorem

**Definition 3.7** We say that a k-shape is irreducible if it cannot be obtained from another k-shape by inserting a k- or $k-1$-rectangle as described in the proof of Proposition 3.5.

We first need to have a better characterization of the irreducible k-shapes.
<figure><img src="image_12.png" /><figcaption>**Figure 12:** The insertion of the 4-rectangle ($2^3$) into the 4-shape (5, 2, 1, 1) produces the 4-shape (7, 4, 3, 3, 2, 1, 1).</figcaption></figure>

**Proposition 3.8** Let $\lambda$ be a k-shape and $(u^v)$ be a k- or $k-1$-rectangle. The following are equivalent:

(i) there exists a k-shape $\mu$ such that $\lambda = \mu + (u^v)$,

(ii) there exist two points $(x_1, y_1)$ and $(x_2, y_2)$ of the k-rim of $\lambda$ lying in $H_u \cap V_v$ such that $x_2 - x_1 \ge u$,

(iii) there exist two points $(x_1, y_1)$ and $(x_2, y_2)$ of the k-rim of $\lambda$ lying in $H_u \cap V_v$ such that $y_2 - y_1 \ge v$.

By Proposition 3.8, in an irreducible k-shape the length of the k-rim is bounded, so that there are only finitely many of them. Therefore the generating function for irreducible k-shapes is a polynomial.

Thanks to the same proposition, we can also prove the following converse of Proposition 3.5:

**Corollary 3.9** Suppose that $\lambda, \lambda_1, \lambda_2$ are k-shapes and that there exist two different k- or $k-1$-rectangles $(u_1^{v_1})$ and $(u_2^{v_2})$ such that $\lambda = \lambda_1 + (u_1^{v_1}) = \lambda_2 + (u_2^{v_2})$. Then there exists a unique k-shape $\mu$ such that $\lambda = \mu + (u_1^{v_1}) + (u_2^{v_2})$.

It has the following important consequence:

**Corollary 3.10** For each k-shape $\lambda$, there is a unique irreducible k-shape $\mu$ and a unique family of non-negative integers $(C_{(u^v)})$ indexed by k- and $k-1$-rectangles $(u^v)$ such that

$$ \lambda = \mu + \sum_{(u^v)} C_{(u^v)}(u^v). \qquad (6) $$

Using this corollary, we can prove that the generating function for k-shapes is of the form shown in (1):
**Corollary 3.11** For $k \in \mathbb{N}$, the generating function for k-shapes is given by

$$f_k(t) = \frac{P_k(t)}{\prod(1 - t^{uv})} \qquad (7)$$

where the product is over the set of all k- or k - 1-rectangles ($u^v$) and $P_k(t) \in \mathbb{N}[t]$ is the polynomial generating function for irreducible k-shapes.

# 4 Work in progress

## 4.1 Main conjecture

In this section we discuss some approaches we are currently exploring around the following conjecture:

**Conjecture 4.1** Irreducible k-shapes are counted by the Genocchi numbers.

This conjecture has been extensively tested for all k up to 9.

We are considering two approaches: a direct bijection between irreducible k-shapes and some family of objects known to be counted by the Genocchi numbers (such as Dumont permutations of some kind, surjective pistols, certain tableaux...) and a recursive proof involving the Gandhi polynomials.

Indeed the following conjectural connection with Gandhi polynomials provides more evidence from the conjecture as well as what we believe is a good angle of attack to prove it. Let us recall the definition of those polynomials:

**Definition 4.2** For $k \ge 1$, the Gandhi polynomials $P_{2k}(x)$ are defined by the following recurrence:

$$\left\{ \begin{array}{l} P_2(x) = x^2 \\ P_{2k+2}(x) = x^2 (P_{2k}(x+1) - P_{2k}(x)) \end{array} \right. \qquad (8)$$

Gandhi [Gan70] conjectured that $P_{2k}(1) = G_{2k+2}$, which was later proved by Carlitz [Car71] and Riordan and Stein [RS73].

We need a small definition before stating a conjecture relating k-shapes and Gandhi polynomials.

**Definition 4.3** Let $\lambda$ be a k-shape and $\ell$ be an integer such that $1 \le \ell \le k$. We say that $(\ell, k+1-\ell)$ is a free k-site in $\lambda$ if there is no cell with $\ell-1$ cells to its right in the same row and $k-\ell$ cells above it in the same column (note that such a cell would have hook length $k$).

For example, the reader can check, looking at Figure 12, that the 4-shape $(5, 2, 1, 1)$ has 3 free 4-sites: $(1, 4)$, $(3, 2)$ and $(4, 1)$.

**Conjecture 4.4** Let $S(k, j)$ be the number of irreducible k-shapes with j free k-sites. Let $S_{2k}(x) = \sum_j S(k, j)x^j$. Then $S_{2k}(x) = P_{2k}(x)$.

We aim to prove this conjecture by showing that the $S_{2k}$ satisfy (8).

## 4.2 Algebraic perspectives

As we said in the introduction, the work presented here has a strong algebraic background. In particular, Lam et al [LLMS, Equation (11)] defined a symmetric function $s_{\mu}^{(k)}$ associated to each k-shape $\mu$. By definition, $s_{\mu}^{(k)}$ reduces to the k-Schur function $s_{\mu}^{(k)}$ if $\mu$ is a k-core and to the $s_{\mu}^{(k+1)}$ if $\mu$ is a k+1-core. Therefore, those functions are not linearly independent. Nevertheless, the operation of adding a k-rectangle to a k-core reflects an algebraic relation on symmetric functions [LM07, Theorem 40]: for any k-core $\lambda$ and k-rectangle $(u^v)$, if $s_{(u^v)}$ is the usual Schur function associated to $(u^v)$, then we have $s_{(u^v)} s_{\lambda}^{(k)} = s_{\lambda+(u^v)}^{(k)}$. It seems that the k-shape functions enjoy a similar property [Lap08]:
**Conjecture 4.5** Let $\lambda$ be a k-shape and $(u^v)$ be a k-rectangle or $k-1$-rectangle. Then

$$s_{(u^v)} \mathfrak{s}_{\lambda}^{(k)} = \mathfrak{s}_{\lambda+(u^v)}^{(k)} \qquad (9)$$

It seems moreover that this property passes to t-analogues replacing the Schur function by a vertex operator and the k-Schur functions by their graded version (see [LLMS, Equation (18)]).

## Acknowledgements

We wish to thank Luc Lapointe, who discussed the problem with us and provided us with useful references, and Matthieu Josuat-Vergès, who introduced us to various aspects of the combinatorics of the Genocchi numbers. We also point out that this research was driven by computer exploration using the open-source mathematical software Sage [S+10] and its algebraic combinatorics features developed by the Sage-Combinat community [SCc10].

## 5 Table

Generating series for irreducible k-shapes:

$$f_1(t) = \frac{1}{1-t},$$

$$f_2(t) = \frac{1}{(1-t)(1-t^2)^2},$$

$$f_3(t) = \frac{1+t+t^3}{(1-t^2)^2(1-t^3)^2(1-t^4)},$$

$$f_4(t) = \frac{1+t+2t^2+t^3+3t^4+2t^5+2t^6+3t^7+t^9+t^{10}}{(1-t^3)^2(1-t^4)^3(1-t^6)^2},$$

$$f_5(t) = \frac{1+t+2t^2+3t^3+3t^4+7t^5+6t^6+9t^7+9t^8+13t^9+13t^{10}+10t^{11}+13t^{12}+13t^{13}+13t^{14}+6t^{15}+10t^{16}+8t^{17}+5t^{18}+3t^{19}+3t^{20}+2t^{21}+t^{22}+t^{23}}{(1-t^4)^2(1-t^5)^2(1-t^6)^2(1-t^8)^2(1-t^9)}.$$

Irreducible 3-shapes: $\emptyset$ $\square$ $\square$

Irreducible 4-shapes: $\emptyset$ $\square$ $\square$ $\square$ $\square$ $\square$ $\square$ $\square$ $\square$ $\square$ $\square$ $\square$ $\square$ $\square$

## References

[BS07] Alexander Burstein and Walter Stromquist. Dumont permutations of the third kind. In 19th International Conference on Formal Power Series and Algebraic Combinatorics (Tianjin), 2007.

[Car71] L. Carlitz. A conjecture concerning Genocchi numbers. Norske Vid. Selsk. Skr. (Trondheim), (9):4, 1971.
[Dum74] Dominique Dumont. Interprétations combinatoires des nombres de Genocchi. *Duke Math. J.*, 41:305-318, 1974.

[Eul55] Leonhard Euler. *Institutiones calculi differentialis*, volume 10 of *Opera Mathematica 1*, chapter 7, pages 368-395. 1913 (orig. date 1755).

[Gan70] J. M. Gandhi. Research Problems: A Conjectured Representation of Genocchi Numbers. *Amer. Math. Monthly*, 77(5):505-506, 1970.

[Gen52] Angelo Genocchi. Intorno all'espressione generale de' numeri Bernulliani. *Annali di scienze matematiche e fisiche*, 3:395-405, 1852.

[Gen86] Angelo Genocchi. Sur les nombres de Bernoulli. *J. Reine Angew. Math.*, 99:315-316, 1886.

[JK81] Gordon James and Adalbert Kerber. *The representation theory of the symmetric group*, volume 16 of *Encyclopedia of Mathematics and its Applications*. Addison-Wesley Publishing Co., Reading, Mass., 1981.

[KR07] Sergey Kitaev and Jeffrey Remmel. Classifying descents according to parity. *Ann. Comb.*, 11(2):173-193, 2007.

[Lap08] Luc Lapointe. private communication, 2008.

[LLM03] L. Lapointe, A. Lascoux, and J. Morse. Tableau atoms and a new Macdonald positivity conjecture. *Duke Math. J.*, 116(1):103-146, 2003.

[LLMS] Thomas Lam, Luc Lapointe, Jennifer Morse, and Marc Shimozono. *k-shape poset and branching of k-Schur functions*. Available at http://fr.arxiv.org/abs/1007.5334.

[LM04] L. Lapointe and J. Morse. Order ideals in weak subposets of Young's lattice and associated unimodality conjectures. *Ann. Comb.*, 8(2):197-219, 2004.

[LM05] Luc Lapointe and Jennifer Morse. Tableaux on $k+1$-cores, reduced words for affine permutations, and $k$-Schur expansions. *J. Combin. Theory Ser. A*, 112(1):44-81, 2005.

[LM07] Luc Lapointe and Jennifer Morse. A $k$-tableau characterization of $k$-Schur functions. *Adv. Math.*, 213(1):183-204, 2007.

[Luc91] Édouard Lucas. *Théorie des nombres. Tome I: Le calcul des nombres entiers, le calcul des nombres rationnels, la divisibilité arithmétique*. Gauthier-Villars, Paris, 1891.

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

[S+10] W. A. Stein et al. *Sage Mathematics Software (Version 4.6)*. The Sage Development Team, 2010. http://www.sagemath.org.

[SCc10] The Sage-Combinat community. *Sage-Combinat: enhancing sage as a toolbox for computer exploration in algebraic combinatorics*, 2010. http://combinat.sagemath.org.

[Slo] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. http://www.research.att.com/~njas/sequences/.