%% if you are submitting an initial manuscript then you should have submission as an option here %% if you are submitting a revised manuscript then you should have revision as an option here %% otherwise options taken by the article class will be accepted \documentclass[finalversion]{FPSAC2024} \articlenumber{68} %% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc %% note that the class file already loads {amsmath, amsthm, amssymb} \usepackage{tikz} %Begin our macros: \newtheorem{theorem}{Theorem}%[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{problem}{Problem} \newtheorem{question}{Question} \theoremstyle{definition} \newtheorem{example}[theorem]{Example} \newtheorem{definition}[theorem]{Definition} \newcommand{\cD}{\mathcal{D}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cT}{\mathcal{T}} \DeclareMathOperator{\Conv}{Conv} \newcommand{\bbN}{\mathbb{N}} \newcommand{\bbR}{\mathbb{R}} \newcommand{\bbY}{\mathbb{Y}} \newcommand{\TYP}{\bbY_\Delta} \newcommand\I{I} \DeclareMathOperator{\dif}{dif} \DeclareMathOperator{\wrd}{wrd} \newcommand\bigO{\mathcal{O}} \newcommand\pp{\hat{p}} \newcommand{\LL}{\mathsf{L}} %End our macros %% define your title in the usual way \title{Combinatorial properties of triangular partitions} %% define your authors in the usual way %% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details \author{Sergi Elizalde\thanks{\href{mailto:sergi.elizalde@dartmouth.edu}{sergi.elizalde@dartmouth.edu}. SE was partially supported by Simons Collaboration Grant \#929653.}\addressmark{1} \and Alejandro B. Galván\thanks{\href{mailto:alejandrobasilio7@gmail.com}{alejandrobasilio7@gmail.com}. AG was partially supported by the mobility grants of CFIS-UPC, Generalitat de Catalunya and Gobierno de Navarra.}\addressmark{2}} %% then use \addressmark to match authors to institutions here \address{\addressmark{1}Department of Mathematics, Dartmouth College, Hanover, NH, USA \\ \addressmark{2}Centre de Formació Interdisciplinària Superior (CFIS) - Universitat Politècnica de Catalunya (UPC), Barcelona, Spain } %% put the date of submission here \received{\today} %% leave this blank until submitting a revised version %\revised{} %% put your English abstract here, or comment this out if you don't have one yet %% please don't use custom commands in your abstract / resume, as these will be displayed online %% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year) \abstract{A {\em triangular partition} is a partition whose Ferrers diagram can be separated from its complement (as a subset of $\bbN^2$) by a straight line. Having their origins in number theory and computer vision, triangular partitions have been studied from a combinatorial perspective by Corteel et al.\ under the name {\em plane corner cuts}, and more recently by Bergeron and Mazin in the context of algebraic combinatorics. Here we derive new enumerative, geometric, and algorithmic properties of such partitions. We give a new characterization of triangular partitions and the cells that can be added or removed while preserving the triangular condition, and use it to describe the Möbius function of the restriction of Young's lattice to triangular partitions. We obtain a formula for the number of triangular partitions whose Young diagram fits inside a square, deriving a new proof of Lipatov's enumeration theorem for balanced words. Finally, we present an algorithm that generates all the triangular partitions of a given size, which is significantly more efficient than previous ones and allows us to compute the number of triangular partitions of size up to $10^5$.} %% put your French abstract here, or comment this out if you don't have one %\resume{} %% put your keywords here, or comment this out if you don't have them yet \keywords{triangular partition, corner cut, balanced word, Young's lattice} %, M\"obius function} %% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier %% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text %% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex %% but you can use bibtex if you want \usepackage[backend=bibtex]{biblatex} \addbibresource{triangular_partitions.bib} %% note the \printbibliography command at the end of the file which goes with these biblatex commands \begin{document} \maketitle %% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above \section{Introduction}\label{sec:intro} An integer partition is said to be triangular if its Ferrers diagram can be separated from its complement by a straight line. Triangular partitions and their higher-dimensional generalizations have been studied from several perspectives during the last five decades. They first appeared in the context of combinatorial number theory~\cite{Boshernitzan1981}, where they were called \textit{almost linear sequences}. Later, the closely related notion of \textit{digital straight lines} became relevant in the field of computer vision~\cite{Bruckstein1990}. From a combinatorial perspective, triangular partitions were first studied by Onn and Sturmfels~\cite{Onn1999}, who defined them in any dimension and called them \textit{corner cuts}. Soon after, Corteel et al.~\cite{Corteel1999} found an expression for the generating function for the number of plane corner cuts. Renewed interest in triangular partitions has recently come from algebraic combinatorics; specifically, from the study of generalizations of the {\em shuffle theorem} and, more broadly, of the ubiquitous connections between Dyck paths, parking functions, diagonal coinvariant spaces, and Macdonald polynomials. In generalizing Dyck paths to Fuss-Catalan paths, then rational Dyck paths, and then rectangular Dyck paths, a natural next step is to consider lattice paths (with unit south and east steps) that stay weakly below the line segment from $(0,s)$ to $(r,0)$, where $r$ and $s$ are any positive real numbers. These paths arise in recent work of Blasiak et al.~\cite{Blasiak2023} generalizing the shuffle theorem. Motivated by this result, Bergeron and Mazin~\cite{Bergeron2023} coined the terms \emph{triangular partitions}, \emph{triangular Dyck paths}, and \emph{triangular parking functions}, and studied some of their combinatorial and algebraic properties. %More recently, motivated by work of Blasiak et al.~\cite{Blasiak2023} generalizing the shuffle theorem for paths under a line, Bergeron and Mazin~\cite{Bergeron2023} coined the term \emph{triangular partitions} and studied some of their combinatorial properties. In this abstract we obtain further enumerative, geometric, poset-theoretic, and algorithmic properties of triangular partitions. In Section~\ref{sec:background} we give basic definitions and summarize some of the work from~\cite{Corteel1999,Bergeron2023}. In Section~\ref{sec:characterizations_triangular} we give a simple alternative characterization of triangular partitions, as those for which the convex hull of the Ferrers diagram and that of its complement (as a subset of $\bbN^2$) have an empty intersection. We also characterize which cells can be added to or removed from the Young diagram while preserving triangularity. In Section~\ref{sec:triangular_young_poset} we study the restriction of Young's lattice to triangular partitions. It was shown in~\cite{Bergeron2023} that this poset is a lattice. Here we completely describe its Möbius function, and we provide an explicit construction of the join and meet of two triangular partitions. In Section~\ref{sec:sturmian}, we introduce a new encoding of triangular partitions in terms of balanced words, and use it to implement an algorithm which computes the number of triangular partitions of each size up to $N$ in time $\bigO(N^{5/2})$. This allows us to produce the first $10^5$ terms of this sequence, compared to the $39$ terms that were known previously. In Section \ref{sec:generating-functions}, refining the approach from \cite{Corteel1999}, we obtain generating functions for triangular partitions with a given number of removable and addable cells. In Section~\ref{sec:subpartitions}, we provide a formula for the number of triangular partitions whose Young diagram fits inside a square (or equivalently, inside a staircase), which involves Euler's totient function. As a byproduct, we obtain a new combinatorial proof of a formula of Lipatov~\cite{Lipatov1982} for the number of balanced words. Due to space constraints, proofs are omitted from this extended abstract. %%%%%%%%%%% \section{Background}\label{sec:background} %%%%%%%%%%% A \emph{partition} $\lambda$ is a weakly decreasing sequence of positive integers, often called the {\em parts} of $\lambda$. We will write $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_k)$, or $\lambda=\lambda_1\lambda_2\dots\lambda_k$ when there is no confusion. We call $|\lambda|=\lambda_1+\lambda_2+\dots+\lambda_k$ the {\em size} of $\lambda$. If $|\lambda|=n$, we say that $\lambda$ is a partition of~$n$. Let $\bbN$ denote the set of positive integers. The {\em Ferrers diagram} of $\lambda$ is the set of lattice points $$\{(a,b)\in\bbN^2\;|\;1\le b \leq k,\;1\le a\leq\lambda_b\}.$$ The {\em Young diagram} of $\lambda$ is the set of unit squares (called {\em cells}) whose north-east corners are the points in the Ferrers diagram. We identify each cell with its north-east corner, so we also use the term cell to refer to points in the Ferrers diagram. In particular, we say that a cell lies above, below or on a line when the north-east corner does. We will often identify $\lambda$ with its Ferrers and Young diagrams, and use notation such as $c=(a,b)\in\lambda$. For a partition $\lambda=\lambda_1\lambda_2\dots\lambda_k$, we call $\lambda_1$ its {\em width}, and $k$ its {\em height}. Let $\sigma^k=(k,k-1,\dots ,2,1)$ denote the \emph{staircase partition} of height $k$. The {\em conjugate} of $\lambda$, obtained by reflecting its Ferrers diagram along the diagonal $y=x$, will be denoted by $\lambda'$. Identifying $\lambda$ with its Ferrers diagram, we define its \emph{complement} to be the set $\bbN^2\setminus\lambda$. \begin{definition}\label{def:triangular} A partition $\tau = \tau_1\tau_2\dots\tau_k$ is \emph{triangular} if there exist positive real numbers $r$ and $s$ such that $$ \tau_j = \left\lfloor{r - jr/s}\right\rfloor, $$ for $1\le j\le k$, and $k = \lfloor s - s/r\rfloor$. \end{definition} In other words, $\tau$ is triangular if its Ferrers diagram consists of the points in $\bbN^2$ that lie on or below the line that passes through $(0,s)$ and $(r,0)$ for some $r,s\in\bbR_{>0}$. See Figure~\ref{fig:chi} for an example. This line is called a \emph{cutting line} of $\tau$. Unlike in the definition given in \cite{Bergeron2023}, here we do not allow $\tau$ to have parts equal to $0$, hence the condition on $k$. We often use $\tau$ to denote a triangular partition. \begin{figure}[!ht] \centering \begin{tikzpicture}[scale=.6] \filldraw[color=black, fill=yellow, semithick] (0,0) -- (0,5) -- (1,5) -- (1,4) -- (3,4) -- (3,3) -- (5,3) -- (5,2) -- (6,2) -- (6,1) -- (8,1) -- (8,0) -- (0,0); \draw[->] (-.5,0)--(10.5,0); \draw[->] (0,-.5)--(0,7.5); \draw[step=1cm,gray,very thin] (0,0) grid (10,7); \draw[green, thick] (0,6.15) -- (9.9,0); \draw[very thick] (.1,6.15)--(-.1,6.15) node[left]{$s$}; \draw[very thick] (9.9,.1)--(9.9,-.1) node[below]{$r$}; \foreach \c in {(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(1,2),(2,2),(3,2),(4,2),(5,2),(6,2),(1,3),(2,3),(3,3),(4,3),(5,3),(1,4),(2,4),(3,4),(1,5)} {\filldraw[black] \c circle (2.5pt); } \begin{scope}[shift={(12,0)}] \filldraw[color=black, fill=yellow, semithick] (0,0) -- (0,5) -- (1,5) -- (1,4) -- (4,4) -- (4,3) -- (7,3) -- (7,2) -- (9,2) -- (9,1) -- (12,1) -- (12,0) -- (0,0); \draw[->] (-.5,0)--(13.5,0); \draw[->] (0,-.5)--(0,6.5); \draw[step=1cm,gray,very thin] (0,0) grid (13,6); \node at (0.83,5.5) [scale=.87]{$\min(\tau)$}; \node at (2.5,4.5) [scale=.87]{$\dif(\tau) + 1$}; \node at (5.5,3.5) [scale=.87]{$\dif(\tau) + 1$}; \node at (8,2.5) [scale=.87]{$\dif(\tau)$}; \node at (10.5,1.5) [scale=.87]{$\dif(\tau) + 1$}; \node at (2.5,3.6) {$1$}; \node at (5.5,2.6) {$1$}; \node at (8,1.6) {$0$}; \node at (10.5,0.6) {$1$}; \end{scope} \end{tikzpicture} \caption{Left: A cutting line for the triangular partition $(8,6,5,3,1)$. Right: Applying the bijection from Theorem~\ref{thm:sturmian_interpretation_2} to $\tau=(12,9,7,4,1)$ gives $\chi(\tau) = (1, 2, 1011)$.} \label{fig:chi} \end{figure} Denote by $\Delta(n)$ the set of triangular partitions of $n$, and by $\Delta=\bigcup_{n\ge0}\Delta(n)$ the set of all triangular partitions. The following two results are due to Corteel et al.~\cite{Corteel1999}. \begin{theorem}[\cite{Corteel1999}]\label{thm:GDelta} The generating function for triangular partitions can be expressed as $$G_{\Delta}(z) = \sum_{n\ge0}|\Delta(n)|z^n = \frac{1}{1 - z} + \sum_{\gcd(a, b) = 1}\sum_{\substack{0\leq j < a \\ 0\leq i < b}}\sum_{1\leq m < k}z^{N_\Delta(a,b,k,m,i,j)},$$ where \begin{align}\label{eq:NDelta} N_\Delta(a,b,k,m,i,j) & = (k - 1)\left(\frac{(a + 1)(b + 1)}{2} - 1\right) + \binom{k - 1}{2}ab + ij\\ &\quad + i(k - 1)a + j(k - 1)b + T(a,b,j) + T(b,a,i) + m, \nonumber \end{align} and $T(a,b,j) = \sum_{r = 1}^j(\lfloor rb/a\rfloor + 1)$. \end{theorem} \begin{theorem}[\cite{Corteel1999}]\label{thm:corteel} There exist positive constants $c$ and $c'$ such that, for all $n > 1$, $$ cn\log n < |\Delta(n)| < c'n\log n. $$ \end{theorem} Let $\lambda = \lambda_1\dots\lambda_k$ be a partition, and let $c = (i,j)$ be a cell of its Young diagram. Define the {\em arm length} and the {\em leg length} of $c$ to be $a(c) = \lambda_j - i$ and $\ell(c) = \lambda'_i-j$, that is, the number of cells to the right of $c$ in its row, and above $c$ in its column, respectively. Bergeron and Mazin~\cite{Bergeron2023} give the following characterization of triangular partitions. \begin{lemma}[{\cite[Lemma 1.2]{Bergeron2023}}]\label{charact_bergeron} A partition $\lambda$ is triangular if and only if $t_\lambda^- < t_\lambda^+$, where $$ t_\lambda^- = \max_{c\in\lambda}\frac{\ell(c)}{a(c) + \ell(c) + 1}, \quad\text{and}\quad t_\lambda^+ = \min_{c\in\lambda}\frac{\ell(c) + 1}{a(c) + \ell(c) + 1}. $$ \end{lemma} \begin{definition} A cell of $\tau\in\Delta$ is \emph{removable} if removing it from $\tau$ yields a triangular partition. A cell of the complement $\bbN^2\setminus\tau$ is \emph{addable} if adding it to $\tau$ yields a triangular partition. \end{definition} \begin{lemma}[{\cite[Lemma 4.5]{Bergeron2023}}] \label{lem:removable-addable} Every nonempty triangular partition has either one removable cell and two addable cells, two removable cells and one addable cell, or two removable cells and two addable cells. \end{lemma} Let $\TYP$ be the poset of triangular partitions ordered by containment of their Young diagrams; equivalently, the restriction of Young's lattice to the subset of triangular partitions. The covering relations in $\TYP$ can be described as follows. \begin{lemma}[{\cite[Lemma 4.2]{Bergeron2023}}] Let $\tau,\nu\in\TYP$ such that $\tau<\nu$. Then, $\tau\lessdot\nu$ if and only if $\tau$ is obtained from $\nu$ by removing exactly one cell. In particular, $\TYP$ is ranked by the size of the partitions. \end{lemma} \begin{lemma}[{\cite[Corollary 4.1, Lemma 4.4]{Bergeron2023}}] The poset $\TYP$ has a planar Hasse diagram, and it is a lattice. \end{lemma} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Characterizations of triangular partitions} \label{sec:characterizations_triangular} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Bergeron and Mazin's~\cite{Bergeron2023} characterization of triangular partitions, given in Lemma~\ref{charact_bergeron} above, requires computing some quotients of arm and leg lengths for all the cells in the partition. In this section, we introduce an alternative and arguably simpler characterization of triangular partitions in terms of convex hulls, along with various ways to identify removable and addable cells. We then use these to describe an algorithm which determines if an integer partition is triangular and finds its removable and addable cells. The convex hull of a set $S\subseteq\bbN^2$ will be denoted by $\Conv(S)$. \begin{proposition} \label{charact_triang2D} A partition $\lambda$ is triangular if and only if $\Conv(\lambda)\cap\Conv(\bbN^2\setminus\lambda) = \emptyset$. \end{proposition} We will use the term {\em vertex} in the sense of a $0$-dimensional face of a polygon; in particular, $\Conv(\tau)$ may have lattice points in its boundary that are not vertices. \begin{proposition} \label{charact_trcp_tacp} Two cells in $\tau\in\Delta$ are removable if and only if they are consecutive vertices of $\Conv(\tau)$ and the line passing through them does not intersect $\Conv(\bbN^2\setminus\tau)$. Similarly, two cells in $\bbN\setminus\tau$ are addable if and only if they are consecutive vertices of $\Conv(\bbN^2\setminus\tau)$ and the line passing through them does not intersect $\Conv(\tau)$. \end{proposition} An immediate consequence is that a triangular partition can have no more than two removable cells and no more than two addable cells, as we knew from Lemma~\ref{lem:removable-addable}. \begin{proposition} \label{charact_orcp_oacp} A cell $c = (a,b) \neq (1,1)$ in $\tau\in\Delta$ is its only removable cell if and only if it is a vertex of $\Conv(\tau)$ and both of the following hold: \begin{itemize} \item if $a > 1$, the line containing the edge of $\Conv(\tau)$ adjacent to $c$ from the left intersects $\Conv(\bbN^2\setminus\tau)$ to the right of $c$; \item if $b > 1$, the line containing the edge of $\Conv(\tau)$ adjacent to $c$ from below intersects $\Conv(\bbN^2\setminus\tau)$ above $c$. \end{itemize} The characterization for a single addable cell is analogous. \end{proposition} The above characterizations can be used to describe an algorithm that determines whether a partition $\lambda$ of $n$ into $k$ parts is triangular, and if it is, it finds its removable and addable cells. The algorithm first finds the vertices of $\Conv(\lambda)$ and $\Conv(\mathbb{N}^2\setminus\lambda)$, and then it searches for a segment of the boundary of one of these convex hulls such that the line containing it does not intersect the opposite convex hull. By Proposition~\ref{charact_trcp_tacp}, such a segment joins two removable or addable cells. This algorithm has complexity $\bigO(k)$ for the initialization and $\bigO(\min\{k,\sqrt{n}\})$ for the rest of its steps, whereas an algorithm based on Bergeron and Mazin's Lemma~\ref{charact_bergeron} would take time $\bigO(n)$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The triangular Young poset} \label{sec:triangular_young_poset} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Bergeron and Mazin \cite{Bergeron2023} introduced the poset $\TYP$ of triangular partitions ordered by containment of their Young diagrams. They showed that it has a planar Hasse diagram, and deduced from this property that $\TYP$ is a lattice, and it is ranked by the size of each partition. Here we describe the M\"obius function of $\TYP$, and we give explicit constructions for the meet and the join of any two elements. Our first result confirms Bergeron's conjecture (personal communication, 2022) that the M\"obius function only takes values in $\{-1,0,1\}$. \begin{theorem} \label{Mobius} Let $\tau,\nu\in\TYP$ such that $\tau\leq\nu$. The value of the Möbius function is: $$ \mu(\tau, \nu) = \begin{cases} 1 & \text{if either $\tau = \nu$ or there exist $\zeta^1\neq\zeta^2$ such that $\nu = \zeta^1\lor\zeta^2$ and $\tau\lessdot\zeta^1,\zeta^2$},\\ -1 &\text{if $\tau\lessdot\nu$},\\ 0 &\text{otherwise.} \end{cases} $$ \end{theorem} It is shown in~\cite{Bergeron2023} that the faces of the Hasse diagram of $\TYP$ are polygons with an even number of sides. We can interpret Theorem~\ref{Mobius} as stating that, if $\tau < \nu$ and $\nu$ does not cover $\tau$, then $\mu(\tau, \nu)$ equals $1$ if $[\tau,\nu]$ is one of the polygonal faces, and $0$ otherwise. The next result explicitly characterizes the join and meet of two elements of $\TYP$. A similar formula works for the join and the meet of any number of elements. \begin{proposition} \label{triang_join_meet_construction} The join and the meet of $\tau,\nu\in\TYP$ are given by $$ \tau\lor\nu = \bbN^2\cap\Conv(\tau\cup\nu) \quad\text{and}\quad \tau\land\nu = \bbN^2\setminus\Big(\bbN^2\cap\Conv\big(\bbN^2\setminus(\tau\cap\nu)\big)\Big). $$ \end{proposition} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Bijections to balanced words and efficient generation} \label{sec:sturmian} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section we present two different interpretations of triangular partitions in terms of factors of Sturmian words. The first interpretation, which is hinted at in~\cite{Bergeron2023}, is quite natural, and it will allow us to prove some enumeration formulas in Section \ref{sec:subpartitions}. The second interpretation encodes families of triangular partitions by one single balanced word, along with two other parameters, and it will be used in Section~\ref{sec:algorithm} to implement efficient algorithms to count triangular partitions by their size. \subsection{Balanced words} Recall that a factor of a word is a consecutive subword. An infinite binary word $s$ is {\em Sturmian} if, for every $n\ge1$, the number of factors of $s$ of length $n$ equals $n + 1$. Sturmian words have applications in combinatorics, number theory, and dynamical systems; see \cite[Chapter 2]{Lothaire2002} for a thorough study. It is known that a finite binary word $w = w_1\dots w_\ell$ is a factor of some Sturmian word if and only if it is {\em balanced}, that is, for any $h \leq \ell$ and $i,j \leq \ell - h + 1$, we have \begin{equation*} \left|(w_i+w_{i+1}+\dots+w_{i+k-1})-(w_j+w_{j+1}+\dots+w_{j+k-1})\right|\le 1. % \left|\sum_{t = i}^{i + h - 1}w_t - \sum_{t = j}^{j + h - 1}w_t\right| \leq 1. \end{equation*} This condition says that for any two factors of $w$ of the same length, the number of ones in these factors differs by at most $1$. We denote by $\cB$ the set of all balanced words, and by $\cB_\ell$ the set of those of length $\ell$. The following enumeration formula for balanced words is due to Lipatov~\cite{Lipatov1982}. We use $\varphi$ to denote Euler's totient function. \begin{theorem}[\cite{Lipatov1982}]\label{lipatov} The number of balanced words of length $\ell$ is $$ |\cB_\ell|=1 + \sum_{i = 1}^\ell (\ell - i + 1)\varphi(i). $$ \end{theorem} \subsection{First Sturmian interpretation} \label{subsection:first-sturmian-interpretation} \begin{definition} A triangular partition is \emph{wide} (respectively \emph{tall}) if it admits a cutting line $x/r+y/s=1$ with $r > s$ (respectively $r < s$). \end{definition} It can be shown that every triangular partition must be wide, tall, or both. Additionally, a triangular partition $\tau$ is wide if and only if its conjugate $\tau'$ is tall. \begin{lemma} \label{lem:wide} For any triangular partition $\tau = \tau_1\dots\tau_k$, we have $$\tau \text{ is wide} \ \Leftrightarrow \ \tau_1 \ge k \ \Leftrightarrow \ \text{the parts of $\tau$ are distinct},$$ $$\tau \text{ is wide and tall} \ \Leftrightarrow \ \tau_1=k \ \Leftrightarrow \ \tau=\sigma^k.$$ \end{lemma} Given a wide triangular partition $\tau = \tau_1\dots\tau_k$, define the binary word \begin{equation}\label{def:w} \omega(\tau)=10^{\tau_1-\tau_2-1}10^{\tau_2-\tau_3-1}\dots10^{\tau_{k-1}-\tau_k-1}10^{\tau_k - 1}. \end{equation} The fact that all the parts of $\tau$ are distinct guarantees that the exponents are nonnegative. For example, $\omega(86531)=10110101$. \begin{proposition} \label{sturmian_interpretation_1} For every $k,\ell\ge1$, the map $\omega$ is a bijection between the set of wide triangular partitions with $k$ parts and first part equal to $\ell$, and the set of balanced words of length $\ell$ with $k$ ones that start with $1$. \end{proposition} \subsection{Second Sturmian interpretation} \label{subsection:second-sturmian-interpretation} Our second encoding of triangular partitions using balanced words appears to be new. Let $\epsilon$ denote the empty partition, and let $\mathcal{W}$ be the set of wide triangular partitions with at least two parts. Let $\cB^0$ denote the set of balanced words that contain at least one $0$. First we describe the possible sets that can be obtained by taking the differences of consecutive parts in a wide triangular partition. For $\tau = \tau_1\dots\tau_k\in\mathcal{W}$, define $$\cD(\tau) = \{\tau_1 - \tau_2,\;\tau_2 - \tau_3,\; \dots ,\;\tau_{k-1} - \tau_k \}.$$ \begin{lemma} \label{lemma_ell_ell+1} For any $\tau = \tau_1\dots\tau_k\in\mathcal{W}$, either $\cD(\tau) = \{d\}$ or $\cD(\tau) = \{d, d + 1\}$ for some $d\ge1$ such that $\tau_k\le d+1$. \end{lemma} Define also $\min(\tau)=\tau_k$, $\dif(\tau) = \min\cD(\tau)$, and $\wrd(\tau) = w_1\dots w_{k-1}$ where, for $i\in[k-1]$, we let $w_i = \tau_{i} - \tau_{i + 1} - \dif(\tau)$. Lemma~\ref{lemma_ell_ell+1} guarantees that $w_i\in\{0,1\}$ for all~$i$. \begin{theorem} \label{thm:sturmian_interpretation_2} The map $\chi = (\min,\dif,\wrd)$ is a bijection between $\mathcal{W}$ and the set $$ \cT = \{(m,d,w)\in\bbN\times\bbN\times\cB^0\;|\;m\le d + 1; \; w1\in\cB^0\;\mathrm{if}\;m = d + 1\}. $$ Its inverse is given by the map \begin{equation*} \xi(m,d,w_1\dots w_{k-1}) = \tau_1\dots\tau_k, \quad\text{where } \tau_i = m + \sum_{j = i}^{k-1}(w_j+d) \text{ for }i\in[k]. \end{equation*} Additionally, given $\tau\in\mathcal{W}$ with image $\chi(\tau)=(m,d,w)$, its number of parts equals the length of $w$ plus one, and its size is \begin{equation}\label{eq:size} |\tau|=km + \binom{k}{2}d + \sum_{i = 1}^{k-1} iw_i. \end{equation} \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Efficient generation} \label{sec:algorithm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% At the time of writing this abstract, the entry of the OEIS~\cite[A352882]{oeis} for the number triangular partitions of $n$ only includes values for $n\le 39$. These are the terms that appear in~\cite{Corteel1999}, where they were obtained using the generating function in Theorem~\ref{thm:GDelta}. Computing more terms using this generating function is impractical for large~$n$. Theorem~\ref{thm:sturmian_interpretation_2} can be used to implement a much more efficient algorithm that can quickly compute the first $10^5$ terms of the sequence. On input $N$, our algorithm to compute $|\Delta(n)|$ for $1\le n\le N$ performs a depth first search through the tree of balanced words of length up to $\lfloor \sqrt{2N} \rfloor$. The parent of a nonempty balanced word in this tree is the balanced word obtained by removing its last letter. For each $w\in\cB_\ell$, our algorithm can quickly determine whether $w0$ and $w1$ are balanced by keeping a vector that records, for each $h\le\ell$, whether all the factors of length $h$ have the same number of ones, or otherwise, whether the rightmost factor of $w$ has more or less ones than other factors. For each $w\in\cB_\ell$ with $\ell\le\sqrt{2N}$, the algorithm finds all the values $m,d\in\bbN$ such that $(m, d, w)\in\cT$, as defined in Theorem~\ref{thm:sturmian_interpretation_2}, and such that the size function given in equation~\eqref{eq:size} is at most $N$. Each triplet $(m,d,w)$ accounts for two triangular partitions, namely $\tau=\chi(m,d,w)$ and its conjugate, except when $w=0^{k-1}$ (for some $k\ge2$) and $m = d$, in which case it accounts for only one partition, the staircase $\sigma^k$. A C++ implementation of this algorithm is available at \cite{website}. In a standard laptop computer, this algorithm yields the first $10^3$ terms of the sequence $|\Delta(n)|$ in under one second, the first $10^4$ terms in one minute, and the first $10^5$ terms in about one hour. \begin{proposition} The above algorithm finds $|\Delta(n)|$ for $1\le n\le N$ in time $\bigO(N^{5/2})$. Additionally, it can be modified to generate all (resp., all wide) triangular partitions of size at most $N$ in time $\bigO(N^{3}\log N)$ (resp., $\bigO(N^{5/2}\log N)$). \end{proposition} The first $10^5$ terms of the sequence $|\Delta(n)|/(n\log n)$ are plotted on the left of Figure~\ref{fig:tp_bounds_nlogn}. The plot suggests that, for large $n$, this sequence oscillates between two decreasing functions that differ by about $0.05$. \begin{figure}[htp] \centering \includegraphics[width=.5\textwidth]{tp_nlogn_new.png}\includegraphics[width=.5\textwidth]{orcp_trcp.png} \caption{Left: The first $10^5$ terms of the sequence $|\Delta(n)|/(n\log n)$. Right: Plot of $|\Delta_2(n)|$ and $|\Delta_1(n)|$ for $1\le n\le100$.} \label{fig:tp_bounds_nlogn} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Generating functions for subsets of triangular partitions} \label{sec:generating-functions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $\Delta_1$ and $\Delta_2$ denote the subsets of triangular partitions with one removable cell and with two removable cells, respectively. Let $\Delta^1$ and $\Delta^2$ denote the subsets of triangular partitions with one addable cell and with two addable cells, respectively. Let $\Delta_2^2=\Delta_2\cap\Delta^2$. Denote partitions of size $n$ in each subset by $\Delta_1(n)$, $\Delta_2(n)$, $\Delta^1(n)$, $\Delta^2(n)$ and $\Delta_2^2(n)$. In this section we obtain generating functions for each of these sets, refining Theorem~\ref{thm:GDelta}. In our following result, $N_\Delta(a,b,k,m,i,j)$ is the function defined in equation~\eqref{eq:NDelta}. \begin{proposition}\label{prop:GDelta_2} The generating function for triangular partitions with two removable cells can be expressed as $$ G_{\Delta_2}(z) = \sum_{n\ge0}|\Delta_2(n)|z^n = \sum_{\gcd(a, b) = 1}\sum_{\substack{0\leq j < a \\ 0\leq i < b}}\sum_{k\ge2}z^{N_{\Delta}(a,b,k,k,i,j)}. $$ \end{proposition} \begin{proposition} The generating functions for partitions in $\Delta_1$, $\Delta^2$, $\Delta^1$, $\Delta_2^2$ can be written in terms of $G_\Delta(z)$ (given in Theorem~\ref{thm:GDelta}) and $G_{\Delta_2}(z)$ (given in Proposition~\ref{prop:GDelta_2}) as follows: \begin{align*} G_{\Delta_1}(z) &= G_{\Delta}(z) - G_{\Delta_2}(z)-1, & G_{\Delta^2}(z) &= \frac{1 - z}{z}G_\Delta(z) + \frac{1}{z}G_{\Delta_2}(z) - \frac{1}{z},\\ G_{\Delta^1}(z) &= \frac{2z - 1}{z}G_\Delta(z) - \frac{1}{z}G_{\Delta_2}(z) + \frac{1}{z}, & G_{\Delta_2^2}(z) &= \frac{1 - 2z}{z}G_\Delta(z) + \frac{1 + z}{z}G_{\Delta_2}(z) - \frac{1}{z}. \end{align*} \end{proposition} We can use the expression for $G_{\Delta_2}$ given in Proposition~\ref{prop:GDelta_2} to write an algorithm to find $|\Delta_2(n)|$. We have computed the first $100$ terms of this sequence using a MATLAB implementation of this algorithm, which is available at~\cite{website}. The initial terms of the sequences $|\Delta_1(n)|$ and $|\Delta_2(n)|$, plotted on the right of Figure~\ref{fig:tp_bounds_nlogn}, suggest that $|\Delta_2(n)|>|\Delta_1(n)|$ for all $n\ge9$, although we do not have a proof of this. It is interesting to note that both the local maxima of $|\Delta_1(n)|$ and the local minima of $|\Delta_2(n)|$ seem to occur precisely when $n\equiv2 \pmod 3$. On the other hand, $|\Delta(n)|$ does not exhibit such periodic extrema. %%%%%%%%%%%%% \section{Triangular subpartitions and a combinatorial proof of Lipatov's formula for balanced words} \label{sec:subpartitions} %%%%%%%%%%%%% For $\tau\in\Delta$, let $\I(\tau)=|\{\nu\in\Delta:\nu\subseteq\tau\}|$ denote the number of triangular subpartitions of $\tau$. We start by giving a recurrence for this number. In some particular cases, we will be able to obtain explicit formulas for $\I(\tau)$. In this section we will also derive a new proof of Theorem~\ref{lipatov}. Let $c^-$ and $c^+$ be the removable cells of $\tau$. Following~\cite{Bergeron2023}, denote by $\tau^\circ$ the triangular partition that is obtained from $\tau$ by removing all the cells in the segment joining $c^-$ and $c^+$. If $\tau$ has only one removable cell, then $c^-=c^+$, and $\tau^\circ$ is simply the partition obtained by removing this cell. \begin{lemma} \label{lem:recurrence_triangular_subpartitions} For any $\tau\in\Delta(n)$ with $n\geq1$, $$ \I(\tau) = \I(\tau\setminus\{c^-\}) + \I(\tau\setminus\{c^+\}) - \I(\tau^\circ) + 1. $$ \end{lemma} This recurrence relation, along with the base case $\I(\epsilon)=1$, allows us to compute $\I(\tau)$ for any $\tau\in\Delta$, although not very efficiently. For example, for the staircase, the first few terms of the sequence $\I(\sigma^\ell)$ for $\ell\ge0$ are $1, 2, 5, 12, 25, 48, 83,\dots$. We use the terms {\em height} and {\em width} of a partition $\tau$ to refer to the number of parts and the largest part of $\tau$, respectively. In order to find explicit formulas for $\I(\tau)$ in some cases, let us consider the closely related problem of counting triangular partitions whose width is at most $\ell$ and whose height is at most $h$; equivalently, those whose Young diagram fits inside an $h\times\ell$ rectangle. We denote by $\Delta^{h\times\ell}$ the set of such partitions. \begin{lemma} \label{equivalence_subpartitions-rectangle} Let $h,\ell\ge1$, and let $\nu\in\Delta$. Then $\nu\in\Delta^{h\times\ell}$ if and only if $\nu\subseteq\tau$, where $\tau=\tau_1\dots\tau_h$ is the triangular partition given by $ \tau_i = \left\lfloor\ell + 1 - \frac{\ell(i - 1) + 1}{h}\right\rfloor, $ for $1\le i\le h$. \end{lemma} Our next goal is to give a formula for $\I(\sigma^\ell)$, which, by Lemma~\ref{equivalence_subpartitions-rectangle}, equals the number of triangular partitions that fit inside an $\ell\times \ell$ square, that is, $\left|\Delta^{\ell\times\ell}\right|$. The proof of the following lemma uses the bijection $\omega$ from equation~\eqref{def:w}. \begin{lemma} \label{lem:h<=l,w=l} For $\ell\ge1$, the number of triangular partitions of width exactly $\ell$ and height at most $\ell$ is $|\cB_\ell|/2$, and \begin{equation*} \left|\Delta^{\ell\times\ell}\setminus\Delta^{(\ell-1)\times(\ell-1)}\right|=\I(\sigma^\ell)-\I(\sigma^{\ell-1})=|\cB_\ell|-1. \end{equation*} \end{lemma} Combining the above lemma with Lipatov's enumeration formula for balanced words (Theorem~\ref{lipatov}), we deduce the following result. \begin{theorem} \label{thm:staircase} For any $\ell\ge0$, $$ \left|\Delta^{\ell\times\ell}\right|=\I(\sigma^\ell) = 1+\sum_{i = 1}^\ell\binom{\ell - i + 2}{2}\varphi(i). $$ \end{theorem} Unfortunately, the proof of Theorem~\ref{thm:staircase} that relies on Lipatov's formula does not give a conceptual understanding of why the terms $\binom{\ell - i + 2}{2}$ and $\varphi(i)$ appear. Instead, we have been able to find a direct, combinatorial proof of Theorem~\ref{thm:staircase} that explains why these terms appear. While this proof does not fit in this extended abstract, we briefly describe its main ideas. First we give a bijection $\phi$ between triangular partitions (except those that have all parts equal to one) and the set $\{(a,b,d,e)\in\bbN^4\;|\;d < a,\;\gcd(d,e) = 1\}$, and characterize the set $\phi(\Delta^{\ell\times\ell})$. Then we show that, for fixed $d