Rook decomposition of the Partition function

N. Guru Sharan · 2025

Read Rook decomposition of the Partition function by N. Guru Sharan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20260.txt.

Introduction

Guru Sharan studies a classic counting problem in number theory through the lens of chess rooks, in a 2025 paper. The partition function counts the ways a whole number can be split into sums of smaller ones. Rook numbers count how many rooks can sit on a board with no two attacking. Sharan links the two by way of the board shapes that come from each split.

For each split, the largest rook count ties to a triangle shape inside its diagram. That link gives a fresh way to break the counting function into parts. The author works out exact formulas for splits whose triangle has size three, four, or five. Those formulas show repeating patterns under division by any whole number. They also show how the counts grow for the smaller triangle sizes, and a new rook-based version of a known recurrence for the function.

Catalog record

CREATORN. Guru Sharan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-20260

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Rook decomposition of the Partition function Thanks: 2020 Mathematics Subject Classification. Primary 05A17; Secondary 11P83, 11N56. Keywords and phrases. Decomposition, rook numbers, Durfee triangle, partition function, asymptotics, periodicity. N. Guru Sharan 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 3 , 4 4 and 5 5 . We obtain their exact formula and further use it to show the periodicity modulo p p for any p ∈ ℕ p\in\mathbb{N} and p ≥ 2 p\geq 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 \lambda_{1},\lambda_{2},\lambda_{3},\ldots,\lambda_{r} such that \sum_{i=0}^{r}\lambda_{i}=n . The individual \lambda_{i} ’s are themselves called the parts of the partition. For a fixed n\in\mathbb{N} , let \mathscr{P}(n) be the set of all unrestricted partitions of n and let P(n) be the cardinality of \mathscr{P}(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 \pi\in\mathscr{P}(n) , we associate a graphical representation called Ferrers diagram , defined by the set of nodes with integer co-ordinates (i,j) such that if \pi=(\lambda_{1},\lambda_{2},\lambda_{3},...\ ,\lambda_{r}) , then the node (i,j) is placed if and only if -r+1\leq i\leq 0 and 0\leq j\leq\lambda_{|i|+1}-1 . For example, the Ferrers diagram of (5,3,2,1) is given in Figure 1(a) . 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 1(a) . Durfee triangle of size n contains \sum_{\ell=1}^{n}\ell=\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 of them are 1,3,6,10,15,.... Formally, a board B is any finite sub-lattice of \mathbb{Z}\times\mathbb{Z} , containing squares of unit dimension. In the context of this study, we define a Ferrers board associated to a partition \pi to be the board that is obtained by replacing each node in the Ferrers diagram of \pi by a unit square. From the defintion of Ferrers Diagram, it is clear that Ferrers Board is a finite connected sub–lattice of \mathbb{Z}\times\mathbb{Z} . See Figure 1(b) 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 rooks 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_{\textup{B}}(x) to be the generating function of the rook numbers R(r,B) , i.e. \displaystyle f_{\textup{B}}(x):=\sum_{n=1}^{\infty}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_{\textup{B}}(x) a polynomial. This term was first coined by Kaplansky and Riordan [ 7 ] . The rook polynomial is well-studied. As shown in [ 11 , Chapter 7] , for a rectangular m\times n board B , it is known that \displaystyle\hskip 99.58464ptf_{\textup{B}}(x)=n!x^{n}L_{n}^{(m-n)}(-x^{-1}),\hskip 56.9055pt(m\geq n) where L_{n}^{\alpha}(x) , the generalized Laguerre polynomial , is \displaystyle L_{n}^{\alpha}(x):=\frac{1}{n!}x^{-\alpha}e^{x}\frac{d^{n}}{dx^{n}}\left(x^{n+\alpha}e^{-x}\right), as defined in [ 13 , Equation (6.23)] . The rook polynomial is nothing but a special case of the matching polynomial studied in Graph theory, which is the generating function of the number of k -edge matchings in a graph. From the theory of matching polynomial, for any fixed board B , it has been shown that the rook numbers R(n,B) are unimodal, i.e. they grow 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 [ 5 , Section 4] . The interested reader is referred to [ 4 , Chapter 2] for finer details. 2. Introduction We call it a decomposition of the partition function when P(n) can be written in terms of a finite sum of other number-theoretic functions. Various decompositions of the partition function have been studied in the literature. For instance, recently, in [ 8 ] and [ 9 ] , a decomposition of the partition function in terms of the Euler totient function and the Möbius function respectively, has been derived. In this paper, we study the highest possible rook number for a given Ferrers board (which is also the degree of the rook polynomial) and use it to get a new decomposition of the partition function in ( 2.4 ), which we call the rook decomposition . For a fixed partition \pi\in\mathscr{P}(n) , if B_{\pi} be the Ferrers board associated to \pi , let us define the max–rook number R(\pi) as follows: \displaystyle R(\pi):= \displaystyle\textup{ The maximal number of non-intersecting rooks that can be placed in }B_{\pi}. Clearly, the maximal number is unique and less than or equal to n , hence R(\pi) is well defined. One example is illustrated in Figure 1(b) . (a) Ferrers diagram (b) Ferrers board Figure 1 . The partition (5,3,2,1) of 11 has a max–rook number 4 . Then, for n\in\mathbb{N} , let us define F(n) as follows: (2.1) \displaystyle F(n):=\textup{max }\bigg\{R(\pi)\ \bigg|\ \pi\in\mathscr{P}(n)\bigg\}. For a fixed n\in\mathbb{N} , and for any \pi\in\mathscr{P}(n) , clearly R(\pi)\leq n . Hence, the maximal element in the above set exists, and F(n) is well-defined. For convention, let us define F(0):=1 . Next, for any fixed n,k\in\mathbb{N} , we define R_{k}(n) , which are the central objects of this study, by (2.2) \displaystyle R_{k}(n):=\#\bigg\{\pi\in\mathscr{P}(n)\ \bigg|\ R(\pi)=k\bigg\}. Thus, R_{k}(n) is the number of partitions of n whose associated Ferrers board has a max–rook number k . Let us denote the generating function of R_{k}(n) by \mathscr{F}_{k}(q) , i.e. (2.3) \displaystyle\mathscr{F}_{k}(q):=\sum_{n=1}^{\infty}R_{k}(n)q^{n}. As explained in Theorem 3.1 , the number of partitions with a max–rook number k is equal to number of the partitions with a Durfee triangle of size k and hence \mathscr{F}_{k}(q)

Read the complete text