Multi-cores, posets, and lattice paths\thanks{The authors are grateful to Adriano Garsia for warm hospitality during the first author's visit at UCSD and his role in initiating this research.
Tewodros Amdeberhan\thanks{ (tamdeber@tulane.edu) Department of Mathematics
Tulane University
New Orleans
LA
70118
Hooks are prominent in representation theory (of symmetric groups) and they play a role in number theory (via cranks associated to Ramanujan's congruences). A partition of a positive integer $n$ has a Young diagram representation. To each cell in the diagram there is an associated statistic called hook length, and if a number $t$ is absent from the diagram then the partition is called a $t$-core. A partition is an $(s,t)$-core if it is both an $s$- and a $t$-core. Since the work of Anderson on $(s,t)$-cores, the topic has received a growing attention. This paper expands the discussion to multiple-cores. More precisely, we explore $(s,s+1,\dots,s+k)$-core partitions much in the spirit of a recent paper by Stanley and Zanello. In fact, our results exploit connections between three combinatorial objects: multi-cores, posets and lattice paths (with a novel generalization of Dyck paths). Additional results and conjectures are scattered throughout the paper. For example, one of these statements implies a curious symmetry for twin-prime $(s,s+2)$-core partitions.
multicores.tex
\documentclass[12pt]{article}
\usepackage{enumerate}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{amsthm}
\usepackage{float}
\pagestyle{plain}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{conj}{Conjecture}
\newtheorem{rmk}{Remark}
\newtheorem{prop}{Proposition}
\newtheorem{case}{Case}
\newtheorem{cor}{Corollary}

\numberwithin{equation}{section}
\numberwithin{thm}{section}
\numberwithin{lemma}{section}
\numberwithin{conj}{section}
\numberwithin{rmk}{section}
\numberwithin{prop}{section}
\numberwithin{cor}{section}

\DeclareMathOperator{\area}{area}
\DeclareMathOperator{\hook}{hook}


\title{Multi-cores, posets, and lattice paths\thanks{The authors are grateful to Adriano Garsia for warm hospitality during the first author's visit at UCSD and his role in initiating this research.}} 

\author{Tewodros Amdeberhan\thanks{ 
(tamdeber@tulane.edu) Department of Mathematics, Tulane University,
New Orleans, LA, 70118}
\and
Emily Leven\thanks{Supported by NSF grant DGE 1144086. 
(esergel@ucsd.edu) Department of Mathematics, University of California, San Diego, CA, 92093}}


\begin{document}

\maketitle

\begin{abstract}
Hooks are prominent in representation theory (of symmetric groups) and they play a role in number theory (via cranks associated to Ramanujan's congruences). A partition of a positive integer $n$ has a Young diagram representation. To each cell in the diagram there is an associated statistic called hook length, and if a number $t$ is absent from the diagram then the partition is called a $t$-core. A partition is an $(s,t)$-core if it is both an $s$- and a $t$-core. Since the work of Anderson on $(s,t)$-cores, the topic has received a growing attention. This paper expands the discussion to multiple-cores. More precisely, we explore $(s,s+1,\dots,s+k)$-core partitions much in the spirit of a recent paper by Stanley and Zanello. In fact, our results exploit connections between three combinatorial objects: multi-cores, posets and lattice paths (with a novel generalization of Dyck paths). Additional results and conjectures are scattered throughout the paper. For example, one of these statements implies a curious symmetry for twin-prime $(s,s+2)$-core partitions. 
\end{abstract}

\textbf{Key words:} hooks, core partitions, posets, generalized Catalan, generalized Dyck paths, Young diagrams, Frobenius problem.\\

\textbf{AMS subject classifications:} Primary 05A15;
Secondary 05A17, 05A19, 20M99.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setcounter{section}{-1}

\section{Introduction} \label{sec:intro}

Let \( S \) be any set of positive integers. Say that \( a \) is \emph{generated} by \( S \) if \( a \) can be written as a non-negative linear combination of the elements of \( S \).
Following the notation of \cite{Stanley}, we define \( P_S \) to be the set whose elements are positive integers not generated by \( S \). Equivalently, \( k \in P_S \) if \( \alpha_k = 0 \) in the generating function below.
\begin{equation}
\prod_{s \in S} \, \frac{1}{1-x^s} \, = \, \sum_{k \geq 0} \, \alpha_k \, x^k
\end{equation}
This is reminiscent of the Frobenius coin exchange problem. We make \( P_S \) into a poset by defining the cover relation so that \( a \) \emph{covers} \( b \) (written \(a \gtrdot b \)) if and only if \( a - b \in S \). For example, see Figure \ref{fig:Pex}. Note that \(P_S\) is finite if and only if the elements of \( S \) are relatively prime (no \( d > 1 \) divides every \( s \in S \)).

\begin{figure}
\begin{center}
\includegraphics[width=1.5in]{Pex}
\caption{The poset $P_{\{5,7,13\}}$}
\label{fig:Pex}
\end{center}
\end{figure}

We depict a partition \( \lambda = (\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_k > 0) \) by its french Ferrers diagram. The hook length of a cell \( c  \) in the diagram of \( \lambda \)  is the number of cells directly north or east of \( c \) including itself. It is denoted by \(\hook_\lambda(c) \), or just \(\hook(c)\) when the partition is clear. For any positive integer \(s\), we say \( \lambda \) an \(s\)-core if its diagram contains no cell \(c\) so that \( s \) divides \( \hook(c) \). For example, see Figure \ref{fig:hooks}.

\begin{figure}
\begin{center}
\includegraphics[width=1.2in]{hooks}
\caption{The french Ferrers diagram of the 4-core \( (6,3,1,1) \) with hook lengths marked.}
\label{fig:hooks}
\end{center}
\end{figure}

Let \( (P,<_P) \) be a poset. We say that a set \( I \subset P\) is a \emph{lower ideal} of this poset if \( a <_P b \) and \( b \in I \) imply \( a \in I \). The work of \cite{Keith} gives a natural bijection between \(s\)-cores and lower ideals of \( P_{\{s\}} \). In particular, this bijection associates the lower ideal \( I \) of \( P_{\{s\}} \) with the \(s\)-core whose first column has hook lengths given by \( I \). For example, the 4-core in Figure \ref{fig:hooks} corresponds to the lower ideal \{1,2,5,9\} of \( P_{\{4\}} \). 

Note that this bijection will send an \(S\)-core to a set which is simultaneously a lower ideal of \( P_{\{s\}} \) for each \(s \in S\), and hence is a lower ideal of \( P_S \). For example, the lower ideal \{1,4,6,11\} of \( P_{\{5,7,13\}} \) (see Figure \ref{fig:Pex}) corresponds to the \{5,7,13\}-core partition (8,4,3,1).

When \( S = \{s, t\} \) and \( \gcd(s,t)=1\), \cite{Anderson} notes that there is a bijection between \(S\)-cores and paths in the \( s \times t \) lattice rectangle consisting of north and east steps which stay above the line \( y = \frac{t}{s} x \). We will call these paths \((s,t)\)-Dyck paths. Furthermore, \cite{Armstrong} make multiple conjectures regarding \( \{s, t\} \)-cores. In \cite{Stanley}, the authors prove one of these conjectures in the special case \( t = s+1 \). They refer to this case as the Catalan case because the aforementioned paths are precisely Dyck paths, and those are counted by the Catalan number \( C_s = \frac{1}{s+1}{2s \choose s} \).

The remainder of this paper consists of four sections. Section 1 gives a \(q\)-analog of the formula for the number of \((s,t)\)-cores. This has a nice interpretation in terms of \((s,t)\)-Dyck paths. Section 2 explores the properties of the case \( t=s+2 \). Section 3 is dedicated to developing a theory of $\{s, s+1, s+2,\dots, s+p\}$-cores. These correspond to an interesting generalization of Dyck paths, which are presented in Section 4. The authors believe these to be new combinatorial objects which include Dyck paths and Motzkin paths as special cases.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Counting \((s,t)\)-Dyck paths}

As noted above, whenever \(s\) and \(t\) are coprime, there is a bijection between \((s,t)\)-cores and \((s,t)\)-Dyck paths. It is easy to show, using the cyclic lemma, that the number of \((s,t)\)-Dyck paths is simply
\begin{equation} \label{mncount}
\frac{1}{s+t} {s+t \choose s}.
\end{equation}
However, we can get another formula using the following theorem of \cite{Krewaras}.

\begin{thm}[\cite{Krewaras}] \label{det}
The number of partitions contained in a shape \( \lambda = (\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_k ) \) is given by
\[ \det \left( {\lambda_j + 1 \choose j-i+1} \right). \]
\end{thm}

Note that the squares above each path in the \( s \times t \) rectangle form the english Ferrers diagram of a partition. Moreover, the path which hugs in the diagonal corresponds in this way to the partition with parts \( \lfloor{ \frac{s}{t} \cdot i } \rfloor \) for \(i\) from 1 to \(t-1\). For example, Figure \ref{75hug} depicts the path hugging the diagonal in the \( 7 \times 5 \) rectangle. We can see the partition \( (5,4,2,1) \) above this path.

\begin{figure}
\begin{center}
\includegraphics[width=1in]{75hug}
\caption{The path closest to the main diagonal in the \(5 \times 7\) rectangle.}
\label{75hug}
\end{center}
\end{figure}

It is surprising that in these cases the determinant of Theorem \ref{det} has the simple closed form of (\ref{mncount}). Moreover, when \(t=s+1\), (\ref{mncount}) gives the Catalan number \(C_s\) and Theorem \ref{det} yields an interesting identity.

\begin{cor}
The Catalan numbers satisfy the identity
\[ \sum_{k=1}^{n} (-1)^k {k+1 \choose n-k} C_k = 0. \]
\end{cor}

\begin{proof}

As observed above, we have \( C_n = \det \left( {n-j+1 \choose j-i+1} \right) \). By reversing the orders of the rows and columns (which introduces a sign of \((-1)^{2(n-1)}=1\)), we get \( C_n = \det \left( {j+1 \choose i-j+1} \right) \). The matrix here is Hessenberg. There is a recursion \cite{Muir} for the determinant of Hessenberg matrices which, in the present case, yields
\begin{align*}
C_n =  \det \left( {j+1 \choose i-j+1} \right)_{1 \leq i,j \leq n-1} &= (-1)^{n-1} \sum_{k=1}^{n-1} (-1)^k {k+1 \choose n-k}  \det \left( {j+1 \choose i-j+1} \right)_{1 \leq i,j \leq k-1} \cr
 &=  (-1)^{n-1} \sum_{k=1}^{n-1} (-1)^k {k+1 \choose n-k} C_k.
\end{align*}

\end{proof}

For a partition \( \lambda = (\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_k ) \), we say \(\mu\) is contained in \(\lambda\), written \( \mu \leq \lambda \), if \( \mu = ( \mu_1 \geq \mu_2 \geq \dots \geq \mu_k \geq 0) \) and \( \mu_i \leq \lambda_i \) for \(1 \leq i \leq k\). Now, we present a simple \(q\)-analog of Theorem \ref{det}.

\begin{thm} \label{qdet}
For a partition \( \lambda = (\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_k ) \), we have the following determinantal formula:
\[
\sum_{\mu \leq \lambda} q^{|\mu|} = \det \left( q^{j-i+1 \choose 2} \left[ {\lambda_j + 1 \atop j-i+1} \right]_q \right).
\]
\end{thm}


\begin{proof}

We will proceed by using the principle of inclusion-exclusion. Let \( A \) be the set of all sequences \(a = (a_1,a_2,\dots,a_k)\) such that \(0 \leq a_i \leq \lambda_i \) for each \(i\). We will write \( |a| = a_1 + a_2 + \dots + a_k \). Let \( A_i  \subset A \) be the set of such sequences with an ascent \( a_i < a_{i+1} \) at position \(i\). Then for any \( S \subset [k-1] \) we let \( A_S = \cap_{i \in S} \, A_i \). In particular, \( A_{\emptyset} = A\). The sequences corresponding to partitions \( \mu \leq \lambda \) are contained in \( A - \cup_{i=1}^{n-1} A_i \).

For any set \(B \subset A \), write
\[ q(B) = \sum_{b \in B} q^{|b|}. \]
We are interested in the quantity \( q(A - \cup_{i=1}^{n-1} A_i )\). By the principle of inclusion-exclusion, this is simply
\[
\sum_{S \subset [k-1]} (-1)^{|S|} \, q(A_S).
\]
Therefore we just need to evaluate \( q(A_s) \) for each \(S\).

Note that any \( S \subset [k-1] \) induces a set partition of \( [k] \) as follows: \( i \) and \(i+1\) are in the same set exactly when \( i \in S \). For example,
\[ S = \{2,3,5\} \hbox{ and } n=8 \Longleftrightarrow \{ \{1\}, \{2,3,4\}, \{5,6\}, \{7\}, \{8\} \}.\]
Let this partition be denoted \( X_S \). Note that whenever \( i \) and \( j \) are in different blocks of \( X_S \), then we can choose \( a_i \) and \(a_j \) independently for \( a \in A_S \). Hence we can express \( q(A_S) \) as a product by breaking up our choices for the sequences into blocks.

Each block of \( X_S \) has the form $\{r,r+1,\dots,s\}$. We need to choose \(s-r+1\) values for the corresponding \(a_i\)'s which are strictly increasing. Since \(a_i \leq a_s \leq \lambda_s \leq \lambda_i\) for each \( r \leq i \leq s\), we may choose any values for the \(a_i\)'s of this block which satisfy \( a_r < a_{r+1} < \dots < a_s \leq \lambda_s \). This given, the contribution of the \(a_i\)'s in this block to \(\sum_{a} q^{|a|} \) will be \[ q^{s-r+1 \choose 2} \left[ {\lambda_r + 1 \atop s-r+1} \right]_q. \]

Define \( r_i^S \) to be the smallest element of the \(i\)th block of \(X_S\) and \( s_i^S \) to be the largest element. Then we have
\[
q(A - \cup_{i=1}^{n-1} A_i ) \,=\, \sum_{S \subset [k-1]} (-1)^{|S|} \prod_{m=1}^{|X_S|}  \left[ {\lambda_{s_m^S} + 1 \atop s_m^S - r_m^S +1} \right]_q.
\]

On the other hand, consider the matrix of Theorem \ref{qdet}. Note that the subdiagonal (where \(i=j+1\)) consists of all 1's and below that the matrix is all 0's. Therefore we can break up our expansion of the determinant
\[
\det (M_{i,j}) = \sum_{\sigma \in S_k} sign(\sigma) M_{\sigma_1,1} M_{\sigma_2,2} \dots M_{\sigma_k,k}
\]
according to which elements of the subdiagonal are chosen. Given some \( S \subset [k-1] \), how many \( \sigma \in S_k \) contribute to the determinant and have \( \sigma_j = j+1 \) precisely when \( j \in S \)? Exactly one. In particular, \( \sigma_{s_i^S} = r_i^S \). This is because after choosing all elements below the main diagonal, \( \sigma \) must assign the first available column \( s_1^S \) to the first available row \( r_1^S \), the next available column \( s_2^S \) to the next available row \(r_2^S\), and so on. Any other choice will include a cell below the subdiagonal, making the contribution of that permutation 0.

For example, choosing \( S=\{2,3,5\} \) when \(n=8\) induces the permutation in Figure \ref{sigchoice}. Cells from the subdiagonal which were not chosen by \(S\) and the rows and columns of chosen subdiagonals are grayed out. Then the choices within the remaining white squares are forced. We can see that in this case \( \sigma = 1 \, 3 \, 4 \, 2 \, 6 \, 5 \, 7 \, 8 \).

\begin{figure}
\begin{center}
\includegraphics[width=1.1in]{sigchoice}
\caption{The permutation \( 1 \, 3 \, 4 \, 2 \, 6 \, 5 \, 7 \, 8 \).}
\label{sigchoice}
\end{center}
\end{figure}

Furthermore, we have \( \sigma = (1)(2,3,4)(5,6)(7)(8) \). In general, the cycle structure of \( \sigma \) induced in this way is given by \( X_S \). Since a cycle of length \(k\) contributes \((-1)^{k-1} \) to the sign of the permutation, we have \( sign(\sigma) = (-1)^{|S|}\). Hence we obtain
\[
\det \left( q^{j-i+1 \choose 2} \left[ {\lambda_j + 1 \atop j-i+1} \right]_q \right)
\,=\,
 \sum_{S \subset [k-1]} (-1)^{|S|} \prod_{m=1}^{|X_S|}  \left[ {\lambda_{s_m^S} + 1 \atop s_m^S - r_m^S +1} \right]_q
\,=\,
q(A - \cup_{i=1}^{n-1} A_i ).
\]

\end{proof}

As noted above, when \(s,t\) are coprime we can use the numbers \( \lfloor \frac{s}{t} \cdot i \rfloor \) for the parts of \( \lambda \) to obtain a correspondence between \((s,t)\)-Dyck paths and partitions \( \mu \leq \lambda \). Hence this theorem gives a formula for the coarea-enumeration of \((s,t)\)-Dyck paths. In particular, this sum is
\[
\det \left( q^{j-i+1 \choose 2} \left[ { \lfloor \frac{s}{t} (t-j) \rfloor +1 \atop j-i+1} \right]_q \right).
\]

\begin{rmk}
Since we have discovered this theorem, several other proofs have been found. In private correspondence, Brendon Rhoades proved the same result using the Gessel-Viennot-Lindstrom Lemma and Jeff Remmel gave a proof using involutions. Each of these proofs yielded interesting extensions.
\end{rmk}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{A curious symmetry in \( P_{\{s,s+2\}} \) }

In order for \( P_{\{s,s+2\}} \) to be a finite poset, we must restrict ourselves to the case when \(s\) is odd. Hence we will fix \(n\) and consider \( P_{\{ 2n-1,2n+1\}} \). To sum up the results of \cite{Anderson}, for this special case, we state the following theorem.

\begin{thm}[\cite{Anderson}]
The following are equinumerous.
\begin{enumerate}
\item the number of \((s,s+2)\)-cores;
\item the number of \((s,s+2)\)-Dyck paths;
\item the number of lower ideals in \( P_{\{s,s+2\}} \).
\end{enumerate}
\end{thm}

Consider the \( (s-1)\times(s+1) \) rectangle \(R_s\) where (\(i,j\)) entry has value \( (s+1)(j-1) + i \), increasing North and Eastbound. Figure \ref{sp2} illustrates the symmetry that the next result alludes to.

\begin{thm} \label{2symm}
For each \(s \geq 3\), the (\(i,j\)) entry of \(R_s\) is an element of \( P_{\{s,s+2\}} \) if and only if the (\(i,s-1-j\)) entry is not. Equivalently, for \( 1 \leq i \leq s+1 \) and \(1 \leq j \leq s-1 \),
\[
(s+1)(j-1) + i \in P_{\{s,s+2\}} \Longleftrightarrow
(s+1)(s-1-j) + i \not\in P_{\{s,s+2\}}.
\]
\end{thm}

\begin{figure}
\begin{center}
\includegraphics[width=2.8in]{sp2}
\caption{The rectangle \(R_6\) with entries in \( P_{\{7,9\}} \) and entries not in \( P_{\{7,9\}} \).}
\label{sp2}
\end{center}
\end{figure}

Before we can prove Theorem \ref{2symm}, we need to introduce some more notation and a result of \cite{Popoviciu}. Let \( \lfloor x \rfloor \) and \( \{x\} \) denote the \emph{integral part} and the \emph{fractional part} of a real number \(x\). Define \( N_{s,t}(x) = \#\{ (k,l) \in \mathbb{Z}^2 : k,l \geq 0, sk+tl=m\} \) to be the number of partitions of \(m\) using only the elements \(s\) and \(t\) as parts. It is then evident that
\[
\frac{1}{(1-x^s)(1-x^t)} \,=\, \sum_{m \geq 0} N_{s,t}(m) x^m.
\]

\begin{prop}[\cite{Popoviciu}] \label{popo}
Let \( \equiv_a \) denote congruence modulo \(a\). If \(s\) and \(t\) are relatively prime, then
\[
N_{s,t}(m) \,=\, \frac{m}{st} - \left\{ \frac{t^{-1} m}{s} \right\} - \left\{ \frac{s^{-1}m}{t} \right\} + 1,
\]
where \(s^{-1},t^{-1} \in \mathbb{N}\) are modular inverses; that is \(t^{-1}t \equiv_s 1\) and \(s^{-1}s \equiv_t 1\).
\end{prop}

There are two immediate consequences of this result, one of which is due to Sylvester.

\begin{cor} \label{PopoCor}
If \(s\) and \(t\) are relatively prime, then
\begin{enumerate}[(i)]
\item the largest integer (Frobenius number) not in \(P_{\{s,t\}}\) is \(st-s-t\);
\item exactly half of the integers in \( \{1,\dots,(s-1)(t-1)\} \) belong to \(P_{\{s,t\}}\).
\end{enumerate}
\end{cor}

\begin{proof}[Proof of Theorem \ref{2symm}]
Write \(s=2n-1\), \(t=s+2=2n+1\). Split up the set \( \{1,2,\dots,(s-1)(t-1)\} \) into disjoint halves:
\begin{align*}
A = \{ m: m=\alpha(s+1)+r+1, 0 \leq \alpha \leq \frac{s-3}{2}, 0 \leq r \leq s\} \cr
B = \{ m': m'= (s-2-\alpha)(s+1)+r+1, 0 \leq \alpha \leq \frac{s-3}{2}, 0 \leq r \leq s\}.
\end{align*}
The map \( \Psi: A \to B \) given by \( \Psi(m) = m' \) establishes a bijection. Proving the theorem is then tantamount to showing \( N_{s,t}(m) + N_{s,t}(m') = 1\). This can be achieved through Proposition \ref{popo} and the special fact that \( s^{-1} = t^{-1} = n = \frac{s+1}{2} \). Omitting the routine calculations this entails, we offer the reader a direct method. At the heart of the matter lies the fact that \emph{exactly one} of the two integers \(m\) and \(m'\) is in the poset \(P_{s,s+2}\). To show this, start with \(m'-m = (s-2-2\alpha)(s+1) > 0\). Observe \(c(s+1) \in P_{\{s,s+2\}}\) if and only if \( c \in \mathbb{N} \) is even. Indeed \(c=2d\) implies \(c(s+1)=d(2s+2)\). Since \(s-2-2\alpha\) is odd, we have that \(m'-m \not\in P_{\{s,s+2\}}\). In particular, \(m\) and \(m' = m + (s-2-2\alpha)(s+1)\) cannot \emph{both} below to the poset \(P_{\{s,s+2\}}\). Another possibility is both \(m,m' \not\in P_{\{s,s+2\}}\). For this to occur, we would have to have another pair \(m,m' \not\in P_{\{s,s+2\}}\) due to Corollary \ref{PopoCor} (ii). But we have already noted that this is impossible. Hence the proof is complete.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Counting in the multi-Catalan case} \label{sec:count}

For brevity, we will write \( T_{s,p} \) for \( P_{\{s,s+1,\dots,s+p\}}\). As mentioned above, the number of lower ideals in \( T_{s,1} \) is given by the Catalan number \( C_s = \frac{1}{s+1}{2s \choose s} \). We can prove this using a simple recursion which also applies to any \( T_{s,p} \). Let \( J(T_{s,p}) \) be the set of all lower ideals in \( T_{s,p} \) for any \(s,p\). Following \cite{Stanley}, for \(1 \leq i \leq s-1 \), let \(J_i(T_{s,p})\) be the set of all lower ideals in \(T_{s,p}\) containing \(1,2,\dots,i-1\) but not \(i\). Also let \(J_s(T_{s,p})\) be the set of all lower ideals in \(T_{s,p}\) containing \(1,2,\dots,s-1\), so that 
\[ J(T_{s,p}) = \bigcup_{i=1}^s J_i(T_{s,p}). \]

\begin{figure}
\begin{center}
\includegraphics[width=2.2in]{J6T122}
\caption{The poset $P_{\{13,14,15\}} = T_{13,3}$. Any ideal in $J_6(T_{13,3})$ must contain the element within the rectangle and may contain elements within the triangles.}
\label{fig:J6T122}
\end{center}
\end{figure}

For example, see Figure \ref{fig:J6T122}. Here we see the poset \( T_{13,3} \) and we have marked the structure an element of \( J_6(T_{13,2}) \) may take. Note that the structures within the triangles are isomorphic to \( T_{4,2} \) and \( T_{7,2} \), respectively. In fact, the elements of \(J_i(T_{s,p})\) are in one-to-one correspondence with pairs of elements, one in \( J(T_{i-p,p}) \) and one in \( J(T_{s-i,p}) \). Hence we have the recursion
\begin{align} \label{Jrecur}
|J(T_{s,p})| &= \sum_{i=1}^s |J_i(T_{s,p})| \cr
&= \sum_{i=1}^s \, |J(T_{i-p,p})| \cdot |J(T_{s-i,p})|
\end{align}
with initial conditions \( |J(T_{\leq 0,p})|=1 \) and \( |J(T_{i,p})| = 2^{i-1} \) for \(1 \leq i \leq p\). This recursion generalizes one for Catalan numbers, so we will denote \( |J(T_{s,r})| \) by \( C_s^{(r)} \).

Using this recursion, we obtain the following generating function by a straight-forward computation.

\begin{thm}
For \( r \geq 1 \) we have
\[
\sum_{s \geq 0} C_s^{(r)} x^s = \frac{ 2-2x-A_r(x) - \sqrt{ A_r(x)^2 - 4x^2 } }{2 x^{r-1}}, \hskip 20pt \hbox{ where } A_r(x) = 1 - x + \frac{x^2 - x^{r-1}}{1-x}.
\]
\end{thm}

As discussed above \( C_s^{(1)}\) is the usual Catalan number \( C_s \). We will show in the next section that \( C_s^{(2)} \) is the \(s\)th Motzkin number. Hence
\[
C_s^{(2)} = \sum_{k \geq 0} {n \choose 2k} C_k.
\]
We have the following conjecture, which is in the same spirit as the conjectures of \cite{Armstrong}. It would be interesting to obtain such a conjecture for \((s,s+1,\dots,s+r)\)-cores or, even more generally, \(S\)-cores.

\begin{conj}
The total sum of the sizes of all \( (s,s+1,s+2) \)-cores equals
\[ %\sum_{j=0}^{s-2} {j+3 \choose 3} \sum_{i \geq 0} {j \choose 2i} C_i = 
\sum_{j=0}^{s-2} {j+3 \choose 3} C_j^{(2)} . \]
\end{conj}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Generalized Dyck Paths}

Below we introduce a novel set of combinatorial objects which are in bijection with elements of \( J(T_{n,k}) \), and therefore \( (n,n+1,...n+k) \)-cores. Fix \( n, k \geq 1 \). Then \( D \) is a generalized Dyck path if \(D\) stays above the line \(y=x\) and consists of the following steps:
\begin{enumerate}
\item vertical steps \(N_k = (0,k)\)
\item horizontal steps \(E_k = (k,0)\)
\item diagonal steps \(D_i = (i,i)\) for \(1 \leq i \leq k-1\).
\end{enumerate}
We will briefly denote the number of such generalized Dyck paths by \( GD_{n,k} \) Note that when \(k=1\), there are no diagonal steps so we get Dyck paths. When \(k=2\), these naturally correspond to Motkzin paths.

\begin{figure}
\begin{center}
\includegraphics[width=5.0in]{GD43}
\caption{The set of all generalized Dyck paths for \(n=4\) and \(k=3\).}
\label{GD43}
\end{center}
\end{figure}

When \( n \leq k \), we can see that \( GD_{n,k} = 2^n \) since the paths hit the main diagonal at any subset of the \( n \) possible places. Moreover, by conditioning the path on the first return to the main diagonal, we get the recursion
\[ GD_{n,k} = \sum_{s=1}^{n} GD_{s-k,k} \cdot GD_{n-s,k}. \]
Here we use the convention that \( GD_{ < 0, k} = 1 \) for any \( k\). This is because when the first return is at the \(s\)th point on the main diagonal and \( s \geq k \), we must have that the first step is \( N_k \) and the last step before the return in \(E_k\). Removing these steps gives a generalized \( (s-k,k) \)-Dyck path and a generalized \( (n-s,k) \)-Dyck path. On the other hand, when \( s < k \), the first step must be \(D_s\) and the removal of this step gives a generalized \( (n-s,k) \)-Dyck path. Hence we have the following theorem.

\begin{thm} \label{GDbij}
For any \(n,k \geq 1\), the number of generalized \((n,k)\)-Dyck paths is
\[ GD_{n,k} = C_n^{(k)}. \]
\end{thm}

\begin{proof}
In light of (\ref{Jrecur}), the recursion above is sufficient to prove the theorem. However, we can give a simple bijective proof. Simply label every \(k\)th diagonal of the \( n \times n \) lattice with consecutive numbers starting each diagonal with \(1, 1 + n+k, 1 + 2n+2k, \dots \). Then replace each step \(D_i \) by \(N_i E_i\) to get an ``inflated'' generalized Dyck path. The set of all labels below the inflated path will correspond to a unique lower ideal of \(T_{n,k}\). For example, see Figure \ref{GDexample}.

\begin{figure}
\begin{center}
\includegraphics[width=4.0in]{GDExample}
\caption{Two lower ideals of \(T_{10,3} \) and their corresponding generalized Dyck paths. To avoid clutter, most edges of the Hasse diagrams have been excluded.}
\label{GDexample}
\end{center}
\end{figure}

\end{proof}

We still have the bijection between cores and lower ideals outlined in the introduction. Therefore the above yields the following analog to the results of \cite{Anderson}.
\begin{thm}
The following are equinumerous.
\begin{enumerate}
\item the number of \((s,s+1,\dots,s+k)\)-cores;
\item the number of \((s,k)\) generalized Dyck paths;
\item the number of lower ideals in \( P_{\{s,s+1,\dots,s+k\}} \).
\end{enumerate}
\end{thm}

\section*{Postscript}

Shortly after our posting of this paper on the ArXiv,
the authors of \cite{Yang} informed us (through private correspondence) that they had an independent set of proofs for the results on $(s,s+1,s+2)$-cores.

\bibliographystyle{abbrv} 
\bibliography{multicores}

\end{document}




multicores.bbl
\begin{thebibliography}{1}

\bibitem{Anderson}
J.~Anderson.
\newblock {Partitions with are simultaneously $t_1$- and $t_2$-core}.
\newblock {\em Discrete Math.}, 248:237--243, 2002.

\bibitem{Armstrong}
D.~Armstrong, C.~Hanusa, and B.~Jones.
\newblock {Results and conjectures on simultaneous core partitions}.
\newblock {\em arXiv preprint arXiv:1308.0572}, 2013.

\bibitem{Keith}
W.~Keith and R.~Nath.
\newblock {Parititions with Prescribed Hooksets}.
\newblock {\em J. of Comb. and Number theory}, 3(1), 2011.

\bibitem{Krewaras}
G.~Krewaras.
\newblock Sur une classe de probl\`emes des d\'enombrement li\'es au trellis
  des partitions des entiers.
\newblock {\em Cahiers Buro}, 6:2--107, 1965.

\bibitem{Muir}
T.~Muir.
\newblock {\em {A Treatise on the Theory of Determinants}}.
\newblock Dover, 1960.

\bibitem{Popoviciu}
T.~Popoviciu.
\newblock Asupra unei probleme de partitie a numerelor.
\newblock {\em Acad. Rep. Pop. Romane, Filiala Cluj, Studii si cercetari
  stiintifice}, 4(7-58), 1953.

\bibitem{Stanley}
R.~Stanley and F.~Zanello.
\newblock {The Catalan case of Armstrong's Conjecture on simultaneous core
  patitions}.
\newblock {\em arXiv preprint arXiv:1312.4352}, 2013.

\bibitem{Yang}
J.~Yang, M.~Zhong, and R.~Zhou.
\newblock {On the Enumeration of $(s,s+1,s+2)$-Core Partitions}.
\newblock {\em In preparation}, 2014.

\end{thebibliography}
