Combinatorial Proof of the Minimal Excludant Theorem

Abstract

The minimal excludant of a partition $\lambda$, $\mathrm{mex}(\lambda )$, is the smallest positive integer that is not a part of $\lambda$. For a positive integer $n$, $\sigma \mathrm{mex}(\mathrm{n})$ denotes the sum of the minimal excludants of all partitions of $n$. Recently, Andrews and Newman obtained a new combinatorial interpretations for $\sigma \mathrm{mex}(\mathrm{n})$. They showed, using generating functions, that $\sigma \mathrm{mex}(\mathrm{n})$ equals the number of partitions of $n$ into distinct parts using two colors. In this paper, we provide a purely combinatorial proof of this result and new properties of the function $\sigma \mathrm{mex}(\mathrm{n})$. We generalize this combinatorial interpretation to ${\sigma }_r\mathrm{mex}(\mathrm{n})$, the sum of least $r$-gaps in all partitions of $n$. The least $r$-gap of a partition $\lambda$ is the smallest positive integer that does not appear at least $r$ times as a part of $\lambda$.

15 pages; this version includes a combinatorial proof of the generalization