Rook Decomposition of the Partition Function

N. Guru Sharan Department of Mathematics Indian Institute of Technology Gandhinagar Palaj, Gandhinagar, Gujarat 382355 India

                     sharanguru5@gmail.com

Abstract

The rook numbers are fairly well-studied in the literature. In this paper, we study the max-rook number of the Ferrers boards associated to integer partitions. We show its connections with the Durfee triangle of the partitions. The max-rook number gives a new decomposition of the partition function. We derive the generating functions of the partitions with the Durfee triangle of sizes 3, 4, and 5. We obtain their exact formula and further use it to show the periodicity modulo p for any p ∈ ℕ and p ≥ 2. We also establish their parity and parity bias. We give the growth asymptotics of partitions with the Durfee triangle of sizes 3 and 4. We obtain a new rook analogue of the recurrence relation of the partition function.

1 Definitions and Notations

A partition of a non-negative integer n is a non-increasing sequence of positive integers λ_{1}, λ_{2}, λ_{3}, …, λ_{r} such that ∑_{i=0}^{r} λ_{i} = n. The individual λ_{i}’s are themselves called the parts of the partition. For a fixed n ∈ ℕ, let 𝒫(n) be the set of all unrestricted partitions of n and let P (n) be the cardinality of 𝒫(n). For example, (5, 3, 2, 1) is a partition of 11, enumerated by P (11). For convention, we take the empty partition to be the only partition of zero, i.e., P (0) = 1.

For each partition π ∈ 𝒫(n), as defined in [?, Section 1.3], we associate a graphical representation called Ferrers diagram, defined by the set of nodes with integer co-ordinates (i, j) such that if π = (λ_{1}, λ_{2}, λ_{3}, …, λ_{r}), then the node (i, j) is placed if and only if −r +1 ≤ i ≤ 0 and 0 ≤ j ≤ λ_{|i|+1} − 1. One must note that the set of nodes begin with the node (0, 0) at the top left. For example, the Ferrers diagram of (5, 3, 2, 1) is given in Figure ??.

The largest square of nodes contained in the Ferrers diagram of a partition starting from the top-left node of the Ferrers diagram is called the Durfee square and its length is called the size of the Durfee square.

Similarly, let us call the largest right-angled isosceles triangle contained in the Ferrers diagram with the right-angle at the top-left node of the partition, the Durfee triangle. The number of nodes on the sides of triangle is called the size of the Durfee triangle. One such example of a Durfee square (size 2) and a Durfee triangle (size 4), of the partition (5, 3, 2, 1) is given in Figure ??. Durfee triangle of size n contains ∑_{ℓ=1}^{n} ℓ = \frac{1}{2}n(n + 1) many nodes, which is called the n^{th} triangular number, which we denote by t_{n}. The first few triangular numbers are 1, 3, 6, 10, 15, …

Formally, a board B is any finite sub-lattice of ℤ×ℤ, containing squares of unit dimension. In the context of this study, we define a Ferrers board^{1} associated to a partition π to be the board that is obtained by replacing each node in the Ferrers diagram of π by a unit square. From the defintion of Ferrers Diagram, it is clear that Ferrers Board is a finite connected sub-lattice of ℤ × ℤ. See Figure ?? for clarity.

A rook is a chess piece, which is only allowed to move horizontally or vertically on a board. Two rooks are said to be non-intersecting if they are not placed in a same row or a same column, which makes the rooks unable to capture each other in the game of chess. In the classical theory of rook numbers, the primary interest is the number of distinct placements of non-intersecting rooks on a board. The rook number R(r, B) is the distinct number of ways of placing r many non-intersecting rooks in the Ferrers board B. For any fixed board B, we define the rook polynomial f_{B}(x) to be the generating function of the rook numbers R(r, B), i.e.

f_{B}(x) := ∑_{n=1}^{∞} R(n, B)x^{n}.

For any fixed board B, R(n, B) vanishes for all large n, depending on the number of squares in the board, thus making f_{B}(x) a polynomial. This term was first coined by Kaplansky and Riordan [?]. The rook polynomial is well-studied. As shown before [?, Chapter 7], for a rectangular m × n board B, it is known that

f_{B}(x) = n!x^{n}L_{n}^{(m−n)}(−x^{−1}), (m ≥ n)

where L_{n}^{α}(x), the generalized Laguerre polynomial, is

L_{n}^{α}(x) := \frac{1}{n!}x^{−α}e^{x} \frac{d^{n}}{dx^{n}} (x^{n+α}e^{−x}) ,

as defined in [?, Equation (6.23)]. The rook polynomial can be seen as a specific case of the matching polynomial studied in Graph theory, which is the generating function of the k-edge matchings in a given graph. For any fixed board B, it has been shown that the rook numbers R(n, B) are unimodal, i.e., they initially increase to a maximal value and then decrease. This has been proved as an implication of the fact that all the zeroes of the matching polynomial are real [?, Section 4]. The interested reader is referred to [?, Chapter 2] for finer details.

1The “Ferrers board” is usually referred to as a “Young diagram” in partition theory. The primary difference in this context is that the boxes are used for the placement of non-intersecting rooks.