M -LEVEL ROOK PLACEMENTS
By
Kenneth Barrese

A DISSERTATION
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of
Mathematics—Doctor of Philosophy
2015

ABSTRACT
M -LEVEL ROOK PLACEMENTS
By
Kenneth Barrese
Rook theory focuses on placements of non-attacking rooks on boards of various shapes.
An important role is played by the rook numbers which count the number of non-attacking
placements of a given number of rooks on a board. Ferrers boards, which are boards indexed
by integer partitions, are of particular interest. Briggs and Remmel introduced a generalization of rook placements, called m-level rook placements, where a rook is able to attack a
subset of the rows.
This manuscript presents generalizations of many of the central results regarding rook
placements to the case of m-level rook placements. Goldman, Joichi, and White defined the
rook polynomial of a board to be the generating function for the rook numbers of that board
in the falling factorial basis. By doing so, they were able to give an elegant factorization of
the rook polynomial of a Ferrers board in terms of the various column heights. Briggs and
Remmel were able to generalize this factorization to the m-level rook polynomial of a subset
of Ferrers boards called singleton boards.
We give two factorization theorems for the m-level rook polynomial of a Ferrers board.
The first is a generalization of the factorization theorem of Briggs and Remmel, working
from similar principles. The second relies on a generalization of transposition which we
present, called the l-operator. We are also able to use the factorization to describe a unique
representative in any m-level equivalence class of Ferrers boards and count the number of
singleton boards in the class..
When generalizing the factorization from singleton boards to all Ferrers boards, we pre-

serve the definition of the m-level rook polynomial and alter the factorization to apply to
all Ferrers boards. We also consider the dual of this problem, applying the factorization of
Briggs and Remmel to all Ferrers boards, then trying to determine what is counted by the
coefficients of the polynomial in the m-falling factorial basis. It turns out that the coefficients
count weighted file placements on a Ferrers board. We also describe a unique representative
in each weighted file placement equivalence class of Ferrers boards, as well as count of the
number of Ferrers boards in a given weighted file placement equivalence class.
Foata and Sch¨
utzenberger presented explicit bijections between rook placements on any
two rook equivalent Ferrers boards as part of their construction of a unique representative
in each equivalence class of Ferrers boards. A key tool in their construction was local
transposition. We present analogous bijections between m-level rook placements on any two
m-level rook equivalent Ferrers boards using the local l-operator.
The Garsia-Milne Involution Principle was first used in Garsia and Milne’s bijective proof
of the Rogers-Ramanujan identities. We use it to construct two types of explicit bijections.
The first is an explicit bijection between m-level rook placements on any two m-level rook
equivalent singleton boards. The second bijection is between the sets counted by the mlevel analogue of hit numbers of any two m-level rook equivalent Ferrers boards, providing
a bijective proof that m-level equivalent Ferrers boards have the same hit numbers.

To Jenn, whose patience with this project often outstripped my own.

iv

ACKNOWLEDGMENTS

I must thank my parents for raising me with a deep seated belief in the value of academic
pursuits. I would not be getting a Ph.D. without it.
Similarly, that I am here stands testament to the enormous talent of the mathematics
educators from whom I have been fortunate enough to study. In public schools these educators began with Mrs. Hanshumaker and ended with my friend Mr. Stallons. Thank you
both, and I’m still not calling you Frank. As an undergraduate, I benefited from the courses
and advice I received from my eventual thesis advisor, Dr. Flahive. Finally, as a doctoral
student I owe great gratitude to my committee members, Dr. Bell, Dr. Hall, Dr. Magyar,
and Dr. Meierfrankenfeld, all of whom have led courses that I greatly enjoyed.
I would like to thank my collaborators, Dr. Loehr and Dr. Remmel, for sharing their
interest in the field of rook placements with me. Finally, I have to thank Dr. Sagan, who
has been an inspiring educator, a valuable collaborator, and an essential mentor for me.

v

TABLE OF CONTENTS

LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapter 1 Introduction and definitions
1.1 Introduction . . . . . . . . . . . . . . .
1.1.1 Background . . . . . . . . . . .
1.1.2 m-level rook placements . . . .
1.2 Organization . . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

1
1
1
6
8

rook polynomials
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

10
10
11
15
22
25
29
33

Chapter 3 Bijections on m-level rook placements . . . . .
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Rook equivalence and bijections . . . . . . . . . . . . . . .
3.2.1 Reduction to singleton boards . . . . . . . . . . . .
3.2.2 The l-operator . . . . . . . . . . . . . . . . . . . .
3.2.3 The local l-operator . . . . . . . . . . . . . . . . . .
3.2.4 The Local l-operation on an m-level rook placement
3.2.5 Bijections with m-increasing boards . . . . . . . . .
3.3 A second bijection on m-level rook placements . . . . . . .
3.3.1 A Garsia-Milne bijection for rook placements . . . .
3.4 A bijection for hit numbers . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

35
35
36
36
39
41
45
47
50
51
58

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

Chapter 2 Factorization for m-level
2.1 Introduction . . . . . . . . . . . .
2.2 The m-Factorization Theorem . .
2.3 Rook equivalence . . . . . . . . .
2.4 Enumeration of singleton boards .
2.5 File placements . . . . . . . . . .
2.6 Weight equivalence classes . . . .
2.7 Weight equivalence class sizes . .

BIBLIOGRAPHY

vi

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

vii

LIST OF FIGURES

Figure 1.1

On the left, a board of size 7 and a placement of three rooks on the
board. On the right, a Ferrers board, B, also of size 7. . . . . . . . .

2

Figure 1.2

Levels and rook placements

7

Figure 2.1

The zones of (1, 1, 2, 3, 5, 7) when m = 3

. . . . . . . . . . . . . . .

11

Figure 2.2

The board Bx . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

Figure 2.3

A board B and l(B) when m = 2 . . . . . . . . . . . . . . . . . . .

17

Figure 2.4

A file placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

Figure 3.1

On the left, a placement of two 2-level rooks on B. In the middle,
the corresponding placement from Lemma 3.2.3 of two 2-level rooks
on singleton board BS . On the right, the placement on l(BS ) from
Lemma 3.2.5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

The dashed line goes through the cells counted by the 2-arm length
of the fourth column and first level, and the shaded cells are counted
by the corresponding 2-leg length. . . . . . . . . . . . . . . . . . . .

42

On the left, B3,2 is shaded within B = (1, 4, 4, 5). Notice that l3,2
is not permissible for B since armlm (4, 2) m < leglm (3, 2), which
means l3,2 (B) will not be a singleton board. On the right the shaded
cells in l(B3,2 ) illustrate this; in this case l3,2 (B) is not even a Ferrers
board. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

On the left, B4,2 is shaded. Here l4,2 is permissible for B and is shown
on the right. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

(a) A 2-level rook placement on a Ferrers board. (b) The placement on the singleton board obtained after applying Lemma 3.2.3.
(c) The placement obtained after applying Lemma 3.2.8 using l3,1 .
(d) The placement obtained on a 2-increasing board after applying
Lemma 3.2.8 again using l3,3 . . . . . . . . . . . . . . . . . . . . . . .

50

Figure 3.2

Figure 3.3

Figure 3.4

Figure 3.5

vii

. . . . . . . . . . . . . . . . . . . . . .

On the top left, an element in S with sign −1. On the top right, the
image under I which has sign +1. Beneath each board is its image
under f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

Figure 3.7

The placement corresponding to partition {1, 4}, {2, 3, 5}, {6}.

. . .

56

Figure 3.8

The placement on Sq3,2 corresponding to (α1 , α2 , α1 ; (1, 3, 2)). . . .

59

Figure 3.9

On the left, an element in S with sign +1. On the right, the image
under I which has sign −1. . . . . . . . . . . . . . . . . . . . . . . .

60

On the left, a 2-level placement of white rooks, black rooks, and
circled black rooks on (1, 1, 1, 3, 6) fit inside Sq5,2 . On the right, the
corresponding placement under the construction in Theorem 3.4.1.

61

Figure 3.6

Figure 3.10

viii

Chapter 1
Introduction and definitions

1.1
1.1.1

Introduction
Background

The study of rook placements began with a 1946 paper of Kaplansky and Riordan [KR46].
They introduced the concept as a way of unifying various results counting the number of
permutations which satisfied certain conditions, or violated a specified number of them. To
do so, they considered placing non-attacking rooks on “chessboards” of various shapes.
A board B is any finite subset of Z+ × Z+ . Geometrically one can think of a board as a
finite number of square cells in a square grid, this is illustrated on the left of Figure 1.1. The
squares with darkened edges form a board and the lighter lines show the underlying grid.
On the right side of the figure there is another board, this time with the underlying grid
omitted. The size of a board B is the number of squares in the board, this is often denoted
|B|. For example, both boards in Figure 1.1 have size 7.
A placement of non-attacking rooks on B, henceforth called a rook placement, is a subset
P ⊆ B such that no two elements of P are in the same row or column. Graphically, one can
think of placing rooks in the squares of the board so that no rook can capture another rook
in a single move, according to the rules of chess. The board on the left in Figure 1.1 contains
a rook placement of 3 rooks. We label each cell by the Cartesian coordinates of its northeast

1

..
.
R
R
...
B = (1, 3, 3) =
R
Figure 1.1: On the left, a board of size 7 and a placement of three rooks on the board. On
the right, a Ferrers board, B, also of size 7.

corner, so the rooks on the left of Figure 1.1 are in cells (1, 3), (2, 4), and (3, 1) from left to
right. Note that this is neither the English nor the French style of writing Ferrers diagrams,
but it is the standard convention in modern rook theory literature. It is useful because we
usually consider placing rooks on the board from left to right and enumerating the number
of such placements is facilitated by our convention.
Kaplansky and Riordan also introduced the generating polynomial of rook placements
on a board. For any board B we let

rk (B) = the number of rook placements P ⊆ B with k rooks.

We call rk (B) the kth rook number of B. Note that for any board r0 (B) = 1, as there is a
unique way to place no rooks on the board, and r1 (B) = |B|, because a single rook can be
placed in any square of the board without violating the non-attacking condition. For either
board in Figure 1.1 r0 (B) = 1, r1 (B) = 7, r2 (B) = 10, r3 (B) = 2, and rk (B) = 0 for k ≥ 4.
Kaplansky and Riordan defined the rook polynomial of B to be the the generating function

2

of these rook numbers in the standard polynomial basis, yielding

rk (B)xk .

(1.1.1)

k≥0

By this definition of the rook polynomial, the rook polynomial of either board in Figure 1.1
is 1 + 7x + 10x2 + 2x3 .
In 1970, Foata and Sch¨
utzenberger [FS70] introduced the term rook equivalent to describe
two boards which have the same rook polynomial. For example, the two boards pictured
in Figure 1.1 are rook equivalent because they have all the same rook numbers. Foata and
Sch¨
utzenberger restricted their consideration to a subset of boards associated with (integer)
partitions. A partition is a weakly increasing sequence (b1 , . . . , bn ) of nonnegative integers.
We will use the same notation for the corresponding Ferrers board B = (b1 , . . . , bn ) which
consists of the the bi lowest squares in column i for 1 ≤ i ≤ n. The board B = (1, 3, 3)
is shown on the right in Figure 1.1, while the board on the left side of Figure 1.1 is not a
Ferrers board.
A Ferrers board B = (b1 , . . . , bn ) is strictly increasing if bi < bi+1 for all i. Note
that the board on the right of Figure 1.1 is not strictly increasing because b2 = b3 = 3.
Restricting attention to Ferrers boards, Foata and Sch¨
utzenberger were able to characterize
the equivalence classes under the rook equivalence relation by showing that there is a unique
strictly increasing Ferrers board in each equivalence class. To do so, they constructed explicit
bijections between rook placements on any Ferrers board in the class and rook placements
on the unique representative.
Theorem 1.1.1 (Theorem 11 [FS70]). Each Ferrers board is rook equivalent to exactly one
strictly increasing Ferrers board.
3

Goldman, Joichi, and White [GJW75] gave a different definition of the rook polynomial
of a board in 1975. Instead of writing it in the standard basis for polynomials, as seen
in 1.1.1, they used the basis of falling factorials

x ↓n = x(x − 1)(x − 2) . . . (x − n + 1)

for any integer n ≥ 0. In this basis, the rook polynomial of a board B with n columns is
n

rk (B)x ↓n−k .
k≥0

This is the definition of rook polynomial we will be using throughout the rest of this document. Using this definition, the rook polynomial of either board in Figure 1.1, both of which
have n = 3, is

1x ↓3 +7x ↓2 +10x ↓1 +2x ↓0 = x(x − 1)(x − 2) + 7x(x − 1) + 10x + 2 = x3 + 4x2 + 5x + 2.

Goldman, Joichi, and White were able to show that the falling factorial rook polynomial of
any Ferrers board factored over the integers.
Theorem 1.1.2 (Theorem 2 [GJW75]). Let B = (b1 , . . . , bn ) be a Ferrers board, then
n

n

rk (B)x ↓n−k =
k=0

(x + bi − i + 1).
i=0

Continuing the above example, we determined that the rook polynomial of B = (1, 3, 3)

4

is

x3 + 4x2 + 5x + 2 = (x + 1)(x + 2)(x + 1) = (x + 1 − 1 + 1)(x + 3 − 2 + 1)(x + 3 − 3 + 1)

as stated in Theorem 1.1.2.
In 2009 Loehr and Remmel [LR09] introduced another explicit bijection between rook
placements on rook equivalent Ferrers board. Their bijection made use of the Garsia-Milne
Involution Principle [GM81], which was developed as part of Garsia and Milne’s bijective
proof of the Rogers-Ramanujan identities.
Another important set of numbers associated with a board are its hit numbers. Given
a permutation ω = (ω(1), . . . , ω(N )) in SN , the symmetric group on N elements, one can
associate a rook placement of N rooks on an N × N square board with ω in the following
way. If ω(i) = j, then place a rook in square (i, N + 1 − j). We will denote this placement
R(ω). This is equivalent to the permutation matrix of ω, considered as a left action, where
the zeroes in the matrix are empty squares and the ones in the matrix are squares containing
rooks.
For any board B and any integer N such that B can be considered as a subset of the
squares of an N × N board, we can define the kth hit set of B by,

Hk,N (B) = {R(ω) | ω ∈ SN and |R(ω) ∩ B| = k}.

Then the kth hit number of B is

hk,N (B) = |Hk,N (B)|.

5

In their seminal 1946 paper, Kaplansky and Riordan noted that this definition implied that
N

N

hk,N
k=0

(B)xk

rk (B)(N − k)!(x − 1)k ,

=
k=0

which implies that two rook equivalent boards will have the same hit numbers for any N
large enough for both to be considered as subboards of the N ×N square board. In the paper
cited above, Loehr and Remmel also used the Garsia-Milne method to give explicit bijections
between the hit sets of any two equivalent Ferrers boards. This provided a bijective proof
that any two rook equivalent Ferrers boards have the same hit numbers.

1.1.2

m-level rook placements

In 2008 Briggs and Remmel [BR06] introduced a generalization of rook placements, called
m-level rook placements. The new rook placements correspond with elements of the wreath
product of the cyclic group of order m with the symmetric group on N elements, Cm SN ,
in the same way that Kaplansky and Riordan’s placements correspond to elements of SN as
detailed at the end of the last subsection. Using m-level rook placements and the concept of
flag descents developed by Adin, Brenti, and Roichman [ABR01], Briggs and Remmel were
able to generalize a formula of Frobenius to Cm Sn . They also provided a factorization,
similar to that of Goldman, Joichi, and White, for the m-rook polynomial of a specific type
of Ferrers board, called a singleton board.
In order to make the concepts of the previous paragraph more precise, we first define
what a level is. Fix a positive integer m. Partition the rows of Z+ × Z+ into levels where
the pth level consists of rows (p − 1)m + 1, (p − 1)m + 2, . . . , pm. The situation for m = 2 is
shown on the left in Figure 1.2 where the boundaries between the levels have been thickened.
6

..
.

{
{

R

level 2

...

R

level 1

R

R

Figure 1.2: Levels and rook placements

Given a board, B, an m-level rook placement (called an m-rook placement by Briggs and
Remmel) is P ⊆ B where no two elements of P are in the same level or the same column.
Note that when m = 1 we recover the ordinary notion of a rook placement. By way of
example, in Figure 1.2, the placement on the middle board is a 2-level rook placement while
the one on the right is not since it has two rooks in the first level. We let

rk,m (B) = the number of m-level rook placements P ⊆ B with k rooks.

In general, we will add a subscript m to quantities when considering their m-level equivalents.
For B = (1, 3, 3) we have r0,2 (B) = 1, r1,2 (B) = 7, r2,2 (B) = 6, and rk,2 (B) = 0 for k ≥ 3.
To state the Briggs-Remmel generalization of Theorem 1.1.2, we need a few more concepts. One is of an m-falling factoring, a generalization of the falling factorial, defined by

x ↓n,m = x(x − m)(x − 2m) . . . (x − (n − 1)m).

Now we define an important subset of Ferrers boards when considering m-level rook placements. Having already fixed a positive integer m, a singleton board (called an m-Ferrers
board by Briggs and Remmel), is a Ferrers board B = (b1 , . . . , bn ) such that there is
7

at most one bi in each of the intervals (0, m), (m, 2m), . . . where (km, (k + 1)m) =
{km + 1, km + 2, . . . , km + m − 1}.
Another way of defining singleton boards is to consider the highest level a column has
squares in. We say that the ith column of B terminates in level p if p is the largest integer such
that the ith column has non-empty intersection with Qp . This gives another characterization
of a singleton board, as any Ferrers board such that, for each positive integer p, the set of
all columns bi terminating in level p contains at most one i such that bi ≡ 0 mod m. Briggs
and Remmel gave a factorization theorem, similar to that of Goldman, Joichi, and White,
but only for singleton boards.
Theorem 1.1.3 (Theorem 2 [BR06]). If B = (b1 , . . . , bn ) is a singleton board then
n

n

(x + bi − (i − 1)m).

rk,m (B)x ↓n−k,m =
k=0

1.2

i=1

Organization

We proceed to generalize the above results for m-level rook placements. In Chapter 2 we
remove the singleton requirement from Theorem 1.1.3. This facilitates generalizing Theorem 1.1.1 to m-level rook placements on Ferrers boards and enumerating the singleton boards
in a given equivalence class, an analogue of a result of Goldman, Joichi, and White. Finally
we consider what is counted if we take the product on the right side of Theorem 1.1.3 for
any Ferrers board and expand it in the m-falling factorial basis.
In Chapter 3 we begin by extending the bijections detailed by Foata and Sch¨
utzenberger
to m-level rook placements on Ferrers boards. We create a second explicit bijection between
m-level rook placements on singleton boards by generalizing that of Loehr and Remmel,
8

again using the Garsia-Milne Involution Theorem. Finally we use similar methods to create
bijections between the sets counted by appropriately defined hit numbers of m-level rook
equivalent Ferrers boards.

9

Chapter 2
Factorization for m-level rook
polynomials

2.1

Introduction

The material in this chapter is a result of a collaboration with Nicholas Loehr, Jeffrey
Remmel, and Bruce Sagan, and has appeared in the paper [BLRS14].
The first goal of this chapter is to remove the singleton board restriction from Theorem 1.1.3 and prove a generalization of this theorem for any Ferrers board. This will be
done in the next section. Call boards B, B m-level rook equivalent if rk,m (B) = rk,m (B )
for all k. In Section 2.3 we extend to all m Theorem 1.1.1 of Foata and Sch¨
utzenberger [FS70]
giving a distinguished member of each 1-level rook equivalence class. Goldman, Joichi and
White used the Factorization Theorem to enumerate the number of Ferrers boards 1-level
rook equivalent to a given board. In Section 2.4 we generalize this formula to count m-level
rook equivalent singleton boards for arbitrary m. The rest of the chapter is devoted to the
following dual problem. Rather than changing the product side of Theorem 1.1.3, keep the
same product for all Ferrers boards and expand it in the m-falling factorial basis. What
do the coefficients count? We show in Section 2.5 that they are generating functions for
certain weighted file placements, where such placements allow more than one rook in a given
row. The next sections investigate properties of the corresponding equivalence classes. In
10

Figure 2.1: The zones of (1, 1, 2, 3, 5, 7) when m = 3

particular, in Section 2.7 we count the number of boards in a given class.

2.2

The m-Factorization Theorem

In order to generalize Theorem 1.1.3 to all Ferrers boards, it will be convenient to break
a board up into zones depending on the lengths of the columns. Given integers s, t, the
interval from s to t will be denoted [s, t] = {s, s + 1, . . . , t}. An m-zone, z, of a board
B = (b1 , . . . , bn ) is a maximal interval [s, t] such that bs m = bs+1 m = · · · = bt m .
To illustrate this concept, consider m = 3 and the board B = (1, 1, 2, 3, 5, 7) shown in
Figure 2.1. In this case the zones are z1 = [1, 3] since b1 3 = b2 3 = b3 3 = 0, z2 = [4, 5]
since b4 3 = b5 3 = 3, and z3 = [6, 6] since b6 3 = 6. The zones in Figure 2.1 are
separated by thick lines (as are the levels). Note that a Ferrers board is a singleton board
if and only if each zone contains at most one column whose length is not a multiple of m.
This is the reason for our choice of terminology.

11

The m-floor function of an integer n is defined as follows, let

n m = the largest multiple of m less than or equal to n.

For example, 17 3 = 15 since 15 ≤ 17 < 18. In addition to taking m-floors, we will have to
consider remainders modulo m. Given an integer n, we denote its remainder on division by
m by ρm (n) = n − n m . Continuing the previous example, ρm (17) = 17 − 17 3 = 2. If z
is a zone of a Ferrers board B = (b1 , . . . , bn ) then its m-remainder is

ρm (bi ).

ρm (z) =
i∈z

In Figure 2.1, the boxes corresponding to the 3-remainders of the zones are shaded. In
particular ρ3 (z1 ) = 1 + 1 + 2 = 4, ρ3 (z2 ) = 0 + 2 = 2, and ρ3 (z3 ) = 1. We are now in a
position to state and prove our generalization of Theorem 1.1.3.
Theorem 2.2.1 (m-Factorization Theorem). If B = (b1 , . . . , bn ) is any Ferrers board then

n

rk,m (B)x ↓n−k,m =
k=0




n 
x + bi m − (i − 1)m + ρm (z) if i is the last index in its zone z,



i=1 
x +

bi m − (i − 1)m

otherwise.

Proof. Since this is a polynomial identity, it suffices to prove it for an infinite number of
values for x. We will do so when x is a nonnegative multiple of m. Consider the board
Bx derived from B by adding an x × n rectangle below B. Figure 2.2 shows a schematic
representation of Bx . Note that since x is a multiple of m, the zones and remainders of B
and Bx are the same. We will show that both the sum and the product count the number
of m-rook placements on Bx consisting of n rooks.
12

B

Bx =

x

n
Figure 2.2: The board Bx

For the sum side, note that any placement of n rooks on Bx must have k rooks in B and
n − k rooks in the rectangle for some 0 ≤ k ≤ n. By definition, rk,m (B) counts the number
of placements on B. Once these rooks are placed, one must place the remaining rooks in
the x × (n − k) subrectangle consisting of those columns of the original rectangle not used
for the rooks on B. Placing these rooks from left to right, there will be x choices for the
position of the first rook, then x − m choices for the next, and so on, for a total of x ↓n−k,m
choices. Thus the sum side is rn,m (Bx ) as desired.
On the product side, it will be convenient to consider placing rooks on Bx zone by zone
from left to right. So suppose z = [s, t] is a zone and all rooks in zones to its left have been
placed. Because z is a zone we have bs m = · · · = bt m = cm for some constant c. Also,
among all the rooks placed in the columns of z, there is at most one which is in the set of
squares R corresponding to ρm (z). If there are no rooks in R then they all go in a rectangle

13

of height x + cm. Thus, using the same ideas as in the previous paragraph, the number of
placements is

(x + cm − (s − 1)m)(x + cm − sm) . . . (x + cm − (t − 1)m).

(2.2.1)

When there is one rook in R, say it is in the column with index i. So there are ρm (bi ) choices
for the placement of this rook and the rest of the rooks go in a rectangle of height x + cm.
This gives a count of

ρm (bi )(x + cm − (s − 1)m)(x + cm − sm) . . . (x + cm − (t − 2)m).

(2.2.2)

Adding together the contributions from (2.2.1) and (2.2.2) and factoring, we see that the
total number of placements is

(x + cm − (s − 1)m) . . . (x + cm − (t − 2)m)(x + cm − (t − 1)m + ρm (z)).

Remembering that bs m = · · · = bt m = cm, we see that this is exactly the contribution
needed for the product.

We should show why our result implies the theorems of Goldman-Joichi-White and
Briggs-Remmel. In both cases, it is clear that the sum sides correspond, so we will concentrate on the products.
For Theorem 1.1.2 we take m = 1. Since n 1 = n for any n, ρ1 (z) = 0 for any zone z
and the two cases in Theorem 2.2.1 are the same. So the contribution of the ith column to

14

the product is
x + bi 1 − (i − 1) · 1 = x + bi − i + 1
in agreement with the Factorization Theorem.
As for Theorem 1.1.3, suppose that B is a singleton board and consider any zone z = [s, t].
If s ≤ i < t then bi is a multiple of m and

x + bi m − (i − 1)m = x + bi − (i − 1)m.

And if i = t then ρm (z) = ρm (bt ) so that

x + bt m − (t − 1)m + ρm (z) = x + bt − (t − 1)m.

So in either case one gets the same factor as in the Briggs-Remmel result.

2.3

Rook equivalence

Two Ferrers boards B, B are m-level rook equivalent if rk,m (B) = rk,m (B ) for all k ≥ 0.
In this case we will write B ≡m B . We will drop the “m” and just say “rook equivalent”
if m = 1. Recall that Foata and Sch¨
utzenberger [FS70] proved a beautiful theorem giving a
distinguished board in each equivalence class.
Theorem 2.3.1 ([FS70]). Every Ferrers board is rook equivalent to a unique strictly increasing board.
The purpose of this section is to extend Theorem 2.3.1 to arbitrary m. The FoataSch¨
utzenberger result was reproved by Goldman-Joichi-White using their Factorization The15

orem. To see the connection, suppose that B = (b1 , . . . , bn ) and B = (b1 , . . . , bn ) are two
Ferrers boards. Although we are writing the boards with the same number of columns, this
is no restriction since we can always pad the shorter board with columns of height 0 on the
left. So B and B are rook equivalent if and only if they have the same generating function
in the falling factorial basis. By Theorem 1.1.2, this happens if and only if the two vectors

ζ(B) = (−b1 , 1−b2 , 2−b3 , . . . , (n−1)−bn ) and ζ(B ) = (−b1 , 1−b2 , 2−b3 , . . . , (n−1)−bn )

are rearrangements of each other since these are the zeros of the corresponding products. We
call ζ(B) the root vector of B. For example, if B = (1, 1, 3) and B = (2, 3) then, rewriting
B = (0, 2, 3), we have ζ(B) = (−1, 0, −1) and ζ(B ) = (0, −1, −1) and so B ≡ B . We
should note that padding a board B with zeros will change the entries of ζ(B). Also, if
ζ(B) is a rearrangement of ζ(B ) then the same will be true when padding both B and B
with any given number of zeros such that both resulting boards have the same number of
columns.
We now return to considering general m. Define the m-level root vector of B = (b1 , . . . , bn )
to be ζm (B) = (a1 , . . . , an ) where

ai =





(i − 1)m − bi m − ρm (z) if i is the last index in its zone z,



(i − 1)m − bi m

otherwise.

The next result is immediate from Theorem 2.2.1.
Proposition 2.3.2. Ferrers boards B and B satisfy B ≡m B if and only if ζm (B) is a
rearrangement of ζm (B ).

16

l(B) =

B=

Figure 2.3: A board B and l(B) when m = 2

Our first order of business will be to restrict the class representative problem to considering singleton boards B = (b1 , . . . , bn ) since then the ai are simpler to compute. Indeed,
the argument in the last paragraph of Section 2.2 shows that in this case

ai = (i − 1)m − bi

for all i. To describe a singleton board in each equivalence class, let Qp denote the set
of squares in the pth level of the tiling Q of the first quadrant and, for any board B =
(b1 , . . . , bn ), let lp = |B ∩ Qp |. For example, if m = 2 and B = (1, 3, 3) as shown on the left
in Figure 2.3, then l1 = 5, l2 = 2, and li = 0 for i ≥ 3. For any Ferrers board B, if t is
the largest index with lt = 0 then we let l(B) = (lt , lt−1 , . . . , l1 ). We call this function the
l-operator on boards. The board on the right in Figure 2.3 shows l(1, 3, 3) = (2, 5).
Lemma 2.3.3. For any m and any Ferrers board B = (b1 , . . . , bn ) the sequence l(B) =
(lt , . . . , l1 ) is a partition, the Ferrers board l(B) is singleton, and B ≡m l(B).
Proof. To see that l(B) is a partition first note that, for any p > 1, the set of columns of
B ∩ Qp is a subset of the columns of B ∩ Qp−1 . Furthermore, for each of the former columns

17

we have m squares of that column in B ∩ Qp−1 . It follows that lp (B) ≤ lp−1 (B) as desired.
To show that l(B) is singleton, it suffices to show that if lp is not a multiple of m then
lp m < lp−1 m . Let c be the number of columns of B ∩ Qp which contain m squares and
d be the number of columns containing fewer than m squares. By assumption d > 0. Since
these c + d columns of B ∩ Qp−1 must all contain m cells we have lp < (c + d)m ≤ lp−1 .
Taking floors finishes this part of the proof.
To prove rook equivalence, pick any L = {p1 > · · · > pk } ⊆ {1, . . . , t}. It suffices to
show that the number of ways to place rooks on the levels of B indexed by L is the same as
the number of ways to place rooks in the columns of l(B) indexed by L. For the former, if
one places the rooks level by level from top to bottom then, since each rook in a higher level
rules out m squares in each level below it, we obtain a count of

lp1 (lp2 − m)(lp3 − 2m) . . . (lpk − (k − 1)m).

Now consider placing the rooks in l(B) column by column from left to right. Since l(B) is singleton, each rook placed eliminates m squares in each column to its right from consideration.
Thus we obtain the same count as before.

It is worth noting here that this gives us an alternative form of the factorization from
Theorem 2.2.1.
Theorem 2.3.4. If B = (b1 , . . . , bn ) is any Ferrers board where t is the largest index with
lt = 0 and N is any integer greater than or equal to both n and t, then
N

N

rk,m (B)x ↓N −k,m =
k=0

(x + lt+1−i − (i − 1)m)
i=1

18

Proof. We know that l(B) is a singleton board by Lemma 2.3.3. To facilitate comparing their
m-level rook polynomials, pad both B and l(B) on the left with columns of height 0 until
both have N columns. This will not alter the singleton property of l(B), so by Theorem 1.1.3,
we know that the product side is the factorization of the m-level rook polynomial of l(B).
Furthermore, since we know B ≡m l(B) from Lemma 2.3.3, we know
N

N

rk,m (B)x ↓N −k,m =
k=0

rk,m (l(B))x ↓N −k,m ,
k=0

which completes the proof.
The possible ζm -vectors of singleton boards are easy to characterize.
Proposition 2.3.5. Consider a vector ζ = (a1 , . . . , an ) where a1 = 0. Let B = (b1 , . . . , bn )
where we define bi = (i − 1)m − ai for all i. We have that ζ = ζm (B) where B is a singleton
board if and only if the following conditions are satisfied:
(i) ai+1 ≤ ai + m for i ≥ 1, and
(ii) if neither of ai+1 , ai are multiples of m then ai+1 m ≤ ai m .
Proof. We claim that (i) and the fact that a1 = 0 are equivalent to B being a weakly
increasing sequence of nonnegative integers. Since a1 = 0 we have b1 = −a1 = 0 which is
nonnegative. And for i ≥ 1

bi+1 − bi = (im − ai+1 ) − ((i − 1)m − ai ) = m + ai − ai+1 .

(2.3.1)

So (i) is equivalent to B being weakly increasing. A similar argument shows that (ii) is
equivalent to the singleton condition.
19

We are finally in a position to give distinguished representatives for the m-level equivalence classes. A Ferrers board B = (b1 , . . . , bn ) is called m-increasing if b1 > 0 and
bi+1 ≥ bi + m for i ≥ 1. Note that a 1-increasing board is strictly increasing in the sense of
Theorem 2.3.1. Also note that, although most properties of Ferrers boards are not affected
by padding with columns of length zero, the m-increasing condition will be destroyed.
Theorem 2.3.6. Every Ferrers board is m-level rook equivalent to a unique m-increasing
board.
Proof. Clearly any m-increasing board is a singleton board. So, by Lemma 2.3.3, it suffices
to show that any singleton board B is m-rook equivalent to a unique m-increasing board. An
example of the construction of this board is given after this proof to illustrate the technique.
Let N = |B| + 1 and pad B with columns of zeros so as to write B = (b1 , . . . , bN ). By the
choice of N , any board B which is m-equivalent to B can be written as B = (b1 , . . . , bN )
and b1 = b1 = 0. Letting ζm (B) = (a1 , . . . , aN ) and ζm (B ) = (a1 , . . . , aN ), the choice of N
also ensures that a1 = a1 = 0 and ai , ai ≥ 0 for all i.
We claim that a singleton board B = (b1 , . . . , bn ) will be m-increasing, after discarding
any columns of height 0, if and only ζm (B ) = (a1 , . . . , an ) is weakly decreasing. Indeed,
this follows directly from (2.3.1).
We first show existence. By the previous paragraph, we wish to rearrange ζm (B) in such
a way that the portion of the rearrangement corresponding to nonzero entries of the board
is weakly decreasing. And the portion of the rearrangement corresponding to zero entries of
the board must be of the form 0, m, 2m, . . . , cm for some c. So choose cm to be the largest
multiple of m in ζ = ζm (B). We claim that the elements 0, m, . . . , (c − 1)m also occur in
ζ. By definition, b1 = 0 so this multiple of m occurs as does cm by assumption. Suppose,
20

towards a contradiction, that jm does not occur where 0 < j < c. Then the definition of jm
and condition (i) of Proposition 2.3.5 implies there must be an index i such that we have
the inequalities (j − 1)m < ai < jm < ai+1 < (j + 1)m. But now ai m < ai+1 m which
contradicts condition (ii) of the same lemma.
We now define ζ = (a1 , . . . , aN ) where

(a1 , a2 , a3 , . . . , ac+1 ) = (0, m, 2m, . . . , cm)

and (ac+2 , ac+3 , . . . , aN ) is the rest of ζ arranged in weakly decreasing order. Since a1 = 0,
we can show that ζ corresponds to an m-increasing board by checking conditions (i) and
(ii) of Proposition 2.3.5. Condition (i) is clearly true for i ≤ c. For i = c, one can show, by
using a proof as in the previous paragraph and the choice of cm as the largest multiple of m
in ζ, that ac+2 < (c + 1)m. So (i) also holds in this case. And for i > c the fact that the
sequence is weakly decreasing makes (i) a triviality. The same reasoning as for (i) shows that
(ii) must also hold. Thus, defining B = (b1 , . . . , bN ) where bi = (i − 1)m − ai for all i results
in a singleton board. Furthermore, by construction, b1 = · · · = bc+1 = 0 and (bc+2 , . . . , bN )
is m-increasing. Hence removing the zeros from B leaves the desired m-increasing board.
To show uniqueness, suppose ζ = (a1 , . . . , aN ) is a rearrangement of ζ corresponding
to a padded m-increasing board. Then ζ must start with 0, m, . . . , cm for some c and be
weakly decreasing thereafter by equation (2.3.1). Without loss of generality, we can assume
ac+2 = (c + 1)m, since if the two are equal we can just add ac+2 to the initial run of
multiples of m. So ζ will be the rearrangement of ζ constructed in the existence proof as
long as cm is the largest multiple of m in ζ. But if cm is not the largest multiple of m in ζ
then (ac+2 , . . . , aN ) must contain an element greater than or equal to (c + 1)m. And since
21

this portion of ζ is weakly decreasing, this forces ac+2 > (c + 1)m since equality was ruled
out earlier. But then ac+1 = cm and ac+2 do not satisfy condition (i) of Proposition 2.3.5,
contradicting the fact that ζ corresponds to a singleton board. This finishes the proof of
uniqueness and of the theorem.

To illustrate the construction in the previous proof, consider m = 2 and the singleton
board B = (1, 2, 2, 3). Now N = 1 + 2 + 2 + 3 = 8 and we pad B with zeros to length
8 + 1 = 9, obtaining B = (0, 0, 0, 0, 0, 1, 2, 2, 3). Thus ζ = ζ2 (B) = (0, 2, 4, 6, 8, 9, 10, 12, 13).
The largest multiple of 2 in ζ is 12, so we rearrange ζ to begin with the multiples of 2 up
through 12 and then decrease. The result is ζ = (0, 2, 4, 6, 8, 10, 12, 13, 9) with associated
board B = (0, 0, 0, 0, 0, 0, 0, 1, 7). Removing the initial zeros, we get the 2-increasing board
(1, 7) which is easily seen to be 2-level rook equivalent to B.

2.4

Enumeration of singleton boards

Goldman, Joichi, and White [GJW75] used their factorization theorem to give a simple
formula for the size of a given rook equivalence class. The basic idea is to count, for any
board B, the number of rearrangements of ζ1 (B) which correspond to a Ferrers board. To
state their result, given any finite vector ν of nonnegative integers, we let n(ν) = (n0 , n1 , . . . )
be defined by
ni = the number of copies of i in ν.
So ni (ν) = 0 if i < 0 or i is sufficiently large.
Theorem 2.4.1 ([GJW75]). Let B = (b1 , . . . , bN ) be a Ferrers board where N = |B| + 1,
and suppose n(ζ1 (B)) = (n0 , n1 , . . . ). The number of Ferrers boards in the equivalence class
22

of B is

i≥1

ni + ni−1 − 1
.
ni

Because the entries of ζm (B) are more complicated for m ≥ 2, we will not be able to
count all boards in an m-level equivalence class. But we can at least enumerate the singleton
boards. The formula will be in terms of multinomial coefficients.
Theorem 2.4.2. Let B = (b1 , . . . , bN ) be a singleton board where N = |B| + 1, and suppose n(ζm (B)) = (n0 , n1 , . . . ). Then the number of singleton boards which are m-level rook
equivalent to B is

i≥0

nim + nim+1 + · · · + nim+m − 1
.
nim − 1, nim+1 , nim+2 , . . . , nim+m

Proof. By the choice of N we have that ζ = ζm (B) begins with a zero and has all entries
nonnegative. So it suffices to compute the number of rearrangements of ζ beginning with 0
and satisfying conditions (i) and (ii) of Proposition 2.3.5. Let d be the maximum entry of ζ.
If d = 0 then the result is easy to verify, so assume d > 0. Let cm be the largest nonnegative
multiple of m with cm < d. Note that cm exists since d > 0 and also that, by the argument
given in the proof of Theorem 2.3.6, ncm > 0.
Consider the vector ζ = (a1 , . . . , an ) obtained from ζ by removing all entries which are
larger than cm. We claim that ζ = ζm (B ) for some singleton board B . As usual, we
use Propostion 2.3.5. Certainly a1 = a1 = 0 since none of the zeros were removed from ζ.
Suppose, towards a contradiction, that condition (i) is false in that aj+1 > aj + m for some
j. Let ai be the element of ζ corresponding to aj . But since we removed the largest elements
of ζ we have
ai+1 ≥ aj+1 > aj + m = ai + m

23

which is impossible. A similar contradiction demonstrates (ii), and our claim is proved.
Now, by induction, it suffices to show that the number of rearrangements of ζ which
come from a given ζ by inserting elements larger than cm is

ncm + ncm+1 + · · · + ncm+m − 1
.
ncm − 1, ncm+1 , ncm+2 , . . . , ncm+m
Consider elements ai , ai+1 in ζ. First note that if ai comes from ζ and ai+1 > cm then we
must have ai = cm. If this were not the case then, since ai < cm < ai+1 , to make condition
(i) true neither ai nor ai+1 would be multiplies of m. But by the same pair of inequalities
we would have ai+1 m ≥ cm > ai m which contradicts condition (ii). Thus we can insert
elements greater than cm only after copies of cm itself. This argument is analogous to that
given in the proof of Theorem 2.3.6. In addition, any ai+1 with cm < ai+1 ≤ cm + m can
come after ai = cm as it is easily verified that we always have conditions (i) and, vacuously,
(ii) for such ai+1 .
We also claim that the elements larger than cm can be arranged in any order with
respect to each other. To see this, suppose cm < ai , ai+1 ≤ cm + m. Condition (i) is
immediate because of the given bounds. And if neither is a multiple of m then we have
cm < ai , ai+1 < cm + m which implies condition (ii).
Finally, if ai > cm and ai+1 comes from ζ then ai+1 < ai and conditions (i) and (ii) are
trivial. So an element greater than cm can be followed by any element of ζ .
We now enumerate the number of ζ coming from ζ using the structural properties from
the previous three paragraphs. There are ncm copies of cm and ncm+1 +ncm+1 +· · ·+ncm+m
elements to be inserted after these copies where the space after a copy can be used multiple
times. And any element of ζ can follow the inserted elements. So the total number of choices

24

R

R

R

R

R

Figure 2.4: A file placement

for this step is the binomial coefficient

ncm + ncm+1 + · · · + ncm+m − 1
.
ncm+1 + ncm+2 + · · · + ncm+m
Now we need to arrange the elements greater than cm among themselves. This can be done
arbitrarily, so the number of choices is

ncm+1 + ncm+2 + · · · + ncm+m
.
ncm+1 , ncm+2 , . . . , ncm+m
Multiplying the two displayed expressions and canceling (ncm+1 + ncm+2 + · · · + ncm+m )!
gives the desired result.

Note that the result just proved does indeed generalize Theorem 2.4.1. This is because
when m = 1, every board is a singleton board. And the products clearly conicide in this
case.

2.5

File placements

Thus far our focus has been to keep the sum side of Theorem 1.1.3 the same and modify the
product side to get equality for all Ferrers boards. Another possibility would be to keep the

25

product side the same, expand it in the m-falling factorial basis, and see if the coefficients of
the linear combination count anything. This will be our approach in the current section. An
equivalent formula in the case where m = 2, albeit in a different rook model, can be found
in a paper of Haglund and Remmel [HR01, Theorem 8].
It turns out that these coefficients count weighted file placements. A file placement on a
board B is F ⊆ B such that no two rooks (elements) of F are in the same column. However,
we permit rooks to be in the same row. Figure 2.4 displays such a placement on the Ferrers
board (2, 2, 3, 3, 3, 3).
We let
fk (B) = the number of file placements F ⊆ B with k rooks.
It is easy to count such placements. If B has bi squares in column i for 1 ≤ i ≤ n (B need not
be a Ferrers board) then fk (B) = ek (b1 , . . . , bn ) where ek is the kth elementary symmetric
function. So in order to get more interesting results, we will weight file placements.
Fix, as usual, a positive integer m. Given a board B and a file placement F ⊆ B, let t
be the largest index of a row in B and consider y1 , . . . , yt where yj is the number of rooks
of F in row j. Define the m-weight of F to be

wtm F = 1 ↓y1 ,m 1 ↓y2 ,m . . . 1 ↓yt ,m .

In the example of Figure 2.4 with m = 3 we have

wtm F = 1 ↓3,3 ·1 ↓0,3 ·1 ↓2,3 = (1)(−2)(−5) · (1) · (1)(−2) = −20.

Note that if F is actually a rook placement then wtm F = 1 because 1 ↓0,m = 1 ↓1,m = 1 for
26

any m.
Given a board, B, we define the associated m-weighted file placement numbers to be

fk,m (B) =

wtm F
F

where the sum is over all file placements F ⊆ B with k rooks. These are the coefficients
which we seek.
Theorem 2.5.1 (m-weight Factorization Theorem). For any Ferrers board B = (b1 , . . . , bn )
n

n

(x + bi − (i − 1)m).

fk,m (B)x ↓n−k,m =

(2.5.1)

i=1

k=0

Proof. In the manner to which we have become accustomed, we consider the board Bx
obtained by attaching an x × n rectangle R to B where x is a nonnegative multiple of m.
Consider mixed placements F ⊆ Bx which are file placements when restricted to B, but
satisfy the m-level condition when restricted to R. We will compute S =

F

wtm F where

the sum is over the mixed placements F on Bx with n rooks.
We first recover the sum side of equation (2.5.1). The mixed placements with k rooks
on B will contribute fk,m (B) to S from these rooks. And x ↓n−k,m will be the contribution
from the n − k rooks on R since any rook placement has m-weight equal to one as noted
previously. So
wtm F k

fk,m (B)x ↓n−k,m =

(2.5.2)

Fk

where the sum is over all mixed placements F k ⊆ Bx having k rooks in B. Now summing
over k gives us the desired equality.
To obtain the product, let B and Bx be B and Bx with their nth columns removed,
27

respectively. By induction on n, it suffices to prove that
n

n−1

fk,m (B)x ↓n−k,m = (x + bn − (n − 1)m)
k=0

fk,m (B )x ↓n−k−1,m .

(2.5.3)

k=0

Comparing equations (2.5.2) and (2.5.3), we see it suffices to show that, for any mixed
placement F ⊆ Bx ,
(x + bn − (n − 1)m) wtm F =

wtm F

(2.5.4)

F

where the sum is over all mixed placements F ⊆ Bx whose restriction to Bx is F . To this
end, let y0 be the number of rooks in F which are in R. Also let yj , 1 ≤ j ≤ bn , be the
number of rooks in the jth row of F ∩ B . Since every column of F has a rook, we have

y0 + y1 + · · · + ybn = n − 1.

(2.5.5)

We now consider two cases depending on whether the rook in column n of F lies in B or
in R. If it lies in R then, by the m-level condition, there are x − y0 m places for the rook.
Since these placements are in rows not occupied by rooks of F , each of them contributes
a factor of 1 to the weight for a total change in weight of x − y0 m from this case. Now
suppose that the rook lies in B, say in the jth row. Then in passing from F to F , the
weight is changed from 1 ↓yj ,m to 1 ↓yj +1,m . This means that the weight is multiplied by
1 − yj m when placing a rook in row j of B. Adding together all the contributions and using
equation (2.5.5) gives
bn

x − y0 m +

(1 − yj m) = x + bn − (n − 1)m.
j=1

28

This completes the proof of equation (2.5.4) and of the theorem.
We note that Theorem 2.5.1 is another generalization of the Factorization Theorem.
Indeed, when m = 1, then any file placement having a row with y ≥ 2 rooks will have a
factor of 1 ↓y,1 = 0. And any rook placement will have a weight of 1. Thus fk,1 (B) = rk,1 (B).

2.6

Weight equivalence classes

Given m, define two boards B, B to be m-weight file equivalent, written B ≈m B , if
fk,m (B) = fk,m (B ) for all k ≥ 0. Our goal in this section is to find distinguished representatives for the m-weight file equivalence classes. Interestingly, our result will be dual to the
one for m-level rook equivalence in the sense that the inequalities will be reversed. In order
to define the representatives, we will have to assume that all our boards start with at least
one zero. So for this section we will write our Ferrers boards in the form B = (b0 , b1 , . . . , bn )
where b0 = 0.
We can use Theorem 2.5.1 to test m-weight file equivalence. The m-weight root vector
of a Ferrers board B = (b0 , b1 , . . . , bn ) is

ωm (B) = (−b0 , m − b1 , 2m − b2 , . . . , nm − bn ).

From the m-weight Factorization Theorem we immediately get the following.
Proposition 2.6.1. Ferrers boards B and B satisfy B ≈m B if and only if ωm (B) is a
rearrangement of ωm (B ).
We will also need a characterization of the vectors which can be m-weight root vectors.
The proof of the next result is similar to that of Proposition 2.3.5 and so is omitted.
29

Proposition 2.6.2. Consider a vector ω = (a0 , a1 , . . . , an ). Let B = (b0 , b1 , . . . , bn ) where
we define bi = im − ai for all i. We have that ω = ωm (B) where B is a Ferrers board if and
only if the following conditions are satisfied:
(i) a0 = 0, and
(ii) ai+1 ≤ ai + m for i ≥ 0.
Now define a Ferrers board B = (b0 , b1 , . . . , bn ) to be m-restricted if bi+1 ≤ bi + m for all
i ≥ 0. We now show that the m-weight file equivalence class of any Ferrers board contains a
unique m-restricted board. An example of the construction of this board follows the proof.
Theorem 2.6.3. Every Ferrers board B = (b0 , . . . , bn ) is m-weight file equivalent to a unique
m-restricted board.
Proof. Similarly to the proof of Theorem 2.3.6, we rewrite B = (b0 , . . . , bN ) where N = |B|.
This assures us that any equivalent board B = (b0 , . . . , bN ) has ωm (B ) which is nonnegative
and starts with zero. Also, using equation (2.3.1), we see that B is m-restricted if and only
if ω(B ) is weakly increasing. So consider ω = (a0 , . . . , aN ) which is the unique weakly
increasing rearrangement of ω = ωm (B) = (a0 , . . . , aN ). It suffices to show that ω =
ωm (B ) for some board B . So we just need to check the two conditions of Proposition 2.6.2.
Condition (i) follows from the choice of N and the fact that ω is nonnegative. For condition
(ii), assume, towards a contradiction, that there is an index i such that ai+1 > ai + m. Let
aj be the element of ω which was rearranged to become ai+1 . Then aj = ai+1 > 0 and so
there must be an element ak with k < j and ak < aj . Let k be the largest such index. By
the choice of k and the fact that ω satisfies (ii), we must have ak ≥ aj − m. Thus

ai < ai+1 − m = aj − m ≤ ak < aj = ai+1 .
30

But then when rearranging ω in weakly increasing order, ak should have been placed between
ai and ai+1 , a contradiction.
By way of illustration, suppose that we take m = 2 and B = (1, 5). This gives N = |B| =
6 and ω = ω2 (B) = (0, 2, 4, 6, 8, 10, 12) − (0, 0, 0, 0, 0, 1, 5) = (0, 2, 4, 6, 8, 9, 7). The weakly
increasing rearrangement of ω is ω = (0, 2, 4, 6, 7, 8, 9) and so B = (0, 2, 4, 6, 8, 10, 12) −
(0, 2, 4, 6, 7, 8, 9) = (0, 0, 0, 0, 1, 2, 3).
There is a close relationship between the m-increasing boards introduced in Section 2.3
and m-restricted boards. This is easy to see if m = 1. In this case, board B is 1-increasing
if and only if its transpose B t (obtained by interchanging rows and columns) is 1-restricted.
Indeed, a Ferrers board is 1-increasing if and only if the northwestern boundary of B contains
no horizontal line segment of length at least 2. And a board is 1-restricted if and only if this
boundary contains no vertical line segment of length at least 2. Note also that when m = 1,
the l-operator of Section 2.3 satisfies l(B) = B t . In generalizing these ideas to all m, it is
the l-operator which is key as the next result shows.
Proposition 2.6.4. The l-operator has the following properties.
(i) If B is m-restricted then l(B) is m-increasing.
(ii) If B is m-increasing then l(B) is m-restricted.
(iii) If B is a singleton board then l2 (B) = B, so l is an involution on singleton boards.
Proof. (i) Let B = (b1 , . . . , bn ) be m-restricted and l(B) = (lt , . . . , l1 ). Keeping in mind
that the subscripts in l(B) are decreasing, we wish to show that lp ≥ lp+1 + m. Let Bi
be the set of cells in column i and let ci = |Bi ∩ Qp | and di = |Bi ∩ Qp+1 | for all i. Now
lp − lp+1 =

i (ci

− di ) and ci − di ≥ 0 for all i. Since B is m-restricted, there is an index
31

k such that Bk has its highest cell in Qp . Let k be the largest such index. Using the fact
that B is m-restricted again forces Bk+1 to have its highest cell in Qp+1 . Thus, using the
m-restricted condition a third time,

lp −lp+1 ≥ (ck −dk )+(ck+1 −dk+1 ) = (bk −(p−1)m)−0+m−(bk+1 −pm) = bk −bk+1 +2m ≥ m.

which is what we wished to prove
(ii) This is similar to (i), finding an upper bound for lp − lp+1 using the fact that, for an
m-increasing board, there is at most one Bk with its highest square in Qp for each p. Details
are left to the reader.
(iii) Induct on |B|. Given B, let B be the board obtained by removing its first level.
Since B is singleton so is B and thus, by induction, l2 (B ) = B . If l(B) = (lt , . . . , l1 ) then
the definition of the l-operator shows that l(B ) = (lt , . . . , l2 ) and l1 = |B ∩ Q1 |. Applying
l to l(B) we see that the column for l1 in l(B) adds m to every column of l2 (B ). Hence
every column of l2 (B) which contains cells in Qp for p ≥ 2 agrees with the corresponding
column in B. Also, again by definition of l, those columns of l2 (B) which lie wholly in Q1
are obtained from the column for l1 in l(B) by breaking it into columns of length m and a
column of length ρm (l1 ). Since this is also the unique way to complete l2 (B) so that it is a
singleton board, it must be that l2 (B) = B as desired.

We now return to considering m-level rook equivalence classes as in Section 2.3. Using
the proposition just proved, we obtain a second distinguished representative in each m-level
rook equivalence class.
Corollary 2.6.5. Every Ferrers board is m-level rook equivalent to a unique m-restricted

32

singleton board.
Proof. By Theorem 2.3.6, we know that each class has a representative B which is mincreasing and so also a singleton board. Applying the previous proposition and Lemma 2.3.3,
we see that l(B) is an m-restricted singleton board in the class. If there is a second such board
B = l(B) then, by Proposition 2.6.4 again, l(B ) and l2 (B) = B will be distinct m-increasing
singleton boards in the class, contradicting the uniqueness part of Theorem 2.3.6.

2.7

Weight equivalence class sizes

In this section we will generalize Theorem 2.4.1 to m-weight equivalence classes.
Theorem 2.7.1. Let B = (b0 , . . . , bN ) be a Ferrers board where N = |B|, and suppose
n(ωm (B)) = (n0 , n1 , . . . ). The number of Ferrers boards in the m-weight equivalence class
of B is

i≥1

ni + ni−1 + · · · + ni−m − 1
.
ni

Proof. We use Proposition 2.6.1 and count the number of rearrangements of ω = ω(B)
which correspond to a Ferrers board. Let d be the maximum value of an entry of ω. Our
assumptions imply that d is nonnegative and all entries of ω are between between 0 and
d inclusive. Consider ω which is obtained from ωm (B) by removing all values equal to d.
Using Proposition 2.6.2, it is easy to see that ω = ωm (B ) for some Ferrers board B . By
induction, it suffices to show that the number of rearrangements of ω which come from a
given ω is
nd + nd−1 + · · · + nd−m − 1
.
nd

33

(2.7.1)

By condition (ii) in the proposition just cited, we can insert d after any element of ω which
is at least d − m. So the number of places for insertion is nd−m + · · · + nd−1 . Since we
need to insert nd copies of d and more than one copy can go in a given place, the number of
choices is given by (2.7.1).

34

Chapter 3
Bijections on m-level rook placements

3.1

Introduction

The material in this chapter is a result of a collaboration with Nicholas Loehr, Jeffrey
Remmel, and Bruce Sagan, and will appear in a forthcoming paper.
The purpose of this chapter is to generalize the bijection of Foata and Sch¨
utzenberger and
those of Loehr and Remmel to m-level rook placements. The remainder of this section gives
the background terminology necessary to begin this task. In Section 3.2 we generalize the
bijection used by Foata and Sch¨
utzenberger. Although this bijection is the composition of
many intermediary bijections, and is therefore not direct, it does provide an explicit bijection
between m-level rook placements on arbitrary m-level rook equivalent Ferrers boards. We will
need this bijection again in Section 3.4. In Section 3.3 we generalize the construction of Loehr
and Remmel. In this case the bijection can only be specified for singleton boards, a subset of
all Ferrers boards. However, the construction leads to an explicit calculation of the m-level
rook numbers for such boards using elementary symmetric functions and Stirling numbers
of the second kind. In Section 3.4, we generalize a second bijection of Loehr and Remmel,
and in doing so prove that any two m-level rook equivalent Ferrers boards have the same hit
numbers. The last two bijections involve the Garsia-Milne Involution Principle [GM81].
Recall that we say that the ith column of B terminates in level p if p is the largest integer
such that the ith column has non-empty intersection with Qp , which provides a character35

7
6

R

5
2
4

R

6

B=
7

5

3

1

4

2

3

1

R

4

2

3

1

6

4

2

5

3

1

R
BS =

R
7

4

4

3

3

2

2

1

1

R
l(BS ) =

Figure 3.1: On the left, a placement of two 2-level rooks on B. In the middle, the corresponding placement from Lemma 3.2.3 of two 2-level rooks on singleton board BS . On the
right, the placement on l(BS ) from Lemma 3.2.5.

ization of singleton boards, specifically, for any given level, a singleton board contains at
most one column that terminates in that level and has a height that is not a multiple of m.
The Ferrers board on the left in Figure 3.1 is not a singleton board, as two different columns
terminate in the second level without having 2 cells in that level, while the Ferrers boards
in the middle and on the right are singleton boards.

3.2
3.2.1

Rook equivalence and bijections
Reduction to singleton boards

In order to produce bijections between m-level rook placements on Ferrers boards, it is
convenient to restrict our attention to singleton boards. In order to do this we prove the
following two lemmas. First we show that for every Ferrers board there is a unique singleton
board which has the same number of cells at each level. Then we prove that there is a
bijection between the rook placements on a Ferrers board and those on the singleton board
guaranteed in the first lemma. These lemmas together imply that every Ferrers board is

36

m-level rook equivalent to a singleton board and that there is an explicit bijection between
the corresponding rook placements.
Lemma 3.2.1. Given a Ferrers board B, there exists a unique singleton board BS which has
the same number of cells at each level as B.
Proof. Let B have lp cells in the pth level. In order for BS to be a singleton board with
lp cells in the pth level, the cells of the pth level must be arranged uniquely as follows. If
lp = cm + r with 0 ≤ r < m, then level p of BS must have one column with r cells followed
on the right by c columns with a full m cells in the level. This is because a singleton board
may have at most one column which intersects a given level non-trivially in fewer than m
cells. Thus BS must be unique if it exists.
In order to show that BS exists, we shall construct it. Arrange each level as specified
above and line up the furthest right column in each level to create the furthest right column
of BS . This yields a Ferrers board because every column which has any cells in the pth level
of B must have a full m cells in the (p − 1)st level of B. Thus the total number of columns in
the pth level of BS will be less than or equal to the number of columns in the (p − 1)st level
of BS containing m cells at that level. Hence a singleton board BS exists and is unique.
Ignoring the rook placement, Figure 3.1 shows a board B and its corresponding board
BS . Since we know that an arbitrary Ferrers board B has the same number of cells at each
level as a unique singleton board BS , we wish to provide an explicit bijection between rook
placements on the two boards. In order to do so we require the following numbering on a
Ferrers board.
Definition 3.2.2. A level numbering of board B assigns a number to each cell of B in the
following way. Proceeding level by level in B, number the cells in the level by numbering each
37

column from bottom to top, starting with the rightmost column and working left. In each
level begin the numbering with 1.
Figure 3.1 presents two examples of this numbering, on the left and middle boards, and
also illustrates the bijection of the next lemma.
Lemma 3.2.3. Given a Ferrers board B, there is an explicit bijection between m-level rook
placements of k rooks on B and m-level rook placements of k rooks on BS , where BS is as
constructed in Lemma 3.2.1.
Proof. Give both B and BS a level numbering as shown in Figure 3.1. Since both boards
have the same number of cells in each level, corresponding levels will each be numbered
with the same set of numbers. Given any m-level rook placement on B, place rooks on BS
initially so that each rook occupies the same numbered cell in the same level as it does in
B. This may not provide an m-level rook placement on BS since two rooks could end up in
the same column, so we will modify it as follows.
Notice that if a rook in column i and level p of B is not in the same cell in BS , then column
i must be to the left of a column of B that intersects Qp in less than m cells. Furthermore,
if the rook ends up in column i in BS , then all columns in the interval [i, i ] have a full m
rooks in levels below p in B. Thus, if any of the rooks that move create a column with two
or more rooks, there will be exactly two rooks in the column and the upper rook will have
moved while the lower rook remained stationary. To rectify the situation, whenever a rook
is moved from column i in b to column i in BS , move all other rooks in columns (i, i ] one
column to the left, preserving their row. This is possible since these columns must contain
m cells in the lower level of both B and BS in order for the upper rook to have been in that
column in B. Rearranging the rooks at each level in this fashion provides a function from
38

m-level rook placements on B to m-level rook placements on BS . Figure 3.1 illustrates this
map on a rook placement, including moving a lower rook one column to the left.
To see that this is a bijection, use the level numbering to produce a set of rooks on B
from those on BS . All the rooks will return to their initial positions once the appropriate
right shift is applied. Similarly one can show that applying the map first to BS and then
to B is the identity. Thus we have a bijection between m-level rook placements on B and
m-level rook placements on BS .
Lemma 3.2.1 and Lemma 3.2.3 guarantee that every Ferrers board is m-level rook equivalent to a singleton board. Additionally, there is an explicit bijection between m-level rook
placements on the two boards. This permits us to restrict our attention to singleton boards
henceforth.

3.2.2

The l-operator

Transposition of boards plays a central role in the Foata-Sch¨
utzenberger construction of
bijections between rook-equivalent Ferrers boards when m = 1. We will use the l-operator,
defined in Section 2.3 of the previous chapter, as a generalization of this operation for
arbitrary m.
Definition 3.2.4. Given a Ferrers board B the l-operator applied to B is defined as follows.
If t is the largest index of a non-empty level of B and the number of cells in the pth level of
B is lp , then
l(B) = (lt , lt−1 , . . . , l1 ).
Figure 3.1 contains an example board BS as well as l(BS ). The fact that l(B) is a
Ferrers board was shown in Lemma 2.3.3 and is analogous to an argument in the proof of
39

Lemma 3.2.1. In particular, if B is a Ferrers board then its pth level must fit above its
(p − 1)st level which implies
lp m ≤ lp−1 m ,
with strict inequality if lp ≡ 0 mod m. It follows that l(B) is a weakly increasing sequence
and so l(B) is a Ferrers board and, because of the strict inequality for non-multiples of m,
a singleton board.
To see that the l-operator is a generalization of transposition, note that if m = 1 then
the levels of B are individual rows and these become the columns of l(B). Furthermore,
when restricted to the set of singleton boards the l-operator is an involution. This is shown
in Proposition 2.6.4 of the previous chapter. Thus, the l-operator is a surjection from the set
of Ferrers boards onto the set of singleton boards with B = l(l(B)) when B is singleton. We
now provide a bijection between m-level rook placements on B and m-level rook placements
on l(B) to generalize the well-known bijection for transposition.
Lemma 3.2.5. Given a singleton board B and a non-negative integer k, there is an explicit
bijection between m-level rook placements of k rooks on B and m-level rook placements of k
rooks on l(B).
Proof. Give B a level numbering, then number the columns of l(B) from bottom to top
beginning with the number 1 in each column. Note that in this case the numbering of a level
of B will consist of the same set of numbers as the numbering of the corresponding column
of l(B). Assume that B has t non-empty levels. For a given m-level rook placement of k
rooks on B, place rooks on l(B) in the following way. If a rook was in the cell numbered n
of level p in B, then place a rook in the cell numbered n in column t − p + 1 in l(B). See
Figure 3.1 for an example of this map for a 2-level placement.
40

We must show that this gives a valid m-level rook placement on l(B). If two rooks end up
in the same column of l(B) they must have originated in the same level of B, contradicting
having an m-level rook placement on B. Similarly, if two rooks end up in the same level of
l(B), then they must have originated in the same column of B, since B is a singleton board.
The inverse of this map acts as follows. If a rook is in the cell numbered a of column
t − p + 1 in l(B) then it is placed in the cell numbered a in level p of B. The proof that this
gives a rook placement is similar to the one in the previous paragraph and so is omitted.
Note that Lemma 3.2.3 and Lemma 3.2.5 combine to provide an explicit bijection between
m-level rook placements on any Ferrers board B and on its m-transpose, l(B) = l(BS ).

3.2.3

The local l-operator

For any set S, let #S be the cardinality of S. Given a column i and a level p define the
m-arm length of column i, level p by

armlm (i, p) = #{ci,j ∈ B | ci,j is strictly above level p}.

In Figure 3.2 the cells counted by the 2-arm length of column 4, level 1 have a dashed line
through them. (Reflecting our boards to put them in English notation will result in the
arm being the usual set of squares when m = 1.) We let armlm (i, p) = ∞ if the number of
columns in B is less than i for reasons detailed in Lemma 3.2.7.
Similarly, define the m-leg length of column i, level p to be

leglm (i, p) = #{ci ,j ∈ B | ci ,j is in level p and i < i}.

41

Figure 3.2: The dashed line goes through the cells counted by the 2-arm length of the fourth
column and first level, and the shaded cells are counted by the corresponding 2-leg length.

The cells counted by the 2-leg length of column 4, level 1 are shaded in Figure 3.2. As
before, this is equivalent to the usual notion of leg length in the m = 1 case. We also let
leglm (i, 0) = ∞ by convention.
Since the l operation generalizes the transposition of a Ferrers board, one would expect
that some sort of local l operation would be the appropriate generalization of the local
transposition introduced by Foata and Sch¨
utzenberger. This is indeed the case, and we
define the local l operation as follows.
Given a Ferrers board B with non-empty intersection of the ith column and pth level, let
Bi,p denote the subboard of B consisting of all cells in or above the pth level and in or to
the left of the ith column: see Figures 3.3 and 3.4 for examples. Note that if B is a singleton
board, then Bi,p is also, because the set of rows in level p of Bi,p will be the same as the
set of rows in level p + p − 1 of B. If B is a Ferrers board then the local l operation at (i, p)
is the result of applying the l operator to the subboard Bi,p and leaving the rest of B fixed.
We will denote the resulting board by li,p (B).
As defined above li,p (B) may not be a Ferrers board, let alone a singleton board. We
now develop a pair of conditions to determine if li,p (B) will be a singleton board.
Definition 3.2.6. The operation li,p is permissible for a singleton board B if

armlm (i, p) ≤ leglm (i, p − 1) m

and
42

leglm (i, p) ≤ armlm (i + 1, p) m .

l3,2 (B) =

B=

Figure 3.3: On the left, B3,2 is shaded within B = (1, 4, 4, 5). Notice that l3,2 is not
permissible for B since armlm (4, 2) m < leglm (3, 2), which means l3,2 (B) will not be a
singleton board. On the right the shaded cells in l(B3,2 ) illustrate this; in this case l3,2 (B)
is not even a Ferrers board.

See Figure 3.3 for an example of a local l-operation not permissible for the given board,
and Figure 3.4 for a local l-operation which is permissible.
Lemma 3.2.7. Let a singleton Ferrers board B have a non-empty intersection of the ith
column and pth level. Then li,p is permissible for B if and only if li,p (B) is a singleton
Ferrers board.
Proof. If column i, level p in B contains fewer than m cells, then li,p (B) = B since B is
singleton, and there is nothing to prove. Henceforth, assume that column i, level p in B
contains m cells. We know that B, Bi,p , and l(Bi,p ) are all singleton Ferrers boards. It
follows that li,p (B) will be a singleton Ferrers board if and only if these three conditions
hold for the board li,p (B).
(a) The lowest row of level p is weakly shorter than the highest row of level p − 1;
(b) column i is weakly lower than column i + 1; and
(c) if columns i and i + 1 terminate at the same level, then the height of column i + 1 is
a multiple of m.
Condition (c) is needed to ensure li,p (B) will be singleton.
43

To determine when these conditions hold, first note that applying li,p to B exchanges
armlm (i, p) and leglm (i, p). Because B is singleton, the top row of level p − 1 in B (and in
li,p (B)) extends left of column i by leglm (i, p − 1) m cells. On the other hand, the new
bottom row of level p in li,p (B) extends left of column i by armlm (i, p) m cells. Thus,
condition (a) holds iff
armlm (i, p) m ≤ leglm (i, p − 1) m .
Since both sides are multiples of m, this inequality is equivalent to armlm (i, p) ≤ leglm (i, p−
1) m , which is the first condition in the definition of permissibility.
Now consider the heights of columns i and i + 1 in li,p (B). Both column i and column
i + 1 have a full m cells in level p. So, in both B and li,p (B), column i + 1 has height pm +
armlm (i + 1, p). On the other hand, the new column i in li,p (B) has height pm + leglm (i, p).
So condition (b) will hold iff

leglm (i, p) ≤ armlm (i + 1, p).

To deal with condition (c), consider two cases. First suppose that armlm (i + 1, p) is a
multiple of m. Then condition (c) must hold, and here condition (b) will hold iff leglm (i, p) ≤
armlm (i + 1, p) m . Now suppose that armlm (i + 1, p) is not a multiple of m. Given that
condition (b) holds, the new board li,p (B) will be singleton iff the strengthened inequality
leglm (i, p) ≤ armlm (i + 1, p) m is true. Thus, this last inequality is equivalent to the truth
of (b) and (c) in all cases.

44

3.2.4

The Local l-operation on an m-level rook placement

Since there is a bijection between rook placements on B and l(B) when B is singleton, it
stands to reason that it would generalize to a bijection between rook placements on B and
li,p (B). The following lemma makes this precise.
Lemma 3.2.8. For a singleton board B, suppose li,p is permissible for B. Then there
is an explicit bijection between m-level rook placements of k rooks on B and m-level rook
placements of k rooks on li,p (B).
Proof. Use the bijection induced by the l operation in Lemma 3.2.5 on the subboard transposed by li,p , not moving the rooks on the part of board B which is fixed. However, this
may cause a rook in the transposed subboard to occupy the same column or level of li,p (B)
as one of the rooks which was fixed. We deal with this possibility next.
In order for two rooks to end up in the same column, there must be rooks placed on B
beneath Bi,p , so we can assume p > 1 without losing generality. Consider the set of columns
of B which do not contain rooks in Bi,p , and the set of columns of li,p (B) which do not
contain rooks in l(Bi,p ). By our assumption on p, these two sets have the same cardinality
and so we can put a canonical bijection on them by pairing the leftmost columns in each set
and moving to the right. If there is a rook lower than level p in one of these columns of B,
use this bijection on the columns to move it to the cell in the same row of the corresponding
column of li,p (B). After doing so, there must be at most one rook in each column of li,p (B).
For example, in Figure 3.4 the rook in c3,2 is in the second column from the left of B which
does not contain a rook in B4,2 . Thus it moves to column 2, which is the second column
from the left of l4,2 (B) that does not contain a rook in l(B4,2 ).
If two rooks end up in the same level we treat them similarly where we can assume,
45

without loss of generality, that the i-th column is not the rightmost column of B. There is
a canonical bijection between the levels of B which do not contain rooks in Bi,p and those
of li,p (B) that do not contain rooks in l(Bi,p ). Adjust the levels of all rooks to the right of
column i using this bijection, fixing the column of the rook that moves. Furthermore, fix
the height of the rook that moves within the level, that is, if the rook was in cell cx,y , move
the rook to cell cx,y in the appropriate level with y ≡ y (mod m). Note that since B is
a singleton board, columns to the right of column i will contain a full m cells at any level
which contained a rook in the subboard Bi,p .
To see that this is a bijection, we construct its inverse. Recall that the l operator is an
involution on singleton boards. Thus, since Bi,p is a singleton subboard, li,p (li,p (B)) = B.
Similarly, applying the bijection from Lemma 3.2.5 and then its inverse returns the original
placement of rooks on Bi,p . All that remains to check is that any rooks moved outside of
Bi,p return to their original cells. Since the rooks return to their original placement on Bi,p ,
the set of columns that gain a rook in Bi,p after the first application of l will be the same set
as those that lose a rook in Bi,p after the second application of l. Thus the bijection on the
columns induced by the first application of l will be the inverse of the bijection induced by the
second application, and any rook required to move in li,p (B) will move back in li,p (li,p (B)).
A similar argument holds for levels, noting that since li,p (B) is singleton ensures that any
level that gains a rook in Bi,p after applying li,p contains a full m cells in every column to
the right of column i. Thus this yields a bijection between rook placements on B and li,p (B).
Figure 3.4 illustrates this bijection.

46

6
5

R

4
1

3
2

R
B=

6

4

2

5

3

1

R

1

l4,2 (B) =

R

R

1

R

Figure 3.4: On the left, B4,2 is shaded. Here l4,2 is permissible for B and is shown on the
right.

3.2.5

Bijections with m-increasing boards

Foata and Sch¨
utzenberger proved there is a unique Ferrers board in every rook equivalence
class whose column lengths are strictly increasing and used this board as a target for their
bijections. To accomplish the same thing, we need the the analogous concepts for m-level
rook placements, developed in the previous chapter.
Definition 3.2.9. A Ferrers board B = (b1 , b2 , . . . , bn ) is called m-increasing if bi+1 ≥ bi +m
for all 1 ≤ i ≤ n − 1.
Recall that when m = 1 strictly increasing and m-increasing are equivalent.
Theorem 3.2.10 (2.3.6). Every Ferrers board is m-level rook equivalent to a unique mincreasing board.
We are now almost ready to prove the main result of this section, Theorem 3.2.12 below.
However, to do so we must put an order on Ferrers boards. Once we have established
this order, we will be able to give an explicit bijection between m-level rook placements
on an arbitrary Ferrers board B and on an m-level rook equivalent Ferrers board which
47

is greater than B in this order, if such a board exists. Additionally, the set of all Ferrers
boards equivalent to B will have a unique maximum element under this order, namely the
m-increasing board guaranteed by [BLRS14].
To define this order, if B = (b1 , . . . , bn ) then consider the reversal of B, B r = (bn , . . . , b1 ).
Now let B < B if B r is lexicographically smaller than (B )r . It is important to note that
when applying Lemma 3.2.3 we will always have

BS ≥ B

(3.2.1)

since in BS all the cells in each level are as far to the right as possible.
Lemma 3.2.11. Given a singleton board B containing a column i and a level p with the
property that
armlm (i, p) < leglm (i, p),

(3.2.2)

there is a singleton board B = li ,p (B) with i ≥ i and B > B.
Furthermore, if B is not m-increasing then a column i and level p satisfying equation 3.2.2
must exist.
Proof. To prove the first statement, let i ≥ i be the maximum index such that armlm (i , p) <
leglm (i , p). Note that by our convention on armlm , we must have that i is at most the
number of columns of B. We claim that it suffices to show that li ,p is permissible for B.
This is because if li ,p is permissible for B, then the resulting board B must satisfy B > B.
Indeed, li ,p (B) increases the length of column i by leglm (i , p) − armlm (i , p), which must
be greater than 0, and column i is the rightmost column affected by li ,p (B). Thus B > B.
If li ,p is not permissible for B, then we claim that we have armlm (i +1, p) < leglm (i +1, p)
48

which will contradict the maximality of i and complete this part of the proof. Note that

armlm (i , p) < leglm (i , p) ≤ leglm (i , p − 1) m .

So li ,p not being permissible for B implies that armlm (i +1, p) m < leglm (i , p) = leglm (i +
1, p) − m since B is singleton. This implies the desired contradiction that armlm (i + 1, p) <
leglm (i + 1, p).
To prove the second statement of the theorem, note that if B is not m-increasing there
are two possible cases, either there are two adjacent columns i − 1, i of B which terminate
at the same level, or column i − 1 terminates in level p and B has exactly r1 cells in the pth
level of column i − 1 and exactly r2 cells in the (p + 1)st level of column i where r1 > r2 > 0.
Case 1: Let columns i − 1 and i both terminate at level p. Then armlm (i, p) = 0, by the
assumption that column i terminates at level p, but leglm (i, p) ≥ 1 since column i − 1 also
terminates at the pth level. Thus armlm (i, p) < leglm (i, p) as desired.
Case 2: By assumption armlm (i, p) = r2 < r1 ≤ leglm (i, p) which completes the proof.

We are now in a position to prove our main theorem of this section.
Theorem 3.2.12. Given any two m-level rook equivalent Ferrers boards, there is an explicit
bijection between m-level rook placements of k rooks on them.

Proof. Given any Ferrers board B, let Bm be the unique m-increasing board in the m-level
rook equivalence class of B guaranteed by Theorem 3.2.10. It suffices to show that there is
an explicit bijection between the m-level rook placements of k rooks on B and those on Bm .
This is trivial if B = Bm so assume B = Bm . By Lemma 3.2.3, we have an explicit bijection
49

R
R

R
R
R

(a)

R
R

(b)

(c)

R
R

R
(d)

R

R

Figure 3.5: (a) A 2-level rook placement on a Ferrers board. (b) The placement on the
singleton board obtained after applying Lemma 3.2.3. (c) The placement obtained after
applying Lemma 3.2.8 using l3,1 . (d) The placement obtained on a 2-increasing board after
applying Lemma 3.2.8 again using l3,3 .

between the placements on B and those on BS where BS ≥ B by equation 3.2.1. If BS = Bm
then we are done. Otherwise, apply the local l operator defined in Lemma 3.2.11 which will
give B = li,p (BS ) with B > BS and, by Lemma 3.2.8, another explicit bijection between
rook placements. We now repeat this process if necessary. Since there are only finitely many
boards in an m-level rook equivalence class and the lexicographic order increases with every
application of Lemma 3.2.8, we must eventually terminate. And, by Lemma 3.2.11 again,
termination must occur at Bm . Composing all the bijections finishes the proof.
See Figure 3.5 for a short example of this process.

3.3

A second bijection on m-level rook placements

Our next two main results will require the Garsia-Milne Involution Principle. The first will
use the Involution Principle to construct another explicit bijection between two arbitrary
m-level rook placements of k rooks on m-level rook equivalent singleton boards.
Theorem 3.3.1 (Garsia-Milne Involution Principle [GM81]). Consider a triple (S, T, I)
where S is a signed set, I is a sign-reversing involution on S, and the set T of fixed points of

50

I is required to be a subset of the positive part S + of S. Let (S , T , I ) be defined similarly.
Then, given an explicit sign-preserving bijection f from S to S , one can construct an explicit
bijection between T and T .
The way that Garsia and Milne define the explicit bijection is as follows. Start with
an element t ∈ T ⊆ S + . If f (t) ∈ T , then apply (f ◦ I ◦ f −1 ◦ I ) to f (t). This takes
f (t) ∈ S + to S − , then to S − , then S + , and finally back to S + . Iterating this procedure
must ultimately yield an element of T which is considered the image of t under the desired
bijection.

3.3.1

A Garsia-Milne bijection for rook placements

We will use the Involution Principle to construct a bijection between m-level rook placements
on two m-level rook equivalent singleton boards. We must first construct a signed set and a
sign-reversing involution so that the m-level rook placements are the fixed points under the
involution. We do this as follows.
Given two Ferrers boards, B and B , we shall say B fits inside B if juxtaposing the two
boards with their lower right cells in the same position makes the cells of B a subset of the
cells of B . Figure 3.6 shows that the thick bordered B = (2, 3) fits inside B = (0, 2, 4, 6).
The shading and rook placement may be ignored for now. Let ∆n,m denote the triangular
Ferrers board (0, m, 2m, . . . , (n − 1)m). Given a singleton board B, fix N large enough that
B fits inside ∆N,m . If B has fewer than N columns, expand B on the left with columns
of height zero so B = (b0 , b1 , . . . , bN −1 ) has the same number of columns as ∆N,m . Fix a
non-negative integer k with k < N and let the integer i vary over 0 ≤ i ≤ k. Then S will
consist of all configurations C constructed as follows. Take ∆N,m with B fitting inside and

51

W

C=

R

W

I(C) =

∈S

R

W

W
f (C) =

R

W
f (I(C)) =

R
R

W R

Figure 3.6: On the top left, an element in S with sign −1. On the top right, the image
under I which has sign +1. Beneath each board is its image under f .

place white rooks W in i cells of ∆N,m that are outside of B so that no two white rooks
are in the same column. Next, place k − i black rooks R forming an m-level rook placement
on the subboard ∆N −i,m which is located in the columns of ∆N,m which do not contain a
white rook. We will call this the inset ∆N −i,m board. Note that the columns of the inset
∆N −i,m may not be contiguous.
See the top left board of Figure 3.6 for an example of such an object C where m = 2.
The singleton board B = (0, 0, 2, 3) fits inside ∆4,2 . Here k = 3 < 4 and there is i = 1 white
rook on the board ∆4,2 \ B and k − i = 2 black rooks on the board ∆3,2 which is represented
by the grey shaded cells inside ∆4,2 . The rooks on ∆3,2 form a 2-level rook placement, but
there is both a black rook and a white rook in the second level of ∆4,2 .
Note that each column of ∆N,m may contain at most one white rook or black rook. On
the other hand, a level of ∆N,m will contain at most one black rook, but may contain any
number of white rooks. Further, define the sign of such a placement to be (−1)i . The sign
52

of the placement on the top left in Figure 3.6 is −1.
To define I on an element C ∈ S, if all rooks of C are in B, and therefore black, then C
is a fixed point. Otherwise, examine the columns of C from left to right until coming to a
column with a rook outside of B. If that column contains a black rook, change the rook to
a white rook, increase i by one, and move every black rook above and to the right of the cell
containing the new white rook down m cells. If that column contains a white rook, change
it to a black rook, decrease i by one, and move every black rook to the right and at the same
level or higher as the new rook up m cells. The placement on the top right in Figure 3.6
illustrates what happens to the board on the left under I. Similarly, I takes the placement
on the right to the placement on the left.
We must show that I(C) will be an element of S. Clearly each column has at most one
rook. When a black rook becomes white, it is clear that there will be at most one black
rook per level on the resulting board, as there was at most one black rook per level on the
original board. If a black rook is added, each level will have at most one black rook since
when a black rook is added all black rooks at its level or above to the right of the new rook
move up one level. Furthermore, there can be no black rooks at the same level or higher to
the left of the new black rook if we change a white rook to a black rook. This is because
the new black rook was a white rook which, by definition, was above board B. Since B is
a singleton board, no columns of B to the left of the white rook in question will terminate
in the level of the white rook. Thus if there were a black rook at the same level or higher
to the left, it too would be outside of board B, which contradicts the white rook being the
leftmost rook outside of board B.
When a black rook is added, the black rooks must be placed on a board ∆N −i+1,m where
the column in which the new black rook is placed is added to the columns in the initial inset
53

∆N −i,m . Since there are no white rooks to the left of the new black rook, there will be no
omitted columns to the left of the column containing the new black rook, thus all cells of
that column will be in the inset ∆N −i+1,m and the new rook must be inside ∆N −i+1,m .
This means that all the columns to the right of the new black rook that do not contain a
white rook will contain m more squares as the inset ∆N −i+1,m than they did as the inset
∆N −i,m . Thus moving black rooks to the right of the new black rook up m cells will keep
them within the new ∆N −i+1,m . Similarly, changing a black rook to a white rook will
decrease the number of cells in the columns of ∆N −i−1,m to the right of the new white rook
by m, but all black rooks to the right of the new white rook and at a higher level than it are
moved down m cells, so they will be in ∆N −i−1,m because they were in ∆N −i,m originally.
Finally, if there are any black rooks below the level of the new white rook but to its right,
they will remain in ∆N −i−1,m because the first column in ∆N −i−1,m to the right of the new
white rook must go up to at least the level of the new white rook since previously it was a
black rook contained in ∆N −i,m .
By construction, I is an involution. The fixed set of I will be denoted T . It is the set of
all configurations which only have rooks on the subboard B and, by definition, these rooks
must be black. As such, T is equal to the set of m-level rook placements of k rooks on B.
Furthermore, if a board is not in T , then I either increases or decreases the number of white
rooks on the board by one. Either way I will change the sign of the board. And if a board
is in T , then it has positive sign.
Given a singleton board B , define N , S , T , and I similarly for B contained in ∆N ,m .
Without a loss of generality, assume N = N . Let B = (b0 , b1 , . . . , bN −1 ). If B and B are
m-level rook equivalent singleton boards we can use I and I to construct an explicit bijection
between m-level rook placements of k rooks on B and m-level rook placements of k rooks on
54

B . We do this by constructing a sign-preserving bijection between S and S . We will need
the following characterization of when two singleton boards are m-level rook equivalent.
The root vector of B is

ζm = (−b0 , m − b1 , . . . , (N − 1)m − bN −1 ).

The following result of Briggs and Remmel determines when two singleton boards are m-level
rook equivalent simply by considering their root vectors.

Theorem 3.3.2 (Briggs-Remmel Theorem 2 [BR06]). Two singleton boards are m-level rook
equivalent if and only if they have the same root vector up to rearrangement for a sufficiently
large N .
We are now ready to apply the Garsia-Milne Involution Principle.
Theorem 3.3.3. Let B and B be m-level rook equivalent singleton boards. Then there
exists an explicit Garsia-Milne bijection between m-level rook placements of k rooks on B
and m-level rook placements of k rooks on B .
Proof. By Theorem 3.3.1 and what we have already established, it suffices to find a signpreserving bijection f : S → S . We construct f as follows.
For clarity of notation, let B be placed in ∆N,m and B be placed in a copy ∆N,m of
∆N,m . Notice that the kth element of the root vector of B, km − bk , is the number of cells
in the kth column of ∆N,m which lie outside of board B. Since B and B are m-level rook
equivalent, the root vector for B is a rearrangement of the root vector for B. Therefore
there is a length-preserving bijection between the columns of the set difference ∆N,m \B and
the columns of ∆N,m \ B which takes the leftmost column of a given length in ∆N,m \ B
55

R
R
R
1 2 3 4 5 6

5
4
3
2
1

Figure 3.7: The placement corresponding to partition {1, 4}, {2, 3, 5}, {6}.

to the leftmost column with that length in ∆N,m \ B and so forth. This bijection induces a
bijection on the placement of the white rooks. If a white rook appears in the jth cell above
B, place a white rook in the jth cell above B in the associated column.
Once all the white rooks are placed, create a copy of ∆N −i,m inside of ∆N,m using the
columns which do not contain a white rook. Place the black rooks on the board with relation
to the ∆N −i,m subboard exactly as they are placed on the original board with relation to the
original ∆N −i,m subboard. Each placement on the bottom of Figure 3.6 is the image under
f of the corresponding placement on the top where B = (0, 0, 2, 3) and B = (0, 0, 1, 4).
Notice that in the top left board, the white rook is at the top of the second column from the
left which has two cells above B. In the board on the bottom left the white rook is still at
the top of the second column from the left which has two cells above B .
Under this map the white rooks must be placed inside ∆N,m but outside B , and the
black rooks are placed inside ∆N −i,m , so f maps S to S . Further this map preserves the
number of white rooks placed on the board, so it is sign preserving. Therefore we may
conclude from the Involution Principle that there is an explicit bijection between m-level
rook placements of k rooks on B and m-level rook placements of k rooks on B .
To obtain a consequence of this construction, we will need some background on symmetric
functions and Stirling numbers. For d ≤ n both non-negative integers, let ed (x1 , x2 , . . . , xn )

56

denote the elementary symmetric function of degree d in n variables, that is,

ed (x1 , x2 , . . . , xn ) =
1≤i1 <i2 <···<id ≤n

xi1 xi2 . . . xid .

(3.3.1)

Let S(n, d) denote the Stirling numbers of the second kind. Recall that S(n, d) can be defined
as the number of ways to partition a set of n elements into d subsets called blocks.
Further, note that S(n, d) counts the number of rook placements of n − d rooks on ∆n,1 .
To see this, number the rows of ∆n,1 from 1 to n − 1 from bottom to top. Then number the
columns, including the zero column, from 1 to n left to right. Given a partition of {1, . . . , n}
into d blocks, order the elements of each block increasingly. Now, if i and j are adjacent
within a block then place a rook in row i column j. See Figure 3.7 for the rook placement
corresponding to {1, 4}, {2, 3, 5}, {6}. Thus the number of m-level rook placements of n − d
rooks on ∆n,m is mn−d S(n, d). The extra mn−d counts the number of ways of choosing a
placement for each of the (n − d) rooks in the m cells of a level.
It is interesting to note that the construction of I yields the following theorem giving an
explicit calculation for the m-level rook numbers of a singleton Ferrers board B.
Theorem 3.3.4. For any singleton board B = (b0 , b1 , . . . , bN −1 ) fitting inside ∆N,m ,
k

(−1)i mk−i S(N − i, N − k)ei (−b0 , m − b1 , . . . , (N − 1)m − bN −1 ).

rk,m (B) =
i=0

Proof. Since the fixed points of the involution I are counted by rk,m (B), it suffices to show
that the sum counts all elements of the set S by sign. First note that the number of ways of
putting i white rooks in i different columns of ∆N,m outside of B is ei (−b0 , m − b1 , . . . , (N −
1)m − bN −1 ). Furthermore the number of m-level rook placements of k − i rooks on ∆N −i,m
57

is mk−i S(N − i, N − k). Putting these two counts together with the appropriate sign gives
the sum as desired.
Note that this theorem implies the backward direction of Theorem 3.3.2.

3.4

A bijection for hit numbers

We will now use the Involution Principle to prove that two boards that are m level rook
equivalent have the same hit numbers. We begin with some definitions. As usual, let m be
a fixed positive integer. We will sometimes suppress m in the following notation to limit the
number of subscripts.
Let B be a Ferrers board and let the integer N be sufficiently large so that B fits inside
a rectangular board, SqN,m with N columns and mN rows. If α is a generator of the cyclic
group Cm , then

Cm SN = {(αs1 , αs2 , . . . , αsN ; σ) | 1 ≤ si ≤ m for each i and σ ∈ SN }.

We associate with ω ∈ Cm SN a placement on SqN,m by placing a rook in level N + 1 − p
and column i if σ(i) = p. Furthermore, the rook in column i will be j cells from the bottom
of the level if si = j. See Figure 3.8 for an example with m = 2 and N = 3, where the
placement corresponds to (α1 , α2 , α1 ; (1, 3, 2)), and σ is in cycle notation. Let R(ω) denote
the rook placement corresponding to ω. Define the kth hit set of B to be

Hk,N (B) = {R(ω) | ω ∈ Cm SN and #(R(ω) ∩ B) = k}.

58

(3.4.1)

R
s∈S=

R
R

Figure 3.8: The placement on Sq3,2 corresponding to (α1 , α2 , α1 ; (1, 3, 2)).

Also define the kth hit number of B to be

hk,N = #Hk,N .

(3.4.2)

In order to show that two m-level rook equivalent Ferrers boards have the same hit
numbers, we use Garsia and Milne’s result again. To do so, we must construct a signed set
and a sign reversing involution which has a set counted by hk,N as its fixed set. We do this
as follows.
Let N be large enough that B fits inside SqN,m , fix non-negative integers i and k with
i ≤ k ≤ N . Then the set S will consist of all configurations C constructed as follows. Place
k black, m-level rooks R on the board B. Furthermore, circle i of the rooks. Finally, consider
the N −k columns and N −k levels which do not contain a black rook as a subboard of shape
SqN −k,m , as in the previous section, we will call this the inset SqN −k,m board. Place N − k
white m-level rooks, denoted by W , on the inset SqN −k,m . Notice that, ignoring the color
of the rooks, this is an m-level rook placement of N rooks on SqN,m . Thus it corresponds
to some element of Cm SN . Let the sign of a configuration be (−1)i . See Figure 3.9 for
two examples of such configurations. Here m = 2 and B = (1, 2, 4) is placed fitting in Sq3,2 .
On the left, there are no circled black rooks so i = 0 and the white rooks are placed on the
shaded inset Sq2,2 . On the right there is one circled black rook so i = 1 and the white rooks
59

W

W

s=

I(s) =

R
W

R
R

Figure 3.9: On the left, an element in S with sign +1. On the right, the image under I
which has sign −1.

are on a shaded inset Sq1,2 .
In order to produce a sign-reversing involution I on such configurations C, we do the
following. If B contains neither a white rook nor a circled black rook, then C is fixed by I.
Otherwise, examine the columns of B from left to right until the first white rook or circled
black rook is found. If the first rook found is white, exchange it for a circled black rook
and increase i by 1. If the first rook found is a circled black rook, exchange it for a white
rook and decrease i by 1. See Figure 3.9 again for an illustration. It is easy to see that I is
an involution and reverses signs in its 2-cycles. Also note that fixed points have no circled
black rooks, so i = 0 and the sign of the configuration is +1. Furthermore, for a fixed point
there are no white rooks placed on B, so the m-level placement intersects B in exactly k
black rooks. Thus the fixed points are exactly the elements of Hk,N (B) if one just ignores
the colors of the rooks.
The reader will find an example illustrating the next proof in Figure 3.10. This example
uses the boards from the example of Theorem 3.2.12 found in Figure 3.5.
Theorem 3.4.1. Let B and B be two m-level rook equivalent Ferrers boards and N be large
enough that B and B both fit inside SqN,m . Then for any non-negative integer k ≤ N , there
is an explicit bijection between Hk,N (B) and Hk,N (B ).
Proof. As in the proof of Theorem 3.3.3, we use the Garsia-Milne Involution Principle.
60

W

W

W

R
R
W
R
R

R

R

Figure 3.10: On the left, a 2-level placement of white rooks, black rooks, and circled black
rooks on (1, 1, 1, 3, 6) fit inside Sq5,2 . On the right, the corresponding placement under the
construction in Theorem 3.4.1.

Construct S for B placed inside SqN,m and S for B placed inside SqN,m . From what we
have already done, all the remains is to construct the sign-preserving bijection f : S → S .
Consider an element C ∈ S. The black rooks, circled and uncircled, form an m-level
rook placement of k rooks on B. Map this to an m-level rook placement of k rooks on B
using the explicit bijection guaranteed by Theorem 3.2.12. Furthermore, add circles to the
rooks on B in such a way so that if the rth rook from the right on board B is circled, the
rth rook from the right on board B is circled. Finally, place the white rooks on SqN,m by
considering the inset SqN −k,m of columns and levels containing no black rooks. Place the
white rooks on this inset board in the exact same arrangement as they are in on the inset
SqN −k,m of SqN,m . This is easily seen to be a bijection and so the proof is complete.
The next corollary follows immediately from the previous theorem.
Corollary 3.4.2. Let B and B be two m-level rook equivalent Ferrers boards and N be large
enough such that B and B both fit inside SqN,m . Then for any non-negative integer k ≤ N ,
hk,N (B) = hk,N (B ).

61

BIBLIOGRAPHY

62

BIBLIOGRAPHY
[ABR01] Ron M. Adin, Francesco Brenti, and Yuval Roichman. Descent numbers and major
indices for the hyperoctahedral group. Adv. in Appl. Math., 27(2-3):210–224,
2001. Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia,
PA, 2000).
[BLRS14] Kenneth Barrese, Nicholas Loehr, Jeffrey Remmel, and Bruce E. Sagan. m-Level
rook placements. J. Combin. Theory Ser. A, 124:130–165, 2014.
[BR06]

Karen S. Briggs and Jeffrey B. Remmel. m-rook numbers and a generalization of
a formula of Frobenius to Cm Sn . J. Combin. Theory Ser. A, 113(6):1138–1171,
2006.

[FS70]

D. Foata and M. P. Sch¨
utzenberger. On the rook polynomials of Ferrers relations. In Combinatorial theory and its applications, II (Proc. Colloq., Balatonf¨
ured, 1969), pages 413–436. North-Holland, Amsterdam, 1970.

[GJW75] Jay R. Goldman, J. T. Joichi, and Dennis E. White. Rook theory. I. Rook equivalence of Ferrers boards. Proc. Amer. Math. Soc., 52:485–492, 1975.
[GM81]

A. M. Garsia and S. C. Milne. Method for constructing bijections for classical
partition identities. Proc. Nat. Acad. Sci. U.S.A., 78(4, part 1):2026–2028, 1981.

[HR01]

J. Haglund and J.B. Remmel. Rook theory for perfect matchings. Adv. in Appl.
Math., 27(2-3):438–481, 2001. Special issue in honor of Dominique Foata’s 65th
birthday (Philadelphia, PA, 2000).

[KR46]

Irving Kaplansky and John Riordan. The problem of the rooks and its applications. Duke Math. J., 13:259–268, 1946.

[LR09]

Nicholas A. Loehr and Jeffrey B. Remmel. Rook-by-rook rook theory: bijective
proofs of rook and hit equivalences. Adv. in Appl. Math., 42(4):483–503, 2009.

63