%% 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]{FPSAC2020}
\articlenumber{23}
\addbibresource{fpsac.bib}
%% 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{amssymb,amsmath,color}
\usepackage{amsthm}
\usepackage{url}
\usepackage{tikz,subcaption}
\usepackage[enableskew]{youngtab}
\usepackage{ytableau,varwidth}


\usepackage{float}

\definecolor{red}{rgb}{1,0,0}
\definecolor{blue}{rgb}{.2,.2,.8}
\newcommand{\ccom}[1]{{\color{red}{CB: #1}} }
\newcommand{\mcom}[1]{{\color{blue}{MM: #1}} }

\def\a{\alpha}
\def\b{\beta}
\def\l{\lambda}
\def\m{\mu}
\def\d{\delta}
\def\T{\mathcal T}
\def\S{\mathcal S}
\def\C{\mathcal C}
\def\B{\mathcal B}
\def\A{\mathcal A}
\def\D{\mathcal D}
\def\O{\mathcal O} 
\def\P{\mathcal P} 
\def\E{\mathcal E}
\def\P{\mathcal P}
\def\MD{\mathcal{MD}}
\def\MDS{\mathcal{DD}}
\def\OD{\overline{\mathcal{D}}}
\def\c{\circ}
\def\bu{\bullet}
\def\vp{\varphi}
\def\ve{\varepsilon}
\def\v{\nu}
\def\w{\omega}
\def\mex{\text{mex}}
\def\e{\  }
\def\smex{\sigma \, \mex}
\def\srmex{\sigma_r \, \mex}

\def\tl{\tilde \l}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{corollary}[thm]{Corollary}
\newtheorem{proposition}[thm]{Proposition}
\crefname{thm}{Theorem}{Theorems}


\theoremstyle{definition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{remark}[thm]{Remark}

\newcommand{\ds}{\displaystyle}


%% define your title in the usual way
\title[The minimal excludant and colored partitions]{The minimal excludant and colored partitions}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Cristina Ballantine and Mircea Merca]{Cristina Ballantine\thanks{\href{mailto:cballant@holycross.edu}{cballant@holycross.edu}.}\addressmark{1} \and Mircea Merca\thanks{\href{mailto:mircea.merca@profinfo.edu.ro}{mircea.merca@profinfo.edu.ro}.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, College of The Holy Cross, Worcester, MA, USA \\ \addressmark{2}Department of Mathematics, University of Craiova, Craiova, Romania and Academy of Romanian Scientists, Bucharest, Romania}

%% put the date of submission here
\received{\today}


%% leave this blank until submitting a revised version
%\revised{}

\abstract{The minimal excludant  of a partition $\l$, $\mex(\l)$, is  the smallest positive integer that is not a part of  $\l$.  For a positive integer $n$,  $ \sigma\,  \mex(n)$ denotes the sum of the minimal excludants of all partitions of $n$. Recently, Andrews and Newman  obtained a new combinatorial interpretation for $\sigma\,  \mex(n)$. They showed, using generating functions,  that $\sigma\, \mex(n)$ equals the number  of partitions of $n$ into distinct parts using two colors. 
 We give a purely combinatorial proof of this result and derive its generalization to the sum of least $r$-gaps. We introduce several new identities connecting the function $\sigma\,  \mex(n)$ to the number of partitions with colored parts satisfying certain congruences. 

}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Partitions, minimal excludant,  least gap in partitions, colored partitions.}


\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{intro}



The minimal excludant  or mex-function of a set $S$ of positive integers is the least positive integer not in $S$. The history of this notion goes back to at least the 1930s when it was  applied  to  combinatorial game theory \cite{S35, G39}. 

Recently, Andrews and Newman \cite{AN19} considered the $\mex$-function applied to integer partitions. 
They defined the minimal excludant of a partition $\l$, $\mex(\l)$, as the smallest positive integer that is not a part of  $\l$. 
Then, for each positive integer $n$, they defined 
$$ \sigma\,  \mex(n) := \sum_{\l\in \P(n)} \mex(\l),$$
where $\P(n)$ is the set of all partitions of $n$.  Elsewhere in the literature, the minimal excludant  of a partition  $\l$  is referred to as the least gap or smallest gap of $\l$.  An exact and asymptotic formula for $\sigma\,  \mex(n)$, as well as its generating function, is given in \cite{GK06}.   In \cite{BM19} we studied a generalization of $\sigma\,  \mex(n)$ and its connection to polygonal numbers. 

Let $\D_2(n)$ be the set of partitions of $n$ into distinct parts using two colors and let $D_2(n)=|\D_2(n)|$. We denote the colors of the parts of partitions in $\D_2(n)$ by $0$ and $1$.  For example, $\D_2(4)=\{4_0,\, 4_1, \,  3_0+1_0, \, 3_0+1_1,\, 3_1+1_0,\, 3_1+1_1, \, 2_1+2_0, \, 2_1+1_1+1_0, \, 2_0+1_1+1_0\}$, and thus $D_2(4)=9$.  In \cite{AN19}, the authors give two proofs of  the following theorem. 
\begin{thm} \label{T1} Given an integer $n \geqslant 0$, we have $\sigma\, \mathrm{mex}(n)=D_2(n).$
\end{thm}  

In \cref{combAN},  we provide a bijective proof of \cref{T1}. 
We make use of the fact  that \begin{equation}\label{smex as sum} \sigma \, \mex(n)=\ds\sum_{j\geqslant 0} p(n-j(j+1)/2),\end{equation} where, as usual, $p(n)$ denotes the number of partitions of $n$.
A combinatorial  proof of  \eqref{smex as sum} is given  in \cite[Theorem 1.1]{BM19}.    The same argument is also described in the second proof of \cite[Theorem 1.1]{AN19}. In fact, the result proven in \cite{BM19} is a  generalization of \eqref{smex as sum} to $\srmex(n)$, the sum of $r$-gaps in all partitions of $n$. The $r$-gap of a partition $\l$ is the least positive integer that does not appear $r$ times as a part of $\l$. In \cref{gen}, we give two generalizations of  \cref{T1} to $\srmex(n)$. 




In \cite{Andrews12}, the authors considered a restricted  $\mex$ function. They defined $M_k(n)$ to be the number of partitions $\lambda$ of $n$ with $\mex(\l)=k$ and  more parts $>k$ than  parts $<k$. 
When $k=1$,  $M_1(n)$ is the number of partitions of $n$ with smallest part greater than $1$. Thus, if $n>0$, we have $M_1(n)=p(n)-p(n-1)$, and  from $\eqref{smex as sum}$, we obtain \begin{equation}\label{T2k=1} \sigma\,  \mathrm{mex}(n) -\sigma\,  \mathrm{mex}(n-1) - \delta(n) 
= \sum_{j=0}^\infty M_1\big(n-j(j+1)/2\big),\end{equation} where $\delta$ is the characteristic function of the set of triangular numbers.



 
We generalize \eqref{T2k=1} in \cref{pfT2} where we  give further connections between $\smex(n)$ and restricted mex functions or partitions and overpartitions. 
In \cref{cop} we present connections with partitions with colored odd parts. 






\section{Combinatorial Proof of \cref{T1}} \label{combAN}

To prove the theorem, we adapt Sylvester's bijective proof of Jacobi's triple product identity \cite{S1882}. 
Given $\l\in\D_2(n)$, let $\l^{(i)}$, $i=0,1$, be the (uncolored) partition whose parts are the parts of color $i$ in $\l$. Then,  $\l^{(1)}$ and  $\l^{(2)}$ are partitions with distinct parts. 
\begin{example} If $\l=4_1+3_0+3_1+2_0+1_0 \in \D_2(13)$, then $\l^{(0)}=3+2+1$ and $\l^{(1)}=4+3$.
\end{example}
Denote by $\eta(j)$  the staircase partition $\eta(j)=j+(j-1)+\cdots +2+1$, with $\eta(0)=\emptyset$. 
We write  $\ell(\l)$ for the number of parts in  partition $\l$. The conjugate of a Ferrers diagram $\nu$ (not necessarily the diagram of a partition) is obtained by reflecting $\nu$ across the main diagonal.  The sum, $\a+\b$, of two composition $\a=(a_1, a_2, \ldots)$ and $\b=(b_1,b_2, \ldots)$, is the composition whose parts are $a_i+b_i$ (appropriately using $0$ as parts  at the end of the shorter composition). 

\begin{definition} Given a diagram of left justified rows of boxes (not necessarily the Ferrers diagram of a partition), the \textit{staircase profile} of the diagram is a zig-zag line starting in the upper left corner of the diagram with a right step and continuing in alternating down and right steps until the end of a row of the diagram is reached. 
\end{definition}

\begin{example} Let $\a$ be the composition  $\a=(1,2,3,7,7,6,6,4,2)$.

\begin{center} \begin{figure}[H]\hspace*{-1cm}\begin{subfigure}{.7\textwidth}\centering\tiny{\begin{tikzpicture}[inner sep=0in,outer sep=0in]\node (n) {\begin{varwidth}{0cm}{\ydiagram{1,2,3,7,7,6,6,4,2}
}\end{varwidth}};
\draw[ultra thick] (-0,1.44)--(0.315,1.44)-- (0.315,1.13)--(.635,1.13)--(.635,.82)--(0.96,.82)--(0.96,.51)--(1.28,.51)--(1.28,.2)--(1.63,.2)--(1.63,-0.13)--(1.945,-0.13) ; 
 \end{tikzpicture}}\end{subfigure}\hspace*{-.5cm}\begin{subfigure}{.5\textwidth}
\scriptsize{\begin{tikzpicture}[inner sep=0in,outer sep=0in]\node (n) {\begin{varwidth}{0cm}{\young(\e\e\e\e\e\e\e\e\e,:\e\e\e\e\e\e\e\e,::\e\e\e\e\e\e,:::\e\e\e\e\e,:::\e\e\e\e,:::\e\e\e\e,:::\e\e)
}\end{varwidth}}; 
\end{tikzpicture}}\hspace*{-.5cm}\end{subfigure}\caption{Staircase profile for $\a$ and the conjugate of $\a$.}\label{fsp}\end{figure}\end{center}
\end{example} 

The \textit{shifted Ferrers diagram} of a partition $\l$ with distinct parts is the Ferrers diagram (with boxes of unit length) of $\l$   with  row $i$  shifted $i-1$ units to the right.

We create a map $$\vp:\bigcup_{j \geqslant 0} \P(n-j(j+1)/2)\to\D_2(n)$$ as follows. 
Start with $\l\in \P(n-j(j+1)/2)$ for some $j\geqslant 0$. Append a diagram with rows of lengths $1, 2, \ldots j$ (i.e., the  diagram of $\eta(j)$ rotated by $90^\circ$ counterclockwise) at the top of the  diagram of $\l$. We obtain a diagram with $n$ boxes. Draw the staircase profile of the new diagram. Let $\a$ be the partition whose parts are the length of the columns to the left of the staircase profile and  $\b$ be the partition whose parts are the length of the rows to the right of the staircase profile. Then $\a$ and $\b$ are partitions with distinct parts. Moreover, $j\leqslant \ell(\a)- \ell(\b)\leqslant j+1$. Color the parts of $\a$ with color $j\!\!\pmod 2$ and the parts of $\b$ with color $j+1\!\!\pmod 2$. Then $\vp(\l)$ is defined as the 2-color partition of $n$ whose parts are the colored parts of $\a$ and $\b$. 


Conversely, start with  $\mu\in \D_2(n)$. Let $\ell_i(\m)$, $i=0,1$, be the number of parts of color $i$ in $\m$ and  set $r=\ell_0(\m)-\ell_1(\m)$. 
Let $$  \ \  \ve=\begin{cases} 0 & \mbox{ if } r\geq 0\\ 1 & \mbox{ if } r< 0, \end{cases} \ \ \mbox{  and }\ \ 
 j=|r|+\ds\frac{(-1)^{|r|+\ve}-1}{2}.$$
 Remove the top $j$ rows (i.e., the rotated  diagram of $\eta(j)$) from the conjugate of the shifted diagram of $\m^{(\ve)}$ to obtain a composition $\gamma$. Define $\vp^{-1}(\m)= \gamma+\m^{(s)}$ where $s\neq \ve$. Then,  $\vp^{-1}(\m)\in \P(n-j(j+1)/2)$.
 \begin{example} Let $n=38, j=3$, and let $\l=7+7+6+6+4+2$ be a partition of $n-j(j+1)/2=32$. We add the rotated  diagram of $\eta(3)$ to the top of the  diagram of $\l$ and draw the staircase profile (see \cref{fsp}). Then $\a=9+8+6+5+3+2$ and $\b=3+2$. Since $j$ is odd, we have $\vp(\l)=9_1+8_1+6_1+5_1+3_1+3_0+2_1+2_0$. 
 
Conversely, suppose $\mu=9_1+8_1+6_1+5_1+3_1+3_0+2_1+2_0\in \D(38)$. Then $\ell_0(\mu)=2$ and $\ell_1(\mu)=6$. We have $r=\ell_0(\m)-\ell_1(\m)=-4$ and $j=3$.  We remove the first $3$ rows from the conjugate of the shifted diagram of $\mu^{(1)}$ (which is precisely the diagram below the staircase profile in \cref{fsp}) and add the resulting composition $\gamma$ to $\m^{(0)}=(3,2)$. We obtain $\vp^{-1}(\mu)=7+7+6+6+4+2\in \P(32)$. 
\end{example}


\section{Generalizations of \cref{T1} to r-gaps} \label{gen}

 Recall that the $r$-gap of a partition $\l$ is the least positive integer that does not appear $r$ times as a part of $\l$. In \cite{BM19}, we proved combinatorially that \begin{equation}\sigma_r \, \mex(n)=\sum_{j \geqslant 0}p(n-rj(j+1)/2). \end{equation} We can employ a transformation similar to that in  the combinatorial proof of \cref{T1} to prove its generalization to sums of $r$-gaps. 

Let $\widetilde D_3^{(r)}(n)$ be the number of partitions $\l$ of $n$ into distinct parts using three colors, $0,1$, and $2$, such that: 
\begin{enumerate}
	\item[(i)] The set of parts of  color $2$  is either empty or  $\{t(r-1)\mid 1\leqslant t\leqslant j\}$ for some $j\geqslant 1$.
		\item[(ii)] $\ell_{j \!\!\pmod 2}(\l)-\ell_{j+1 \!\!\pmod 2}(\l) \in \{j, j+1\}$, where $j=0$ if $\l^{(2)}=\emptyset$.
	
	\end{enumerate}


\begin{thm} Let $n,r$ be integers with $r>0$ and $n\geqslant 0$. Then $\sigma_r \, \mex(n)=\widetilde D_3^{(r)}(n).$
  \end{thm}
  
  

\begin{proof}For a sketch of the proof see \cite{BM19b}. \end{proof}

In \cite{BM19} we give the generating function for $\sigma_r \, \mex(n)$, namely \begin{equation}\label{sr} \sum_{n=0}^\infty\sigma_r \, \mex(n)q^n=\frac{(q^{2r};q^{2r})_\infty}{(q;q)_\infty (q^r;q^{2r})_\infty},\end{equation} where $(a;q)_n = \prod\limits_{k=0}^{n-1} (1-aq^k)$ if $n>0$,  $(a;q)_n=1$ if $n=0$, and $(a;q)_\infty  =\ds \lim_{n\to \infty}(a;q)_n$.

Denote $\widetilde D_2^{(r)}(n) $  the number of partitions $\l$ of $n$  using two colors, $0$ and $1$, such that: 
\begin{enumerate}
\item[(i)] $\l^{(0)}$ is a partition into distinct parts divisible by $r$. 
\item[(ii)]  $\l^{(1)}$ is a partition with parts repeated at most $2r-1$ times.
\end{enumerate}

The following generalization of \cref{T1} is immediate from \eqref{sr}. 

\begin{thm} 
 Let $n,r$ be integers with $r>0$ and $n\geq 0$. Then $\sigma_r \, \mex(n)=\widetilde D_2^{(r)}(n).$ \end{thm} 

	
\section{Identities involving restricted $\mex$-functions} \label{pfT2}

In this section we introduce identities relating $\smex(n)$ and restricted $\mex$ functions for partitions and overpartitions. 

\subsection{$\smex(n)$ and $M_k(n)$}

We have the follwing   generalization of \eqref{T2k=1}. 



\begin{thm}\label{T2}
	Let $k, n$ be integers with  $k\geqslant 1$ and $n\geqslant 0$. Then,
	$$
	 (-1)^{k-1} \left( \sum_{j=-(k-1)}^k (-1)^j \sigma\, \mathrm{mex}\big(n-j(3j-1)/2\big) - \delta(n) \right) 
	 = \sum_{j=0}^\infty M_k\big(n-j(j+1)/2\big).$$
\end{thm} 
The following infinite family of linear inequalities involving $\sigma\, \mathrm{mex}$ is immediate.


\begin{corollary}
	Let $k$ be a positive integer. Given an integer $n\geqslant 0$, we have
	\begin{align*}
		& (-1)^{k-1} \left( \sum_{j=-(k-1)}^k (-1)^j \sigma\, \mathrm{mex}\big(n-j(3j-1)/2\big) - \delta(n) \right) \geqslant 0,
	\end{align*}	
	with strict inequality if $n\geqslant k(3k+1)/2$.
\end{corollary}



\begin{proof}[Analytic proof of \cref{T2}]

	In \cite{Andrews12}, the authors gave the following truncated Euler's pentagonal number theorem.
\begin{equation} \label{TPNT}
\frac{(-1)^{k-1}}{(q;q)_\infty} \sum_{n=-(k-1)}^{k} (-1)^{j} q^{n(3n-1)/2}= (-1)^{k-1}+ \sum_{n=k}^\infty \frac{q^{{k\choose 2}+(k+1)n}}{(q;q)_n}
\begin{bmatrix}
n-1\\k-1
\end{bmatrix},
\end{equation}
where
$$
\begin{bmatrix}
n\\k
\end{bmatrix} 
=
\begin{cases}
\dfrac{(q;q)_n}{(q;q)_k(q;q)_{n-k}}, &  \text{if $0\leqslant k\leqslant n$},\\
0, &\text{otherwise.}
\end{cases}
$$
Multiplying both sides of \eqref{TPNT} by
$$
\frac{(q^2,q^2)_\infty}{(q,q^2)_\infty} = \sum_{n=0}^\infty q^{n(n+1)/2},
$$
and using \eqref{sr} with $r=1$ and the generating function for $M_k(n)$ \cite{Andrews12},
$$
\sum_{n=0}^\infty M_k(n) q^n = \sum_{n=k}^\infty \frac{q^{{k\choose 2}+(k+1)n}}{(q;q)_n}
\begin{bmatrix}
n-1\\k-1
\end{bmatrix},
$$
we obtain
\begin{align*}
& (-1)^{k-1} \left( \bigg( \sum_{n=0}^\infty \sigma\, \mathrm{mex}(n) q^n \bigg) \bigg(  \sum_{n=-(k-1)}^{k} (-1)^{j} q^{n(3n-1)/2}\bigg) -\sum_{n=0}^\infty q^{n(n+1)/2}\right)   \\
& =   \left( \sum_{n=0}^\infty q^{n(n+1)/2} \right) \left( \sum_{n=0}^\infty M_k(n) q^n\right).
\end{align*}
The proof follows easily using Cauchy's multiplication of two power series.\medskip
\end{proof}

\begin{proof}[Combinatorial proof of \cref{T2}]

The statement of \cref{T2} is equivalent to identity \eqref{T2k=1} together with
\begin{align}
& \sigma \, \mex
\left(n-\frac{k(3k+1)}{2}\right)-\sigma \, \mex
\left(n-\frac{k(3k+5)}{2}-1\right)\nonumber \\
& \qquad\qquad = \sum_{j=0}^\infty \Big(M_k\big(n-j(j+1)/2\big) +M_{k+1}\big(n-j(j+1)/2\big)\Big).\label{T2kequiv}
\end{align}
Using \eqref{smex as sum}, identity \eqref{T2kequiv} becomes
\begin{align}
& \sum_{j=0}^\infty \Bigg(p
\bigg(n-\frac{j(j+1)}{2}-\frac{k(3k+1)}{2}\bigg)-p\bigg(n-\frac{j(j+1)}{2}-\frac{k(3k+5)}{2}-1\bigg)\Bigg)\nonumber \\
& \qquad\qquad = \sum_{j=0}^\infty \Big(M_k\big(n-j(j+1)/2\big) +M_{k+1}\big(n-j(j+1)/2\big)\Big). \label{T2kequiv1} 
\end{align}
Identity \eqref{T2kequiv1} was proved combinatorially in \cite{Y15}. Together with the combinatorial proof of \eqref{smex as sum}, this gives a combinatorial proof of \cref{T2}. 
\end{proof}

Next, we  give a combinatorial interpretation for $\ds  \sum_{t=0}^\infty M_k\big(n-t(t+1)/2\big)$. 
For  integers $k,n$ such that $k\geqslant 1$ and $n\geqslant 0$, we denote by $D^{(k)}_3(n)$  the number of partitions $\mu$ of $n$ into distinct parts using three colors and satisfying the following conditions: 
\begin{enumerate}
	\item[(i)] $\mu$ has exactly $k$ parts of color $2$ and, if $k>1$, twice the smallest part of color $2$ is greater than largest part of color $2$.
	\item[(ii)] With $r$ and $j$ as in the combinatorial proof of \cref{T1}, 	the largest part of color $j \!\!\pmod 2$ must equal $j$ more that the smallest part of color $2$.
\end{enumerate}


\begin{proposition}\label{prop}
For  integers $k,n$ such that $k\geqslant 1$ and $n\geqslant 0$, we have \begin{equation}\label{p1}\sum_{t=0}^\infty M_k\big(n-t(t+1)/2\big)=D^{(k)}_3(n).\end{equation}
\end{proposition}

\begin{proof} See \cite{BM19b}.
\end{proof}

Combining \cref{T1,T2}, and \cref{prop} we obtain the following corollary which, by the discussion above, has both analytic and combinatorial proofs. 

\begin{corollary}
	For  integers $k,n$ such that $k\geqslant 1$ and $n\geqslant 0$, we have 
	%\begin{align*}
	$$(-1)^{\max(0,k-1)} \left( \sum_{j=-\max(0,k-1)}^k (-1)^j \sigma\, \mathrm{mex}\big(n-j(3j-1)/2\big) - \delta(n) \right) \\
	= D^{(k)}_3(n).$$
	%\end{align*}
	
\end{corollary} 


Note that, if $k=0$, the statement of the corollary reduces to \cref{T1}.




\subsection{$\smex(n)$ and  overpartitions} \label{op}

Overpartitions
are ordinary partitions with the added 
condition that the first appearance 
of any part may be overlined.
There are eight overpartitions of $3$:
\[
3, \overline{3}, 2+1, \overline{2}+1, 2+\overline{1}, \overline{2}+\overline{1}, 1+1+1, \overline{1}+1+1.
\]
As usual, we denote by  $\overline{p}(n)$  the number of overpartitions of $n$. The generating function for $\overline{p}(n)$ is 
\[
\sum_{n=0}^\infty \overline{p}(n) q^n=\frac{(-q;q)_\infty}{(q;q)_\infty}.
\]
We have the following identity relating $\smex(n), \overline{p}(n)$ and  $M_k(n)$. 
 \begin{thm}\label{TH2}
	Let $k$ be a positive integer. Given an integer $n\geqslant 0$, we have
	\[
	 (-1)^{k-1} \left( \sum_{j=-(k-1)}^k (-1)^j \overline{p}\big(n-j(3j-1)\big) - \sigma\, \mathrm{mex}(n) \right) 
	 = \sum_{j=0}^{\lfloor n/2 \rfloor} M_k(j) \sigma\, \mathrm{mex}(n-2j).
\]
\end{thm}

\begin{proof}
	By \eqref{TPNT}, with $q$ replaced by $q^2$, we obtain
	\begin{equation}\label{TPNT1}
	\frac{(-1)^{k-1}}{(q^2;q^2)_\infty} \left( \sum_{n=-(k-1)}^{k} (-1)^{j} q^{n(3n-1)}-1\right) =  \sum_{n=k}^\infty M_k(n) q^{2n}.
	\end{equation}
	Multiplying both sides of \eqref{TPNT1} by the generating function for $\smex(n)$,
	we obtain
	\begin{align*}
& (-1)^{k-1} \left( \bigg( \sum_{n=0}^\infty \overline{p}(n) q^n \bigg) 
        \bigg(  \sum_{n=-(k-1)}^{k} (-1)^{j} q^{n(3n-1)}\bigg) 
        -\sum_{n=0}^\infty \sigma\, \mathrm{mex}(n) q^n \right)   \\
& =   \left( \sum_{n=0}^\infty \sigma\, \mathrm{mex}(n) q^n \right) \left( \sum_{n=0}^\infty M_k(n) q^{2n}\right).
\end{align*}
   The proof follows by equating the coefficients of $q^n$ in this identity. 
\end{proof}

The limiting case $k\to\infty$ of \cref{TH2} reads as follows.

\begin{corollary}
	For $n\geqslant 0$,
	$
	\sigma\, \mathrm{mex}(n)  = \ds \sum_{j=-\infty}^\infty (-1)^j \overline{p}\big(n-j(3j-1)\big).
	$
\end{corollary}

\begin{remark}Since it is known that $\overline{p}(n)$ is odd if and only if $n=0$, it follows that   $\sigma\, \mathrm{mex}(n)$ is odd if and only if $12n+1$ is a square.\end{remark}

In \cite{AM18},  the authors denoted by  $\overline{M}_k(n)$ the number of overpartitions 
of $n$ in which the first part larger than $k$ appears at least $k+1$ times. 
We have the following identity.
\begin{thm}\label{T3}
	For integers $k,n>0$, we have
	\[
	 (-1)^k \left( \sigma\, \mathrm{mex}(n) + 2\sum_{j=1}^{k} (-1)^j \sigma\, \mathrm{mex}(n-j^2) - \delta'(n)\right) 
	 =\sum_{j=-\infty}^\infty (-1)^j  \overline{M}_k\big(n-j(3j-1)\big),
\]
	where % $\delta$  is the characteristic function of the set of twice generalized pentagonal numbers, i.e.,
$\delta'(n)=	(-1)^m$ if $n=m(3m-1)$, $m\in\mathbb{Z}$ and $\delta'(n)=0$ otherwise. 
	\end{thm}

\begin{proof} The proof, given in \cite{BM19b}, follows from a truncated theta series identity
	 \cite{AM18}. 
\end{proof}

There is a substantial amount of numerical evidence  to conjecture the following inequality.

\begin{conjecture}\label{T4}
	For $k,n>0$,
	\begin{align*}
	\sum_{j=-\infty}^\infty (-1)^j  \overline{M}_k\big(n-j(3j-1)\big)\geqslant 0,
	\end{align*}
	with strict inequality if $n\geqslant (k+1)^2$.
\end{conjecture}

A combinatorial interpretation for the sum in this conjecture would be  interesting.
 








\subsection{$\smex(n)$ and  partitions into distinct parts} \label{dist}
To keep notation uniform, let $D_1(n)$ be the number of partitions of $n$ into distinct parts. Set $D_1(x)=0$ if $x$ is not a positive integer. For proof of the next theorem see  \cite{BM19b}.

\begin{thm}\label{T5}
	For any integer $n\geqslant 0$, we have
	\begin{equation}\label{sumdist}
	\sum_{j=0}^\infty (-1)^{j(j+1)/2} \sigma\, \mathrm{mex}\big(n-j(j+1)/2 \big)
	= \sum_{j=0}^\infty D_1\left( \frac{n-j(j+1)/2}{2}\right). 
	\end{equation}
\end{thm}


 Let $D_2^*(n)$ be the 
 number of partitions of $n$ with distinct parts using two colors such that: (i)  parts of color $0$ form a gap-free partition (staircase) and (ii)
only even parts can have color $1$. 
Then, we have the following identity of Watson type \cite{BM19a} which gives  a combinatorial interpretation for the  right hand side of \eqref{sumdist}. For its proof see \cite{BM19b}.

\begin{proposition}
	For $n\geqslant 0$,
	$$\sum_{j=0}^\infty D_1\left( \frac{n-j(j+1)/2}{2}\right)= D_2^*(n).$$	
\end{proposition}




In \cite{AM18}, the authors denoted by  $MP_k(n)$ 
the number of partitions of $n$ in which the first part larger than $2k-1$	is odd and appears exactly $k$ times.
All other odd parts appear at most once. We have the following truncated form of \cref{T5}.
\begin{thm}\label{T6}
	For integers $n,k>0$,
$$
	 (-1)^{k-1} \left( \sum_{j=0}^{2k-1} (-1)^{j(j+1)/2} \sigma\, \mathrm{mex}\big(n-j(j+1)/2 \big) -D^*_2(n) \right) 
	 = \sum_{j=0}^n MP_k(j) D^*_2(n-j).
$$
\end{thm}

\begin{proof} The proof, given in \cite{BM19b}, follows from the truncated theta series identity of 
	 \cite{AM18}. 
\end{proof}

A combinatorial interpretation for 
$\ds \sum_{j=0}^n  MP_k(j) D^*_2(n-j) $
would be very welcome.


The following corollary of \cref{T6} is immediate.
\begin{corollary}
		For integers $n,k>0$,
	\begin{align*}
	(-1)^{k-1} \left( \sum_{j=0}^{2k-1} (-1)^{j(j+1)/2} \sigma\, \mathrm{mex}\big(n-j(j+1)/2 \big) -D^*_2(n) \right) \geqslant 0,
	\end{align*}
	with strict inequality if $n\geqslant k(2k+1)$.
\end{corollary}

A second corollary involves the function $\mathrm{pod}(n)$, the number of partitions of $n$ in which odd parts are not repeated, i.e.,

\begin{corollary}
	For $n\geqslant 0$,
	$ 
	\ds \sigma\, \mathrm{mex}(n) = \sum_{j=0}^n  \mathrm{pod}(j) D^*_2(n-j).
	$	
\end{corollary}


\section{$\smex(n)$ and partitions with colored odd parts }\label{cop}

In this section we present several identities relating $\smex(n)$ with the number of partitions of $n$ in which odd parts  are colored in with $j$ colors, $j=2,3,4$. Elsewhere in the literature, colored partitions are referred to as vector partitions. Due to space restrictions, we will present the proofs of all theorems in this section in a future article. 

\subsection{Three colors for the odd parts} 

Let $C_3(n)$ be the number of partitions of $n$ using $3$ colors for the odd parts and let $C'_3(n)$ be the number of partitions of $n$ into parts not congruent to $2 \bmod 4$ using $3$ colors for the odd parts.  The  generating functions for $C_3(n)$ and $C'_3(n)$ are respectively
$$\sum_{n=0}^\infty C_3(n) q^n = \frac{1}{(q^2;q^2)_\infty (q;q^2)_\infty^3}\ \ \mbox{and} \ \ \sum_{n=0}^\infty C'_3(n) q^n = \frac{1}{(q^4;q^4)_\infty (q;q^2)_\infty^3}.$$ Using  the truncated Euler's pentagonal number theorem \cite{Andrews12}, we prove the following identity which relates $C_3(n)$ and the function $M_k(n)$ defined in \cref{intro}.
\begin{thm}\label{TH1}
	Let $k$ be a positive integer. Given an integer $n\geqslant 0$, we have
	$$
	(-1)^{k-1} \left( \sum_{j=-(k-1)}^k (-1)^j C_3\big(n-j(3j-1)/2\big) - \sigma\, \mathrm{mex}(n) \right) 
	 = \sum_{j=0}^n \sigma\, \mathrm{mex}(j) M_k(n-j).
$$
\end{thm}

A combinatorial
interpretation of
$
\ds \sum_{j=0}^n \sigma\, \mathrm{mex}(j) M_k(n-j)
$ would be appealing. 

The limiting case $k\to\infty$ of \cref{TH1} gives the following decomposition of $\sigma\, \mathrm{mex}(n)$.

\begin{corollary}
	For $n\geqslant 0$, we have
	$
	\sigma\, \mathrm{mex}(n) = \ds \sum_{j=-\infty}^\infty (-1)^j C_3\big(n-j(3j-1)/2\big).
	$
\end{corollary}


 Using  the truncated theta series identity of  \cite{AM18}, we prove the following identity which relates $C'_3(n)$ and the function $MP_k(n)$ of \cref{dist}.


\begin{thm}
		Let $k$ be a positive integer. Given an integer $n\geqslant 0$, we have
	$$
	 (-1)^{k-1} \left( \sum_{j=0}^{2k-1} (-1)^{j(j+1)/2} C'_3\big(n-j(j+1)/2\big) - \sigma\, \mathrm{mex}(n) \right) 	 = \sum_{j=0}^n \sigma\, \mathrm{mex}(j) MP_k(n-j).
$$
\end{thm}

\begin{corollary}
	For $n\geqslant 0$, 
	$
	\sigma\, \mathrm{mex}(n) = \ds \sum_{j=0}^{\infty} (-1)^{j(j+1)/2} C'_3\big(n-j(j+1)/2\big).
	$
\end{corollary}


\subsection{Four colors for the odd parts}

Let $C_4(n)$ be  the number of partitions of $n$ using $4$ colors for the odd parts. The  generating function for $C_4(n)$ is $$\sum_{n=0}^\infty C_4(n) q^n = \frac{1}{(q^2;q^2)_\infty (q;q^2)_\infty^4}.$$ Then, $C_4(n)$ and the function $M_k(n)$ of \cref{op} are related by the next theorem and its corollary. 
\begin{thm}Let $k$ be a positive integer. Given an integer $n\geqslant 0$, we have
	\begin{align*}
	& (-1)^k \left( C_4(n) + 2\sum_{j=1}^{k} (-1)^j C_4(n-j^2) - \sigma\, \mathrm{mex}(n) \right) 
	 =\sum_{j=0}^n C_4(j) \overline{M}_k\big(n-j\big).
	\end{align*}
\end{thm}


\begin{corollary}
	For $n\geqslant 0$,
	$
	\sigma\, \mathrm{mex}(n) =  \ds C_4(n) + 2\sum_{j=1}^{\infty} (-1)^j C_4(n-j^2).
	$
\end{corollary}

Note that the partition functions $\sigma\, \mathrm{mex}(n)$ and $C_4(n)$ have the same parity.



\subsection{Two colors for parts $\not\equiv 0$ mod $4$}

Let $C_2(n)$ be the number of partitions of $n$ using two colors for the parts not congruent to $0 \bmod 4$.
The generating function for $C_2(n)$ is 
$$\sum_{n=0}^\infty C_2(n) q^n = \frac{(q^4;q^4)_\infty}{(q;q)_\infty^2}.$$
The following  identity relating $C_2(n)$ and $\overline{M}_k(n)$ follows from the truncated theta identity of \cite{AM18}.

\begin{thm}Let $k$ be a positive integer. Given an integer $n\geqslant 0$, we have
$$ (-1)^k \left( C_2(n) + 2\sum_{j=1}^{k} (-1)^j C_2(n-2j^2) - \sigma\, \mathrm{mex}(n) \right) 
	 =\sum_{j=0}^{\lfloor n/2 \rfloor}  \overline{M}_k\big(j\big) \sigma\, \mathrm{mex}(n-2j).$$
\end{thm}

\begin{corollary}
	For $n\geqslant 0$,
	$
	\sigma\, \mathrm{mex}(n) = \ds  C_2(n) + 2\sum_{j=1}^{\infty} (-1)^j C_2(n-2j^2).
	$
\end{corollary}
We see that the partition functions $\sigma\, \mathrm{mex}(n)$ and $C_2(n)$ have the same parity.


\subsection{Two colors for the odd parts in partitions into parts $\not \equiv 4$ mod $8$}

We denote by $C^*_2(n)$ the number of partitions of $n$ into parts not congruent to $4 \bmod 8$ using two colors for the odd parts. The generating function for $C^*_2(n)$ is given by
$$
\sum_{n=0}^{\infty} C^*_2(n) q^n = \frac{1}{(q^2,q^6,q^8;q^8)_\infty (q;q^2)_\infty^2}.
$$ The proof of following theorem relating $C^*_2(n)$ and $MP_k$ again uses  results from \cite{AM18}.
\begin{thm}
	Let $k$ be a positive integer. Given an integer $n\geqslant 0$, we have
	$$
	 (-1)^{k-1} \left( \sum_{j=0}^{2k-1} (-1)^{j(j+1)/2} C^*_2\big(n-j(j+1)\big) - \sigma\, \mathrm{mex}(n) \right) 
	 = \sum_{j=0}^{\lfloor n/2 \rfloor} MP_k(j) \sigma\, \mathrm{mex}(n-2j).
	$$
\end{thm}

 
\begin{corollary}
	For $n\geqslant 0$,
	$
	\sigma\, \mathrm{mex}(n) = \ds \sum_{j=0}^{\infty} (-1)^{j(j+1)/2} C^*_2\big(n-j(j+1)\big).
	$
\end{corollary}
 




\printbibliography





\end{document}
