\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
New Identities for the Polarized Partitions \\
\vskip .11in
and Partitions with $d$-Distant Parts
}
\vskip 1cm
\large
Ivica Martinjak and Dragutin Svrtan\\
Faculty of Science\\
University of Zagreb\\
Bijeni\v cka cesta 30 \\
HR-10000 Zagreb\\
Croatia\\
\href{mailto:imartinjak@phy.hr}{\tt imartinjak@phy.hr} \\
\href{mailto:dsvrtan@math.hr}{\tt dsvrtan@math.hr}
\end{center}

\vskip .2 in

\begin{abstract} 
In this paper we present a new class of integer partition identities.
The number of partitions with $d$-distant parts can be written as a sum
of the numbers of partitions of various lengths with 1-distant parts
whose even parts, if there are any, are greater than twice the number
of odd parts. We also provide a direct bijection between these classes
of partitions.
\end{abstract}


\section{Preliminaries and introduction}

A {\it partition} is the sequence $\lambda $=$(\lambda_1, \lambda_2, \ldots ,\lambda_l)$,  where $\lambda_i$ is a natural number $\forall i$, assuming $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_l$. When
$\sum_{i=1}^l \lambda_i$=$|\lambda|$=$n$ we say that $\lambda$ is a
partition of $n$, and denote it by $\lambda \vdash n$. The numbers $\lambda_i$
are {\it parts} of a partition, and the number of parts $l(\lambda)$=$l$
is the {\it length} of a partition. We let ${\cal P}_n$ denote the set
of all partitions of $n$, with $p(n):=|{\cal P}_n|$. The number of
partitions $\lambda \vdash n$ with exactly $k$ summands is denoted
by $p_k(n)$. We let  $p(n,r)$ denote the number of partitions $\lambda
\vdash n$ with the smallest part $ \ge r$.

Now we define certain families of partitions. The set ${\cal D}_n$ consists of partitions $\lambda \vdash n$ with distant parts. We say that such a
partition has 1-distant parts and we let $p^{(1)}(n)(=|{\cal D}_n|)$ denote the number of such partitions $\lambda \vdash n$. Similarly we set 
\begin{eqnarray*}
{\cal D}_n^d &:= &\{(\lambda_1, \lambda_2, \ldots ,\lambda_l) : \lambda_i-\lambda_{i+1} \ge d\}, \text{ and} \\
p^{(d)}(n)&:=&|{\cal D}_d|.
\end{eqnarray*}
We say that elements of ${\cal D}_n^2$ have 2-distant parts while
elements of ${\cal D}_n^3$ have 3-distant parts.

Let $l_{i,q}(\lambda)$ denote the number of parts of a partition
$\lambda$ congruent to $i\pmod q$. In particular,
$l_o(\lambda)=l_{1,2}(\lambda)$ is the number of odd parts of a
partition.

\begin{definition}
Let $e(\lambda)$ be the smallest even part of a partition $\lambda \vdash n$ or, in case of a partition with all parts odd, we set $e(\lambda):=l_o(\lambda)+2$. Partitions with distant parts and obeying the property $e(\lambda) > 2l_o(\lambda)$ we call polarized partitions.
\end{definition}

We let $\hat{p}^{(1)}(n)$ denote the number of polarized partitions $\lambda \vdash n$,
$$\hat{p}^{(1)}(n):=|\{ \lambda \in {\cal D}_n :e(\lambda)>2l_o(\lambda)  \}|.$$ 

It is known that the number of partitions of $\lambda \vdash n$ with $d$-distant parts equals the number of partitions $\mu \vdash n$ with $1$-distant parts fulfilling the following constraint: the smallest part that is congruent to $i\pmod d$ is greater than $$d\sum_{j=1}^{i-1} l_{j,d}(\mu),$$ $1 \leq i \leq d$ \cite{Bre}. Namely, given a  partition with $d$-distant parts, subtract $q$ from the second smallest part, than $2q$, $3q$, $\ldots$ from the subsequent smallest parts. During this operation, the parts of resulting partition keep the same congruence condition with respect to $q$ whereas the weight of the partition is decreased and the $d$-difference is lost. The opposite can be done in a unique way. On the other hand, the similar procedure leads to the same resulting partition starting with a partition with $1$-distant parts satisfying the condition above. These two facts prove the identity above.

Note that for $d$=$2$ the previous sum is reduced to only one term, resulting with $2l_o(\mu)$. In this case the number of partitions with $2$-distant parts equals the number of partitions with 1-distant parts and with every even part, if there are any, greater than twice the number of odd parts. This polarization, expressed by the next theorem, is of additional interest since it interprets the left hand side of the first Rogers-Ramanujan identity \cite{AE, BoPa,MM}. 

\begin{figure}[H]
\begin{center}
\includegraphics[width=350pt]{Fig1.eps}
\end{center}
\caption{The map (12,10,7,4,1) $\mapsto$ (12,10,6,5,1). Resulting partition consists of $1$-distant parts, having 3 even and two odd parts. \label{Fig1}}
\end{figure}

The proof is illustrated by the Young diagrams in Figure~\ref{Fig1}.
Arrange the diagram in a way the left margin has two dots extra
indentation per row. Draw the line of justification (of the original
diagram) in such a way that in the last row one point remains on the
left side of the line. Now rearrange the rows on the right side of the
normal line: firstly put odd parts in descending order and then even
parts in decreasing order too. As a result we have a new partition
starting with even parts. Every row has size at least $2k$--1, where
$k$ is counted from the bottom of the diagram. This means, if diagram
possessed $k$ odd parts then the smallest even part is at least
($2k$-$1$)+$2$+$1$.

In order to prove that this correspondence is invertible, we start with
adjusted left margin as in the previous consideration. Now we have to
explain that all rows intersect the normal line. The condition
$e(\mu)>2l_o(\mu)$ ensures that the smallest even part intersects
the line. Having in mind that even parts are mutually different by $2$
or more, all other even parts intersect the justification line. In
the following theorem we show this proof more explicitly.

\begin{theorem}\label{Thm1}
The number of partitions $\lambda \vdash n$ with $2$-distant parts is equal to the number of polarized partitions $\mu \vdash n$,
\begin{equation}
p^{(2)}(n)=\hat{p}^{(1)}(n).
\end{equation}
\end{theorem}

\begin{proof}
Suppose that $\lambda$ has $j$ odd parts, at indexes $b_1<b_2< \cdots <b_j$, where $\lambda_{b_1} \le \cdots \le \lambda_{b_j}$, and thus $k-j$ even parts, at indexes $c_1 < c_2 \cdots < c_{k-j}$, where $\lambda_{c_1} \le \cdots \le \lambda_{c_{k-j}}$.

Then the decreasing rearrangement of 
$$\lambda_{b_1}-2b_1+2, \lambda_{b_2}-2b_2+4, \ldots , \lambda_{b_j}-2b_j+2j, \enspace \lambda_{c_1}-2c_1+2j+2, \ldots, \lambda_{c_{k-j}}-2c_{k-j}+2k$$ 
is a partition with distant parts, again with $j$ odd and $k-j$ even parts. The new partition has distant parts. Namely, 
\begin{eqnarray*}
(\lambda_{b_{i+1}}-2b_{i+1}+2(i+1) ) - (\lambda_{b_i}-2b_i+2i) &=&(\lambda_{b_{i+1}} - \lambda_{b_i} )-2(b_{i+1}-b_i)+2 \\
&\ge& 2, 
\end{eqnarray*}
as $\lambda_{b_{i+1}} \ge \lambda_{b_i}+2(b_{i+1}-b_i)$ since the original partition had 2-distant parts, $1 \le i < j$. The same reasoning holds true for even parts.

The smallest even part of the original partition $\lambda_{c_1}$ is greater than or equal to $2c_1$, twice its index. Therefore the smallest even part of the new partition, $\lambda_{c_1}-2c_1+2j+2$, is strictly greater than $2j$, twice the number of odd parts in the new partition.
\end{proof}

For the purpose to take an insight into the nature of partitions $\lambda \vdash n$ with $d$-distant parts, note that they are in one to one correspondence with the partitions $\mu$ such that
\begin{description}
\item [(i)] $\mu \in {\cal S}_{n}^d$, ${\cal S}_n^d:=\{\mu : \mu \in {\cal P}_n, \mu_{min} \ge 1+(l(\mu)-1)q/2\}$ when $d$ is even, 
\item [(ii)] $\mu \in {\cal S}_n^d \cap {\cal D}_n $ when $d$ is odd; $q=d-[d=odd]$.
\end{description}
Namely, for $d$ even we have
\begin{eqnarray*}
1+(1+d)+\cdots+(1+(l-1)d)&=&l+d{ l \choose 2}\\
&=&l \left(1+\frac{(l-1)d}{2} \right),
\end{eqnarray*} 
and analogously when $d$ is odd. Let $p^{sd}(n):=|{\cal S}_n^d|$.

In particular, we have
\begin{eqnarray}
p^{(2)}(n)&=&p^{s2}(n)\\
p^{(3)}(n)&=&p^{(1){s2}}(n)
\end{eqnarray}
meaning that partitions with 2-distant parts are equinumerous to the partitions having exactly one Durfee square. On the other hand, partitions with 3-distant parts are equinumerous to the partitions having exactly one Durfee square but with distant parts. These facts allow to represent $p^{(d)}(n)$ as the sum either of regular partitions (when $d$ is even) or partitions with 1-distant parts ($d$ odd). For $d=2$ and $3$ it follows immediately:
\begin{eqnarray}
p^{(2)}(n)&= &\sum_{i^2 \leq n} \sum_{j \leq i}   p_j(n-i^2)\\
p^{(3)}(n)&= &\sum_{i^2 <n} \sum_{j = i-1,i }   p^{(1)}_j(n-i^2).
\end{eqnarray}





\section{The maximal length of a $d$-distant partition}

We let $l(n,d)$ denote the length $l(\lambda)$ of the longest partition $\lambda \in {\cal D}_n^d$. Obviously, for the partitions having $2$-distant parts the minimal number $n=|\lambda|, \enspace \lambda \in {\cal D}_n^2 $, $l(n,2)$=$2$ is $4$ since $1+3=4$. The minimal $n$ with length $3$ is $9$ since $1+3+5=9$ etc. Thus, for every square number $m$, the maximal length increases by $1$ in respect to the previous square number, 
$$l(m,2)=l((\sqrt{m}-1)^2,2)+1.$$ 
Consequently, the next relation follows:
\begin{eqnarray}
l(n,2)= \big\lfloor\sqrt{n} \big\rfloor.
\end{eqnarray}
This rule is generalized in the next lemma.

\begin{lemma}
Let $\lambda \in {\cal D}_n^d$. Then the maximal length $l(n,d)$ of $\lambda \vdash n$ is as follows:
\begin{eqnarray}
l(n,d)= \Bigg\lfloor \frac{d-2+\sqrt{(d-2)^2+8dn}}{2d} \Bigg \rfloor.
\end{eqnarray}
\end{lemma}

\begin{proof}
Let $n$ be the smallest number with property $l(n,d)=l(n-1,d)+1$. Then, the value of the $d$-distant partition $\lambda$, $n \leq |\lambda| < n+q$, $q$ being non-negative integer, corresponds to the largest integer smaller than or equal to the sum of $m$ numbers $1, (1+d), (1+2d), \ldots ,(dm-(d-1))$. This sum equals $\frac{m(dm-d+2)}{2}$, which leads to the quadratic equation 
$$dm^2-(d-2)m-2n=0.$$ 
Since $l(n,d)=\lfloor m \rfloor$ the statement of lemma follows immediately.
\end{proof}





\section{The main result}

The result of Bressoud, mentioned above, of which Theorem \ref{Thm1} is a special case, gives identities between partitions with $d$-distant parts and partitions with 1-distant parts having parts separated by certain congruence condition. In particular, when $d$=$2$ this condition is reduced to $\equiv$ $0,1\pmod 2$, separating a partition into even and odd parts. Here we extend these ideas of the polarization of partition. More precisely, we show that there is one to one correspondence between partitions with $d$-distant parts, where $d>2$, and partitions with 1-distant parts having even parts, if there are any, greater than twice the number of odd parts.

\begin{theorem}\label{Thm2}
The number of partitions $\lambda \vdash n$ with $3$-distant parts is equal to the sum of numbers of polarized partitions of various lengths $\mu_i \vdash n-{ i \choose 2}$, $l(\mu_i)=i, \enspace i=1, \ldots ,l(n,3)$,
\begin{equation}
p^{(3)}(n)= \sum_{i \ge 1 } \hat{p}^{(1)}_i \left(n- { i \choose 2}\right). 
\end{equation}
\end{theorem}

\begin{proof}
We arrange the starting partition $\lambda \vdash n$ in the same manner as in the proof of Theorem \ref{Thm1}, thus obtaining rows on the left side of the line of justification are shifted by two. Since the partition $\lambda$ consists of 3-distant parts this means that rows on the right side of vertical line are spaced at least by 1, as Figure \ref{Fig2} presents. In case the last row possesses two or more spaces, we have Sylvester triangle with side $l(\lambda)$ on the right side (see Corollary \ref{Cor1} and Figure \ref{Fig3}). However, this is not the general case but the triangle with side $l(\lambda)$--1.

Extracting the triangular partition $$\nu_i \vdash \frac{i(i-1)}{2}, \enspace i=l(\lambda)$$  form $\lambda$, we obtain partition $\mu_i \in {\cal D}_{|\lambda|-{ i \choose 2}}$. Furthermore, the proof is completed by the same reasoning as in Theorem \ref{Thm1}.
\end{proof}


\begin{figure}[ht]
\includegraphics[width=\textwidth]{Fig2.eps}
\caption{The partition $\lambda = (13,9,5,2)$ after extracting the Sylvester's triangle and rearranging rows is mapped to $\mu = (10,6,4,3), \enspace |\mu|=29-6=23$. \label{Fig2}}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=200pt]{Fig3.eps}
\end{center}
\caption{When the smallest part of a partition with 3-distant parts is equal to or greater than $2$ the side of a Sylvester triangle equals the length of the starting partition. \label{Fig3}}
\end{figure}


Thus, the number of partitions $\lambda \vdash n$ with 3-distant parts equals the sum of partitions $\mu_i \vdash m_i$ with 1-distant parts and with the smallest even part greater than $2l_o(\mu_i)$ (if partition has any even part); $m_i=|\mu_i|=n-i(i-1)/2$, $l(\mu_i)=i$ for every $i=1,2, \ldots ,l(n,3)$, i.e., terms in the sum represent the partition $\mu_i$ that arises by subtracting the Sylvester's triangle $\frac{i(i-1)}{2}$ from the $\lambda$.

As an example, we calculate the number of partitions with 3-distant parts for $n$=$15$. First, note that the partition $\lambda =(n)$ gets mapped into itself, which means that the first term in the sum in Theorem \ref{Thm2} is always 1. So, according to Theorem \ref{Thm2}, for this particular case we have
\begin{eqnarray*}
p^{(3)}(15)&=&1+\hat{p}^{(1)}_2(14)+\hat{p}^{(1)}_3(12)\\
&=&1+6+3 \\
&=&10.
\end{eqnarray*}
The all 6 partitions of 14 of length 2 has even parts greater than the number of odd parts, whereas 3 out of 7 partitions of 12 having length 3 are in line with the condition.

\begin{corollary}\label{Cor1}
The number of partitions $\lambda \vdash n$ with $3$-distant parts and with the smallest part at least $2$ is equal to the sum of numbers of polarized partitions of various lengths $\mu_i \vdash n-\frac{i(i+1)}{2}$, $l(\mu_i)=i, \enspace i=1,2, \ldots $
\begin{equation}
p^{(3)}(n, 2)= \sum_{i \ge 1 } \hat{p}^{(1)}_i \left(n- \frac{ i(i+1)}{2} \right). 
\end{equation}
\end{corollary}

An argument analogous to the proof of Theorem \ref{Thm2} proves identities for partitions with $d$-distant parts. Therefore, when $d=4$ we have
\begin{equation}
p^{(4)}(n)= \sum_{i \ge 1 } \hat{p}^{(1)}_i(n + i -i^2) 
\end{equation}
with the corollary
\begin{equation}
p^{(4)}(n,2)= \sum_{i \ge 1 } \hat{p}^{(1)}_i(n-  i^2). 
\end{equation}
As the Figure \ref{Fig4} illustrates, for the extracted partition we have
\begin{eqnarray*}
1+2+3+\cdots+(l-1)&=&{l \choose 2}\\
(d-2)+(2d-4)+(3d-6)+\cdots+(l-1)(d-2)&=&(d-2){l \choose 2}\\
\end{eqnarray*}
for $d=3$ and for general case, respectively, where $l$ is the length of a starting partition. So, for any $d$ we keep $2$-distant parts on the left side of the justification line, which means that these parts are odd. After applying 
\begin{description}
\item [(i)] subtracting partition $\nu_i \vdash (d-2){ i \choose 2}, \enspace i=1, \ldots ,l(n,d)$; and
\item [(ii)] sorting parts on the right side of the justification line,
\end{description}
we get a partition polarized into even and odd parts. This proves the next theorem.


\begin{figure}[h]
\begin{center}
\includegraphics[width=380pt]{Fig4.eps}
\end{center}
\caption{Extracted partitions for $d=3,4,5$, respectively. \label{Fig4}}
\end{figure}


\begin{theorem}\label{Thm3}
Partitions $\lambda \vdash n$ with $d$-distant parts are equinumerous to polarized partitions $\mu_i \vdash n-(d-2){ i \choose 2}$, $l(\mu_i)=i, \enspace i=1, \ldots ,l(n,d)$,
\begin{equation}
p^{(d)}(n)= \sum_{i \ge 1 } \hat{p}^{(1)}_i(n- (d-2){ i \choose 2}). 
\end{equation}
\end{theorem}

Imagine a partition with $3$-distant parts and a partition with $3$-distant parts where the minimal part is at least $2$. According to Theorem \ref{Thm2} and Corollary \ref{Cor1} there is one to one correspondence between these partitions and a certain polarized partitions. Note that if the starting partitions are of the same length $l$ then the difference between extracted parts is exactly $l$. Obviously, the difference $l$ between extracted parts is always the case when starting partitions have characteristics mentioned above. Thus, the generalization of the previous corollaries is as follows:
\begin{equation}
p^{(d)}(n, 2)= \sum_{i \ge 1} \hat{p}^{(1)}_i \left( 
n-i-  (d-2){ i \choose 2} \right). 
\end{equation}
A similar identity holds for the general case, i.e., when there is any constraint on the minimal part of a partition. Let the starting partition $\lambda$, $l(\lambda)=l$ in our bijection has minimal part equal to $r$. Then the parts on the right side of the justification line that we subtract from the starting partition are 
$$r-1, r-1+(d-2), r-1+2(d-2), \ldots ,r-1+(l-1)(d-2).$$ 
In other words, we subtract $r-1$ rows of the height $l$ more than in the case we consider in the previous theorem, i.e., the subtracted part is 
$$(r-1)l+  (d-2){ l \choose 2}.$$ 
This reasoning leads to the next corollary.

\begin{corollary}\label{Cor2}
Partitions $\lambda \vdash n$ with $d$-distant parts and with the smallest part at least $r$ are equinumerous to polarized partitions $\mu_i \vdash n-(r-1)i-\frac{i(i+1)}{2}$, $\enspace i=1,2,\ldots$
\begin{equation}
p^{(d)}(n, r)= \sum_{i \ge 1} \hat{p}^{(1)}_i(n-(r-1)i-  (d-2){ i \choose 2}). 
\end{equation}
\end{corollary}

Results demonstrated in this paper show that the number $p^{(d)}(n, r)$, $d \ge2, r \ge1, n\ge 0$ can be represented as the sum of numbers of polarized partitions of a certain natural number, with $k$ $1$-distant parts. In other words, there is one to one correspondence between polarized partitions and partitions with $d$-distant parts possibly having a constraint on the minimal part.   

\section{Acknowledgment}

The authors thank the anonymous referee for valuable suggestions that improved the final version of the paper.


\begin{thebibliography}{6}

\bibitem{Aig} M. Aigner, {\it A Course in Enumeration}, Springer, 2007.

\bibitem{An} G. E. Andrews, {\it The Theory of Partitions}, Cambridge University Press, 1998.

\bibitem{AE} G. E. Andrews and K. Eriksson, {\it Integer Partitions}, Cambridge University Press, 2004.

\bibitem{BoPa} C. Boulet and I. Pak,  Combinatorial proof of the
Rogers-Ramanujan and Schur identities, {\it J. Combin. Theory Ser. A}
{\bf 113} (2006), 1019--1030.

\bibitem{Bre} D. M. Bressoud, A new family of partition identities, {\it Pacific J. Math.} {\bf 77} (1978), 71--74.

\bibitem{MM} P. A. MacMahon, {\it Combinatory Analysis}, Vol.~2,
Cambridge University Press, 1916.  Reprint, Chelsea, 1960.

\bibitem{Pak} I. Pak, Partition bijections, a survey, {\it Ramanujan
J.} {\bf 12} (2006), 5--75.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11P84; Secondary 05A17.

\noindent \emph{Keywords: } integer partition, partition identity, direct bijection, Durfee square, Rogers-Ramanujan identity.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A003106},
\seqnum{A003114}, and
\seqnum{A025157}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 14 2014;
revised versions received September 1 2014; October 24 2014.
Published in {\it Journal of Integer Sequences}, November 7 2014.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in



\end{document}

.