# On the combinatorics of $r$-chain minimal and maximal excludants

Subhash Chand Bhoria  Subhash Chand Bhoria, Department of Mathematics, Pt.
Chiranji Lal Sharma Government College, Urban Estate, Sector-14, Karnal,
Haryana - 132001, India<EMAIL_ADDRESS>,  Pramod Eyyunni  Pramod
Eyyunni, Department of Mathematics, Birla Institute of Technology and Science
Pilani, Rajasthan - 333031, India<EMAIL_ADDRESS>and  Runqiao Li  Runqiao Li, Department of Mathematics, The Pennsylvania State
University, Pennsylvania - 16801, U.S.A<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

The minimal excludant (mex) of a partition was introduced by Grabner and
Knopfmacher under the name ‘least gap’ and was revived by a couple of papers
due to Andrews and Newman. It has been widely studied in recent years together
with the complementary partition statistic maximal excludant (maex), first
introduced by Chern. Among such recent works, the first and second authors
along with Maji introduced and studied the $r$-chain minimal excludants
($r$-chain mex) which led to a new generalization of Euler’s classical
partition theorem and the sum-of-mex identity of Andrews and Newman. In this
paper, we first give combinatorial proofs for these two results on $r$-chain
mex. Then we introduce the $r$-chain maximal excludants ($r$-chain maex) and
establish the associated identity for the sum of $r$-chain maex over all
partitions, both analytically and combinatorially.

$2020$ Mathematics Subject Classification. Primary 05A17, 11P84, 05A19;
Secondary 11P81.
Keywords and phrases. Minimal excludant, maximal excludant, $r$-chain minimal
excludants, $r$-chain maximal excludants, partition identities, bijective
proofs.

##  1\. Introduction

A _partition_ $\lambda$ of a positive integer $n$ is a weakly decreasing
sequence of positive integers
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell})$ such that
$n=\lambda_{1}+\lambda_{2}+\cdots+\lambda_{\ell}$. The terms $\lambda_{i}$ are
called the _parts_ of $\lambda$, and the number of parts of $\lambda$ is
called the _length_ of $\lambda$, denoted by $\\#(\lambda)$. We let
$\mathcal{P}(n)$ represent the collection of partitions of a non-negative
integer $n$ and put $p(n):=|\mathcal{P}(n)|$.

In the mid eighteenth century, Euler proved the following celebrated result on
partitions.

######  Theorem 1.1.

The number of partitions of a positive integer $n$ into odd parts equals the
number of those into distinct parts.

This set in motion the rich area of partition identities. The reader may
consult [1, 10] for more on the history of partition identities. Euler’s
theorem has been generalized by Glaisher [8] and Franklin [7] in the following
manner.

######  Theorem 1.2 (Glaisher).

The number of partitions of $n$ into parts not divisible by a positive integer
$r$ equals the number of partitions of $n$ with each integer occurring less
than $r$ times.

######  Theorem 1.3 (Franklin).

The number of partitions of $n$ in which exactly $j$ different parts (these
parts can be repeated) are divisible by $r$ equals the number of partitions of
$n$ in which exactly $j$ different parts occur at least $r$ times each and
rest of the parts appear at most $r-1$ times.

Throughout this paper, we shall call partitions with no multiple of $r$
appearing as a part as $r$ \- regular partitions and those partitions where
each integer appears at most $r-1$ times as $r$ \- strict partitions. In the
rest of the article, we adopt the following $q$-series notation: For
$a,q\in\mathbb{C}$, we define

$\displaystyle(a;q)_{0}$ $\displaystyle:=1,\
(a;q)_{n}:=\prod_{i=0}^{n-1}(1-aq^{i}),\ n\in\mathbb{N},$
$\displaystyle(a;q)_{\infty}$
$\displaystyle:=\lim_{n\to\infty}(a;q)_{n}=\prod_{i=0}^{\infty}(1-aq^{i})\quad\text{for}\
|q|<1,$ $\displaystyle{n\brack m}$
$\displaystyle=\frac{(q;q)_{n}}{(q;q)_{m}(q;q)_{n-m}},\ n\geq m\geq 0.$

We also present below some frequently used notations throughout the sequel:

  * •

$\pi$ := an integer partition,

  * •

$|\pi|$ := sum of the parts of $\pi$,

  * •

$\pi^{{}^{\prime}}$ := the conjugate partition of $\pi$,

  * •

$s(\pi)$ := the smallest part of $\pi$,

  * •

$\ell(\pi)$ := the largest part of $\pi$

  * •

$\nu_{\pi}(t)$ := the multiplicity of an integer $t$ in $\pi$, the subscript
being omitted if the partition in question is clear.

  * •

$\mathcal{P}_{r}^{0}(n)$ := set of partitions of $n$ where the gap between any
two successive parts is at most $r$ and the smallest part is at most $r$,

  * •

$\mathcal{P}_{r}^{+}(n)$ := $\mathcal{P}(n)\setminus\mathcal{P}_{r}^{0}(n)$,

As we shall see shortly, both $\mathcal{P}_{r}^{0}(n)$ and
$\mathcal{P}_{r}^{+}(n)$ are closely intertwined with our generalization of
the maximal excludant and subsequent results. They also play a crucial role in
the bijective proofs pertaining to both the minimal and maximal excludants.
Before describing these results, we give a brief introduction to these
concepts. In 2019, Andrews and Newman [2, 3] undertook a combinatorial study
of the minimal excludant (‘mex’) of partitions, earlier defined by Grabner and
Knopfmacher [9]. The minimal excludant of a partition $\lambda$, denoted by
$mex(\lambda)$, is the smallest positive integer that does not appear in
$\lambda$. They established the following result.

######  Theorem 1.4.

The generating function for the sum of minimum excludants over all partitions
of $n$, denoted by $\sigma\textup{mex}(n)$, is given by

$\sum_{n=0}^{\infty}\sigma\textup{mex}(n)q^{n}=\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}mex(\lambda)q^{n}=(-q;q)_{\infty}^{2}.$

This theorem implies that for any positive integer $n$, the sum of the mex
taken over all partitions of $n$ equals the number of partitions of $n$ into
distinct parts using two colors. Later, a bijective proof of this fact was
given by Ballantine and Merca [4].

Recently, the first and second authors along with Maji [5] generalized the
minimal excludant and studied the $r$-chain minimal excludant of partitions.
Given any partition $\lambda$, the $r$-chain minimal excludant of $\lambda$,
denoted by $mex(\lambda;r)$, is the smallest positive integer $k$ such that
none of $k,k+1,\ldots,k+r-1$ appears as a part of $\lambda$. They proved the
following two results concerning the $r$-chain minimal excludant (‘$r$-chain
mex’ for short). The first one below [5, Theorem $2.4$] is an analogue of
Franklin’s result (Theorem 1.3) concerning the total number of multiples of
$r$. Here, an $r$-repeating part in a partition is an integer which has
multiplicity _at least_ $r$.

######  Theorem 1.5.

Suppose that $j$ is a non-negative integer and $r\geq 2$ is a positive
integer. Then the number of partitions of $n$ with exactly $j$ multiples of
$r$ equals the number of partitions of $n$ whose largest $r$-repeating part is
$j$, which is also equal to the number of partitions of $n$ with $j$ parts
greater than the $(r-1)$-chain mex.

We provide a combinatorial proof of this identity in this paper, as requested
in [5, Problem $2$, Section $4$]. Coming to the second result [5, Theorem
$2.6$], it is a generalization of Theorem 1.4 to the case of the $r$-chain
mex.

######  Theorem 1.6.

If $r$ is a positive integer, then

$\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}mex(\lambda;r)q^{n}=-\frac{(r-1)}{(q;q)_{\infty}}+\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}\sum_{m=1}^{r}\frac{1}{(q^{m};q^{r+1})_{\infty}}.$

We give a bijective proof of this identity as well in the sequel, answering
Problem $5$ in [5, Section $4$]. Instead of directly proving the theorem as
stated above, we prove an equivalent statement due to a technical reason to be
explained shortly. Firstly, note that Theorem 1.6 can be recast as

$\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}\left(mex(\lambda;r)+r-1\right)q^{n}=\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}\sum_{m=1}^{r}\frac{1}{(q^{m};q^{r+1})_{\infty}}.$
(1.1)

Now on the right hand side of (1.1), the fraction of $q$-products

$\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}$

is the generating function for $(r+1)$ \- strict partitions. Also, the sum

$\sum_{m=1}^{r}\frac{1}{(q^{m};q^{r+1})_{\infty}}$

generates $(r+1)$ \- regular partitions with all parts in the same congruence
class modulo $(r+1)$. As the constant term in this sum is $r$, the empty
partition must be counted for $r$ times. Before constructing a bijective proof
for Theorem 1.6, i.e. for (1.1), we first prove a similar result that avoids
counting the empty partition multiple times.

For any partition $\lambda\in\mathcal{P}(n)$, we define the following weight
function:

$\omega_{r}(\lambda)=\begin{cases}0,&\lambda\in\mathcal{P}_{r}^{0}(n),\\\
r-1,&\lambda\in\mathcal{P}_{r}^{+}(n).\end{cases}$ (1.2)

We then have the following companion identity to (1.1).

######  Theorem 1.7.

Given any positive integer $r$, we have

$\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}(mex(\lambda;r)+\omega_{r}(\lambda))q^{n}=\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}\left(1+\sum_{n=1}^{\infty}\frac{q^{n}(1-q^{rn})}{(1-q^{n})(q^{r+1};q^{r+1})_{n}}\right).$

We first obtain a bijective proof of Theorem 1.7 and then modify it to
construct one for (1.1). But the heavy lifting is done in the proof of Theorem
1.7.

Inspired by the minimal excludant, Chern [6] investigated the maximal
excludant of partitions (‘maex’ for short). He defined the maximal excludant
of a partition $\lambda$, denoted by $maex(\lambda)$, to be the largest
integer less than the largest part of $\lambda$ that does not appear in
$\lambda$. He proved the following result for the maex as an analogue of
Theorem 1.4. Here, $\sigma L(n)$ denotes the sum of largest parts taken over
all partitions of $n$, i.e., $\sum_{\pi\in\mathcal{P}(n)}\ell(\pi)$.

######  Theorem 1.8.

The sum of maximum excludants of all partitions of $n$, denoted by
$\sigma\textup{maex}(n)$, satisfies the following identity:

$\sum_{n=0}^{\infty}\left(\sigma
L(n)-\sigma\textup{maex}(n)\right)q^{n}=\frac{1}{(q;q)_{\infty}}\sum_{n=1}^{\infty}q^{n}(q^{2};q^{2})_{n-1}.$

It is natural to consider a generalization of the maex analogous to the
$r$-chain minimal excludant.

######  Definition 1 ($r$-chain maximal excludant).

For $r\geq 1$, we define the $r$-chain maximal excludant (‘$r$-chain maex’ for
short) of a partition $\lambda$, denoted by $maex(\lambda;r)$, to be the
largest positive integer $k$ less than the largest part of $\lambda$ such that
the positive integers $k,k-1,\ldots,k-r+1$ do not occur as parts in $\lambda$.
If there is no such positive integer $k$ for $\lambda$, we set
$maex(\lambda;r)=0$.

From this definition, $maex(\lambda;r)>0$ if and only if there is a string of
at least $r$ consecutive integers missing between two successive parts of
$\lambda$ or if the smallest part of $\lambda$ is greater than $r$ or both.
This means precisely that $\lambda\in\mathcal{P}_{r}^{+}(n)$, as defined in
the frequently used notations just before the statement of Theorem 1.4. This
also implies that $maex(\lambda;r)=0$ if and only if
$\lambda\in\mathcal{P}(n)\setminus\mathcal{P}_{r}^{+}(n)=\mathcal{P}_{r}^{0}(n)$.
We then have the following theorem for the $(r-1)$-chain maex analogous to
Theorem 1.5.

######  Theorem 1.9.

Suppose that $r\geq 2$ and $j\geq 1$ are two positive integers. Then the
number of partitions of $n$ where the largest multiple of $r$ occurs exactly
$j$ times equals the number of partitions of $n$ whose smallest $r$-repeating
part is $j$. Moreover, both these quantities also equal the number of
partitions in $\mathcal{P}_{r-1}^{+}(n)$ with $j$ parts greater than the
$(r-1)$-chain maex.

######  Example 1.

Let $r=3$ and $j=1$ and consider the partitions in $\mathcal{P}_{2}^{+}(7)$,
i.e. the partitions of $7$ whose $2$-chain maex is positive with exactly one
part greater than it. One can check that the partitions $7,\ 6+1,\ 5+2,\
5+1+1$ and $4+1+1+1$ are precisely the ones in this category. Now, coming to
the partitions of $7$ whose smallest $3$-repeating part is $1$, we see that
$4+1+1+1,\ 3+1+1+1+1,\ 2+2+1+1+1,\ 2+1+1+1+1+1$ and $1+1+1+1+1+1+1$ are the
required ones. Finally, partitions of $7$ whose largest multiple of $3$ occurs
exactly once are $6+1,\ 4+3,\ 3+2+2,\ 3+2+1+1$ and $3+1+1+1+1$. In all the
cases, there are an equal number of partitions (exactly five) as expected.

For a partition $\lambda\in\mathcal{P}(n)$, we define another weight function:

$\Omega_{r}(\lambda)=\begin{cases}1,&\lambda\in\mathcal{P}_{r}^{0}(n),\\\
r,&\lambda\in\mathcal{P}_{r}^{+}(n).\end{cases}$ (1.3)

Then we have the following generalization of Theorem 1.8, which can be
considered to be a maximal excludant analogue for Theorem 1.6.

######  Theorem 1.10.

For any positive integer $r$, we have

$\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}(\ell(\lambda)-maex(\lambda;r)+\Omega_{r}(\lambda))q^{n}=\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}+\frac{1}{(q;q)_{\infty}}\sum_{n=1}^{\infty}\frac{q^{n}(q^{r+1};q^{r+1})_{n}}{1-q^{n}}.$
(1.4)

The rest of this paper is organized as follows. In Section 2, we give
combinatorial proofs for Theorem 1.5 and Theorem 1.9, along with a $q$-series
proof for Theorem 1.9. In Section 3, we demonstrate Theorem 1.7 and Theorem
1.6 combinatorially. Finally, in Section 4, we prove Theorem 1.10 both
analytically and bijectively.

##  2\. Proofs of Theorem 1.5 and Theorem 1.9

We first give a combinatorial proof of Theorem 1.5 and then proceed to prove
Theorem 1.9 both analytically and combinatorially.

  * Combinatorial proof of Theorem 1.5.

Firstly, note that partitions with $j$ parts greater than the $(r-1)$-chain
mex on conjugation give rise to partitions whose largest $r$-repeating part is
$j$. Now, we give a bijective proof of the equinumerosity of partitions having
$j$ multiples of $r$ and those with largest $r$-repeating part $j$. We denote
by $E_{j,r}(n)$ and $L_{j,r}(n)$, respectively, the collection of partitions
of $n$ into $j$ multiples of $r$ and the collection whose largest
$r$-repeating part is $j$. Before establishing a bijection between them, we
recall a bijection due to Glaisher [8] between the set $\mathcal{O}_{r}(n)$ of
partitions of an integer $n$ into parts not divisible by $r$ and the set
$\mathcal{D}_{r}(n)$ of partitions of $n$ where each integer repeats less than
$r$ times. Let

$f:\mathcal{O}_{r}(n)\rightarrow\mathcal{D}_{r}(n)$ (2.1)

be the map acting on a partition $\pi\in\mathcal{O}_{r}(n)$ by merging every
$r$ copies of the same integer until there is no integer which repeats $r$
times or more. And in the reverse direction, for a partition in
$\mathcal{D}_{r}(n)$, we split each multiple of $r$ into $r$ equal parts until
there is no multiple of $r$ remaining. It is readily seen that this process is
the inverse of $f$ and so $f$ is a bijection. Next, we define the
‘concatenation’ of two partitions $\alpha,\mu$ in $\mathcal{P}$ (the two
partitions need not partition the same integer $m$) to be another partition
$\alpha*\mu$ obtained by taking together all the parts in $\alpha$ and $\mu$.
For example, if $\alpha=(3^{2},1^{3})$ and $\mu=(5,2^{3},1^{2})$, then
$\alpha*\mu=(5,3^{2},2^{3},1^{5})$.

We now construct a bijective map $\phi_{r}:E_{j,r}(n)\rightarrow L_{j,r}(n)$.
A partition $\pi$ in $E_{j,r}(n)$ can be written uniquely as
$\pi_{o}*\pi_{r}$, with $\pi_{r}$ consisting of all the parts that are
multiples of $r$ and the remaining parts being included in $\pi_{o}$. Since
$\pi\in E_{j,r}(n)$, it has $j$ multiples of $r$ and so
$\pi_{r}=(r\ell_{1},r\ell_{2},\dots,r\ell_{j})$ for some
$\ell_{1}\geq\ell_{2}\geq\cdots\geq\ell_{j}\geq 1$. Now put
$\tilde{\pi_{o}}:=f(\pi_{o})$, where $f$ is the map defined in (2.1). Then
$\tilde{\pi_{o}}$ is a partition where each integer appears less than $r$
times. Further, define $\tilde{\pi_{r}}:=\pi_{r}^{{}^{\prime}}$, and observe
that $\tilde{\pi_{r}}$ has largest part equal to $j$. Moreover, each integer
in $\tilde{\pi_{r}}$ repeats a multiple of $r$ times. In other words, $j$
appears at least $r$ times in $\tilde{\pi_{r}}$. Finally, noting that
$\tilde{\pi_{o}}*\tilde{\pi_{r}}$ is a partition with largest $r$-repeating
part $j$, we set $\phi_{r}(\pi):=\tilde{\pi_{o}}*\tilde{\pi_{r}}$. We next
define a map $\psi_{r}:L_{j,r}(n)\rightarrow E_{j,r}(n)$, which will turn out
to be the inverse of $\phi_{r}$. Suppose that $\nu\in L_{j,r}(n)$, so that its
largest $r$-repeating part is $j$. Write
$\nu=(m^{f_{m}},\dots,j^{f_{j}},\dots,1^{f_{1}})$ where $\ell(\nu)=m,\
f_{j}\geq r,\ f_{t}\geq 0$ for $t<j$ and $0\leq f_{t}<r$ for $t>j$. Employing
the division algorithm, we have $f_{i}=rq_{i}+s_{i}$, where $0\leq s_{i}<r$
for each $i$. Next, define $\nu_{r}:=(j^{rq_{j}},\dots,1^{rq_{1}})$ and
$\nu_{o}:=(m^{f_{m}},\dots,j^{s_{j}},\dots,1^{s_{1}})$. Note that since $0\leq
s_{i}<r$ and $0\leq f_{t}<r$ for $t>j$, $\nu_{o}$ is a partition where each
integer appears less than $r$ times. Next, set $\kappa:=f^{-1}(\nu_{o})$,
which is an $r$-regular partition, and $\gamma:=\nu_{r}^{{}^{\prime}}$, which
is a partition with parts that are multiples of $r$ such that $\\#(\gamma)=j$.
As a result, $\kappa*\gamma\in E_{j,r}(n)$ and we put
$\psi_{r}(\nu):=\kappa*\gamma$. It is easy to check that $\psi_{r}$ is indeed
the inverse of $\phi_{r}$. ∎

######  Example 2.

This is an illustration in the case when $r=3$. Take $\pi:=(9,7,6^{3},1^{4})$.
Note that there are $j=4$ multiples of $r$. Split this into
$\pi_{r}:=(9,6^{3})$ and $\pi_{o}:=(7,1^{4})$. Then
$\tilde{\pi_{o}}:=f(\pi_{o})=(7,3,1)$ and
$\tilde{\pi_{r}}:=\pi_{r}^{{}^{\prime}}=(4^{6},1^{3})$. Therefore,
$\phi_{r}(\pi)=\tilde{\pi_{o}}*\tilde{\pi_{r}}=(7,4^{6},3,1^{4})$, which has
its largest $3$-repeating part equal to $4$. Conversely, beginning with
$\nu=(7,4^{6},3,1^{4})$, we see that $\nu_{r}=(4^{6},1^{3})$ and
$\nu_{o}=(7,3,1)$. Now, $\kappa:=f^{-1}(\nu_{o})=(7,1^{4})$ and
$\gamma:=\nu_{r}^{{}^{\prime}}=(9,6^{3})$ and thereby
$\psi_{r}(\nu)=\kappa*\gamma=(9,7,6^{3},1^{4})=\pi$.

Before proceeding to the proof of Theorem 1.9 and beyond, we note down a
crucial ingredient, namely, the $q$-binomial theorem: For $|q|<1$ and any
$a\in\mathbb{C}$, we have

$\sum_{n=0}^{\infty}\frac{(a;q)_{n}}{(q;q)_{n}}z^{n}=\frac{(az;q)_{\infty}}{(z;q)_{\infty}}.$
(2.2)

  * Analytic proof of Theorem 1.9.

The proof proceeds in two parts. We first prove that the partitions in
$\mathcal{P}_{r-1}^{+}(n)$ having $j$ parts greater than their $(r-1)$-chain
maex are equinumerous with partitions of $n$ whose smallest $r$-repeating part
is $j$.

Part 1: Suppose $k\geq 1$ is the $(r-1)$-chain maex of a partition $\pi$ and
that there are $j$ parts greater than $k$. This means that $k,\ k-1,\
\cdots,k-r+2$ are all positive integers and missing from $\pi$. First of all,
since $k-r+2\geq 1$, we have $k\geq r-1$. Note that $\pi$ comprises two
pieces, the first piece $\pi_{1}$ consisting of parts less than $k-r+2$ with
no restriction on what and how many parts may occur. So the generating
function for this piece is

$\frac{1}{(q;q)_{k-r+1}}.$ (2.3)

Coming to the second piece $\pi_{2}$ of $\pi$, it consists of those parts of
$\pi$ that are greater than $k$. Note that $k+1$ must be a part, for otherwise
it becomes the $(r-1)$-chain maex of $\pi$. Also, parts in $\pi_{2}$ must
occur in such a manner so that no string of $r-1$ consecutive integers should
be missing (to ensure that $k$ is the $(r-1)$-chain maex of $\pi$). That means
in $\pi_{2}$, the gaps between successive parts must be at most $r-1$.
Moreover, since there are $j$ parts in $\pi$ greater than the $(r-1)$-chain
maex $k$, this translates to $\pi_{2}$ having exactly $j$ parts. So, in
summary, $s(\pi_{2})=k+1,\ \\#(\pi)=j$, and gaps between successive parts
$\leq r-1$. By conjugation, this implies
$\nu(\ell(\pi_{2}^{{}^{\prime}}))=k+1,\ \ell(\pi_{2}^{{}^{\prime}})=j$ and
that each integer in $\pi_{2}^{{}^{\prime}}$ repeats less than $r$ times. The
generating function for such partitions (and hence for those of the type
$\pi_{2}$) is:

$q^{j(k+1)}\prod_{n=1}^{j-1}(1+q^{n}+\cdots+q^{n(r-1)}).$ (2.4)

Putting together the generating functions for the two pieces $\pi_{1}$ and
$\pi_{2}$, i.e., (2.3) and (2.4) and summing over the possible values of $k$,
we can write the generating function for partitions $\pi$ as follows:

$\displaystyle\sum_{k=r-1}^{\infty}\frac{q^{j(k+1)}}{(q;q)_{k-r+1}}\prod_{n=1}^{j-1}(1+q^{n}+\cdots+q^{n(r-1)})$
$\displaystyle=\prod_{n=1}^{j-1}(1+q^{n}+\cdots+q^{n(r-1)})\sum_{k=r-1}^{\infty}\frac{q^{j(k+1)}}{(q;q)_{k-r+1}}$
$\displaystyle=\prod_{n=1}^{j-1}(1+q^{n}+\cdots+q^{n(r-1)})\sum_{k=0}^{\infty}q^{jr}\frac{q^{jk}}{(q;q)_{k}}$
$\displaystyle=\frac{q^{jr}}{(q^{j};q)_{\infty}}\prod_{n=1}^{j-1}(1+q^{n}+\cdots+q^{n(r-1)})$
$\displaystyle=\frac{q^{jr}}{1-q^{j}}\times\frac{1}{(q^{j+1};q)_{\infty}}\prod_{n=1}^{j-1}(1+q^{n}+\cdots+q^{n(r-1)}),$
(2.5)

where we invoked (2.2) in the penultimate equality. Now, the expression in
(2.5) is precisely the generating function for partitions with smallest
$r$-repeating part $j$.

Part 2: Coming to the second part of the theorem, we prove that the expression
in (2.5) also generates partitions with the largest multiple of $r$ occurring
exactly $j$ times. We write

$\displaystyle\frac{q^{jr}}{1-q^{j}}\times\frac{1}{(q^{j+1};q)_{\infty}}\prod_{n=1}^{j-1}(1+q^{n}+\cdots+q^{n(r-1)})$
$\displaystyle=\frac{q^{jr}}{(q^{j};q)_{\infty}}\times\frac{(q^{r};q^{r})_{j-1}}{(q;q)_{j-1}}$
$\displaystyle=\frac{q^{jr}}{(q;q)_{\infty}}\times\frac{(q^{r};q^{r})_{\infty}}{(q^{jr};q^{r})_{\infty}}$
$\displaystyle=\frac{q^{jr}(q^{r};q^{r})_{\infty}}{(q;q)_{\infty}}\sum_{k=0}^{\infty}\frac{(q^{jr})^{k}}{(q^{r};q^{r})_{k}}\quad\text{(by
\eqref{q-binomial})}$
$\displaystyle=\frac{(q^{r};q^{r})_{\infty}}{(q;q)_{\infty}}\sum_{k=1}^{\infty}\frac{q^{krj}}{(q^{r};q^{r})_{k-1}}$
$\displaystyle=\frac{(q^{r};q^{r})_{\infty}}{(q;q)_{\infty}}\sum_{k=1}^{\infty}\frac{1}{1-q^{r}}\times\dots\times\frac{1}{1-q^{(k-1)r}}\times(q^{kr})^{j},$

and the last expression is precisely the generating function for partitions
with $j$ occurrences of the largest multiple of $r$. ∎

  * Combinatorial proof of Theorem 1.9.

The proof closely parallels the proof of Theorem 1.5 and so, we give only a
sketch of the ideas involved. Firstly, note that partitions in
$\mathcal{P}_{r-1}^{+}(n)$ with $j$ parts greater than the $(r-1)$-chain maex
on conjugation give rise to unrestricted partitions whose smallest
$r$-repeating part is $j$. Let $H_{j,r}(n)$ and $S_{j,r}(n)$ denote the
collection of partitions of $n$ in which the largest multiple of $r$ has
multiplicity $j$ and that collection whose smallest $r$-repeating part is $j$
respectively. Take any partition $\pi$ in $H_{j,r}(n)$, then it can be
expressed uniquely in the form $\pi_{o}*\pi_{r}$, with $\pi_{r}$ containing
only multiples of $r$ and all the remaining parts in $\pi_{o}$. As $\pi\in
H_{j,r}(n)$, it has $j$ copies of the largest multiple of $r$. We can write it
as $\pi_{r}=(\underbrace{r\ell_{1},\dots,r\ell_{1}}_{j\
\text{times}},r\ell_{2},\dots,r\ell_{j})$ for some
$\ell_{1}>\ell_{2}\geq\cdots\geq\ell_{j}\geq 1$. Next, set
$\tilde{\pi_{o}}:=f(\pi_{o})$, where $f$ is Glaisher’s bijection, as defined
in the proof of Theorem 1.5. Further, we also define
$\tilde{\pi_{r}}:=\pi_{r}^{{}^{\prime}}$, and note that $\tilde{\pi_{r}}$ is a
partition where each integer has multiplicity a multiple of $r$ with smallest
part being $j$. So, $\tilde{\pi_{o}}*\tilde{\pi_{r}}$ is a partition whose
smallest $r$-repeating part is $j$, and we define $\Phi_{r}:H_{j,r}(n)\to
S_{j,r}(n)$ by $\Phi_{r}(\pi):=\tilde{\pi_{o}}*\tilde{\pi_{r}}$.

In the other direction, suppose that $\nu\in S_{j,r}(n)$, so that the smallest
$r$-repeating part of $\nu$ equals $j$. Then $\nu$ can be represented in the
form $\nu=(m^{f_{m}},\dots,j^{f_{j}},\dots,1^{f_{1}})$ with $\ell(\nu)=m,\
f_{j}\geq r,\ f_{k}\geq 0$ for $k>j$ and $0\leq f_{k}<r$ for $k<j$. Using the
division algorithm, we can write $f_{i}=rq_{i}+s_{i}$, where $0\leq s_{i}<r$
for each $i$. We now define $\nu_{r}:=(m^{rq_{m}},\dots,j^{rq_{j}})$ and
$\nu_{o}:=(m^{s_{m}},\dots,j^{s_{j}},(j-1)^{f_{j-1}},\dots,1^{f_{1}})$. We can
see that $\nu_{o}$ is a partition with each integer appearing less than $r$
times and hence $\kappa:=f^{-1}(\nu_{o})$ is an $r$-regular partition. Also,
$\gamma:=\nu_{r}^{{}^{\prime}}$ is a partition with parts that are multiples
of $r$ such that the largest part has multiplicity $j$. Therefore,
$\kappa*\gamma\in H_{j,r}(n)$ and setting $\Psi_{r}(\nu):=\kappa*\gamma$, we
see that $\Psi_{r}$ is the inverse of $\Phi_{r}$. In this way, we have a
constructed a bijection between $H_{j,r}(n)$ and $S_{j,r}(n)$ and the proof is
complete. ∎

##  3\. Bijective proofs of identities for the sum of $r$-chain minimal
excludants

In this section, we give a combinatorial proof of Theorem 1.6. Before going to
that, we first prove Theorem 1.7.

  * Proof of Theorem 1.7.

Note that from the definition of the weight $\omega_{r}$ in (1.2), we have

$\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}(mex(\lambda;r)+\omega_{r}(\lambda))q^{n}=\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}(mex(\lambda;r)+r-1)q^{n}-\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}_{r}^{0}(n)}(r-1)q^{n},$
(3.1)

and the first sum on the right hand side is given by (1.1). So it remains to
calculate the second sum on the right hand side. We have

$\displaystyle\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}_{r}^{0}(n)}(r-1)q^{n}=(r-1)\sum_{n=0}^{\infty}|\mathcal{P}_{r}^{0}(n)|q^{n}=(r-1)\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}.$

And this used along with the right hand side of (1.1) turns (3.1) into

$\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}(mex(\lambda;r)+\omega_{r}(\lambda))q^{n}=\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}\sum_{m=1}^{r}\frac{1}{(q^{m};q^{r+1})_{\infty}}-(r-1)\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}.$
(3.2)

Now for any integer $1\leq m\leq r$, we have

$\frac{1}{(q^{m};q^{r+1})_{\infty}}=\sum_{n=0}^{\infty}\frac{q^{nm}}{(q^{r+1};q^{r+1})_{n}}=1+\sum_{n=1}^{\infty}\frac{q^{nm}}{(q^{r+1};q^{r+1})_{n}},$

thus giving us

$\sum_{m=1}^{r}\frac{1}{(q^{m};q^{r+1})_{\infty}}=\sum_{m=1}^{r}\left(1+\sum_{n=1}^{\infty}\frac{q^{nm}}{(q^{r+1};q^{r+1})_{n}}\right)=r+\sum_{n=1}^{\infty}\frac{q^{n}(1-q^{rn})}{(1-q^{n})(q^{r+1};q^{r+1})_{n}},$

and consequently

$\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}\sum_{m=1}^{r}\frac{1}{(q^{m};q^{r+1})_{\infty}}=\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}\left(r+\sum_{n=1}^{\infty}\frac{q^{n}(1-q^{rn})}{(1-q^{n})(q^{r+1};q^{r+1})_{n}}\right).$

Therefore, from (3.2), we finally have

$\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}(mex(\lambda;r)+\omega_{r}(\lambda))q^{n}=\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}\left(1+\sum_{n=1}^{\infty}\frac{q^{n}(1-q^{rn})}{(1-q^{n})(q^{r+1};q^{r+1})_{n}}\right).$

∎

We will first construct a bijection for Theorem 1.7 and then extend it to
prove (1.1). For this, we interpret Theorem 1.7 as counting certain objects.

Let $S_{r}(n)$ be the number of $r$ \- strict partitions of $n$. Let
$M_{r}(n)$ be the number of partitions of $n$ such that the multiplicity of
the largest part is not divisible by $r$ while all the other parts must have a
multiplicity that is divisible by $r$. Then we have

$\displaystyle\sum_{n=0}^{\infty}S_{r+1}(n)q^{n}$
$\displaystyle=\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}},$

and

$\displaystyle\sum_{n=0}^{\infty}M_{r+1}(n)q^{n}$
$\displaystyle=1+\sum_{n=1}^{\infty}\left(\frac{q^{n}}{1-q^{n}}-\frac{q^{(r+1)n}}{1-q^{(r+1)n}}\right)\prod_{i=1}^{n-1}(1+q^{(r+1)i}+q^{2(r+1)i}+\cdots)$
$\displaystyle=1+\sum_{n=1}^{\infty}\frac{q^{n}(1-q^{rn})}{(1-q^{n})(1-q^{(r+1)n})}\times\frac{1}{(q^{r+1};q^{r+1})_{n-1}}$
$\displaystyle=1+\sum_{n=1}^{\infty}\frac{q^{n}(1-q^{rn})}{(1-q^{n})(q^{r+1};q^{r+1})_{n}}.$

So in Theorem 1.7, the coefficient of $q^{n}$ on the left hand side is the
number of ordered pairs $(\lambda,i)$ such that

$\lambda\in\mathcal{P}(n),\quad\text{and}\quad\begin{cases}1\leq i\leq
mex(\lambda;r),&\text{if}\quad\lambda\in\mathcal{P}_{r}^{0}(n),\\\ 1\leq i\leq
mex(\lambda;r)+r-1,&\text{if}\quad\lambda\in\mathcal{P}_{r}^{+}(n).\end{cases}$
(3.3)

On the other hand, the coefficient of $q^{n}$ on the right hand side in
Theorem 1.7 is the number of ordered pairs of partitions $(\alpha,\beta)$ such
that

$\displaystyle|\alpha|+|\beta|=n,\quad\text{$\alpha$ is an $(r+1)$ - strict
partition},$ $\displaystyle\text{$\nu_{\beta}(\ell(\beta))$ is not divisible
by $r+1$, \quad\text{and} \quad$\nu_{\beta}(t)$ is divisible by $r+1$ for
$t<\ell(\beta)$}.$ (3.4)

So now our aim is to construct a bijection between the pairs of partitions in
(3.3) and (3.4).

We first introduce some operators on partitions.

  * •

Conjugate

For any partition $\lambda=(\lambda_{1},\ldots,\lambda_{\ell})$, let
$\lambda^{\prime}$ denote the conjugate of $\lambda$.

  * •

The horizontal cut

For any integer $1\leq i\leq\ell+1$, we define two partitions
$\lambda\uparrow^{(i)}$ and $\lambda\downarrow^{(i)}$ as

$\lambda\uparrow^{(i)}=(\lambda_{1},\lambda_{2},\ldots,\lambda_{i-1})\
\text{and}\
\lambda\downarrow^{(i)}=(\lambda_{i},\lambda_{i+1},\ldots,\lambda_{\ell}),$

with $\lambda\uparrow^{(1)}=\lambda\downarrow^{(\ell+1)}=\emptyset$. Note that
in view of the Ferrers diagram for a partition, this means that the Ferrers
diagram of $\lambda$ can be cut into two parts horizontally between
$\lambda_{i-1}$ and $\lambda_{i}$. Then $\lambda\uparrow^{(i)}$ and
$\lambda\downarrow^{(i)}$ are the partitions corresponding to the upper part
and lower part respectively.

  * •

The $\Psi$ operator

Let $(\alpha,\beta)$ be a pair of partitions. We are going to define an
operator $\Psi$ on such pairs. To this end, we write $\beta$ in a more compact
notation:

$\beta=\left(\beta_{1}^{\nu(\beta_{1})},\beta_{2}^{\nu(\beta_{2})},\ldots,\beta_{k}^{\nu(\beta_{k})}\right),$

where $\beta_{1}>\beta_{2}>\cdots>\beta_{k}$. Then for each $i$ we can find
unique nonnegative integers $q_{i},h_{i}$ such that

$\nu(\beta_{i})=q_{i}(r+1)+h_{i},$

with $r$ being a fixed positive integer and $0\leq h_{i}\leq r$. Now we retain
all the copies of $\beta_{1}$ in $\beta$, and for each $2\leq i\leq k$, we
move $h_{i}$ copies of $\beta_{i}$ from $\beta$ to $\alpha$. For convenience,
let the resultant new versions of $\alpha$ and $\beta$, by abuse of notation,
be denoted by $\Psi(\alpha)$ and $\Psi(\beta)$ respectively. Then we define
$\Psi(\alpha,\beta):=(\Psi(\alpha),\Psi(\beta))$.

Based on the definition of the operator $\Psi$, the following properties are
immediate.

######  Lemma 3.1.

If the smallest part of $\alpha$ is greater than or equal to the largest part
of $\beta$, and $\alpha$ is an $(r+1)$-strict partition. Then $\Psi(\alpha)$
is also an $(r+1)$-strict partition.

######  Lemma 3.2.

In $\Psi(\beta)$, only the largest part may have multiplicity not divisible by
$r+1$.

Now we are ready to construct a bijection $\Gamma$ for Theorem 1.7.

  * Bijective proof of Theorem 1.7.

Given any partition $\lambda$ and an integer $i$ with $1\leq i\leq
mex(\lambda;r)+\omega_{r}(\lambda)$, we consider the following cases.

Case 1. Let $(\lambda,i)$ be an ordered pair such that
$\lambda\in\mathcal{P}_{r}^{0}(n)$ and $1\leq i\leq mex(\lambda;r)$.

In this case, let
$\lambda^{\prime}=(\lambda^{\prime}_{1},\lambda^{\prime}_{2},\dots)$ be the
conjugate of $\lambda$. We apply the operator $\Psi$ on
$(\lambda^{\prime}\uparrow^{(i)},\lambda^{\prime}\downarrow^{(i)})$, with the
claim that
$\Psi(\lambda^{\prime}\uparrow^{(i)},\lambda^{\prime}\downarrow^{(i)})$ is of
the type described in (3.4). Indeed, by the definition of
$\mathcal{P}_{r}^{0}(n)$, we have $\lambda_{j}-\lambda_{j+1}\leq r$ for all
$j$ less than the length of $\lambda$, and the smallest part of $\lambda$ is
also less than or equal to $r$. Thus in the conjugate $\lambda^{\prime}$, each
part appears at most $r$ times. So this is also true in
$\lambda^{\prime}\uparrow^{(i)}$. Now by Lemma 3.1, it follows that each part
in $\Psi(\lambda^{\prime}\uparrow^{(i)})$ also repeats at most $r$ times. As
for $\Psi(\lambda^{\prime}\downarrow^{(i)})$, we only need to show that the
multiplicity of its largest part is not a mutiple of $(r+1)$. And this is
indeed the case since the largest part of
$\Psi(\lambda^{\prime}\downarrow^{(i)})$ is nothing but the largest part of
$\lambda^{\prime}\downarrow^{(i)}$, which has multiplicity less than $r+1$. We
thus set
$\Gamma(\lambda,i)=\Psi(\lambda^{\prime}\uparrow^{(i)},\lambda^{\prime}\downarrow^{(i)})$.

Case 2. Let $(\lambda,i)$ be an ordered pair such that
$\lambda\in\mathcal{P}_{r}^{+}(n)$ and $1\leq i\leq mex(\lambda;r)-1$.

In this case, the mapping is the same as that in Case $1$. By the definition
of $mex(\lambda;r)$, one can observe that $\lambda^{\prime}\uparrow^{(i)}$ is
still an $(r+1)$ \- strict partition. And the largest part of
$\lambda^{\prime}\downarrow^{(i)}$ still has multiplicity less than $r+1$.
Thus $\Psi(\lambda^{\prime}\uparrow^{(i)},\lambda^{\prime}\downarrow^{(i)})$
is once again of the desired type. So we again let
$\Gamma(\lambda,i)=\Psi(\lambda^{\prime}\uparrow^{(i)},\lambda^{\prime}\downarrow^{(i)})$.

Case 3. Let $(\lambda,i)$ be an ordered pair such that
$\lambda\in\mathcal{P}_{r}^{+}(n)$ and $mex(\lambda;r)\leq i\leq
mex(\lambda;r)+r-1$.

In this case, the first step is still to find
$\Psi(\lambda^{\prime}\uparrow^{(i)},\lambda^{\prime}\downarrow^{(i)})$. Now
let $G(\lambda)$ be the number of parts in $\lambda$ that are greater than
$mex(\lambda;r)$ and let $k$ be the multiplicity of $G(\lambda)$ in
$\lambda^{\prime}$. Then $k\geq(r+1)$ and for $mex(\lambda;r)\leq i\leq
mex(\lambda;r)+k-1$, we have $\lambda^{\prime}_{i}=G(\lambda)$. So this time
the largest part of $\lambda^{\prime}\downarrow^{(i)}$, which will be equal to
$G(\lambda)$, has multiplicity $k-(i-mex(\lambda;r))$ in
$\lambda^{\prime}\downarrow^{(i)}$. And since this may or may not be a
multiple of $(r+1)$, we need to consider two subcases as follows.

Subcase 3.1. If $k-(i-mex(\lambda;r))\not\equiv 0\ (\text{mod}\ (r+1))$, that
means the multiplicity of the largest part of
$\Psi(\lambda^{\prime}\downarrow^{(i)})$ is not divisible by $(r+1)$. So
$\Psi(\lambda^{\prime}\uparrow^{(i)},\lambda^{\prime}\downarrow^{(i)})$ is
exactly what we need. Thus, set
$\Gamma(\lambda,i)=\Psi(\lambda^{\prime}\uparrow^{(i)},\lambda^{\prime}\downarrow^{(i)})$
in this subcase.

Subcase 3.2. If $k-(i-mex(\lambda;r))\equiv 0\ (\text{mod}\ (r+1))$, then we
move $r-(i-mex(\lambda;r))$ copies of $G(\lambda)$ from
$\Psi(\lambda^{\prime}\downarrow^{(i)})$ to
$\Psi(\lambda^{\prime}\uparrow^{(i)})$. Let the modified versions of
$\Psi(\lambda^{\prime}\downarrow^{(i)})$ and
$\Psi(\lambda^{\prime}\uparrow^{(i)})$ be denoted by
$\Psi^{*}(\lambda^{\prime}\downarrow^{(i)})$ and
$\Psi^{*}(\lambda^{\prime}\uparrow^{(i)})$ respectively. Now we have $r$
copies of $G(\lambda)$ in $\Psi^{*}(\lambda^{\prime}\uparrow^{(i)})$ and $k-r$
copies of $G(\lambda)$ in $\Psi^{*}(\lambda^{\prime}\downarrow^{(i)})$. Since
$0\leq i-mex(\lambda;r)\leq r-1$, we see that $1\leq r-(i-mex(\lambda;r))\leq
r$, and so
$k-r=\left(k-(i-mex(\lambda;r))\right)-\left(r-(i-mex(\lambda;r))\right)$ is
not divisible by $(r+1)$. Hence, we put
$\Gamma(\lambda,i)=\left(\Psi^{*}(\lambda^{\prime}\uparrow^{(i)}),\Psi^{*}(\lambda^{\prime}\downarrow^{(i)})\right)$
for this subcase. This finishes the construction of the mapping $\Gamma$.

We have seen that $\Gamma(\lambda,i)$ satisfies the constraints on the pair
$(\alpha,\beta)$ in (3.4) in all the cases. Now we need to show that it is
invertible. Suppose that we are given a pair of partitions $(\alpha,\beta)$
such that $\alpha$ is an $(r+1)$ \- strict partition, and in $\beta$, the
multiplicity of the largest part is not divisible by $(r+1)$, while the other
parts have multiplicities divisible by $(r+1)$. Then we wish to recover the
pair $(\lambda,i)$ such that

$|\lambda|=|\alpha|+|\beta|,\quad 1\leq i\leq
mex(\lambda;r)+\omega_{r}(\lambda),\
\text{and}\quad\Gamma(\lambda,i)=(\alpha,\beta).$

It is straightforward to find the corresponding $\lambda$, we simply need to
put all the parts of $\alpha$ and $\beta$ together, rearrange them in the
weakly decreasing order and take the conjugate. And now with $\lambda$ in
hand, we can find $G(\lambda)$ and its multiplicity in $\lambda^{\prime}$, let
it be $k$.

If $G(\lambda)$ has multiplicity $r$ in $\alpha$, then this would correspond
to Subcase $3.2.$, and we know that $i-mex(\lambda;r)\equiv k\ (\text{mod}\
(r+1))$. Now since $mex(\lambda;r)\leq i\leq mex(\lambda;r)+r-1$ and
$k\not\equiv r\ (\text{mod}\ (r+1))$, we can determine $i$ uniquely.

On the other hand, suppose the multiplicity of $G(\lambda)$ in $\alpha$ is
different from $r$. Then it would correspond to one of the other cases. But
note that in each of those cases, since $\lambda^{\prime}\uparrow^{(i)}$
consists of parts greater than or equal to the largest part of
$\lambda^{\prime}\downarrow^{(i)}$, applying the operator $\Psi$ simply moves
some (possibly none) of the parts in $\lambda^{\prime}\downarrow^{(i)}$ that
are less than the largest part of $\lambda^{\prime}\downarrow^{(i)}$ to
$\lambda^{\prime}\uparrow^{(i)}$ giving us
$\Psi(\lambda^{\prime}\uparrow^{(i)},\lambda^{\prime}\downarrow^{(i)})$. There
is no transfer of the largest parts in $\lambda^{\prime}\downarrow^{(i)}$ to
$\lambda^{\prime}\uparrow^{(i)}$. In other words,
$\ell(\lambda^{\prime}\downarrow^{(i)})=\ell(\Psi(\lambda^{\prime}\downarrow^{(i)}))=\ell(\beta)$.
So to get $i$, we just need to count the number of parts in $\alpha$ that are
greater than or equal to the largest part of $\beta$ and add $1$ to it. This
concludes the bijective proof of the theorem. ∎

Next we extend the definition of $\Gamma$ to $\Gamma^{*}$, which gives a
bijective proof for Theorem 1.6.

  * Bijective proof of (1.1).

Note that if $(\alpha,\beta)$ is a pair of partitions counted by the right
hand side of Theorem 1.7, then $(\alpha,\beta^{\prime})$ will also be a pair
counted by the right hand side of (1.1). So the only difference is that the
pairs $(\alpha;\beta)$ must be counted multiple times when $\beta$ is the
empty partition. To this end, we assume that the empty partition can be
assigned any of $r$ different colors. We will denote by
$(\alpha;\emptyset_{i})$ the pair with arbitrary $\alpha$ and $\beta$ being
the empty partition and assigned the $i$-th color (for $1\leq i\leq r$).

Now, given a partition $\lambda$, we consider two different cases. If
$\lambda\in\mathcal{P}_{r}^{+}(n)$, then $mex(\lambda;r)+r-1$ is less than
$\ell(\lambda)$, i.e., the largest part of $\lambda$. And our bijection
$\Gamma$ works fine on them, so we take
$\Gamma^{*}(\lambda;i)=\Gamma(\lambda,i)$. Also, in this case, if
$(\alpha;\beta)$ is the image of $\lambda$ under our map, then $\beta$ will
never be empty. Since the length of the conjugate of $\lambda$, which is just
$\ell(\lambda)$, is greater than $mex(\lambda;r)+r-1$, there will always be
some parts assigned to $\beta$.

For the partitions $\lambda\in\mathcal{P}_{r}^{0}(n)$, we have
$mex(\lambda;r)=\ell(\lambda)+1$. In this case, $\lambda^{\prime}$, the
conjugate of $\lambda$, has length $\ell(\lambda)$, which means we can only
cut it horizontally in $\ell(\lambda)+1$ different ways. In this case, we fail
to find the other $(r-1)$ images of $\lambda$. But this can be easily fixed as
we can assign different colors to $\beta$ when it is empty. Suppose we have a
pair $(\lambda;i)$ where $\lambda$ is a partition in $\mathcal{P}_{r}^{0}(n)$
while $1\leq i\leq mex(\lambda;r)+r-1$ is an integer. If $1\leq i\leq
mex(\lambda;r)-1=\ell(\lambda)$, then we can apply our map $\Gamma$ as usual
and $\beta$ will not be empty, so we define
$\Gamma^{*}(\lambda;i)=\Gamma(\lambda;i)$ as well. And for $mex(\lambda;r)\leq
i\leq mex(\lambda;r)+r-1$, we define the image as
$\Gamma^{*}(\lambda;i)=(\lambda^{\prime},\emptyset_{i-mex(\lambda;r)+1})$. The
inverse of this additional definition is clear. So this finishes the proof. ∎

##  4\. The sum of $r$-chain maximal excludants

In this section, we prove Theorem 1.10.

  * Analytic proof of Theorem 1.10.

The left hand side of (1.4) can be written as

$\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}\ell(\lambda)q^{n}-\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}(maex(\lambda;r)-\Omega_{r}(\lambda))q^{n}$
(4.1)

and we treat the two double sums separately.

For the first double sum, we proceed as follows.

$\displaystyle\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}\ell(\lambda)q^{n}=\left.\frac{\partial}{\partial{z}}\sum_{n=0}^{\infty}\frac{z^{n}q^{n}}{(q;q)_{n}}\right|_{z=1}$
$\displaystyle=\left.\frac{\partial}{\partial{z}}\frac{1}{(zq;q)_{\infty}}\right|_{z=1}$
$\displaystyle=\frac{1}{(zq;q)_{\infty}}\left.\frac{\partial}{\partial{z}}\log\frac{1}{(zq;q)_{\infty}}\right|_{z=1}$
$\displaystyle=\frac{1}{(zq;q)_{\infty}}\left.\frac{\partial}{\partial{z}}\sum_{n=1}^{\infty}-\log(1-zq^{n})\right|_{z=1}$
$\displaystyle=\frac{1}{(q;q)_{\infty}}\sum_{n=1}^{\infty}\frac{q^{n}}{1-q^{n}}.$
(4.2)

For the second double sum in (4.1), as required by the definitions of
$maex_{r}(\lambda)$ and $\Omega_{r}(\lambda)$, we divide the partitions of $n$
into two classes. Doing this gives us

$\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}(maex(\lambda;r)-\Omega_{r}(\lambda))q^{n}=\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}_{r}^{0}(n)}(maex(\lambda;r)-\Omega_{r}(\lambda))q^{n}+\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}_{r}^{+}(n)}(maex(\lambda;r)-\Omega_{r}(\lambda))q^{n}.$
(4.3)

For the partitions $\lambda$ in $\mathcal{P}_{r}^{0}(n)$, we have
$maex(\lambda;r)-\Omega_{r}(\lambda)=0-1=-1$. Thus,

$\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}_{r}^{0}(n)}(maex(\lambda;r)-\Omega_{r}(\lambda))q^{n}=\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}_{r}^{0}(n)}(-1)q^{n}=-\sum_{n=0}^{\infty}|\mathcal{P}_{r}^{0}(n)|q^{n}=-\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}},$
(4.4)

where the last equality arises by taking the conjugates of the partitions in
$\mathcal{P}_{r}^{0}(n)$.

Let $\mathcal{P}_{r}^{+}(m,n)$ be the subcollection of partitions in
$\mathcal{P}_{r}^{+}(n)$ with $maex(\lambda;r)=m$. We count these partitions
according to the number $\ell$ of parts that are greater than $m$ in
$\lambda$. We have

$\displaystyle\mathbb{P}_{r}^{+}(z,q):=\sum_{n=0}^{\infty}\sum_{m=r}^{\infty}|\mathcal{P}_{r}^{+}(m,n)|z^{m}q^{n}$
$\displaystyle=\sum_{m=r}^{\infty}\sum_{\ell=1}^{\infty}\frac{z^{m}q^{(m+1)\ell}}{(q;q)_{m-r}}\frac{(q^{r+1};q^{r+1})_{\ell-1}}{(q;q)_{\ell-1}}$
$\displaystyle=\sum_{m=0}^{\infty}\sum_{\ell=1}^{\infty}\frac{z^{m+r}q^{(m+r+1)\ell}}{(q;q)_{m}}\frac{(q^{r+1};q^{r+1})_{\ell-1}}{(q;q)_{\ell-1}}$
$\displaystyle=\sum_{\ell=1}^{\infty}\frac{(q^{r+1};q^{r+1})_{\ell-1}}{(q;q)_{\ell-1}}z^{r}q^{(r+1)\ell}\sum_{m=0}^{\infty}\frac{z^{m}q^{m\ell}}{(q;q)_{m}}$
$\displaystyle=\sum_{\ell=1}^{\infty}\frac{(q^{r+1};q^{r+1})_{\ell-1}}{(q;q)_{\ell-1}}z^{r}q^{(r+1)\ell}\frac{1}{(zq^{\ell};q)_{\infty}}$
$\displaystyle=z^{r}\sum_{n=0}^{\infty}\frac{q^{(r+1)(n+1)}(q^{r+1};q^{r+1})_{n}}{(q;q)_{n}(zq^{n+1};q)_{\infty}}.$
(4.5)

Note that

$\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}_{r}^{+}(n)}(maex(\lambda;r)-\Omega_{r}(\lambda))q^{n}=\left.\frac{\partial}{\partial{z}}\mathbb{P}_{r}^{+}(z,q)\right|_{z=1}-r\mathbb{P}_{r}^{+}(1,q).$
(4.6)

Now we calculate the two terms in the right hand side above. Firstly, by
(4.5), observe that

$\displaystyle\left.\frac{\partial}{\partial{z}}\mathbb{P}_{r}^{+}(z,q)\right|_{z=1}$
$\displaystyle=\left.\frac{\partial}{\partial{z}}z^{r}\sum_{n=0}^{\infty}\frac{q^{(r+1)(n+1)}(q^{r+1};q^{r+1})_{n}}{(q;q)_{n}(zq^{n+1};q)_{\infty}}\right|_{z=1}$
$\displaystyle=r\mathbb{P}_{r}^{+}(1,q)+\left.\frac{\partial}{\partial{z}}\sum_{n=0}^{\infty}\frac{q^{(r+1)(n+1)}(q^{r+1};q^{r+1})_{n}}{(q;q)_{n}(zq^{n+1};q)_{\infty}}\right|_{z=1}.$
(4.7)

Thus, from (4.5) and (4.7), we have

$\displaystyle\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}_{r}^{+}(n)}(maex(\lambda;r)-\Omega_{r}(\lambda))q^{n}$
$\displaystyle=\left.\frac{\partial}{\partial{z}}\sum_{n=0}^{\infty}\frac{q^{(r+1)(n+1)}(q^{r+1};q^{r+1})_{n}}{(q;q)_{n}(zq^{n+1};q)_{\infty}}\right|_{z=1}$
$\displaystyle=\sum_{n=0}^{\infty}\frac{q^{(r+1)(n+1)}(q^{r+1};q^{r+1})_{n}}{(q;q)_{n}}\left.\frac{\partial}{\partial{z}}\frac{1}{(zq^{n+1};q)_{\infty}}\right|_{z=1}$
$\displaystyle=\sum_{n=0}^{\infty}\frac{q^{(r+1)(n+1)}(q^{r+1};q^{r+1})_{n}}{(q;q)_{n}(zq^{n+1};q)_{\infty}}\left.\frac{\partial}{\partial{z}}\log\frac{1}{(zq^{n+1};q)_{\infty}}\right|_{z=1}$
$\displaystyle=\sum_{n=0}^{\infty}\frac{q^{(r+1)(n+1)}(q^{r+1};q^{r+1})_{n}}{(q;q)_{n}(zq^{n+1};q)_{\infty}}\sum_{m=1}^{\infty}\left.\frac{\partial}{\partial{z}}\left\\{-\log(1-zq^{n+m})\right\\}\right|_{z=1}$
$\displaystyle=\sum_{n=0}^{\infty}\frac{q^{(r+1)(n+1)}(q^{r+1};q^{r+1})_{n}}{(q;q)_{n}(q^{n+1};q)_{\infty}}\sum_{m=1}^{\infty}\frac{q^{n+m}}{1-q^{n+m}}$
$\displaystyle=\frac{1}{(q;q)_{\infty}}\sum_{n=0}^{\infty}q^{(r+1)(n+1)}(q^{r+1};q^{r+1})_{n}\sum_{m=n+1}^{\infty}\frac{q^{m}}{1-q^{m}}$
$\displaystyle=\frac{1}{(q;q)_{\infty}}\sum_{m=1}^{\infty}\frac{q^{m}}{1-q^{m}}\sum_{n=0}^{m-1}q^{(r+1)(n+1)}(q^{r+1};q^{r+1})_{n}$
$\displaystyle=\frac{1}{(q;q)_{\infty}}\sum_{m=1}^{\infty}\frac{q^{m}}{1-q^{m}}(1-(q^{r+1};q^{r+1})_{m}).$
(4.8)

Finally, using (4.2), (4.3), (4.4), and (4.8), we obtain

$\displaystyle\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}(\ell(\lambda)-maex(\lambda;r)+\Omega_{r}(\lambda))q^{n}=$
$\displaystyle\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}\ell(\lambda)q^{n}-\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}(maex(\lambda;r)-\Omega_{r}(\lambda))q^{n}$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}(n)}\ell(\lambda)q^{n}-\left(\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}_{r}^{0}(n)}(maex(\lambda;r)-\Omega_{r}(\lambda))q^{n}\right.$
$\displaystyle\left.+\sum_{n=0}^{\infty}\sum_{\lambda\in\mathcal{P}_{r}^{+}(n)}(maex(\lambda;r)-\Omega_{r}(\lambda))q^{n}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{(q;q)_{\infty}}\sum_{n=1}^{\infty}\frac{q^{n}}{1-q^{n}}-\left(-\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}\right.$
$\displaystyle+\left.\frac{1}{(q;q)_{\infty}}\sum_{m=1}^{\infty}\frac{q^{m}}{1-q^{m}}(1-(q^{r+1};q^{r+1})_{m})\right)$
$\displaystyle=$
$\displaystyle\frac{1}{(q;q)_{\infty}}\sum_{n=1}^{\infty}\frac{q^{n}}{1-q^{n}}+\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}$
$\displaystyle-\frac{1}{(q;q)_{\infty}}\sum_{m=1}^{\infty}\frac{q^{m}}{1-q^{m}}(1-(q^{r+1};q^{r+1})_{m})$
$\displaystyle=$
$\displaystyle\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}+\frac{1}{(q;q)_{\infty}}\sum_{m=1}^{\infty}\frac{q^{m}}{1-q^{m}}(q^{r+1};q^{r+1})_{m}.$

This finishes the proof. ∎

Next we aim to give a combinatorial proof for Theorem 1.10, which will be
similar to the bijection $\Gamma$ for Theorem 1.7. We first need to interpret
the right hand side of Theorem 1.10 as the generating function of certain
partition-theoretic objects. Recall that

$\sum_{n=0}^{\infty}S_{r+1}(n)q^{n}=\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}$
(4.9)

is the generating function for $(r+1)$ \- strict partitions. Let $W_{r}(n)$ be
the number of partitions of $n$ such that only the smallest part may have
multiplicity not congruent to $0$ mod $r$. Then we have

$\displaystyle\sum_{n=0}^{\infty}W_{r+1}(n)q^{n}$
$\displaystyle=1+\sum_{n=1}^{\infty}\frac{q^{n}}{1-q^{n}}\prod_{i=1}^{\infty}(1+q^{(r+1)(n+i)}+q^{2(r+1)(n+i)}+\cdots)$
$\displaystyle=1+\sum_{n=1}^{\infty}\frac{q^{n}}{1-q^{n}}\frac{1}{(q^{(n+1)(r+1)};q^{r+1})_{\infty}}$
$\displaystyle=1+\frac{1}{(q^{r+1};q^{r+1})_{\infty}}\sum_{n=1}^{\infty}\frac{q^{n}(q^{r+1};q^{r+1})_{n}}{1-q^{n}}.$
(4.10)

By (4.9) and (4.10), we finally get

$\left(\sum_{n=0}^{\infty}S_{r+1}(n)q^{n}\right)\left(\sum_{n=0}^{\infty}W_{r+1}(n)q^{n}\right)=\frac{(q^{r+1};q^{r+1})_{\infty}}{(q;q)_{\infty}}+\frac{1}{(q;q)_{\infty}}\sum_{n=1}^{\infty}\frac{q^{n}(q^{r+1};q^{r+1})_{n}}{1-q^{n}},$
(4.11)

which is the right hand side of Theorem 1.10.

Now we are ready to give the bijective proof. The coefficient of $q^{n}$ on
the left hand side of Theorem 1.10 is the number of ordered pairs
$(\lambda,i)$ such that

$\lambda\in\mathcal{P}(n),\quad\text{and}\quad 1\leq
i\leq\ell(\lambda)-maex(\lambda;r)+\Omega_{r}(\lambda).$ (4.12)

Coming to the right hand side of Theorem 1.10 and taking into account its
alternate form in (4.11), i.e.,
$\left(\sum_{n=0}^{\infty}S_{r+1}(n)q^{n}\right)\left(\sum_{n=0}^{\infty}W_{r+1}(n)q^{n}\right)$,
we see that the coefficient of $q^{n}$ here is the number of ordered pairs of
partitions $(\alpha,\beta)$ such that

$\displaystyle|\alpha|+|\beta|=n,\quad\text{$\alpha$ is an $(r+1)$ - strict
partition},$ $\displaystyle\text{$\nu_{\beta}(t)$ is divisible by $r+1$ for
$t>s(\beta)$}.$ (4.13)

So we aim to construct a bijection between the pairs of partitions in (4.12)
and (4.13). This time, we will need an operator similar to $\Psi$.

We define an operator $\Phi$ on pairs $(\alpha,\beta)$ of partitions. Firstly,
write $\beta$ in a more compact notation:

$\beta=\left(\beta_{1}^{\nu(\beta_{1})},\beta_{2}^{\nu(\beta_{2})},\ldots,\beta_{k}^{\nu(\beta_{k})}\right),$

with $\beta_{1}>\beta_{2}>\cdots>\beta_{k}$. Then for each $i$ we can find
unique nonnegative integers $q_{i},h_{i}$ such that

$\nu(\beta_{i})=q_{i}(r+1)+h_{i},$

where $r$ is a fixed positive integer and $0\leq h_{i}\leq r$. Now we keep all
the copies of $\beta_{k}$ in $\beta$, and for each $1\leq i\leq k-1$, we move
$h_{i}$ copies of $\beta_{i}$ from $\beta$ to $\alpha$. For the sake of
convenience let the resulting versions of $\alpha$ and $\beta$, by abuse of
notation, be represented by $\Phi(\alpha)$ and $\Phi(\beta)$ respectively.
Then we define $\Phi(\alpha,\beta):=(\Phi(\alpha),\Phi(\beta))$.

  * Bijective proof of Theorem 1.10.

For any $(\lambda,i)$ with $\lambda\in\mathcal{P}(n)$ and $1\leq
i\leq\ell(\lambda)-maex(\lambda;r)+\Omega_{r}(\lambda)$, define

$\Delta(\lambda,i)=\Phi(\lambda^{\prime}\downarrow^{(\ell(\lambda)+2-i)},\lambda^{\prime}\uparrow^{(\ell(\lambda)+2-i)}).$

We show that this gives a bijective proof for Theorem 1.10.

Firstly, we need to show that $\Delta$ is well defined. For this, all we need
to check is $1\leq\ell(\lambda)+2-i\leq\ell(\lambda)+1$, since otherwise, the
horizontal cut cannot be performed on $\lambda^{\prime}$. The second
inequality $\ell(\lambda)+2-i\leq\ell(\lambda)+1$ readily follows as $i\geq
1$. Now if $\lambda\in\mathcal{P}_{r}^{0}(n)$, then $\Omega_{r}(\lambda)=1$
and $maex(\lambda;r)=0$, so that $1\leq i\leq\ell(\lambda)+1$. This gives us
$\ell(\lambda)+2\geq i+1$ or $\ell(\lambda)+2-i\geq 1$. On the other hand, if
$\lambda\in\mathcal{P}_{r}^{+}(n)$, then we have $\Omega_{r}(\lambda)=r$ and
$r\leq maex(\lambda;r)<\ell(\lambda)$, so that

$\ell(\lambda)+2-i\geq\ell(\lambda)+2-\ell(\lambda)+maex(\lambda;r)-\Omega_{r}(\lambda)=2+maex(\lambda;r)-r\geq
2.$

So in both the cases, $\Delta$ is well defined.

Next, we need to show that
$\Phi(\lambda^{\prime}\downarrow^{(\ell(\lambda)+2-i)},\lambda^{\prime}\uparrow^{(\ell(\lambda)+2-i)})$
is of the type described in (4.13). By our choice of $i$ and the definition of
$maex(\lambda;r)$, one can see that
$\lambda^{\prime}\downarrow^{(\ell(\lambda)+2-i)}$ is always an $(r+1)$ \-
strict partition. So $\Phi(\lambda^{\prime}\downarrow^{(\ell(\lambda)+2-i)})$
is an $(r+1)$ \- strict partition as well. And from the definition of the
operator $\Phi$, it is clear that for
$\Phi(\lambda^{\prime}\uparrow^{(\ell(\lambda)+2-i)})$, only its smallest part
may have multiplicity not divisible by $r+1$. So
$\Phi(\lambda^{\prime}\downarrow^{(\ell(\lambda)+2-i)},\lambda^{\prime}\uparrow^{(\ell(\lambda)+2-i)})$
satisfies all the conditions that we are looking for.

Finally, we need to show that $\Delta$ is invertible. Given any pair
$(\alpha,\beta)$, we can first recover $\lambda$ in the same manner as that of
the inverse of $\Gamma$. And now one can see that $i$ is equal to $1$ plus the
number of parts in $\alpha$ which are less than or equal to the smallest part
of $\beta$. Here we take the smallest part of $\beta$ to be infinity when
$\beta$ is the empty partition. This concludes the proof. ∎

##  5\. Acknowledgements

The first author expresses his thanks towards his institution Pt. CLS Govt.
College, Sector-14, Karnal, Haryana under the aegis of Directorate of Higher
Education Haryana (India) for their immense support and for providing a
conducive research environment. The second author wishes to thank his current
employers BITS Pilani and former employers IIT Indore for the wonderful
research facilities. The third author is thankful to Prof. Ae Ja Yee for
fruitful discussions and for providing helpful suggestions. In addition, the
authors of this work are grateful to Dr. Damanvir Singh Binner for initial
discussions thereby providing impetus to this work.

## References

  * [1] H. L. Alder, Partition identities – From Euler to the present, _Amer. Math. Monthly_ , Issue 7, 76 (1969), 733–746.
  * [2] G. E. Andrews and D. Newman, Partitions and the minimal excludant, _Ann. Comb._ , 23(2) (2019), 249–254.
  * [3] G. E. Andrews and D. Newman, The minimal excludant in integer partitions, _J. Integer Seq._ , 23 (2020), Article 20.2.3.
  * [4] C. Ballantine and M. Merca, Combinatorial proof of the minimal excludant theorem, _Int. J. Number Theory_ , 17(08) (2021), 1765–1779.
  * [5] S. C. Bhoria, P. Eyyunni and B. Maji, A new generalization of the minimal excludant arising from an analogue of Franklin’s Identity, _Discrete Math._ , Issue 5, 346 (2023), 113334.
  * [6] S. Chern, Partitions and the maximal excludant, _Electron. J. Combin._ , 28(3) (2021), Article P3.13.
  * [7] F. Franklin, On partitions, _Johns Hopkins Univ. Cir._ , 2 (1883), p. 72.
  * [8] J. W. L. Glaisher, A theorem in partitions, _Messenger of Math._ , 12 (1883), 158–170.
  * [9] P. J. Grabner and A. Knopfmacher, Analysis of some partition statistics, _Ramanujan J._ , 12 (2006), 439–454.
  * [10] I. Pak, Partition bijections, a survey, _Ramanujan J._ , 12 (2006), 5–75.


# Selective Prediction for Semantic Segmentation using Post-Hoc Confidence
Estimation and Its Performance under Distribution Shift

Bruno L. C. Borges  Dept. of Electrical and Electronic Engineering
Federal University of Santa Catarina (UFSC)
Florianópolis, Brazil  Bruno M. Pacheco  Dept. of Automation and Systems
Engineering
Federal University of Santa Catarina (UFSC)
Florianópolis, Brazil  Danilo Silva Dept. of Electrical and Electronic
Engineering
Federal University of Santa Catarina (UFSC)
Florianópolis, Brazil

###### Abstract

Semantic segmentation plays a crucial role in various computer vision
applications, yet its efficacy is often hindered by the lack of high-quality
labeled data. To address this challenge, a common strategy is to leverage
models trained on data from different populations, such as publicly available
datasets. This approach, however, leads to the distribution shift problem,
presenting a reduced performance on the population of interest. In scenarios
where model errors can have significant consequences, selective prediction
methods offer a means to mitigate risks and reduce reliance on expert
supervision. This paper investigates selective prediction for semantic
segmentation in low-resource settings, thus focusing on post-hoc confidence
estimators applied to pre-trained models operating under distribution shift.
We propose a novel image-level confidence measure tailored for semantic
segmentation and demonstrate its effectiveness through experiments on three
medical imaging tasks. Our findings show that post-hoc confidence estimators
offer a cost-effective approach to reducing the impacts of distribution shift.

##  1 Introduction

Deep learning has demonstrated remarkable success in various computer vision
tasks, offering a powerful aid to labor-intensive processes. However, the
scarcity of labeled data hinders the use of state-of-the-art models in many
applications. This is particularly true in semantic segmentation of medical
images, as the high dimensionality of input and output coupled with the high
specialization needed for expert annotation usually implies in high costs for
labeled data.

To circumvent the data limitation, a common approach is to leverage models
trained on datasets drawn from different populations, giving rise to the
problem of distribution shift. For example, a hospital in a developing country
that does not have enough magnetic resonance images with high-quality
annotations to train a state-of-the-art tumor segmentation model can resort to
publicly available datasets on that application. However, the images used for
training come from a different distribution than those expected to be fed to
the model during clinical practice, as the acquisition hardware and the
subjects’ population may differ. Generally, the greater the degree of this
distribution shift between training and test (or deployment) data, the poorer
the generalization performance [Koh et al., 2021, Malinin et al., 2022].

In scenarios where model mistakes are critical, selective prediction methods
are valuable tools to reduce the costs with expert supervision, as proposed in
the seminal works of Geifman and El-Yaniv [2017] and Hendrycks and Gimpel
[2016]. At the core of selective prediction is the confidence estimator, a
scalar function used to determine whether the model should abstain from a
prediction and instead an expert should be invoked. A good confidence
estimator enables the trade-off between expected performance and abstention
rate of the deep learning model.

In this paper, we investigate the problem of selective prediction for semantic
segmentation in low-resource settings. Given a lack of high-quality annotated
data, we assume that a pre-trained model will be used and focus on post-hoc
confidence estimators. In other words, a deep learning model trained on a
different data distribution is used for inference, and the confidence
estimators have as input solely the model’s output. To evaluate the resulting
selective prediction methods, we perform our experiments in three medical
imaging segmentation tasks with state-of-the-art pre-trained models.
Furthermore, we propose a novel image-level confidence measure based on the
soft Dice loss [Sudre et al., 2017, Milletari et al., 2016], and show that it
outperforms all other confidence measures we tested.

The main contributions of this paper are summarized as follows:

  * •

This is the first paper to evaluate image-level post-hoc confidence measures
for selective prediction in semantic segmentation, extending the existing
methods for classification;

  * •

We propose a novel image-level confidence estimation method designed
specifically for image segmentation, which takes into account usual
segmentation evaluation metrics;

  * •

We evaluate all methods in 3 medical imaging tasks (polyp segmentation, optic
cup segmentation and multiple sclerosis lesion segmentation) under
distribution shift, and show that the proposed method significantly
outperforms other confidence estimators.

###  1.1 Related work

Given the increased labeling costs (in comparison to classification),
selective prediction methods for semantic segmentation hold great promise.
Many works [Nair et al., 2020, Jungo and Reyes, 2019, DeVries and Taylor,
2018, Lambert et al., 2022] have investigated the natural extension of
classification confidence measures to pixel-wise (or voxel-wise) confidence
estimation on semantic segmentation tasks. Such confidence maps (or
uncertainty maps) can be useful for explainability, but often the expert
intervention is performed on the whole image, rather than at pixel-level or
region-level, which results in a need for image-level confidence estimates.
Although the aggregation of pixel-level measures seems a natural choice, in
this paper we show that they are unsuitable for semantic segmentation and
instead proposed a novel measure designed specifically for this task.

Within the uncertainty estimation literature, a popular approach to compute
confidence is the use of ensembles, which combine multiple predictions made
for the same input; this includes conventional ensembles [Lakshminarayanan et
al., 2017, Wen et al., 2020, Kushibar et al., 2022] as well as techniques
based on Bayesian reasoning [Gal and Ghahramani, 2016, Malinin et al., 2022,
Lambert et al., 2022]. However, ensembles are not well suited to low-resource
settings, as they usually increase training, development and/or storage costs.
At the very least, ensembles either require multiple network passes for
inference, increasing operational costs, or require custom models with custom
training regimes, preventing the use of state-of-the-art, publicly-available
pre-trained models. To fit the low-resource paradigm, our scope is limited to
confidence estimation methods applicable to pre-trained single models.

We do not consider techniques to increase robustness to distribution shift, as
they are entirely orthogonal to our approach; as long as there is some
remaining performance gap due to distribution shift, selective prediction can
always be used as a last resort to reduce this gap.

##  2 Selective Prediction for Semantic Segmentation

###  2.1 Selective Prediction

Let $P$ be an unknown distribution over $\mathcal{X}\times\mathcal{Y}$, where
$\mathcal{X}$ is the input space and $\mathcal{Y}$ is the label space, and let
$h:\mathcal{X}\to\mathcal{Y}$ be a (predictive) model. The risk of $h$ is
$R(h)=E_{P}[\ell(h(x),y)]$, where
$\ell:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}^{+}$ is a loss function. A
selective model [Geifman and El-Yaniv, 2017, 2019] is a pair $(h,g)$, where
$g:\mathcal{X}\to\mathbb{R}$ is a confidence estimator (also known as
confidence score function or confidence-rate function), which quantifies the
model’s confidence on its prediction for a given input. For some fixed
threshold $t$, given an input $x$, the selective model makes a prediction
$h(x)$ if $g(x)\geq t$, otherwise the prediction is rejected. A selective
model’s coverage $\phi(h,g)=P[g(x)\geq t]$ is the probability mass of the
selected samples in $\mathcal{X}$, while its selective risk
$R(h,g)=E_{P}[\ell(h(x),y)\mid g(x)\geq t]$ is its risk restricted to the
selected samples. In particular, a model’s risk equals its selective risk at
full coverage (i.e., for $t$ such that $\phi(h,g)=1$). These quantities can be
evaluated empirically given a given a test dataset
$\\{(x^{(i)},y^{(i)})\\}_{i=1}^{N}$ drawn i.i.d. from $P$, yielding the
empirical coverage
$\hat{\phi}(h,g)=(1/N)\sum_{i=1}^{N}\mathbbm{1}[g(x^{(i)})\geq t]$ and the
empirical selective risk

$\hat{R}(h,g)=\frac{\sum_{i=1}^{N}\ell(h(x^{(i)}),y^{(i)})\mathbbm{1}[g(x^{(i)})\geq
t]}{\sum_{i=1}^{N}\mathbbm{1}[g(x^{(i)})\geq t]}.$ (1)

Note that, by varying $t$, it is generally possible to trade off coverage for
selective risk, i.e., a lower selective risk can usually (but not necessarily
always) be achieved if more samples are rejected. This tradeoff is captured by
the risk-coverage (RC) curve [Geifman and El-Yaniv, 2017], a plot of
$\hat{R}(h,g)$ as a function of $\hat{\phi}(h,g)$. While the RC curve provides
a full picture of the performance of a selective classifier, it is convenient
to have a scalar metric that summarizes this curve. A commonly used metric is
the area under the RC curve (AURC) [Ding et al., 2020, Geifman et al., 2019],
denoted by $\text{AURC}(h,g)$. However, the AURC is not always easy to
interpret. For a more tangible metric, we propose here a simple generalization
of the selective accuracy constraint [Galil et al., 2023] from classification
to generic prediction: the coverage at selective risk (CSR), defined as the
maximum coverage allowed for a model to achieve a specified risk.

In the case of semantic segmentation, inputs are images and labels are
segmentation masks, so, e.g., $\mathcal{X}=[0,1]^{n_{C}\times n_{W}\times
n_{H}}$ and $\mathcal{Y}=\\{0,1,\ldots,K-1\\}^{n_{W}\times n_{H}}$ if images
are $n_{W}\times n_{H}$ pixels with $n_{C}$ channels and segmentation masks
are divided into $K$ classes. Here we consider only binary segmentation, so
$K=2$. To simplify notation, we assume flattened segmentation masks, so that
$\mathcal{Y}=\\{0,1\\}^{n}$, where $n=n_{W}n_{H}$ is the total number of
output pixels. In the binary case, a commonly used quality metric is the Dice
Similarity Coefficient (DSC), defined as

$D(\hat{\mathbf{y}},\mathbf{y})=2\sum_{j=1}^{n}\hat{y}_{j}y_{j}/\sum_{j=1}^{n}(\hat{y}_{j}+y_{j})$

where $\hat{\mathbf{y}},\mathbf{y}\in\mathcal{Y}$. We convert it to a loss by
taking $\ell(\hat{\mathbf{y}},\mathbf{y})=1-D(\hat{\mathbf{y}},\mathbf{y})$.

###  2.2 Confidence estimators

We restrict attention to segmentation models that can be decomposed as
$h(x)=\mathbbm{1}[f(x)>\gamma]$, where $f:\mathcal{X}\to[0,1]^{n}$ is a neural
network, $\gamma\in[0,1]$ is a decision threshold (e.g., $\gamma=0.5$), and
$\mathbbm{1}[\cdot]$ denotes the indicator function extended to vectors in
element-wise fashion. In other words, if we denote $\hat{\mathbf{p}}=f(x)$,
then $\hat{p}_{j}$ can be interpreted as an estimate of the posterior
probability $P[y_{j}=1|x]$ that the $j$th pixel of the ground truth mask is
equal to 1.

We focus on confidence estimators that can be computed directly from the model
outputs $\hat{\mathbf{p}}=f(x)$ and $\hat{\mathbf{y}}=h(x)$. To the best of
our knowledge, image-level confidence estimators applicable to a single model
had not been proposed before, so first we consider a few natural baselines.

The first two are based on widely-used pixel-level confidence estimators,
namely, the maximum softmax probability (MSP) [Hendrycks and Gimpel, 2016,
Geifman and El-Yaniv, 2017, Ding et al., 2020]

$g_{j}(x)=\max\\{\hat{p}_{j},1-\hat{p}_{j}\\}$

and the negative entropy111Note that any uncertainty estimator can be used as
a confidence estimator by taking its negative. [Belghazi and Lopez-Paz, 2021]

$g_{j}(x)=\hat{p}_{j}\log\hat{p}_{j}+(1-\hat{p}_{j})\log(1-\hat{p}_{j}).$

We adapt them to image-level confidence estimators by taking their mean over
all pixels, $g(x)=(1/n)\sum_{j=1}^{n}g_{j}(x)$.

The third baseline exploits a peculiarity of the Dice score. As shown in
[Carass et al., 2020, Raina et al., 2023, Malinin et al., 2022], the Dice
score is biased towards providing higher scores to images with higher
prevalence of lesion. With this in mind, we propose as a baseline confidence
estimator the predicted lesion load, computed as the proportion of the
predicted foreground class of an image, namely,

$g(x)=\hat{\rho}(x)\triangleq(1/n)\sum_{j=1}^{n}\hat{y}_{j}.$

Finally, we propose a confidence measure based on the Dice coefficient. Our
motivation is to have a confidence estimator somehow connected to the
evaluation metric. We define the soft Dice confidence (SDC) as222The SDC is
inspired by and closely related to the soft Dice loss (SDL) [Sudre et al.,
2017]; specifically, it is equal to 1 minus SDL when the hard predictions
$\hat{\mathbf{y}}$ are used in place of the ground truth $\mathbf{y}$.

$g(x)=2\sum_{j=1}^{n}\hat{p}_{j}\hat{y}_{j}/\sum_{j=1}^{n}(\hat{p}_{j}+\hat{y}_{j}).$

Note that the SDC increases as the confidence of a gixen pixel increases
within the same class; in particular, it is highest (equal to 1) when
$\hat{\mathbf{p}}=\hat{\mathbf{y}}$. On the other hand, when the model is
least confident at the pixel level, $\hat{\mathbf{p}}\approx\gamma$, it can be
shown that $g(x)\approx 2\gamma/(1+\gamma/\hat{\rho}(x))$, which is an
increasing function of the predicted lesion load $\hat{\rho}(x)$. Thus, in
this case, it at least retains the properties of the lesion load baseline.

##  3 Experiments and Results

###  3.1 Semantic Segmentation tasks

In the following we describe the segmentation tasks and respective models
considered, as well as the datasets used for in-distribution (ID) and out-of-
distribution (OOD) evaluation.

####  3.1.1 Polyp Segmentation

Polyp segmentation in colonoscopy images aids identification and evaluation of
these clumps, which is key in colorectal cancer prevention [Jha et al., 2019].
In our study, we build the dataset for polyp segmentation as reported in Dong
et al. [2023]. More specifically, 900 images from KvasirSEG [Jha et al., 2019]
and 548 images from ClinicDB [Bernal et al., 2015] build the training set,
while the remaining 162 images from both are used for ID evaluation. The OOD
dataset is composed with 196 images from ETIS [Silva et al., 2014], 380 images
from ColonDB [Tajbakhsh et al., 2016], and 60 images from EndoScene [Vázquez
et al., 2017].

As segmentation models, we use the Polyp-PVT, a deep learning model based on
the pyramid vision transformer (PVT), and a baseline U-Net. Both models were
made available (both structure and weights) by Dong et al. [2023].

####  3.1.2 Optic Cup Segmentation

Accurately segmenting the cup and disc in color fundus photography (CFP) plays
a key role in the early diagnosis of glaucoma and the prevention of
irreversible vision loss [Orlando et al., 2020]. To instantiate optic cup
segmentation task, we use three publicly available datasets: REFUGE [Orlando
et al., 2020], with 1600 images; ORIGA [Zhuo Zhang et al., 2010], with 650
images; and G1020 [Bajwa et al., 2020], with 1020 images. 1200 images from
REFUGE compose the training set, while the remaining 400 images are used as
the ID evaluation set, and the entirety of ORIGA and G1020 compose the OOD
evaluation set. All images (and corresponding masks) were preprocessed by the
MNet DeepCDR model [Fu et al., 2018] to crop a region of interest containing
the optic disc and cup. To maintain consistency with the other tasks, images
corresponding to labels with $\mathbf{y}=\boldsymbol{0}$ (no optic cup
appearing in the ground truth mask) were systematically excluded as they
trivially indicate a preprocessing failure. Therefore, the resulting revised
evaluation datasets comprise 394 images from REFUGE, 648 from ORIGA, and 782
from G1020.

For segmentation, we use the Segtran model, developed and made available by Li
et al. [2021]. The authors aim to streak a balance between increasing context
and improving localization accuracy by combining a convolutional backbone with
a series of squeeze-and-expansion transformer layers.

####  3.1.3 Multiple Sclerosis White Matter Lesion (MSWML) Segmentation

The segmentation of white matter lesions caused by multiple sclerosis helps
physicians follow the progress of the disease through the evolution of the
lesions [Thompson et al., 2018]. We use the datasets and baseline segmentation
model provided in the Shifts 2.0 challenge [Malinin et al., 2022]. We consider
the ISBI [Carass et al., 2017] and MSSEG-1 [Commowick et al., 2018] as ID
data, while the PubMRI [Lesjak et al., 2018] is considered OOD. The ID
evaluation set contains 33 images from each source, while the OOD set contains
25 images.

As our baseline segmentation model, we use a (single-model) 3D U-Net made
available by the competition organizers, as few competitors were able to
overcome the baseline performance in terms of ID and OOD Dice score.

###  3.2 Results

For each task and model, we evaluate the confidence estimators presented in
Sec. 2.2 with respect to their selective prediction performance on OOD data,
simulating the low-resource setting described in Sec. 1. As a bound, we also
evaluate a hypothetically optimal confidence estimator (denoted “ideal”) that
perfectly orders samples in decreasing order of their losses. Following the
literature on selective prediction, we use the AURC metric, with selective
risk taken as 1 minus the average Dice score over the selected samples (see
Sec. 2.1). The results are shown in Table 1 where, for comparison, the
performance on ID data is also shown. The full RC curves for all task-model
pairs on ID and OOD data are shown in Fig. 1 and Fig. 2, respectively. Even
though the performances differ significantly between tasks (and even between
models, as in the case of the polyp segmentation), the proposed confidence
estimator SDC visibly achieves the best overall performance, providing the
smallest risk in almost all coverage levels for all tasks and models.
Furthermore, the predicted lesion load, although being a simple heuristic,
presents a reasonable performance in some cases, substantiating the intuition
that originated it. On the other hand, the two baselines derived from pixel-
level confidence estimators sometimes show performance even worse than a
random ordering of predictions (whose performance is always equal to the full-
coverage risk).

Table 1: AURC of confidence estimators across all task-model pairs (lower is better). _Risk_ indicates the original risk without selective prediction, which equals the AURC of the random estimator. | Polyp (PVT) | Polyp (U-Net) | Optic cup (Segtran) | MSWML (U-Net)
---|---|---|---|---
| ID | OOD | ID | OOD | ID | OOD | ID | OOD
Risk | 0.072 | 0.186 | 0.173 | 0.507 | 0.074 | 0.228 | 0.377 | 0.497
MSP | 0.068 | 0.129 | 0.099 | 0.370 | 0.078 | 0.270 | 0.414 | 0.600
Negative Entropy | 0.068 | 0.128 | 0.091 | 0.319 | 0.078 | 0.268 | 0.418 | 0.595
Lesion Load | 0.063 | 0.185 | 0.170 | 0.333 | 0.064 | 0.169 | 0.302 | 0.355
SDC | 0.036 | 0.076 | 0.059 | 0.217 | 0.058 | 0.146 | 0.282 | 0.338
Ideal | 0.028 | 0.062 | 0.049 | 0.195 | 0.047 | 0.119 | 0.259 | 0.326

(a) Polyp (PVT)

(b) Polyp (U-Net)

(c) Optic cup (Segtran)

(d) MSWML (U-Net)

Figure 1: Risk-coverage curves for all confidence estimators across all task-
model pairs on the respective ID evaluation sets. The dashed lines represent
the random confidence estimator (horizontal line) and the ideal confidence
estimator.

(a) Polyp (PVT)

(b) Polyp (U-Net)

(c) Optic cup (Segtran)

(d) MSWML (U-Net)

Figure 2: Risk-coverage curves for all confidence estimators across all task-
model pairs on the respective OOD evaluation sets. The dashed lines represent
the random confidence estimator (horizontal line) and the ideal confidence
estimator.

Finally, to give a more tangible illustration of the potential of selective
prediction, in Table 2 we measure the maximum coverage on OOD data that
produces a selective risk equal to that obtained at full coverage on ID data
(assuming that the ID performance of the models would be considered
satisfactory). In other words, for each confidence estimator, we estimate how
much of the OOD data can be processed solely by the deep learning model
(instead of resorting to an expert) so that no performance drop is observed
due to the distribution shift. It can be seen that the SDC is not only the
best option by a wide margin, but also the only that provided consistent
results. However, we can also see that this metric is highly dependent on the
task and model.

Table 2: Maximum coverage of the OOD dataset using the designated confidence estimator that reproduces the ID risk at 100 % coverage (higher is better). Blank values (-) indicate that the corresponding ID risk could not be achieved for any coverage levels. | Polyp (PVT) | Polyp (U-Net) | Optic cup (Segtran) | MSWML (U-Net)
---|---|---|---|---
MSP | - | - | - | -
Negative Entropy | - | 6.0 % | - | -
Lesion Load | - | - | - | 56.0 %
SDC | 60.5 % | 49.5 % | 0.8 % | 64.0 %
Ideal | 70.9 % | 56.8 % | 18.3 % | 64.0 %

Our full results on OOD data broken-down by each data source are presented in
Appendix A.

##  4 Conclusion

In this paper, we evaluated confidence estimators for semantic segmentation
with respect to their selective prediction capacity in the context of
distribution shift due to the lack of in-domain, high-quality data. The
proposed confidence estimator, soft Dice confidence, outperformed all other
confidence estimators evaluated, as shown through the RC curves of our results
(see Fig. 1, Fig. 2 and Table 1).

Furthermore, our results suggest that selective prediction can be a viable
option for tackling the distribution shift problem when other options have
been exhausted. With a suitable confidence estimator, a selective model
provides a sensible way of achieving ID performance during clinical practice,
while saving on expert costs. The evaluation through the maximum coverage to
achieve ID performance in OOD data (see Table 2) demonstrates such goal, as
this ratio can be directly translated into expert hours that could be saved by
employing a selective model. However, despite a significant performance in the
tasks of polyp and MSWML segmentation, the poor performance on optic cup
segmentation indicates that there is still a wide avenue for future research.

## References

  * Bajwa et al. [2020] Muhammad Naseer Bajwa, Gur Amrit Pal Singh, Wolfgang Neumeier, Muhammad Imran Malik, Andreas Dengel, and Sheraz Ahmed.  G1020: A Benchmark Retinal Fundus Image Dataset for Computer-Aided Glaucoma Detection.  2020\.  10.48550/ARXIV.2006.09158.  URL https://arxiv.org/abs/2006.09158.  Publisher: arXiv Version Number: 1.
  * Belghazi and Lopez-Paz [2021] Mohamed Ishmael Belghazi and David Lopez-Paz.  What classifiers know what they don’t?, July 2021.  URL http://arxiv.org/abs/2107.06217.
  * Bernal et al. [2015] Jorge Bernal, F. Javier Sánchez, Gloria Fernández-Esparrach, Debora Gil, Cristina Rodríguez, and Fernando Vilariño.  WM-DOVA maps for accurate polyp highlighting in colonoscopy: Validation vs. saliency maps from physicians.  _Computerized Medical Imaging and Graphics_ , 43:99–111, July 2015.  ISSN 0895-6111.  10.1016/j.compmedimag.2015.02.007.  URL https://www.sciencedirect.com/science/article/pii/S0895611115000567.
  * Carass et al. [2017] Aaron Carass, Snehashis Roy, Amod Jog, Jennifer L. Cuzzocreo, Elizabeth Magrath, Adrian Gherman, Julia Button, James Nguyen, Ferran Prados, Carole H. Sudre, Manuel Jorge Cardoso, Niamh Cawley, Olga Ciccarelli, Claudia A. M. Wheeler-Kingshott, Sébastien Ourselin, Laurence Catanese, Hrishikesh Deshpande, Pierre Maurel, Olivier Commowick, Christian Barillot, Xavier Tomas-Fernandez, Simon K. Warfield, Suthirth Vaidya, Abhijith Chunduru, Ramanathan Muthuganapathy, Ganapathy Krishnamurthi, Andrew Jesson, Tal Arbel, Oskar Maier, Heinz Handels, Leonardo O. Iheme, Devrim Unay, Saurabh Jain, Diana M. Sima, Dirk Smeets, Mohsen Ghafoorian, Bram Platel, Ariel Birenbaum, Hayit Greenspan, Pierre-Louis Bazin, Peter A. Calabresi, Ciprian M. Crainiceanu, Lotta M. Ellingsen, Daniel S. Reich, Jerry L. Prince, and Dzung L. Pham.  Longitudinal multiple sclerosis lesion segmentation: Resource and challenge.  _NeuroImage_ , 148:77–102, March 2017.  ISSN 1053-8119.  10.1016/j.neuroimage.2016.12.064.  URL https://www.sciencedirect.com/science/article/pii/S1053811916307819.
  * Carass et al. [2020] Aaron Carass, Snehashis Roy, Adrian Gherman, Jacob C. Reinhold, Andrew Jesson, Tal Arbel, Oskar Maier, Heinz Handels, Mohsen Ghafoorian, Bram Platel, Ariel Birenbaum, Hayit Greenspan, Dzung L. Pham, Ciprian M. Crainiceanu, Peter A. Calabresi, Jerry L. Prince, William R. Gray Roncal, Russell T. Shinohara, and Ipek Oguz.  Evaluating White Matter Lesion Segmentations with Refined Sørensen-Dice Analysis.  _Scientific Reports_ , 10(1):8242, May 2020.  ISSN 2045-2322.  10.1038/s41598-020-64803-w.  URL https://www.nature.com/articles/s41598-020-64803-w.  Number: 1 Publisher: Nature Publishing Group.
  * Commowick et al. [2018] Olivier Commowick, Audrey Istace, Michaël Kain, Baptiste Laurent, Florent Leray, Mathieu Simon, Sorina Camarasu Pop, Pascal Girard, Roxana Améli, Jean-Christophe Ferré, Anne Kerbrat, Thomas Tourdias, Frédéric Cervenansky, Tristan Glatard, Jérémy Beaumont, Senan Doyle, Florence Forbes, Jesse Knight, April Khademi, Amirreza Mahbod, Chunliang Wang, Richard McKinley, Franca Wagner, John Muschelli, Elizabeth Sweeney, Eloy Roura, Xavier Lladó, Michel M. Santos, Wellington P. Santos, Abel G. Silva-Filho, Xavier Tomas-Fernandez, Hélène Urien, Isabelle Bloch, Sergi Valverde, Mariano Cabezas, Francisco Javier Vera-Olmos, Norberto Malpica, Charles Guttmann, Sandra Vukusic, Gilles Edan, Michel Dojat, Martin Styner, Simon K. Warfield, François Cotton, and Christian Barillot.  Objective Evaluation of Multiple Sclerosis Lesion Segmentation using a Data Management and Processing Infrastructure.  _Scientific Reports_ , 8(1):13650, September 2018.  ISSN 2045-2322.  10.1038/s41598-018-31911-7.  URL https://www.nature.com/articles/s41598-018-31911-7.  Number: 1 Publisher: Nature Publishing Group.
  * DeVries and Taylor [2018] Terrance DeVries and Graham W. Taylor.  Leveraging Uncertainty Estimates for Predicting Segmentation Quality.  2018\.  10.48550/ARXIV.1807.00502.  URL https://arxiv.org/abs/1807.00502.  Publisher: arXiv Version Number: 1.
  * Ding et al. [2020] Yukun Ding, Jinglan Liu, Jinjun Xiong, and Yiyu Shi.  Revisiting the Evaluation of Uncertainty Estimation and Its Application to Explore Model Complexity-Uncertainty Trade-Off.  In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , pages 22–31, June 2020.  10.1109/CVPRW50498.2020.00010.  URL https://ieeexplore.ieee.org/document/9150782.  ISSN: 2160-7516.
  * Dong et al. [2023] Bo Dong, Wenhai Wang, Deng-Ping Fan, Jinpeng Li, Huazhu Fu, and Ling Shao.  Polyp-PVT: Polyp Segmentation with Pyramid Vision Transformers, April 2023.  URL http://arxiv.org/abs/2108.06932.  arXiv:2108.06932 [cs, eess].
  * Fu et al. [2018] Huazhu Fu, Jun Cheng, Yanwu Xu, Changqing Zhang, Damon Wing Kee Wong, Jiang Liu, and Xiaochun Cao.  Disc-aware Ensemble Network for Glaucoma Screening from Fundus Image.  _IEEE Transactions on Medical Imaging_ , 37(11):2493–2501, November 2018.  ISSN 0278-0062, 1558-254X.  10.1109/TMI.2018.2837012.  URL http://arxiv.org/abs/1805.07549.  arXiv:1805.07549 [cs].
  * Gal and Ghahramani [2016] Yarin Gal and Zoubin Ghahramani.  Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pages 1050–1059, New York, New York, USA, June 2016. PMLR.  URL https://proceedings.mlr.press/v48/gal16.html.
  * Galil et al. [2023] Ido Galil, Mohammed Dabbah, and Ran El-Yaniv.  What Can We Learn From The Selective Prediction And Uncertainty Estimation Performance Of 523 Imagenet Classifiers, February 2023.  URL http://arxiv.org/abs/2302.11874.  arXiv:2302.11874 [cs].
  * Geifman and El-Yaniv [2017] Yonatan Geifman and Ran El-Yaniv.  Selective Classification for Deep Neural Networks.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/hash/4a8423d5e91fda00bb7e46540e2b0cf1-Abstract.html.
  * Geifman and El-Yaniv [2019] Yonatan Geifman and Ran El-Yaniv.  SelectiveNet: A Deep Neural Network with an Integrated Reject Option.  In _Proceedings of the 36th International Conference on Machine Learning_ , pages 2151–2159. PMLR, May 2019.  URL https://proceedings.mlr.press/v97/geifman19a.html.  ISSN: 2640-3498.
  * Geifman et al. [2019] Yonatan Geifman, Guy Uziel, and Ran El-Yaniv.  Bias-Reduced Uncertainty Estimation for Deep Neural Classifiers, April 2019.  URL http://arxiv.org/abs/1805.08206.  arXiv:1805.08206 [cs, stat].
  * Hendrycks and Gimpel [2016] Dan Hendrycks and Kevin Gimpel.  A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks.  2016\.  10.48550/ARXIV.1610.02136.  URL https://arxiv.org/abs/1610.02136.  Publisher: arXiv Version Number: 3.
  * Jha et al. [2019] Debesh Jha, Pia H. Smedsrud, Michael A. Riegler, Pål Halvorsen, Thomas de Lange, Dag Johansen, and Håvard D. Johansen.  Kvasir-SEG: A Segmented Polyp Dataset, November 2019.  URL http://arxiv.org/abs/1911.07069.  arXiv:1911.07069 [cs, eess].
  * Jungo and Reyes [2019] Alain Jungo and Mauricio Reyes.  Assessing Reliability and Challenges of Uncertainty Estimations for Medical Image Segmentation.  In Dinggang Shen, Tianming Liu, Terry M. Peters, Lawrence H. Staib, Caroline Essert, Sean Zhou, Pew-Thian Yap, and Ali Khan, editors, _Medical Image Computing and Computer Assisted Intervention – MICCAI 2019_ , volume 11765, pages 48–56. Springer International Publishing, Cham, 2019.  ISBN 978-3-030-32244-1 978-3-030-32245-8.  10.1007/978-3-030-32245-8_6.  URL https://link.springer.com/10.1007/978-3-030-32245-8_6.  Series Title: Lecture Notes in Computer Science.
  * Koh et al. [2021] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran Haque, Sara M Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang.  WILDS: A Benchmark of in-the-Wild Distribution Shifts.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 5637–5664. PMLR, July 2021.  URL https://proceedings.mlr.press/v139/koh21a.html.
  * Kushibar et al. [2022] Kaisar Kushibar, Víctor Manuel Campello, Lidia Garrucho Moras, Akis Linardos, Petia Radeva, and Karim Lekadir.  Layer Ensembles: A Single-Pass Uncertainty Estimation in Deep Learning for Segmentation, March 2022.  URL http://arxiv.org/abs/2203.08878.  arXiv:2203.08878 [cs, eess].
  * Lakshminarayanan et al. [2017] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell.  Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/hash/9ef2ed4b7fd2c810847ffa5fa85bce38-Abstract.html.
  * Lambert et al. [2022] Benjamin Lambert, Florence Forbes, Senan Doyle, Alan Tucholka, and Michel Dojat.  Fast Uncertainty Quantification for Deep Learning-based MR Brain Segmentation.  page 1, January 2022.  URL https://hal.science/hal-03498120.
  * Lesjak et al. [2018] Žiga Lesjak, Alfiia Galimzianova, Aleš Koren, Matej Lukin, Franjo Pernuš, Boštjan Likar, and Žiga Špiclin.  A Novel Public MR Image Dataset of Multiple Sclerosis Patients With Lesion Segmentations Based on Multi-rater Consensus.  _Neuroinformatics_ , 16(1):51–63, January 2018.  ISSN 1539-2791, 1559-0089.  10.1007/s12021-017-9348-7.  URL http://link.springer.com/10.1007/s12021-017-9348-7.
  * Li et al. [2021] Shaohua Li, Xiuchao Sui, Xiangde Luo, Xinxing Xu, Yong Liu, and Rick Goh.  Medical Image Segmentation Using Squeeze-and-Expansion Transformers, June 2021.  URL http://arxiv.org/abs/2105.09511.  arXiv:2105.09511 [cs, eess] version: 3.
  * Malinin et al. [2022] Andrey Malinin, Neil Band, Ganshin, Alexander, German Chesnokov, Yarin Gal, Mark J. F. Gales, Alexey Noskov, Andrey Ploskonosov, Liudmila Prokhorenkova, Ivan Provilkov, Vatsal Raina, Vyas Raina, Roginskiy, Denis, Mariya Shmatova, Panos Tigas, and Boris Yangel.  Shifts: A Dataset of Real Distributional Shift Across Multiple Large-Scale Tasks, February 2022.  URL http://arxiv.org/abs/2107.07455.  arXiv:2107.07455 [cs, stat].
  * Milletari et al. [2016] Fausto Milletari, Nassir Navab, and Seyed-Ahmad Ahmadi.  V-Net: Fully Convolutional Neural Networks for Volumetric Medical Image Segmentation.  In _2016 Fourth International Conference on 3D Vision (3DV)_ , pages 565–571, Stanford, CA, USA, October 2016. IEEE.  ISBN 978-1-5090-5407-7.  10.1109/3DV.2016.79.  URL http://ieeexplore.ieee.org/document/7785132/.
  * Nair et al. [2020] Tanya Nair, Doina Precup, Douglas L. Arnold, and Tal Arbel.  Exploring uncertainty measures in deep networks for Multiple sclerosis lesion detection and segmentation.  _Medical Image Analysis_ , 59:101557, January 2020.  ISSN 13618415.  10.1016/j.media.2019.101557.  URL https://linkinghub.elsevier.com/retrieve/pii/S1361841519300994.
  * Orlando et al. [2020] José Ignacio Orlando, Huazhu Fu, João Barbossa Breda, Karel van Keer, Deepti R. Bathula, Andrés Diaz-Pinto, Ruogu Fang, Pheng-Ann Heng, Jeyoung Kim, JoonHo Lee, Joonseok Lee, Xiaoxiao Li, Peng Liu, Shuai Lu, Balamurali Murugesan, Valery Naranjo, Sai Samarth R. Phaye, Sharath M. Shankaranarayana, Apoorva Sikka, Jaemin Son, Anton van den Hengel, Shujun Wang, Junyan Wu, Zifeng Wu, Guanghui Xu, Yongli Xu, Pengshuai Yin, Fei Li, Xiulan Zhang, Yanwu Xu, Xiulan Zhang, and Hrvoje Bogunović.  REFUGE Challenge: A Unified Framework for Evaluating Automated Methods for Glaucoma Assessment from Fundus Photographs.  _Medical Image Analysis_ , 59:101570, January 2020.  ISSN 13618415.  10.1016/j.media.2019.101570.  URL http://arxiv.org/abs/1910.03667.  arXiv:1910.03667 [cs].
  * Raina et al. [2023] Vatsal Raina, Nataliia Molchanova, Mara Graziani, Andrey Malinin, Henning Muller, Meritxell Bach Cuadra, and Mark Gales.  Tackling Bias in the Dice Similarity Coefficient: Introducing nDSC for White Matter Lesion Segmentation, February 2023.  URL http://arxiv.org/abs/2302.05432.  arXiv:2302.05432 [cs, eess].
  * Silva et al. [2014] Juan Silva, Aymeric Histace, Olivier Romain, Xavier Dray, and Bertrand Granado.  Toward embedded detection of polyps in WCE images for early diagnosis of colorectal cancer.  _International Journal of Computer Assisted Radiology and Surgery_ , 9(2):283–293, March 2014.  ISSN 1861-6410, 1861-6429.  10.1007/s11548-013-0926-3.  URL http://link.springer.com/10.1007/s11548-013-0926-3.
  * Sudre et al. [2017] Carole H. Sudre, Wenqi Li, Tom Vercauteren, Sebastien Ourselin, and M. Jorge Cardoso.  Generalised Dice Overlap as a Deep Learning Loss Function for Highly Unbalanced Segmentations.  In M. Jorge Cardoso, Tal Arbel, Gustavo Carneiro, Tanveer Syeda-Mahmood, João Manuel R.S. Tavares, Mehdi Moradi, Andrew Bradley, Hayit Greenspan, João Paulo Papa, Anant Madabhushi, Jacinto C. Nascimento, Jaime S. Cardoso, Vasileios Belagiannis, and Zhi Lu, editors, _Deep Learning in Medical Image Analysis and Multimodal Learning for Clinical Decision Support_ , volume 10553, pages 240–248. Springer International Publishing, Cham, 2017.  ISBN 978-3-319-67557-2 978-3-319-67558-9.  10.1007/978-3-319-67558-9_28.  URL http://link.springer.com/10.1007/978-3-319-67558-9_28.  Series Title: Lecture Notes in Computer Science.
  * Tajbakhsh et al. [2016] Nima Tajbakhsh, Suryakanth R. Gurudu, and Jianming Liang.  Automated Polyp Detection in Colonoscopy Videos Using Shape and Context Information.  _IEEE Transactions on Medical Imaging_ , 35(2):630–644, February 2016.  ISSN 1558-254X.  10.1109/TMI.2015.2487997.  URL https://ieeexplore.ieee.org/document/7294676.  Conference Name: IEEE Transactions on Medical Imaging.
  * Thompson et al. [2018] Alan J Thompson, Brenda L Banwell, Frederik Barkhof, William M Carroll, Timothy Coetzee, Giancarlo Comi, Jorge Correale, Franz Fazekas, Massimo Filippi, Mark S Freedman, Kazuo Fujihara, Steven L Galetta, Hans Peter Hartung, Ludwig Kappos, Fred D Lublin, Ruth Ann Marrie, Aaron E Miller, David H Miller, Xavier Montalban, Ellen M Mowry, Per Soelberg Sorensen, Mar Tintoré, Anthony L Traboulsee, Maria Trojano, Bernard M J Uitdehaag, Sandra Vukusic, Emmanuelle Waubant, Brian G Weinshenker, Stephen C Reingold, and Jeffrey A Cohen.  Diagnosis of multiple sclerosis: 2017 revisions of the McDonald criteria.  _The Lancet Neurology_ , 17(2):162–173, February 2018.  ISSN 1474-4422.  10.1016/S1474-4422(17)30470-2.  URL https://www.sciencedirect.com/science/article/pii/S1474442217304702.
  * Vázquez et al. [2017] David Vázquez, Jorge Bernal, F. Javier Sánchez, Gloria Fernández-Esparrach, Antonio M. López, Adriana Romero, Michal Drozdzal, and Aaron Courville.  A Benchmark for Endoluminal Scene Segmentation of Colonoscopy Images.  _Journal of Healthcare Engineering_ , 2017:1–9, 2017.  ISSN 2040-2295, 2040-2309.  10.1155/2017/4037190.  URL https://www.hindawi.com/journals/jhe/2017/4037190/.
  * Wen et al. [2020] Yeming Wen, Dustin Tran, and Jimmy Ba.  BatchEnsemble: An Alternative Approach to Efficient Ensemble and Lifelong Learning, February 2020.  URL http://arxiv.org/abs/2002.06715.  arXiv:2002.06715 [cs, stat].
  * Zhuo Zhang et al. [2010] Zhuo Zhang, Feng Shou Yin, Jiang Liu, Wing Kee Wong, Ngan Meng Tan, Beng Hai Lee, Jun Cheng, and Tien Yin Wong.  ORIGA${}^{\textrm{-light}}$: An online retinal fundus image database for glaucoma analysis and research.  In _2010 Annual International Conference of the IEEE Engineering in Medicine and Biology_ , pages 3065–3068, Buenos Aires, August 2010. IEEE.  ISBN 978-1-4244-4123-5 978-1-4244-4124-2.  10.1109/IEMBS.2010.5626137.  URL http://ieeexplore.ieee.org/document/5626137/.

Selective Prediction for Semantic Segmentation using Post-Hoc Confidence
Estimation and Its Performance under Distribution Shift
(Supplementary Material)

##  Appendix A Full Results on OOD Data

###  A.1 Polyp segmentation

Table 3: AURC of confidence estimators across the Polyp task (lower is better). _Risk_ indicates the original risk without selective prediction, which equals the AURC of the random estimator. | Polyp (PVT) | Polyp (U-Net)
---|---|---
| ColonDB | ETIS | Endoscene | ColonDB | ETIS | Endoscene
Risk | 0.189 | 0.210 | 0.096 | 0.496 | 0.597 | 0.283
MSP | 0.137 | 0.137 | 0.075 | 0.357 | 0.526 | 0.206
Negative Entropy | 0.136 | 0.134 | 0.075 | 0.306 | 0.476 | 0.152
Lesion Load | 0.203 | 0.160 | 0.104 | 0.320 | 0.389 | 0.304
SDC | 0.080 | 0.078 | 0.064 | 0.207 | 0.301 | 0.108
Ideal | 0.065 | 0.066 | 0.049 | 0.188 | 0.262 | 0.093
Table 4: Maximum coverage of the OOD dataset for Polyp using the designated confidence estimator that reproduces the ID risk at 100 % coverage (higher is better). Blank values (-) indicate that the corresponding ID risk could not be achieved for any coverage levels. | Polyp (PVT) | Polyp (U-Net)
---|---|---
| ColonDB | ETIS | Endoscene | ColonDB | ETIS | Endoscene
MSP | - | - | 76.7 % | - | 1.5 % | 76.7 %
Negative Entropy | - | - | 78.3 % | 1.8 % | 2.0 % | 76.7 %
Lesion Load | - | 9.2 % | 3.3 % | 0.3 % | - | -
SDC | 58.7 % | 53.1 % | 83.3 % | 54.0 % | 30.1 % | 85.0 %
Ideal | 68.9 % | 67.3 % | 93.3 % | 58.7 % | 43.4 % | 85.0 %

###  A.2 Optic cup segmentation

Table 5: AURC of confidence estimators across the Optic cup task (lower is better). _Risk_ indicates the original risk without selective prediction, which equals the AURC of the random estimator. | Optic cup (Segtran)
---|---
| ORIGA | G1020
Risk | 0.212 | 0.241
MSP | 0.268 | 0.276
Negative Entropy | 0.269 | 0.273
Lesion Load | 0.145 | 0.187
SDC | 0.134 | 0.154
Ideal | 0.109 | 0.129
Table 6: Maximum coverage of the OOD dataset for Optic cup using the designated confidence estimator that reproduces the ID risk at 100 % coverage (higher is better). Blank values (-) indicate that the corresponding ID risk could not be achieved for any coverage levels. | Optic cup (Segtran)
---|---
| ORIGA | G1020
MSP | - | -
Negative Entropy |  | -
Lesion Load | - | 0.3 %
SDC | 1.7 % | 0.9 %
Ideal | 23.6 % | 13.6 %