A note on Diagonal sequences of integer partitions
Michael Neubauer, Harmony Vargas · 2024
Read A note on Diagonal sequences of integer partitions by Michael Neubauer, Harmony Vargas (2024) 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-2412-06856.txt.
Introduction
A partition breaks a whole number into a sum of smaller parts, and each partition can be read along its diagonal to give a second sequence of numbers. Michael Neubauer and Harmony Vargas study that diagonal reading in a 2024 note. They ask how many partitions share one diagonal sequence, and how those partitions relate to each other.
Under a classic ordering that compares partitions by their early partial sums, the sharers form a tidy ranked set. It has exactly one largest and one smallest member. The authors also give a direct formula that counts the sharers for any diagonal sequence. Short as it is, the note ties a picture-based reading of partitions to counting, a link that partition theory can build on.
Catalog record
| CREATOR | Michael Neubauer, Harmony Vargas |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-06856
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A note on Diagonal sequences of integer partitions Michael Neubauer, Harmony Vargas Abstract . Let 𝒫 ( n ) \mathcal{P}(n) be the set of partitions of the positive integer n n . For α = ( α 1 , … , α t ) ∈ 𝒫 ( n ) \alpha=(\alpha_{1},...,\alpha_{t})\in\mathcal{P}(n) define the diagonal sequence δ ( α ) = ( d k ( α ) ) k ≥ 1 \delta(\alpha)=(d_{k}(\alpha))_{k\geq 1} via d k ( α ) = | { i | 1 ≤ i ≤ k and α i + i − 1 ≥ k } | . d_{k}(\alpha)=\big\lvert\{i\,\rvert\,1\leq i\leq k\mbox{ and }\alpha_{i}+i-1\geq k\}\big\rvert. We show that the set of all partitions in 𝒫 ( n ) \mathcal{P}(n) with the same diagonal sequence is a partially ordered set under majorization with unique maximal and minimal elements and we give an explicit formula for the number of partitions with the same diagonal sequence. 2020 Mathematics Subject Classification Primary: 11P81, 11P84; Secondary: 05A17 1. Introduction Let \mathcal{P}(n) be the set of partitions of the natural number n , i.e., for \alpha=(\alpha_{1},...,\alpha_{l})\in\mathcal{P}(n) we assume \alpha_{1}\geq\alpha_{2}\geq\cdots\geq\alpha_{l}\geq 1 , \alpha_{i}\in\mathbb{N} , and \sum_{i=1}^{l}\alpha_{i}=n . Let \mathcal{P}(n,k) be the partitions of n with exactly k non-zero parts and let \mathcal{P}(n,k)^{*} be the set of conjugates of \mathcal{P}(n,k) , i.e., \mathcal{P}(n,k)^{*} is the set of all partitions of n that have largest part equal to k .. Definition For a partition \alpha=(\alpha_{1},\cdots,\alpha_{l})\in\mathcal{P}(n) define its diagonal sequence \delta(\alpha)=(d_{k})_{k\geq 1} via (1.1) d_{k}=d_{k}(\alpha)=\big\lvert\{i\,\rvert\,1\leq i\leq k\mbox{ and }\alpha_{i}+i-1\geq k\}\big\rvert. Since only finitely many d_{k} are positive we may omit writing trailing zeroes for \delta(\alpha) . Using Young diagrams we can visualize diagonal sequences in two ways. For example, the partition \alpha=(7,7,4,1,1,1)\in\mathcal{P}(21) has diagonal sequence \delta(\alpha)=(1,2,3,4,4,4,2,1). \alpha \alpha 1 1 1 1 1 1 1 2 2 2 2 2 2 1 3 3 3 3 4 4 4 a b c d e f g b c d e f g h c d e f d e f In the Young diagram on the left the numbers in the squares indicate the position of the square on the respective diagonal. In the Young diagram on the right all squares on the same diagonal are marked by the same letter. Definition Let \Delta(n)=\{\delta(\alpha)\,|\,\alpha\in\mathcal{P}(n)\} . This defines \delta as a map from \mathcal{P}(n) to \Delta(n) with \alpha\rightarrow\delta(\alpha) . The map \delta is surjective by definition and it is not injective as is easy to see. Different partitions may have the same diagonal sequence. If we move a square of the Young diagram on an upper left to lower right diagonal in such a way that we end up with another Young diagram then the two partitions will have the same diagonal sequence. E.g., the partition \beta=(8,6,2,2,2,1)\in\mathcal{P}(21) \beta \beta 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 4 4 4 a b c d e f g h b c d e f g c d e f d e f has the same diagonal sequence as the partition \alpha=(7,7,4,1,1,1) above. The h-square in row 2 of \alpha moved to the last position in row 1 of \beta while the e-square in row 5 of \alpha moved to the second position in row 4 of \beta and the f-square in row 6 of \alpha moved to the fourth square in row 4 of \beta . The reader may have noticed that there are more diagonal moves that yield different partitions with the same diagonal sequence. Theorem 4.6 in Section 4 gives and explicit expression for the number of partitions with the same diagonal sequence. The transition from \alpha to \beta moved squares up along the diagonals. In fact, the squares of the Young diagram of \beta are as high up along their respective diagonals as possible. We explore this idea in Section 3 . We can define an equivalence relation on \mathcal{P}(n) via \alpha\sim\beta if and only if \delta(\alpha)=\delta(\beta) . The equivalence class of a partition \alpha\in\mathcal{P}(n) is characterized by the invariant \delta(\alpha)=d . For d\in\Delta(n) define [\,d\,]=\delta^{-1}(d)\subseteq\mathcal{P}(n) . In particular, the partition \alpha\in\mathcal{P}(n) and its conjugate \alpha^{*} have the same diagonal sequence and hence belong to the same equivalence class, i.e., \alpha\sim\alpha^{*} and \delta(\alpha)=\delta(\alpha^{*}) . The conjugate partition is obtained by reflecting the Young diagram about the upper left to lower right diagonal which maps each upper right to lower left diagonal onto itself. Diagonal sequences were used in [ 2 ] to find graphs with maximal sums of squares of degrees and in [ 5 ] to find bipartite graphs with maximal sums of squares of degrees. In the next section we prove properties of \delta(\alpha) in preparation for the main results of Sections 3 and 4 . In Section 3 we show that [\,d\,] is a partially ordered set under majorization with unique maximal and unique minimal element. In Section 4 we give an explicit formula for the size of \delta(\alpha)=[\,d\,] . In Section 5 we list the 36 partitions in the equivalence class of \alpha=(7,7,4,1,1,1) , i.e., we list all \alpha\in\mathcal{P}(21) with \delta(\alpha)=(1,2,3,4,4,4,2,1) . 2. Properties of \delta(\alpha) We first prove that the sequence \delta(\alpha) increases from 1 to a positive integer q in increments of 1 and then continues in a non-increasing sequence. Lemma 2.1 . Let \alpha=(\alpha_{1},\cdots,\alpha_{l})\in\mathcal{P}(n) with \delta(\alpha)=(d_{k})_{k\geq 1} . (1) d_{k+1}-d_{k}\leq 1 with equality if and only if d_{j}=j for all 1\leq j\leq k+1 . (2) If d_{k}\geq d_{k+1} , then d_{k+1}\geq d_{k+2} . Proof. By definition d_{k+1}\leq d_{k}+1 . Notice that if for some 1\leq j\leq k we have \alpha_{j}+j-1<k , then \alpha_{j+1}+(j+1)-1=\alpha_{j+1}+j\leq\alpha_{j}+j<k+1. Hence if d_{j}<j , then d_{j}\geq d_{j+1} . ∎ Corollary 2.2 . For all partitions \alpha\in\mathcal{P}(n) there exist unique integers q>0 and s_{1},\cdots,s_{q}\geq 0 such that (2.1) \delta(\alpha)=\left(1,2,\cdots,q-1,q,q^{(s_{q})},(q-1)^{(s_{q-1})},\cdots,1^{(s_{1})}\right). with (2.2) \dfrac{q(q+1)}{2}+\sum_{k=1}^{q}k\,s_{k}=n. Let d=(d_{1},d_{2},\cdots,d_{L})\in\Delta(n) . We characterize two special elements [\,d\,] . The notation \overline{\alpha} and \underline{\alpha} will become clear in Section 3 . Proposition 2.3 . Let s_{1},\cdots,s_{q}\geq 0 be integers such that \frac{q(q+1)}{2}+\sum_{k=1}^{q}k\,s_{k}=n . Let \overline{\alpha}_{i}=q-i+1+\sum_{k=i}^{q}s_{k} for 1\leq i\leq q . Then (1) \overline{\alpha}=(\overline{\alpha}_{1},\cdots,\overline{\alpha}_{q})\in\mathcal{P}(n) , (2) \overline{\alpha}_{1}>\overline{\alpha}_{2}>\cdots>\overline{\alpha}_{q} , (3) \delta(\overline{\alpha})=\left(1,2,\cdots,q-1,q,q^{(s_{q})},(q-1)^{(s_{q-1})},\cdots,1^{(s_{1})}\right) , (4) s_{i}=\overline{\alpha}_{i}-\overline{\alpha}_{i+1}-1 , 1\leq i\leq q-1 , and s_{q}=\overline{\alpha}_{q}-1 . Proof. By definition \overline{\alpha}_{1}>\overline{\alpha}_{2}>\cdots>\overline{\alpha}_{q} and since \sum_{i=1}^{q}\overline{\alpha}_{i}=\sum_{i=1}^{q}(q-i)+\sum_{i=1}^{q}\,\sum_{k=i}^{q}s_{k}=\frac{q(q+1)}{2}+\sum_{k=1}^{q}k\,s_{k}=n, \overline{\alpha}=(\overline{\alpha}_{1},\cdots,\overline{\alpha}_{q}) is a partition of n , i.e., \overline{\alpha}\in\mathcal{P}(n). Next, we will show that (2.3) \delta(\overline{\alpha})=\left(1,2,\cdots,q-1,q,q^{(s_{q})},(q-1)^{(s_{q-1})},\cdots,1^{(s_{1})}\right). If 1\leq k\leq q , then \overline{\alpha}_{i}+i-1=q+\sum_{j=i}^{q}s_{j}\geq q\geq k for 1\leq i\leq k . Hence d_{k}=k for 1\leq k\leq q . If q<k\leq q+s_{q} , then \overline{\alpha_{i}}+q-1=q+\sum_{j=i}^{q}s_{j}\geq q+s_{q}\geq k\mbox{ for }1\leq i\leq q. Hence d_{k}=q for q<k\leq q+s_{q} . Similarly, if q+\sum_{j=i}^{q}s_{j}<k\leq q+\sum_{j=i-1}^{q}s_{j} , i\geq 2 , then \begin{split}\overline{\alpha}_{j}+j-1&=q+\sum_{l=j}^{q}s_{l}<k\mbox{ for }j\geq i\\ \overline{\alpha}_{j}+j-1&=q+\sum_{l=j}^{q}s_{l}\geq k\mbox{ for }j<i.\\ \end{split} Hence d_{k}=i-1 for q+\sum_{j=i}^{q}s_{j}<k\leq q+\sum_{j=i-1}^{q}s_{j} . Lastly, we show how to compute the values of s_{i} , 1\leq i\leq q , given \overline{\alpha} . Let s=(s_{1},s_{2},,\cdots,s_{q}) , v=(q,q-1,\cdots,1) and T=\begin{bmatrix}1&1&1&\cdots&1\\ 0&1&1&\cdots&1\\ 0&0&1&\cdots&1\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1\\ \end{bmatrix}. It follows that \overline{\alpha}=v+Ts and hence s=T^{-1}(\overline{\alpha}-v) . Since T^{-1}=\begin{bmatrix}1&-1&0&0&\cdots&0&0\\ 0&1&-1&0&\cdots&0&0\\ 0&0&1&-1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\ddots&\vdots&\vdots\\ \vdots&\vdots&\vdots&\vdots&\ddots&\ddots&\vdots\\ 0&0&0&0&\cdots&1&-1\\ 0&0&0&0&\cdots&0&1\end{bmatrix} we get s_{i}=\overline{\alpha}_{i}-\overline{\alpha}_{i+1}-1 for 1\leq i<q and s_{q}=\overline{\alpha}_{q}-1. ∎ There are some consequences of Proposition 2.3 that are worth pointing out. Corollary 2.4 . |\Delta(n)| is equal to the number of partitions of \mathcal{P}(n) with distinct parts which is equal to