FPSAC 2011, Reykjavík, Iceland

DMTCS proc. AO, 2011, 493–504

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 symmetricfunctions 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 pourles 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 dela 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
1

Introduction

2

Background495
2.1 Genocchi numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
2.2 Integer partitions and skew partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
2.3 k-cores and k-shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496

3

Irreducible k-shapes
497
3.1 Addition of rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
3.2 Main theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500

4Work in progress502
4.1 Main conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
4.2 Algebraic perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502

5

Table
† florent.hivert@univ-rouen.fr‡ olivier.mallet@univ-rouen.fr

1365–8050 c 2011 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

494

503

494

Florent Hivert and Olivier Mallet

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 thek-Schur functions of Lapointe-Lascoux-Morse; however, the reader who is not familiar with the theory ofsymmetric functions can skip the following paragraphs without harm.
The fundamental theorem of symmetric functions states that their ring Sym is freely generated by thehomogeneous symmetric functions (hi )i>0 . It therefore makes sense to study the subring Sym(k) generated
by the first k homogeneous functions Sym(k) := Q[h1 , h2 , . . . hk ]. Say that a partition λ = (λ1 , λ2 , . . . , λl )is k-bounded if it has no part exceeding k (i.e., k ≥ λ1 ≥ λ2 ≥ · · · ≥ λl > 0). Then, if we definehλ := hλ1 hλ2 . . . hλl , then (hλ )λ where λ 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, witha different definition, k-Schur functions in [LM05, LM07]. It should be noted that those papers actuallydeal with a more general setting where homogeneous symmetric functions are replaced with their naturalq-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’slattice on k + 1-cores.
(k)
An important question is to find a combinatorial way to expand the k-Schur function sλ in terms of
the usual Schur functions sλ . 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-coresand k + 1-cores. They indeed define a certain partially ordered set of partitions they call k-shapes (seeDefinition 2.1) such that k + 1-cores are the minimal elements and k-cores the maximal ones. The expansion(k)of sλ is essentially described by counting paths from k-cores to k + 1-cores in this poset up to someequivalence 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 ∈ N, the generating function for k-shapes is given by
Pk (t)uv
u,v (1 − t )fk (t) = Q(1)

where the product is over the set of all couples (u, v) of positive integers such that u + v ∈ {k, k + 1} and
Pk (t) ∈ N[t] is a polynomial with nonnegative integer coefficients.
Using computer, we evaluated the numerator Pk (t) up to k = 9 (see Section 5). Setting t = 1, one getsthe following tablekPk (1)

1
1

2
1

3
3

4
17

5
155

6
2073

7
38227

8
929569928820619

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:
Pk (1) is the k th Genocchi number.

Combinatorics of k-shapes and Genocchi numbers

495

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 wellas 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 G2n can be defined using the Bernoulli numbers Bn by
G2n = 2(22n − 1)|B2n |or via the generating function
X
t2n
2t
n
=
t
+
.
(−1)
G
2n
1 + et(2n)!
n≥1These 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]: G2n+2
is the number of permutations σ ∈ S2n such that σ2n is odd and, for i such that 1 ≤ i ≤ 2n − 1, σi isfollowed 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 λ = (λ1 , . . . , λm ) is a nonincreasing sequence of positive integers which are called the parts ofthe partition. We will sometimes also use the exponential notation for partitions: if λ is a partition and fi isthe number of occurrences of i in λ,Pthen we write λ = (1f1 2f2 . . .). The number of parts of λ is denotedmby ℓ(λ). The weight of λ is |λ| := i=1 λi . If the weight of λ is n, we say that λ is a partition of n. A
sequence c = (c1 , . . . , cm ) (not necessarily nonincreasing) of positive integers whose sum is n is called acomposition of n. We denote by c · c′ the concatenation of the two compositions c and c′ .
A partition λ is classically represented by a Ferrers diagram, which we denote by [λ], where the ith row
has λi squares (also called cells). We use the French notation for Ferrers diagrams: the rows are counted
from bottom to top. More precisely, [λ] is formed by the unit cells (x, y) with upper right corner at the point(x, y), where 1 ≤ y ≤ ℓ(λ) and 1 ≤ x ≤ λy . An example is shown on Figure 1.
The union of two partitions λ and µ, which we denote by λ ∪ µ, is a partition that is obtained by gathering
all the parts of λ and µ and sorting them in nonincreasing order. For example, if λ = (5, 4, 3, 3) andµ = (7, 6, 5, 3, 2, 1), we have λ ∪ µ = (7, 6, 5, 5, 4, 3, 3, 3, 2, 1).
The notion of skew partition will be needed throughout the paper. Given two partitions λ and µ, we writeµ ⊆ λ if µi ≤ λi for all i. If λ and µ satisfy µ ⊆ λ, we identify the skew partition λ/µ with its diagram,which is the set-theoretic difference [λ] r [µ]. The weight of λ/µ is |λ/µ| := |λ| − |µ|. For example,
λ/µ = (4, 3, 2, 2, 1)/(2, 1, 1) has weight 8 and its diagram is shown on Figure 2.

496

Florent Hivert and Olivier Mallet
y
4
3
2
1
x
1 2 3 4 5
Figure 1: The Ferrers diagram of (5, 4, 3, 3).

Figure 2: The diagram of the skew partition λ/µ = (4, 3, 2, 2, 1)/(2, 1, 1). The dotted lines indicate the cells of [µ].

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 locatedto 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.

b

Figure 3: The hook of the cell (2, 2) in the diagram of λ = (7, 6, 4, 3).

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 frombottom to top. Consequently, the cells of a diagram [λ] whose hook length is (strictly) larger than k form thediagram of a partition. Following [LLMS], we call this partition the k-interior of λ and denote it by Intk (λ).
As for the cells whose hook length does not exceed k, they form the diagram of a skew partition, which wecall the k-boundary of λ and denote by ∂ k (λ). We also define the k-rim of λ as the line that starts at theupper 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 λ/µ and denote by rs(λ/µ) the sequence of the lengths of the rows
(from bottom to top) of λ/µ. Likewise, we call column shape of λ/µ and denote by cs(λ/µ) the heights ofthe columns (from left to right) of λ/µ. Both rs(λ/µ) and cs(λ/µ) are compositions of |λ/µ|. For example,
if we call λ/µ the 6-interior of the partition represented on Figure 5, we have rs(λ/µ) = (5, 4, 2, 1) andcs(λ/µ) = (2, 2, 1, 1, 2, 1, 1, 1, 1). We also define rsk (λ) := rs(∂ k (λ)) and csk (λ) := cs(∂ k (λ)).
Definition 2.1 (Lam et al. [LLMS]) A partition λ is a k-shape if rsk (λ) and csk (λ) are both partitions.

Combinatorics of k-shapes and Genocchi numbers

497

1
2
5 2 1
6 3 2
9 6 5 2 1
Figure 4: The diagram of the 4-core (5, 3, 3, 1, 1) with its hook lengths.

1
3 1
7 5 3 2 1
12 10 8 7 6 4 3 2 1
Figure 5: The diagram of λ = (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 λ and those above it form the 6-boundary.

See Figure 6 for an example. Note that k-cores and k + 1-cores are k-shapes [LLMS, Proposition 10].
1234cs4 (λ)1
3 1
7 5 3 2 1
12 10 8 7 6 4 3 2 1
2 1 1 1 1 1 1 1 1

rs4 (λ)Figure 6: λ = (9, 5, 2, 1) is a 4-shape.

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 ourframework, to adding a k-rectangle to a k + 1-core.
Definition 3.1 ([LLM03]) A k-rectangle is a partition of the form (ℓk+1−ℓ ), where ℓ satisfies 1 ≤ ℓ ≤ k.
Evidently, k-rectangles are the partitions whose Ferrers diagram is a rectangle and whose largest hook lengthis k.
Lemma 3.2 Let r = (r1 , . . . , rm ) and c = (c1 , . . . , cp ) be two compositions of the same integer n. Then
there exists at most one skew partition λ/µ of weight n such that rs(λ/µ) = r and cs(λ/µ) = c.

498

Florent Hivert and Olivier Mallet

Proof: We build the skew partition row by row, from top to bottom. At the ith step (1 ≤ i ≤ m), we try
to insert a row of length rm+1−i . The first c1 rows must be left-justified so that the first column contains
c1 cells, as desired. The subsequent c1 − c2 rows must be shifted by one so that the first column does notcontain more than c1 cells and the second column contains c2 cells, and so on. Therefore, the resulting skew
partition is unique.
2
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 λ be a k-shape, r = rsk (λ) and c = csk (λ). For all i ∈ N∗ , let
Hi = [max{j | rj > i}, min{j | rj < i} − 1]
Vi = [max{j | cj > i}, min{j | cj < i} − 1]

(2)
(3)

We use the convention that if π is a partition, we have π0 = ∞ and πj = 0 if j > ℓ(π).
The horizontal strip Hi is the set {(x, y) ∈ R2 | y ∈ Hi }. Similarly, the vertical strip Vi is the set{(x, y) ∈ R2 | x ∈ Vi }.
Note that the interval Hi (resp. Vi ) is reduced to a singleton if there is no integer j such that rj = i(resp. cj = i). In this case, the corresponding strip is a single line. An example is the vertical strip V2 in the
k-shape shown on Figure 7.

H1

H2
H3
V4 V3

V1

V2
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 V2 is reduced
to a single line.

Proposition 3.4 Let λ be a k-shape and (uv ) be a k-rectangle or k − 1-rectangle. Then there exists a pointof the k-rim of λ that belongs to Hu ∩ Vv .
Proof (sketch): Using hook length considerations, we show that the upper right corner of the intersection
Hu ∩ Vv 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.
2

Combinatorics of k-shapes and Genocchi numbers

499
b

Hu

a

b
b

Vv
Figure 8: a is in the k-boundary and b in the k-interior; the k-rim therefore passes between these two points.

Proposition 3.5 Let λ be a k-shape and (uv ) be a k-rectangle or k −1-rectangle. Then there exists a uniquek-shape, which we denote by λ + (uv ), such thatrsk (λ + (uv )) = rsk (λ) ∪ (uv )
k

v

k

u

cs (λ + (u )) = cs (λ) ∪ (v )

(4)
(5)

Proof: We describe an algorithm that constructs ∂ k (λ + (uv )) from ∂ k (λ) by “inserting” the rectangle into
the k-shape. Proposition 3.4 implies that we can decompose ∂ k (λ) into three parts: the cells located to theright of p and above it, which we call the foot (region F in Figure 9), the cells to the left of the foot (regionA) and the cells below the foot (region B).
u
A

v

F
p

b

B

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.

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

v

F
v

u

F̄
F2
B

Figure 10: Result of the insertion process. F2 is a copy of F and F̄ is the complement of F in (uv ).

500

Florent Hivert and Olivier Mallet

We call this skew partition λ̃/µ̃. First, we must prove that it satisfies (4) and (5). If R1 and R2 are tworegions of the diagram, let R1 ∨ R2 denote their set-theoretic union. We have thatrs(λ̃/µ̃) = rs(B) · rs(F̄ ∨ F2 ) · rs(A ∨ F )= rs(B) · (uv ) · rs(A ∨ F )= rs(λ/µ) ∪ (uv )because rs(B) is a partition into parts ≥ u and rs(A ∨ F ) is a partition into parts ≤ u, since λ is a k-shape.
Therefore, λ̃/µ̃ satisfies (4); the proof that it satisfies (5) is similar.
We now need to check that µ̃ is indeed the k-interior of λ̃, i.e. that the hook lengths of λ̃/µ̃ do not exceed
k and those of µ̃ are greater than k. To this end, we decompose [λ̃] as shown on Figure 11.

A
A′

F
F̄
F2
C
B′

B

Figure 11: Decomposition of [λ̃] 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.

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 F2 ) have not been modified either,
for the same reason. A cell in the region F̄ has at most u − 1 cells to its right in the same row and at mostv − 1 cells above it in the same column: its hook length thus does not exceed u + v − 1 ≤ k. Likewise, a cellin the region C has at least u cells to its right in the same row and v cells above it in he same column, andtherefore has hook length at least u + v + 1 ≥ 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. 2
See Figure 12 for an example of the insertion process.
Proposition 3.6 Let λ be a k-shape and let (uv11 ) and (uv22 ) be two k- or k − 1-rectangles. Then(λ + (uv11 )) + (uv22 ) = (λ + (uv22 )) + (uv11 ).
Proof: We have rs ((λ + (uv11 )) + (uv22 )) = rs(λ) ∪ (uv11 ) ∪ (uv22 ) = rs ((λ + (uv22 )) + (uv11 )) and likewisecs ((λ + (uv11 )) + (uv22 )) = cs ((λ + (uv22 )) + (uv11 )). The proof is completed by using Lemma 3.2.
2

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.

Combinatorics of k-shapes and Genocchi numbers

H1

A
b

H2
H3

501

b

b

b

F
B

V3

V1

(a) The initial 4-shape
λ=(5, 2, 1, 1)
with the possible
insertion points for the
4-rectangle (23 ).

(b) Decomposition of∂ 4 (λ) with respect tothe insertion point p =(1, 1).

A
F
F̄
F2
B
(d) The final 4-shape(7, 4, 3, 3, 2, 1, 1).

(c) The skew partition resulting from the insertion
process.

Figure 12: The insertion of the 4-rectangle (23 ) into the 4-shape (5, 2, 1, 1) produces the 4-shape (7, 4, 3, 3, 2, 1, 1).

Proposition 3.8 Let λ be a k-shape and (uv ) be a k- or k − 1-rectangle. The following are equivalent:(i) there exists a k-shape µ such that λ = µ + (uv ),(ii) there exist two points (x1 , y1 ) and (x2 , y2 ) of the k-rim of λ lying in Hu ∩ Vv such that x2 − x1 ≥ u,(iii) there exist two points (x1 , y1 ) and (x2 , y2 ) of the k-rim of λ lying in Hu ∩ Vv such that y2 − y1 ≥ 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 λ, λ1 , λ2 are k-shapes and that there exist two different k- or k − 1-rectangles(uv11 ) and (uv22 ) such that λ = λ1 + (uv11 ) = λ2 + (uv22 ). Then there exists a unique k-shape µ such that
λ = µ + (uv11 ) + (uv22 ).
It has the following important consequence:
Corollary 3.10 For each k-shape λ, there is a unique irreducible k-shape µ and a unique family of nonnegative integers (C(uv ) ) indexed by k- and k − 1-rectangles (uv ) such that
λ=µ+X

C(uv ) (uv ) .

(uv )Using this corollary, we can prove that the generating function for k-shapes is of the form shown in (1):

(6)

502

Florent Hivert and Olivier Mallet

Corollary 3.11 For k ∈ N, the generating function for k-shapes is given by
Pk (t)
fk (t) = Q(1 − tuv )(7)

where the product is over the set of all k- or k − 1-rectangles (uv ) and Pk (t) ∈ 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 familyof 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 theconjecture 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 ≥ 1, the Gandhi polynomials P2k (x) are defined by the following recurrence:(
P2 (x) = x2
P2k+2 (x) = x2 (P2k (x + 1) − P2k (x))(8)

Gandhi [Gan70] conjectured that P2k (1) = G2k+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 λ be a k-shape and ℓ be an integer such that 1 ≤ ℓ ≤ k. We say that (ℓ, k + 1 − ℓ) is afree k-site in λ if there is no cell with ℓ − 1 cells to its right in the same row and k − ℓ cells above it in thesame 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 S2k (x) =Pjj S(k, j)x . Then S2k (x) = P2k (x).
We aim to prove this conjecture by showing that the S2k satisfy (8).

4.2 Algebraic perspectives
As we said in the introduction, the work presented here has a strong algebraic background. In particular, Lam(k)et al [LLMS, Equation (11)] defined a symmetric function sµ associated to each k-shape µ. By definition,
(k)
(k)
(k+1)
sµ reduces to the k-Schur function sµ if µ is a k-core and to the sµ
if µ is a k + 1-core. Therefore,
those functions are not linearly independent. Nevertheless, the operation of adding a k-rectangle to a k-corereflects an algebraic relation on symmetric functions [LM07, Theorem 40]: for any k-core λ and k-rectangle(k)(k)(uv ), if s(uv ) is the usual Schur function associated to (uv ), then we have s(uv ) sλ = sλ+(uv ) . It seems thatthe k-shape functions enjoy a similar property [Lap08]:

Combinatorics of k-shapes and Genocchi numbers

503

Conjecture 4.5 Let λ be a k-shape and (uv ) be a k-rectangle or k − 1-rectangle. Then
(k)

(k)

s(uv ) sλ = sλ+(uv )(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 TableGenerating series for irreducible k-shapes:
f1 (t) =

1
,
1−t

1
,
(1 − t)(1 − t2 )2
1 + t + t3,
f3 (t) =2
2(1 − t ) (1 − t3 )2 (1 − t4 )1 + t + 2t2 + t3 + 3t4 + 2t5 + 2t6 + 3t7 + t9 + t10,
f4 (t) =(1 − t3 )2 (1 − t4 )3 (1 − t6 )2
1 + t + 2t2 + 3t3 + 3t4 + 7t5 + 6t6 + 9t7 + 9t8 + 13t9 + 13t10 + 10t11 + 13t12 +13t13 + 13t14 + 6t15 + 10t16 + 8t17 + 5t18 + 3t19 + 3t20 + 2t21 + t22 + t23
f5 (t) =.
(1 − t4 )2 (1 − t5 )2 (1 − t6 )2 (1 − t8 )2 (1 − t9 )f2 (t) =Irreducible 3-shapes: ∅Irreducible 4-shapes: ∅References[BS07]

Alexander Burstein and Walter Stromquist. Dumont permutations of the third kind. In 19thInternational 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.

504

Florent Hivert and Olivier Mallet[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 branchingof 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 associatedunimodality 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 desnombres 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/.