# Hankel Determinants of convoluted Catalan numbers and nonintersecting
lattice paths: A bijective proof of Cigler’s Conjecture

Markus Fulmek

###### Abstract.

In recent preprints, Cigler considered certain Hankel determinants of
convoluted Catalan numbers and conjectured identities for these determinants.
In this note, we shall give a bijective proof of Cigler’s Conjecture: This
proof employs the reflection principle, the Lindström–Gessel–Viennot–method
and a certain construction involving reflections and overlays of
nonintersecting lattice paths.

##  1\. Introduction

In recent preprints [3, 2], Cigler considered Hankel determinants

$D_{K,M}\left(N\right)\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\det\left(C_{K,i+j+M}\right)_{i,j=0}^{N-1},$ (1)

for $M\in{\mathbb{Z}}$ and $K,N\in{\mathbb{N}}$, $K\geq 1$, where the entries
are convolution powers of Catalan numbers for $p\in{\mathbb{N}}$

$\displaystyle C_{K,p}$ $\displaystyle\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\binom{2p+K-1}{p}-\binom{2p+K-1}{p-1}$
$\displaystyle=\frac{K}{p+K}\binom{2p+K-1}{p}=\frac{K}{2p+K}\binom{2p+K}{p},$

and $C_{K,p}=0$ for $p\in{\mathbb{Z}}$ with $p<0$.

Cigler presented the following conjecture [3, Conjecture 1, equations (7) and
(8)] regarding these determinants, which we formulate as a theorem since we
will give a proof for it:

######  Theorem 1 (Cigler’s Conjecture).

Let $m,k\in{\mathbb{N}}$, with $m,k>0$. Then for $K=2k$ we have the even
identities

$\displaystyle D_{2k,1-k-m}\left(0\right)$ $\displaystyle=1\text{ (true by
definition)},$ $\displaystyle D_{2k,1-k-m}\left(N\right)$
$\displaystyle=0\text{ for }N=1,2,\dots,m+k-1,$ (2)

and for all $n\in{\mathbb{N}}$

$D_{2k,1-k-m}\left(n+m+k\right)=\left(-1\right)^{\binom{m+k}{2}}D_{2k,1-k+m}\left(n\right)$
(3)

Moreover, for $K=2k-1$ we have the odd identities

$\displaystyle D_{2k-1,2-k-m}\left(0\right)$ $\displaystyle=1\text{ (true by
definition)},$ $\displaystyle D_{2k-1,2-k-m}\left(N\right)$
$\displaystyle=0\text{ for }N=1,2,\dots,m+k-2,$ (4)

and for all $n\in{\mathbb{N}}$

$D_{2k-1,2-k-m}\left(n+m+k-1\right)=\left(-1\right)^{\binom{m+k-1}{2}}D_{2k-1,1-k+m}\left(n\right)$
(5)

We shall prove this by interpreting the determinants as generating functions
of tuples of lattice paths.

In order to keep things as brief as possible, from now on we shall refer to

  * •

the determinants to the left and to the right in identities (2), (3), (4) or
(5),

  * •

and/or their parameters $K,M,N$, which depend on $k$, $m$ and $n$, and on the
“parity” (even or odd) of the identity

  * •

and/or the lattice path interpretation for these determinants and their
parameters (yet to be explained)

simply as

  * •

right–hand side (which we abbreviate as rhs)

  * •

and left–hand side (which we abbreviate as lhs),

respectively. Moreover, we shall illustrate our constructions with many
pictures and refer to relations which are “geometrically obvious” (like
“above”, “between”, or “to the left”) in simple terms (instead of stating
everything with coordinates or equations).

In section 2, we briefly recall basic concepts, and in section 3 we present
the proof of Cigler’s Conjecture.

##  2\. Preliminary considerations

We recall basic facts and make some elementary observations.

###  2.1. Binomial coefficients and lattice paths

If we restrict the binomial coefficient $\binom{2m+k-1}{m}$ to the case
$m,2m+k-1\in{\mathbb{N}}$, then we may interpret it as the number of lattice
paths in the integer lattice ${\mathbb{Z}}^{2}$ consisting of

  * •

horizontal steps to the right, i.e., from $\left(x,y\right)$ to
$\left(x+1,y\right)$

  * •

or vertical steps upwards, i.e., from $\left(x,y\right)$ to
$\left(x,y+1\right)$,

which start at $\left(a-m,a-m-k+1\right)\in{\mathbb{Z}}^{2}$ and end at
$\left(a,a\right)\in{\mathbb{Z}}^{2}$ for some $a\in{\mathbb{Z}}$, see the
following picture illustrating such path for $a=0$, $m=3$ and $k=2$:

If we want to count only paths which do never touch the forbidden line $y=x-k$
(this is the dashed line in the above picture), then we must subtract

  * •

from the number $\binom{2m+k-1}{m}$ of all lattice paths

  * •

the number of all lattice paths which do touch the forbidden line,

and by the well–known reflection principle [1] we have that the latter equals
$\binom{2m+k-1}{m-1}$, see the following picture where the initial segment of
the path up to the first point of intersection (indicated by a small square in
the picture) with the forbidden line is reflected on the forbidden line:

###  2.2. Determinants interpreted as generating functions

So, we may interpret the entry

$C_{K,i+j+M}=\binom{2\left(i+j+M\right)+K-1}{i+j+M}-\binom{2\left(i+j+M\right)+K-1}{i+j+M-1}$

of the determinant (1) as the number of lattice paths which

  * •

start at initial point $A_{i}=\left(-i-M,-i-M-K+1\right)$

  * •

and end at terminal point $B_{j}=\left(j,j\right)$

  * •

and do not touch the forbidden line $y=x-K$,

as long as $2\left(i+j+M\right)+K-1\geq 0$ (otherwise, the number of such
lattice paths clearly is zero, while the binomial coefficients might be
nonzero111For instance, if $M=-1$, $K=1$ and $i=j=0$, then
$\binom{2\left(i+j+M\right)+K-1}{i+j}=\binom{-2}{0}=1$.).

By assigning constant weight $1$ to each single lattice path, we may interpret
the number $C_{K,i+j+M}$ as the generating function of the set of all such
lattice paths.

Denoting the permutation group on $\left\\{0,1,\dots,N-1\right\\}$ by
${\mathfrak{S}}_{N}$, the determinant $D_{K,M}\left(N\right)$

$\det\left(C_{K,i+j+M}\right)_{i,j=0}^{N-1}=\sum_{\pi\in{\mathfrak{S}}_{N}}\mathop{sgn}\left(\pi\right)\cdot\prod_{i=0}^{N-1}C_{K,i+\pi\left(i\right)+M}$
(6)

may be viewed as the generating function of the set $\mathcal{P}$ of all
$N$–tuples $t$ of lattice paths

  * •

from initial points $A_{i}$

  * •

to terminal points $B_{\pi\left(i\right)}$,

for some $\pi\left(t\right)=\pi\in{\mathfrak{S}}_{N}$ which we call the
permutation of $t$, where the weight of such $N$–tuple $t$ equals
$\mathop{sgn}\left(\pi\left(t\right)\right)$:

$\det\left(C_{K,i+j+M}\right)_{i,j=0}^{N-1}=\sum_{t\in\mathcal{P}}\mathop{sgn}\left(\pi\left(t\right)\right).$
(7)

The following pictures illustrate this idea by two triples of lattice paths
for $K=M=N=3$ and $\pi=\left(1,0,2\right)$ (in one–line–notation):

$0$$0$$1$$1$$2$$2$$0$$0$$1$$1$$2$$2$

Note that in the right picture (where different colours for the paths are used
just to make their course more visible), there are two points of intersections
of lattice paths, indicated in the picture by small squares: If some $N$–tuple
of lattice paths has such points of intersections, then it is called
intersecting, otherwise it is called nonintersecting (so the left picture
above shows a nonintersecting triple of lattice paths).

In the following considerations, we will also encounter initial and terminal
points $A^{\prime}_{i},B^{\prime}_{j}$ in other positions, and we will
sloppily refer to any such configuration of initial and terminal points as
situation. If we know in some situation that initial point $A^{\prime}_{i}$ is
(or must be) connected with terminal point $B^{\prime}_{\pi\left(i\right)}$ by
a lattice path, we call $\pi$ the permutation corresponding to this situation.
(So $\pi=\left(1,0,2\right)$ is the permutation corresponding to the situation
shown in the above pictures.)

###  2.3. The Lindström–Gessel–Viennot method

The well–known Lindström–Gessel–Viennot method [5, 4] constructs an involution
$\varphi$ on the set $\mathcal{P}$ of all $N$–tuples of lattice paths, i.e.,

$\varphi\colon\;{\mathcal{P}}\to{\mathcal{P}}\text{ is bijective and
}\varphi^{-1}=\varphi,$

which is sign–reversing, i.e.,

$\varphi\left(t\right)\neq
t\implies\mathop{sgn}\left(\varphi\left(t\right)\right)=-\mathop{sgn}\left(t\right).$

Clearly, such sign–reversing involution $\varphi$ results in a cancellation of
summands in (7), the only “survivors” of which are the fixed points of
$\varphi$ (i.e., $N$–tuples $t$ of lattice paths with
$\varphi\left(t\right)=t$).

Consider the lexicographic order on ${\mathbb{Z}}^{2}$:

$\left(r,s\right)\succ\left(u,v\right){\stackrel{{\scriptstyle\text{def}}}{{\iff}}}r>u\text{
or }\left(r=u\text{ and }s>v\right).$

The Lindström–Gessel–Viennot–involution $\varphi$ is defined as follows: If
$t$ is a nonintersecting $N$–tuple of lattice paths, then
$\varphi\left(t\right)=t$. Otherwise choose the maximal point of intersection
$P$ in lexicographic order (in the right picture above, this is the point with
coordinates $\left(-3,-2\right)$): Assuming that (precisely) the two paths
ending in $B_{j_{1}}$ and $B_{j_{2}}$ meet in $P$, we obtain another (again
intersecting) $N$–tuple $t^{\prime}$ of lattice paths with the opposite sign
by exchanging the terminal path segments from $P$ up to $B_{j_{1}}$ and
$B_{j_{2}}$, respectively; and we set $\varphi\left(t\right)=t^{\prime}$.

For instance, after applying this involution to the situation of the right
picture above, we obtain the following picture for
$\pi^{\prime}=\left(0,1,2\right)$ (in one–line–notation, again):

$0$$0$$1$$1$$2$$2$

Clearly, the fixed points of this involution are precisely the nonintersecting
$N$–tuples of lattice paths. For the rest of this paper, we shall only
consider such $N$–tuples of nonintersecting lattice paths, which we call
survivors (since they “survive” the cancellation implied by the
Lindström–Gessel–Viennot–involution): Note that the generating of these
survivors equals the determinant $D_{K,M}\left(N\right)$ in (7), where the
sign $\mathop{sgn}\left(o\right)$ of a survivor $o$ connecting initial points
$A_{i}$ to terminal points $B_{\pi\left(i\right)}$ is defined as the sign
$\mathop{sgn}\left(\pi\right)$ of the permutation $\pi$.

In the typical application of the Lindström–Gessel–Viennot method, there is
only one permutation $\pi$ (typically: the identity) for which a tuple of
nonintersecting paths is possible: Note that this is not necessarily the case
in the situation we are considering here, see again the above pictures.

###  2.4. Enforced segments for survivors

Observe that the nonintersecting lattice paths starting in $A_{i}$,
$i=0,1,\dots,N-1$, must not start with a horizontal step to the right (since
they must not touch the forbidden line): So each lattice path starts with an
enforced initial segment of vertical upward steps (which might be empty in
special cases), and since the lattice paths are nonintersecting, the length of
the enforced initial segment starting in $A_{i+1}$ exceeds the length of the
enforced initial segment starting in $A_{i}$ by two, except in cases where
this enforced initial segment runs into one of the end points $B_{j}$, where
it is “stopped” immediately (so if some initial point coincides with some
terminal point, the enforced initial segment starting there has length $0$).
Following these enforced initial segments from their (original) initial points
leads to (new) enforced initial points: So instead of considering the original
initial points, we may always consider these enforced initial points.

The meaning of this will become clear by looking at the following pictures
(where $K=4$, $M=-1$ and $N=4$). Here, the enforced initial segments are shown
as blue vertical lines in the middle picture, and the enforced initial points
are either blue or bicoloured (blue and red; if the enforced initial point
coincides with a terminal point):

Note that in the situation shown in the above pictures, for any
nonintersecting $4$–tuple the lattice path

  * •

starting in $A_{0}$ or $A_{3}$ must end in $B_{2}$ or in $B_{3}$,

  * •

starting in $A_{1}$ must end in $B_{1}$,

  * •

starting in $A_{2}$ must end in $B_{0}$,

and the corresponding enforced sub–permutation

$\pi\colon\;1\mapsto 1,\;2\mapsto 0$

is of length $2$ is descending and thus contributes
$\left(-1\right)^{\binom{2}{2}}=-1$ to the sign of the overall permutation
(which depends on whether $A_{0}$ is connected to $B_{2}$ or $B_{3}$; for both
possibilities there are nonintersecting $4$–tuples of lattice paths).

###  2.5. Positions of enforced initial points

As a preparation for the proof, we examine the enforced initial points of the
nonintersecting lattice paths corresponding to the lhs and rhs of

  * •

the even identities (2) and (3),

  * •

and the odd identities (4) and (5).

As examples we consider

  * •

the even identity for $k=2$, $m=4$ and $n=2$,

  * •

and the odd identity for $k=3$, $m=4$ and $n=3$;

see the following pictures. As can be seen in the pictures, there are

  * •

enforced initial points which are not terminal points (coloured blue),

  * •

terminal points which are not enforced initial points (coloured red),

  * •

and enforced initial points which are also terminal points (with colours blue
and red, we call such points two–faced).

l, e, $k=2$, $m=4$, $n=2$$K=4$, $M=-5$, $N=8$r, e, $k=2$, $m=4$, $n=2$$K=4$,
$M=3$, $N=2$l, o, $k=3$, $m=4$, $n=3$$K=5$, $M=-5$, $N=9$r, o, $k=3$, $m=4$,
$n=3$$K=5$, $M=2$, $N=3$

In order to show that there are

  * •

always two–faced points in the lhs,

  * •

but never two–faced points in the rhs,

(as the above pictures suggest), note that the first enforced initial points
lie on the line

$\left(y=-x-2M-K+2\right)$

with slope $-1$ through the point $\left(-M,-M-K+2\right)$. This line
intersects the diagonal $\left(y=x\right)$ (which contains the terminal
points) in the point

$S=\left(-M+1-\frac{K}{2},-M+1-\frac{K}{2}\right),$

so terminal points which are also initial points only exist if the following
inequality holds:

$-M+1-\frac{K}{2}\geq 0\iff\frac{K}{2}\leq-M+1.$ (8)

If (8) holds, then the number of two–faced points is
$\left\lfloor-M+1-\frac{K}{2}\right\rfloor+1$.

####  2.5.1. Even identities

In the even case, the parameters for the lhs are

$K=2k,M=1-k-m,N=n+m+k,$

so the point of intersection is $S=\left(m,m\right)$, and inequality (8) reads

$k\leq m+k,$

which is true for $m\geq 0$ (and there are $m+1$ two–faced points), and the
parameters for the rhs are

$K=2k,M=1-k+m,N=n$

so the point of intersection is $S=\left(-m,-m\right)$, and (8) reads

$k\leq k-m,$

which is false for $m\geq 1$ (and there are no two–faced points).

####  2.5.2. Odd identities

In the odd case, the parameters for the lhs are

$K=2k-1,M=2-k-m,N=n+m+k-1,$

so the point of intersection is $S=\left(m-\frac{1}{2},m-\frac{1}{2}\right)$,
and (8) reads

$k-\frac{1}{2}\leq m+k-1$

which is true for $m\geq 1$ (and there are $m$ two–faced points), and the
parameters for the rhs are

$K=2k-1,M=1-k+m,N=n,$

so so the point of intersection is
$S=\left(-m+\frac{1}{2},-m+\frac{1}{2}\right)$, and (8) reads

$k-\frac{1}{2}\leq-m+k,$

which is false for $m\geq 1$ (and there are no two–faced points).

####  2.5.3. Even and odd identities

It is easy to see that for the lhs and the rhs, the number of initial points
strictly below the diagonal $\left(y=x\right)$ is always
$\min\left(k-1,N\right)$, and that for the lhs and $n\geq 0$, the number of
initial points

  * •

strictly above the diagonal $\left(y=x\right)$ is always $n$,

  * •

on the diagonal (these are the two–faced points) is

    * –

$m+1$ for the even case

    * –

and $m$ for the odd case,

which we express uniformly as $\left(m+\left[\text{even}\right]\right)$, using
Iverson’s bracket.

(Iverson’s bracket $\left[\text{``some assertion''}\right]$ is defined as $1$
if “some assertion” is true, otherwise as $0$: We shall employ this useful
notation also in the following.)

The following pictures give a schematic illustration of the situation (here,
the two–faced points for the lhs are indicated by a box coloured blue and red,
and all other initial and terminal points are indicated by blue and red boxes,
respectively):

$\delta=m-\frac{1}{2}\cdot\left[\text{odd}\right]$$n$$m+\left[\text{even}\right]$$n+k-1$$k-1$lhs
(schematic):$\delta=m-\frac{1}{2}\cdot\left[\text{odd}\right]$$k-1$$n$$n-k+1$rhs
(schematic):

Note that the distance $\delta$ between the orthogonal projections

  * •

of the first initial point (for the lhs: above the diagonal
$\left(y=x\right)$)

  * •

and of the first terminal point (for the lhs: which is not two–faced)

on the forbidden line is the same for the lhs and the rhs (namely
$\delta=m+\frac{1}{2}\cdot\left[\text{odd}\right]$, see the above pictures).

####  2.5.4. A first consequence

These simple observations already prove identities (2) and (4): If for the lhs

  * •

$N<m+k$ in the even case

  * •

or $N<m+k-1$ in the odd case,

then the terminal point $\left(0,0\right)$ cannot be reached by any initial
point, and therefore the generating function of the corresponding
nonintersecting lattice paths is zero. So it only remains to prove identities
(3) and (5)

###  2.6. A warmup–exercise: Cigler’s Conjecture for $k=1$

The simple observations we made so far already give a simple bijective proof
(essentially by looking at suitable pictures) for the special case $k=1$ of
Theorem 1 (the odd identities for $k=1$ are, in fact, equivalent to Cigler’s
earlier result [3, equation (5)], see also [2, Theorem 1, equation (6)]):

###### Proof of Cigler’s Conjecture for special case $k=1$.

We start with the odd identities with parameters $K=2k-1=1$ and

  * •

$M=1-m$ and $N=n+m$ for the lhs,

  * •

$M=m$ and $N=n$ for the rhs.

Observe that in this situation the initial points $A_{i}$ and the terminal
points $B_{j}$ are collinear.

Recall that (4) was already proved in section 2.5.4.

For $N=m$ (this is the special case $n=0$ for the lhs of (5)), we have

$B_{i}=\left(i,i\right)=A_{m-1-i}\text{ for }i=0,1,\dots,m-1,$

and there is precisely one $N$–tuple of nonintersecting lattice paths (where
all paths have length $0$), and the corresponding permutation

$\pi\colon\;i\mapsto m-1-i\text{ for }i=0,1,\dots,m-1$

has sign $\mathop{sgn}\left(\pi\right)=\left(-1\right)^{\binom{m}{2}}$. Since
the rhs of (5) equals $1$ by convention for $N=n=0$, equality holds in this
special case.

The following pictures illustrate these simple observations for $m=3$ (i.e.,
$M=2-k-m=-2$) and $N=n=1,2,3$ (again, two–faced points are coloured blue and
red):

In order to show (5) for $n>0$, observe that in this specific situation there
are also “enforced terminal segments” of horizontal steps to the right for the
lattice paths, since no terminal point $B_{j}$ can be reached by a vertical
upward step. The following pictures illustrate the situation for $m=3$ and
$n=1,2$, implying

  * •

$M=2-k-m=-2$ and $N=4,5$ for the lhs of (5), shown in the left pictures below,

  * •

$M=1-k+m=3$ and $N=1,2$ for the rhs of (5), shown in the right pictures below:

Now observe that the enforced initial and terminal points corresponding to the
lhs of (5) are simply obtained by a translation of the enforced initial and
terminal points corresponding to the rhs (recall the considerations and
pictures in section 2.5.3), and that the $m$ enforced two–faced points

  * •

correspond to the same translation of the forbidden line

  * •

and contribute a factor $\left(-1\right)^{\binom{m}{2}}$ to the sign of the
corresponding permutation (which has fixed points $m+1,m+2,\dots,N-1$).

These observations conclude the proof of the odd identity (5) for the special
case $k=1$.

The proof of the even identity (5) with parameters $K=2k=2$ and

  * •

$M=-m$ and $N=n+m+1$ for the lhs,

  * •

$M=m$ and $N=n$ for the rhs,

is completely analogous to the odd case, see the following pictures for $m=2$
(i.e., $M=1-k-m=-2$ and $M=1-k+m=2$, respectively, for the lhs and the rhs):

The same reasoning as for the odd identity concludes the proof. ∎

##  3\. Bijective proof of Cigler’s Conjecture for $k>1$

The rest of this paper is devoted to a bijective proof of Ciglers’s Conjecture
for $k>1$. While all single arguments are elementary, the chain of arguments
is long and complicated: We will make extensive use of pictures to explain
them, hoping that the saying “A picture is worth a thousand words” proves to
be true.

###  3.1. Encoding permutations of survivors

Let us call a permutation $\pi$ admissible if there are survivors ($N$–tuples
of nonintersecting lattice paths) connecting initial point $A_{i}$ to terminal
point $B_{\pi\left(i\right)}$ for $i=0,1,\dots,N-1$.

Note that for every survivor, the lattice path reaching terminal point $B_{i}$
may have length $0$ (if $B_{i}$ is also an enforced initial point: This can
only happen for the lhs; see subsection 2.5.3), but otherwise must end

  * •

either with an upwards step from below

  * •

or with a rightwards step from the left;

see the following pictures:

l, o, $k=3$, $m=3$, $n=3$$K=5$, $M=-4$,
$N=8$$0$$1$$2$$3$$4$$5$$6$$7$$2$$3$$4$$0$$1$$5$$6$$7$r, o, $k=3$, $m=3$,
$n=3$$K=5$, $M=1$, $N=3$$0$$1$$2$$0$$1$$2$

Considering the lhs, note that all lattice paths starting at enforced initial
points

  * •

below the diagonal must end with an upwards step,

  * •

on the diagonal have length $0$,

  * •

above the diagonal must end with a rightwards step.

This means that all admissible permutations for the lhs must map

  * •

indices $k-1,k,k+1,\dots,k+\left(m+\left[\text{even
situation}\right]\right)-2$

  * •

to indices $0,1,\dots,\left(m+\left[\text{even situation}\right]\right)-1$

in reverse order (in the above picture: $2\mapsto 2$, $3\mapsto 1$ and
$4\mapsto 0$). We may disregard this “enforced subpermutation” and renumber
the initial and terminal points as indicated in the following picture:

l, o, $k=3$, $m=3$, $n=3$$K=5$, $M=-4$, $N=8$$0$$1$$2$$3$$4$$0$$1$$2$$3$$4$

With this renumbering for the lhs (and the original numbering for the rhs), we
assign to $\pi$ the $01$–code (omitting terminal point $B_{0}$)

$c\left(\pi\right)=\left(\left[\text{Terminal point $B_{i}$ is reached from
the left}\right]\right)_{i\geq 1}.$

By considering enforced terminal segments, as illustrated in the following
pictures, is easy see that the mapping $\pi\mapsto c\left(\pi\right)$ is
injective:

Code 01.Code 10.Code 11.

(Note that no admissible permutation is mapped to $01$–code $00$ in the
situation depicted above, since the paths must not intersect the forbidden
line.) We call a $01$–code admissible if it is assigned to an admissible
permutation, so (by definition) there is a bijection between the set of
admissible permutations and the set of admissible codes.

###  3.2. Relations between signs of admissible permutations and their codes

We want to express the sign of an admissible permutation $\pi$ in terms of its
corresponding $01$–code $c\left(\pi\right)$: As base cases, we consider the
$01$–codes

  * •

consisting of $k-1$ zeros, followed by $n$ ones, for the lhs,

  * •

consisting of $l\geq 0$ zeros, followed by $n-l$ ones, for the rhs (note that
$l=1$ means that the permutation has precisely one inversion).

The permutations corresponding to these base cases are visualized in the
following pictures:

$k-1$$m+\left[\text{even}\right]$$n$$l+1$$n\\!-\\!l\\!-\\!1$LHSRHS

Clearly, the signs of these permutations are

  * •

$\left(-1\right)^{\binom{m+\left[\text{even}\right]+k-1}{2}}$ for the lhs
(since the number of inversions of this permutation is
${\binom{m+\left[\text{even}\right]+k-1}{2}}$),

  * •

$\left(-1\right)^{\binom{l+1}{2}}$ for the rhs (since the permutation has
${\binom{l+1}{2}}$ inversions (note that this is true also for $l=0$).

For a $01$–code $c=\left(c_{i}\right)_{i\geq 1}$, an inversion of $c$ is a
pair of indices $\left(i<j\right)$ such that $c_{i}>c_{j}$. Denote by
$\mathop{inv}\left(c\right)$ the number of inversions of $c$.

If we number the zeros in some $01$–code $c$ from left to right (starting with
$1$) and assume that the $i$–th zero appears at index $z_{i}$ ($z_{i}\geq 1$
by definition) in $c$, then the number of inversions of $c$ equals the sum

$\mathop{inv}\left(c\right)=\sum_{i=1}^{\\#\left(\text{zeros in
$c$}\right)}\left(z_{i}-i\right).$

It is easy to see: A permutation $\pi$ with code $c\left(\pi\right)$

  * •

for the lhs has

${\binom{m+\left[\text{even}\right]}{2}}+\mathop{inv}\left(c\left(\pi\right)\right)$
(9)

inversions,

  * •

for the rhs has

$\binom{l+1}{2}+\mathop{inv}\left(c\left(\pi\right)\right)=\sum_{i=1}^{l}{z_{i}}$
(10)

inversions, if $c$ contains exactly $l$ zeros.

(We will use this facts at the end of our proof.)

Assume that in some $01$–code $c=\left(c_{k}\right)_{k\geq 1}$ we have for
$1\leq i<j$

  * •

$c_{i}=1$

  * •

and $c_{j}=0$,

and let $l$ be the number of components $c_{k}=0$, for $i<k<j$: Then swapping
$c_{i}$ and $c_{j}$

  * •

decreases the number of inversions involving $c_{i}$ by $l+1$,

  * •

increases the number of inversions by $1$ for each of the $j-i-1-l$ ones
between $i$ and $j$,

so the change in sign effected by such swap is
$\left(-1\right)^{{\left\lvert{j-i}\right\rvert}}$, and the same holds true
for $c_{i}=0$ and $c_{j}=1$: We note this simple observation for later
reference.

###  3.3. Rewrite the identities as equations for sums over $01$–codes

If we consider the set of all admissible codes for the lhs and for the rhs in
equations (3) and (5) and write ${\mathbf{gf}\left(c\right)}$ for the
generating function of survivors corresponding to $c$ (i.e., with permutation
$\pi$ of terminal points corresponding to $c$), then we may write (3) and (5)
in a uniform way:

$\sum_{C\text{ for
LHS}}\mathop{sgn}\left(\pi\right){\mathbf{gf}\left(C\right)}=\sum_{c\text{ for
RHS}}\mathop{sgn}\left(\pi\right){\mathbf{gf}\left(c\right)}.$ (11)

In general, neither the summation ranges nor the summands of this identity
coincide: Our proof will involve “reducing” the (larger) sum for the lhs to
the sum of the rhs, by certain cancellations resembling the
Lindström–Gessel–Viennot–involution.

###  3.4. Plan for our bijective proof

The plan for our bijective proof is simple:

  1. (1)

Find another sign–reversing involution $\psi$ on the set of all survivors
(i.e., nonintersecting lattice paths) corresponding to the lhs.

  2. (2)

Show that there is a bijection $\xi$

     * •

from the set of the fixed points of $\psi$ (i.e., the survivors of the second
cancellation corresponding to $\psi$) for the lhs

     * •

to the set of survivors corresponding to the rhs

     * •

which changes the sign by a constant factor $f$ (i.e.,
$\mathop{sgn}\left(\xi\left(o\right)\right)=f\cdot\mathop{sgn}\left(o\right)$),
namely

       * –

$f=\left(-1\right)^{\binom{m+k}{2}}$ in the even case,

       * –

$f=\left(-1\right)^{\binom{m+k-1}{2}}$ in the odd case.

As it will turn out, the bijection $\xi$ “respects the summands in (11)” in
the following sense: It implies a bijection between

  * •

the summation range (i.e., $01$–codes $C$) of survivors of the second
cancellation (effected by $\psi$) appearing in the lhs of (11)

  * •

and the summation range (i.e., $01$–codes $c=\xi\left(C\right)$) for the rhs
of (11),

and it maps

  * •

survivors of the second cancellation corresponding to $01$–code $C$ in the lhs

  * •

to survivors corresponding to $01$–code $c=\xi\left(C\right)$ in the rhs.

###  3.5. Step 1: Construct the sign–reversing involution $\psi$

We shall construct the sign–reversing involution $\psi$ on the set of
survivors for the lhs by combining the Lindström–Gessel–Viennot–idea with
simple reflections on the diagonal line $d=\left(y=x\right)$.

####  3.5.1. Reflection for the lhs: The folded situation

If we reflect on the diagonal $d$ all nonintersecting lattice paths for the
lhs which lie above $d$, then we call the result of such reflection the folded
situation. In the following pictures, reflected paths will be coloured green,
as well as their reflected initial points (and all paths and initial points
below $d$, which are not reflected, will be coloured blue, as before).

We illustrate this for the odd identity with parameters $k=3$, $m=2$ and $n=2$
(i.e., $K=2k-1=5$, $M=2-k-m=-3$, and $N=n+m+k-1=6$). “In terms of initial,
two–faced and terminal points”, the transition from the original situation to
the folded situation looks like this:

l, o, $k=3$, $m=2$, $n=2$$K=5$, $M=-3$, $N=6$l, o, $k=3$, $m=2$, $n=2$$K=5$,
$M=-3$, $N=6$

Note that in the right picture above (showing the folded situation), a certain
trapezoid is marked in colour, and additional white points on the forbidden
line points are shown. We call this the essential region: Its significance and
the meaning of the white points will soon become clear.

####  3.5.2. Reflection for the rhs: The reflected situation

If we reflect on $d$ the forbidden line $y=x-K$ and all nonintersecting
lattice paths for the rhs, then we call the result of such reflection the
reflected situation.

Again, we illustrate this for the odd identity with parameters $k=3$, $m=2$
and $n=2$ (i.e., $K=2k-1=5$, $M=1-k+m=0$, and $N=n=2$). “In terms of initial
and terminal points”, the transition from the original situation to the
reflected situation looks like this:

r, o, $k=3$, $m=2$, $n=2$$K=5$, $M=0$, $N=2$r, o, $k=3$, $m=2$, $n=2$$K=5$,
$M=0$, $N=2$

Note that in the right picture above (showing the reflected situation), a
certain trapezoid is marked in colour again, which we also call the essential
region (for the reflected situation).

####  3.5.3. Essential regions

It is easy to see (recall the considerations and illustrations in section
2.5.3) that there is a translation which transforms

  * •

the essential regions for the folded situation

  * •

to the essential region for the reflected situation,

which maps bijectively

  * •

green initial points to green initial points

  * •

and white additional points to terminal points,

and which swaps the roles of the diagonal and the forbidden line for the
folded situation and the reflected situation (see the essential regions in the
above pictures).

This congruence of essential regions is crucial for the second step in our
proof: Clearly, the reflections explained above give sign–preserving
bijections (since the permutation $\pi$ is not affected by the reflections)
from the “original situation” to the folded or reflected situation,
respectively, so instead of defining a sign–preserving bijection between

  * •

the survivors for the lhs which also “survive” the cancellation effected by
the second sign–reversing involution $\psi$ (yet to be defined)

  * •

and the survivors for the rhs,

we will define the sign–preserving bijection $\xi$ between

  * •

the “twofold” survivors for the lhs in the folded situation

  * •

and the survivors for the rhs in the reflected situation.

The construction of this bijection $\xi$ will involve only the essential
regions, leaving segments of green paths outside the essential regions
unchanged.

####  3.5.4. Folded overlays

In the following illustration, the left picture shows nonintersecting lattice
paths (for the lhs), and the right picture shows the folded situation,
obtained by the reflection of all paths above the diagonal
$d=\left(y=x\right)$ on $d$:

$\pi\colon\;\left(3,1,0,2,4\right)$.

Observe that by this reflection, we get an overlay of green and blue paths,
such that

  * •

all paths (blue or green) are restricted to the range $y\leq x$,

  * •

blue paths additionally are restricted to the range $y>x-K$,

  * •

blue and green paths are nonintersecting, i.e., there is no point of
intersection of two blue paths or two green paths.

We shall call such overlay of green and blue paths a folded overlay. (As
already mentioned, folded overlays are in sign–preserving bijection with the
“original” nonintersecting lattice paths).

Note that a folded overlay appears as a directed subgraph of the lattice
${\mathbb{Z}}^{2}$ with green and blue edges, which

  * •

have the normal direction (rightwards or upwards),

  * •

but might be traversed in the reversed direction (leftwards or downwards),

and where double edges (which necessarily must be of opposite colours blue and
green) are allowed. We call vertices in this graph which are incident only
with a green (or blue, respectively) edge a green (or blue, respectively)
point, and we call points which are incident with green and blue edges
bicoloured.

####  3.5.5. Points of bicoloured intersection and the
Lindström–Gessel–Viennot–idea for folded overlays

An overlay of green and blue paths may have bicoloured points where some blue
path intersects some green path: In the above right picture, there are three
such points of bicoloured intersection, the maximal (in lexicographic order)
of them is indicated by a small square. Clearly,

  * •

every terminal point and every initial point which is not bicoloured is
incident with precisely one step which is either green or blue,

  * •

every bicoloured point is incident with

    * –

precisely two blue and precisely two green steps if it is not an initial
point,

    * –

precisely one blue and precisely one green step if it is an initial point,

  * •

every other point is incident with precisely two steps of the same colour
(either green or blue).

In the above pictures, we immediately see how a sign–reversing involution
resembling the Lindström–Gessel–Viennot–method might work — just look at the
pictures below, where terminal segments of paths after the maximal point of
bicoloured intersection are exchanged:

$\pi\colon\;\left(4,1,0,2,3\right)$.

However, we need a slightly more complicated construction.

####  3.5.6. The significance of essential regions

Clearly, a point of bicoloured intersection in some folded overlay can only be
located

  * •

weakly above the forbidden line (since there are no blue steps strictly below)

  * •

and weakly above the line containing the blue initial points (since there are
no blue steps strictly below)

  * •

and weakly below the line $\left(y=x\right)$ (since there are no points above)

  * •

and weakly to the left of the line $x=M-1$ (since there are no points to the
right).

Note that the region just described is precisely the essential region for the
folded situation: In the following, we will mostly focus our attention on this
essential region.

####  3.5.7. Bicoloured connections and the sign–reversing involution

For each terminal point $B_{j}$ in a folded overlay, we construct the
bicoloured path starting at $B_{j}$ as follows: We start with

  * •

$P=B_{j}$,

  * •

the reversed direction as current direction

  * •

and the unique colour of the path ending in $B_{j}$ as current colour.

As long as this is possible, we traverse the edge incident with $P$

  * •

of the current colour

  * •

in the current direction,

to its other endpoint $Q$ and set $P=Q$; and if $Q$ is a point of bicoloured
intersection, we swap the current colour (blue/green) and the current
direction (normal/reversed).

It is easy to see that this construction must end in an initial or terminal
point $Q$ where we cannot continue (i.e., where there is no incident edge of
the current colour and current direction): We call such bicoloured path from
$B_{j}$ to $Q$ a bicoloured connection of $B_{j}$ and $Q$.

The following pictures illustrate this construction: In the left picture, we
start at the green terminal point labeled $Q$, and in the right picture, we
start at the green terminal point labeled $P$.

$P$$Q$$P$$Q$

(Observe that there is also a shorter bicoloured connection, indicated in the
pictures by the crosshatched area.)

Now we are in the position to define the involution $\psi$ on the set of all
overlays of green and blue paths in the folded situation of the lhs: Let $o$
be an overlay of green and blue paths: We call a bicoloured connection $c$ in
$o$

  * •

which connects two different terminal points $B_{a}\neq B_{b}$,

  * •

and whose green segments never intersect the forbidden line

an involutive bicoloured connection. (Note that $B_{a}$ and $B_{b}$ must have
opposite colours, and that an involutive bicoloured connection never leaves
the essential region.)

A moment’s thought shows that swapping the colours (green to blue and vice
versa) of all edges belonging to an involutive bicoloured connection gives
another overlay of green and blue paths $o^{\prime}$:

  * •

By construction, the blue paths and the green paths in $o^{\prime}$ are
nonintersecting,

  * •

and the blue paths in $o^{\prime}$ do not intersect the forbidden line.

(The right picture above is obtained by this swapping of colours, and vice
versa.)

So for all folded overlays $o$

  * •

which do not contain any involutive bicoloured connection, we simply set
$\psi\left(o\right)=o$,

  * •

which contain involutive bicoloured connections, we choose the maximal
terminal point (in lexicographic order) for which an involutive bicoloured
connection $c$ exists and define $\psi\left(o\right)$ as the folded overlay
$o^{\prime}$ obtained by the swapping of colours in $c$ (as described above).

In the following pictures, the possible courses of bicoloured connections
through a point of bicoloured intersection are indicated by small arrows:

  * •

They show “essentially all” possible situations at points of intersections in
the network of blue and green paths (modulo swap of colours blue and green, or
directions horizontal and vertical)

  * •

and make clear that each bicoloured edge would form a (trivial) bicoloured
connection of the vertices it is incident with (so bicoloured edges never
belong to bicoloured connections of initial or terminal points).

A moment’s thought shows that swapping colours in a bicoloured connection

  * •

does not change any other bicoloured connection,

  * •

does not destroy any existing bicoloured connection,

  * •

and does not introduce new bicoloured connections:

So the mapping $\psi$ is, in fact, an involution.

Moreover, bicoloured connections may intersect, but (by construction) can
never cross (neither “itself” nor “one another”). Therefore, a bicoloured
connection of terminal points $B_{a}$ and $B_{b}$ forms an “impenetrable
barrier” for other bicoloured connections (see the above pictures, where the
area enclosed by this “barrier” is coloured). But this implies that the number
of terminal points between $B_{a}$ and $B_{b}$ must be even, so for
$o\neq\psi\left(o\right)$, we have
$\mathop{sgn}\left(\psi\left(o\right)\right)=-\mathop{sgn}\left(o\right)$,
since the swapping of colours amounts to swapping

  * •

a zero at position $a$

  * •

and a one at position $b$

(or vice versa) with odd distance ${\left\lvert{a-b}\right\rvert}$ in the
$01$–code corresponding to $o$ (see the considerations in section 3.1).
Therefore, the mapping $\psi$ is, in fact, sign–reversing.

So the determinant on the lhs in (3) and (5) appears as the generating
function of the fixed points of $\psi$, who “survive” the cancellation
effected by $\psi$. Clearly, these fixed points are the folded overlays which
do not contain any involutive bicoloured connection: We shall call them folded
survivors.

The next step in our proof is the exhibition of a bijection $\xi$ between the

  * •

the folded survivors in the lhs (in the folded situation)

  * •

and all (“normal”) survivors in the rhs (in the reflected situation)

of identities (3) and (5).

###  3.6. Step 2: Exhibit the bijection $\xi$

The bijection $\xi$ we shall exhibit in this section between

  * •

folded survivors (i.e, nonintersecting lattice paths from the folded situation
of the lhs which “survive” the cancellation by the sign–preserving involution
$\psi$),

  * •

and (“normal”) survivors (i.e., nonintersecting lattice paths) from the
reflected rhs

will leave unchanged all segments of paths outside the essential regions and
employ a “natural transformation” from

  * •

the restriction to the essential region of folded survivors, which have

    * –

terminal points on the diagonal $y=x$

    * –

and the forbidden line for blue paths $y=x-K$,

  * •

and the restriction to the essential region of (“normal”) survivors, which
have

    * –

terminal points on the diagonal (corresponding by a translation to the
forbidden line)

    * –

and the reflected forbidden line $y=x+K$ (corresponding by a translation to
the diagonal).

In order to conceive this “natural transformation” inside the essential
region, we will show that a folded overlay is a folded survivor if and only if
it has a certain simple structure. This will be the most strenuous part of
this section: Once we have achieved this, the “natural transformation” will
basically be obtained by “inspection of pictures”.

####  3.6.1. Examples of folded survivors

By definition, a folded survivor is a folded overlay which does not have an
involutive bicoloured connection, i.e.,

  * •

either there is no point of intersection at all

  * •

or each bicoloured connection of terminal points contains some green segment
which intersects the forbidden line $y=x-k$.

The following pictures illustrate this:

It is hard to conceive the structure of folded survivors in small examples, so
we shall consider larger ones: In order to limit the size of the corresponding
pictures, we observe that for any folded overlay $\mathcal{F}$ there are
constants $z\in{\mathbb{Z}}$ such that $\mathcal{F}$ does not have points of
bicoloured intersection $\left(x,y\right)$ with $y>z$, so we will “cut away”
the uninteresting part above such level $z$ in the following graphical
illustrations.

The following picture shows a folded survivor in the odd case with parameters
$k=7$, $m=4$ and $n=9$, where we have “cut away” the part above level $5$:

Here, only two terminal points are shown (the others are “cut away”), and the
essential region (which, too is cut) is indicated as coloured area.

It is easy to verify “by inspection” that this folded overlay has no
involutive bicoloured connection. We shall use this folded survivor as a
running example in this section.

Since the transformation we want to present only involves the part inside the
essential region (where points of bicoloured intersections might be located),
we shall omit the green segments of paths outside the essential region in the
following pictures.

####  3.6.2. The planar graph corresponding to a folded overlay

Let $\mathcal{F}$ be some folded overlay: If we

  * •

consider only points and steps inside the essential region,

  * •

disregard the orientation (but not the colour!) of all edges,

  * •

and “merge” all double (undirected) edges thus obtained into bicoloured single
edges (having colours blue and green; we shall call the edges of unique colour
unicoloured),

then we obtain a simple planar graph. Note that all “interior” vertices of
this graph have degree $2$, $3$ or $4$, and “loose ends” (vertices of degree
$1$) can only appear on the “boundary”, i.e., they are

  * •

either terminal points

  * •

or initial blue points

  * •

or green points on the forbidden line.

We can “close such loose ends” by introducing artificial slanted edges
connecting neighbouring “loose ends”, with the following “colouring rule”:

  * •

slanted edges on the line $\left(y=x\right)$ have the same colour as their
left point,

  * •

slanted edges on the line $\left(y=-x-2M-K+2\right)$ (this is the line
containing the blue intital points) are coloured green,

  * •

slanted edges on the forbidden line $\left(y=x-K\right)$ are coloured blue;

see the following picture for an illustration, where we also added blue and
green terminal points (shifted downwards, to limit the height of the picture)
together with the entries in the corresponding $01$–code: Recall that, by
definition,

  * •

blue terminal points are reached from below,

  * •

green terminal points are reached from the left

in the original (unfolded) situation (the rightmost isolated green point on
the forbidden line indicates the $9$–th green path, all whose steps are
completely “cut away”) in this picture:

$0$$1$$1$$0$$1$$0$$1$$1$$1$$0$$1$$0$$1$$1$

The only reason for introducing these artificial slanted edges is to avoid the
tedious distinction between “partially open” and “closed areas”, which now
uniformly appear as finite faces in the simple planar graph thus obtained: We
call it the planar graph corresponding to $\mathcal{F}$ and denote it by
$\overline{\mathcal{F}}$

####  3.6.3. Faces of the planar graph corresponding to a folded overlay

It is obvious that $\overline{\mathcal{F}}$ is connected, and that the
boundary $\partial f$ of each finite face $f$ of $\overline{\mathcal{F}}$ is a
closed curve in ${\mathbb{R}}^{2}$, which we may traverse in counterclockwise
orientation. But it is not so obvious that this closed curve must correspond
to a circle in the graph–theoretical sense (i.e., passes through every point
at most once).

When traversing (in counterclockwise orientation) the boundary $\partial f$ of
a finite face $f$ of of some general planar subgraph $G$ (without vertices of
degree $1$) of the lattice ${\mathbb{Z}}^{2}$, there are edges

  * •

which are traversed rightwards or upwards: call those the black edges,

  * •

which are traversed leftwards or downwards: call those the red edges.

Now observe that, in general, there can be precisely eight types of kinks in
$\partial f$, as shown in the following picture (where the crosshatched areas
indicate the finite face $f$ whose boundary contains the kink):

${\color[rgb]{1,0,0}rr}$${\color[rgb]{1,0,0}r}b$$bb$$b{\color[rgb]{1,0,0}r}$${\color[rgb]{1,0,0}\overline{rr}}$$\overline{bb}$

But a moment’s thought shows that two of these kinks are impossible if $f$ is
a finite face of the planar graph $\overline{\mathcal{F}}$ corresponding to
some folded overlay ${\mathcal{F}}$ (these are “crossed out” in the pictures
above), so there are only

  * •

two types of kinks consisting of two red edges: Denote them by
${\color[rgb]{1,0,0}rr}$ and ${\color[rgb]{1,0,0}\overline{rr}}$,

  * •

two types of kinks consisting of two black edges: Denote them by $bb$ and
$\overline{bb}$

  * •

and one type of kink where a red edge is followed by a black edge (denote this
by ${\color[rgb]{1,0,0}r}b$,

  * •

and one type of kink where a black edge is followed by a red edge (denote this
by $b{\color[rgb]{1,0,0}r}$),

which can occur in the boundary $\partial f$ of some finite face $f$ of
$\overline{\mathcal{F}}$. Note that when traversing such boundary in
counterclockwise orientation,

  * •

${\color[rgb]{1,0,0}rr}$ may follow ${\color[rgb]{1,0,0}\overline{rr}}$, and
vice versa; and ${\color[rgb]{1,0,0}rr}$ may also be followed by
${\color[rgb]{1,0,0}r}b$,

  * •

$bb$ may follow $\overline{bb}$, and vice versa; and $bb$ may also be followed
by $b{\color[rgb]{1,0,0}r}$,

  * •

$b{\color[rgb]{1,0,0}r}$ can only be followed by ${\color[rgb]{1,0,0}rr}$,

  * •

${\color[rgb]{1,0,0}r}b$ can only be followed by $bb$,

and there is no other possible succession of types of kinks.

Clearly, the boundary $\partial f$ must contain at least

  * •

one red path segment (consisting only of red edges)

  * •

and one black path segment (consisting only of black edges)

(since otherwise $\partial f$ would be just a path in ${\mathbb{Z}}^{2}$), and
red and black segments must be “joined” by kinks $b{\color[rgb]{1,0,0}r}$ or
${\color[rgb]{1,0,0}r}b$. Now consider the maximal kink
$b{\color[rgb]{1,0,0}r}$ (in lexicographic order) in $\partial f$: The
following picture (where the maximal kink $b{\color[rgb]{1,0,0}r}$ is labeled
$P$) makes clear that there cannot be another kink $b{\color[rgb]{1,0,0}r}$ in
$\partial f$.

PQ

So the boundary $\partial f$ of every finite face of $\overline{\mathcal{F}}$
consists precisely of

  * •

one black segment (we shall call it the right boundary of $f$)

  * •

and one red segment (we shall call it the left boundary of $f$).

####  3.6.4. Vertical strips

For our further considerations we will need a very simple special case: We
call a finite face $f$ of $\overline{\mathcal{F}}$ a vertical strip if its
left and right boundaries both contain only one horizontal or slanted step,
and we call the vertical segment of the left (or right, respectively) boundary
of $f$ the left side (or right side, respectively) of $f$.

It is easy to see that for any vertical strip $f$ in $\overline{\mathcal{F}}$,

  * •

the last (vertical) edge $v$ of the left (or right) side of $f$ and the
horizontal edge $h$ immediately following $e$ must have opposite colours,
whence both $v$ and $h$ must be unicoloured,

  * •

and all edges of the left (or right) side of $f$ must have the same colour as
$e$ (but some of them might have both colours);

see the following picture, which shows the four possible combinations of the
colours of the left and right side of vertical strips, which we denote by
${\color[rgb]{0,0,1}B}{\color[rgb]{0,0,1}B}$,
${\color[rgb]{0,0,1}B}{\color[rgb]{0,1,0}G}$,
${\color[rgb]{0,1,0}G}{\color[rgb]{0,0,1}B}$ and
${\color[rgb]{0,1,0}G}{\color[rgb]{0,1,0}G}$:

${\color[rgb]{0,0,1}B}{\color[rgb]{0,0,1}B}$${\color[rgb]{0,0,1}B}{\color[rgb]{0,1,0}G}$${\color[rgb]{0,1,0}G}{\color[rgb]{0,0,1}B}$${\color[rgb]{0,1,0}G}{\color[rgb]{0,1,0}G}$

Note that the horizontal edges in the pictures above could also be artificial
slanted edges, as explained above.

####  3.6.5. Adjacency of vertical strips

We say that a pair $\left(f_{l},f_{r}\right)$ of vertical strips is adjacent
if the intersection

  * •

of the right side of $f_{l}$

  * •

with the left side of $f_{r}$

is not empty, but does not contain a horizontal edge, and we call $f_{l}$ the
left strip and $f_{r}$ the right strip of the adjacent pair. The following
pictures show all the relative positions (“modulo the swap of colours blue and
green”) of left and right strips of an adjacent pair
$\left(f_{l},f_{r}\right)$, and make clear that not all of these relative
positions are possible in the planar graph $\overline{\mathcal{F}}$
corresponding to some folded overlay $\mathcal{F}$: Recall that according to
the above considerations,

  * •

all horizontal (or artificial slanted) edges are necessarily unicoloured
edges,

  * •

and

    * –

the upper horizontal (or artificial slanted) edge of the left strip $f_{l}$
and the uppermost vertical edge of the right side of $f_{l}$

    * –

as well as the the lower horizontal (or artificial slanted) edge of the right
strip $f_{r}$ and the lowest vertical edge of the left side of $f_{r}$

are both unicoloured and of different colours.

In the following pictures, unicoloured horizontal edges whose colour is not
already determined (as just explained) are drawn in gray. However, in some
situations, their colour is implied by the situation of the adjacency: This is
shown by marking such edges by double exclamation marks of the respective
colour in the following pictures.

####  3.6.6. Impossible adjacencies

A careful inspection reveals that the following situations of adjacencies are
impossible (and therefore are crossed out in the pictures):

!!!!!!!!!!!!

To see this, just note that in a folded overlay

  * •

a point is never incident with two outgoing (or incoming) steps of the same
colour as is the case in the first three of the above pictures,

  * •

and a path never starts (or ends) in the side of a vertical strip, as is the
case in the last three of the above pictures.

Also the following situations of adjacencies are impossible (note that the
vertical sides are of different colour here):

####  3.6.7. Possible adjacencies: Ascending and descending

However, the similar situations with vertical sides of the same colour are
possible: We say that an adjacent pair in any of these relative positions is
ascending.

Note for later reference that

  * •

the horizontal edges involved in an ascending adjacent pair of vertical strips

  * •

together with their adjacent vertical edges

may be viewed as (segments of) nonintersecting lattice paths, see the
following picture for an illustration, where these segments are drawn in
black:

Finally, also the following situations of adjacencies are all possible: We say
that an adjacent pair in any of the relative positions shown below is
descending.

!!!!!!!!!!!!!!!!

The following observation is an immediate consequence of the above
considerations:

  * •

For any descending adjacent pair, the left strip and the right strip must be
of the same type ${\color[rgb]{0,0,1}B}{\color[rgb]{0,0,1}B}$,
${\color[rgb]{0,0,1}B}{\color[rgb]{0,1,0}G}$,
${\color[rgb]{0,1,0}G}{\color[rgb]{0,0,1}B}$ or
${\color[rgb]{0,1,0}G}{\color[rgb]{0,1,0}G}$.

  * •

If in an ascending adjacent pair the left strip is of type
${\color[rgb]{0,0,1}B}{\color[rgb]{0,0,1}B}$ or
${\color[rgb]{0,1,0}G}{\color[rgb]{0,0,1}B}$, then the right strip must be of
the type ${\color[rgb]{0,0,1}B}{\color[rgb]{0,0,1}B}$ or
${\color[rgb]{0,0,1}B}{\color[rgb]{0,1,0}G}$.

  * •

If in an ascending adjacent pair the left strip is of type
${\color[rgb]{0,0,1}B}{\color[rgb]{0,1,0}G}$ or
${\color[rgb]{0,1,0}G}{\color[rgb]{0,1,0}G}$, then the right strip must be of
the type ${\color[rgb]{0,1,0}G}{\color[rgb]{0,0,1}B}$ or
${\color[rgb]{0,1,0}G}{\color[rgb]{0,1,0}G}$.

####  3.6.8. Rows of columns of vertical strips

Note that if every finite face of $\overline{{\mathcal{F}}}$ is a vertical
strip, then we can partition the family of these faces in maximal chains of
descending adjacent vertical strips, i.e.,

  * •

sequences $\left(v_{1},v_{2},\dots,v_{l}\right)$ of vertical strips of the
same type

  * •

where $\left(v_{i},v_{i+1}\right)$ are descending adjacent (as explained
above) for $i=1,2,\dots,l-1$,

  * •

which cannot be “extended” to a longer sequence with the same properties.

We call such maximal chains columns.

Note that these columns may be ordered such that (the vertical strips
belonging to) two consecutive columns are ascending adjacent: We call such
succession of ascending adjacent columns a row of columns.

####  3.6.9. Free kinks and other configurations

We consider the following four situations that might occur in the simple
planar graph $\overline{\mathcal{F}}$ corresponding to some folded overlay
${\mathcal{F}}$:

  * •

A free kink is a unicoloured path segment consisting of a horizontal step
followed by a vertical step, whose “middle vertex” has degree $2$ (i.e., is
not incident to another edge)

  * •

a horizontal bicoloured edge (as defined above),

  * •

an isolated vertex is a point in the essential region which does not belong to
any path,

  * •

an uncrossed double step is a unicoloured path segment consisting of two
horizontal steps.

The pictures below illustrate these simple notions:

####  3.6.10. Folded overlays down to some given level $y_{0}$

Let ${\overline{\mathcal{F}}}$ be the planar graph corresponding to some
folded overlay ${\mathcal{F}}$. For some fixed $z\in{\mathbb{Z}}$, we may
remove all vertices and edges which lie strictly below the horizontal line
$\left(y=z\right)$ in both ${\overline{\mathcal{F}}}$: We denote by
$\overline{\mathcal{F}_{z}}$ the result of this operation.

This operation might introduce “new loose ends” (vertices of degree $1$) in
${\overline{\mathcal{F}_{z}}}$: As before, we “close” such “loose ends” by
adding edges of appropriate colour (again, these artificial edges are only
introduced “for convenience”, in order to simplify the description). Note that
the boundaries of all finite faces in ${\overline{\mathcal{F}}_{y}}$ again
consist of a right segment and a left segment, as described in section 3.6.3

######  Lemma 1.

Let ${\mathcal{F}}$ be a folded overlay, and let $z\in{\mathbb{Z}}$. If
$\overline{{\mathcal{F}}}_{z+1}$ does not contain a free kink, then
$\overline{{\mathcal{F}}}_{z}$ does contain

  * •

neither an isolated vertex

  * •

nor a horizontal bicoloured edge

  * •

nor an uncrossed double step.

###### Proof.

Consider the set

$S=\left\\{\zeta\in{\mathbb{Z}}\colon\;{\overline{\mathcal{F}}}_{\zeta}\text{
does contain a horizontal step}\right\\}\subset{\mathbb{Z}}.$

If $S$ is empty, then $\overline{{\mathcal{F}}}$ clearly does contain neither
a horizontal bicoloured edge nor an uncrossed double step, and since in this
case the whole graph appears as a “curtain of vertical paths, pending from the
terminal points without any gaps”, there also is no isolated vertex: So the
assertion is true in this case.

If $S\neq\emptyset$, then consider $z_{0}=\max\left(S\right)\in{\mathbb{Z}}$.

For $z\geq z_{0}$, $\overline{\mathcal{F}}_{z}$ might be empty: In this case
the assertion is trivially true. Otherwise, $\overline{\mathcal{F}}_{z}$
consists of a “curtain of vertical paths” (as above), and some (unicoloured!)
horizontal steps on level $z_{0}$ (only if $z=z_{0}$): So every vertex
$\left(x,y\right)$ in $\overline{{\mathcal{F}}}_{z}$ is adjacent to a vertical
step, and this implies that $\overline{{\mathcal{F}}}_{z}$ does contain

  * •

neither an isolated vertex

  * •

nor a horizontal bicoloured edge $b$ (since the vertical upwards step incident
with the left point of this edge $b$ would have the same colour as $b$)

  * •

nor an uncrossed double step.

Now assume that the assertion is false, and let $z_{1}<z_{0}$ be the maximal
level for which this is the case, i.e., $z_{1}$ is the maximal integer such
that $\overline{{\mathcal{F}}}_{z_{1}+1}$ does not contain a free kink, but
$\overline{{\mathcal{F}}}_{z_{1}}$ contains

  * •

either an isolated vertex

  * •

or a horizontal bicoloured edge

  * •

or an uncrossed double step.

But a close look at these situations reveals that this impossible:

$z_{1}$

Note that in all three situations at level $z_{1}$ depicted above, the vertex
directly above (indicated by a small box in the pictures) cannot be entered by
a vertical step from below. But it is not an isolated vertex (since there are
none on level $z_{1}+1$ by assumption), so

  * •

it must be entered from the left by a horizontal step of unique colour, since
there are no bicoloured edges on level $z_{1}+1$,

  * •

and it must be left by a vertical step (of the same colour, of course), since
there are no uncrossed horizontal steps at level $z_{1}+1$.

But this would give a free kink on level $z_{1}+1$, a contradiction. ∎

######  Lemma 2.

Let ${\mathcal{F}}$ be a folded overlay, and let $z\in{\mathbb{Z}}$. If
$\overline{{\mathcal{F}}}_{z+1}$ does not contain a free kink, then every
finite face of $\overline{{\mathcal{F}}_{z}}$ is a vertical strip.

###### Proof.

Let $f$ be an arbitrary finite face of the planar simple graph
$\overline{{\mathcal{F}}_{z}}$ and consider the left side $l$ of $f$, which we
traverse now in the normal direction (i.e., rightwards and upwards).

Recall that $l$ starts with a vertical step. If $l$ does not contain a
horizontal step, it must end with a single slanted step.

By Lemma 1, $l$ does contain

  * •

neither a horizontal bicoloured edge

  * •

nor an uncrossed double step:

So every horizontal step $h$ belonging to $l$ is unicoloured: If $h$ is not
the last step in $l$, then it must be followed by a vertical edge $v$ in $l$,
and since $l$ starts with a vertical step, this horizontal step $h$ must
appear on some level $>z$.

Since $\overline{{\mathcal{F}}}_{z+1}$ does not contain a free kink, $v$ must
be bicoloured. But the segment $\left(h,v\right)$ cannot belong to the left
side of $f$, as the following picture shows:

$f$$-2$$-1$$0$$1$$-2$$-1$$0$$1$$2$

So only the last step in $l$ may be horizontal or slanted: In both cases, the
right side of $f$ is a path from the initial point $\left(x,y\right)$ of $l$
to its terminal point $\left(x+1,y+h\right)$ (for some integer $h$) which
starts with a horizontal or slanted step, and $f$ is a vertical strip. ∎

######  Lemma 3.

If $\mathcal{F}$ is a folded survivor, then $\overline{\mathcal{F}}$ cannot
contain free kinks strictly above the forbidden line (i.e., the “middle
vertex” of any free kink must lie on the forbidden line).

###### Proof.

Consider again the set

$S=\left\\{\zeta\in{\mathbb{Z}}\colon\;\overline{\mathcal{F}}_{\zeta}\text{
does contain a horizontal step}\right\\}\subset{\mathbb{Z}}.$

If $S$ is empty, then $\overline{\mathcal{F}}$ clearly does not contain a free
kink: So the assertion is true in this case.

If $S\neq\emptyset$, then consider $z_{0}=\max\left(S\right)\in{\mathbb{Z}}$:
Clearly, $\overline{\mathcal{F}}_{z_{0}+1}$ does not contain a free kink. Now
assume that the assertion is false, and let $z\leq z_{0}$ be the maximal
number such that $\overline{{\mathcal{F}}_{z}}$ does contain a free kink above
the forbidden line.

By Lemma 2, every finite face of $\overline{{\mathcal{F}}_{z}}$ is a vertical
strip, and we may arrange the family of these faces in a row of columns.
Clearly, a free kink can only occur in columns of type
${\color[rgb]{0,0,1}B}{\color[rgb]{0,1,0}G}$ or
${\color[rgb]{0,1,0}G}{\color[rgb]{0,0,1}B}$. The following picture shows the
possibilities for such columns:

$1$$2$$3$$4$$5$

Picture $5$ (counted from the left) shows an impossible chain (since blue
paths never intersect the forbidden line) and is thus crossed out.

Picture $4$ shows a column of type
${\color[rgb]{0,0,1}B}{\color[rgb]{0,1,0}G}$ which ends with a (green) free
kink on the forbidden line.

Picture $3$ shows a column of type
${\color[rgb]{0,1,0}G}{\color[rgb]{0,0,1}B}$ which does not end in a free
kink.

Pictures $1$ and $2$ show free kinks strictly above the forbidden line (marked
by small rhombi in the pictures): It is easy to see that these chains would
give involutive bicoloured connections of two terminal points of different
colour, which contradicts our assumption that $\mathcal{F}$ is a folded
survivor. ∎

######  Lemma 4.

If $\mathcal{F}$ is a folded survivor which contains a column $c$ of type
${\color[rgb]{0,1,0}G}{\color[rgb]{0,0,1}B}$, then there cannot be a column
$c^{\prime}$ of type ${\color[rgb]{0,0,1}B}{\color[rgb]{0,0,1}B}$ which lies
to the right of $c$.

In particular, any column which is ascending adjacent “to the right” of $c$
must be of type ${\color[rgb]{0,0,1}B}{\color[rgb]{0,1,0}G}$.

###### Proof.

If $c$ would end above the forbidden line, then it would have a free kink
above the forbidden line and thus yield an involutive bicoloured connection:
So $c$ ends on the forbidden line, and the same must be true for $c^{\prime}$:
But it is impossible for a column of type
${\color[rgb]{0,0,1}B}{\color[rgb]{0,0,1}B}$ to run into the forbidden line,
see the middle picture in the following illustration:

(It is no problem for a column of type
${\color[rgb]{0,1,0}G}{\color[rgb]{0,1,0}G}$ to run into the forbidden line,
see the left picture above, and a column of type
${\color[rgb]{0,0,1}B}{\color[rgb]{0,0,1}B}$ must end in blue initial points,
see the right picture above.)

By the considerations in section 3.6.5, a column $c^{\prime}$ which is
ascending adjacent to the right of $c$ must be of type
${\color[rgb]{0,0,1}B}{\color[rgb]{0,1,0}G}$ or
${\color[rgb]{0,0,1}B}{\color[rgb]{0,0,1}B}$, and we just made clear that type
${\color[rgb]{0,0,1}B}{\color[rgb]{0,0,1}B}$ is impossible. ∎

Our considerations make clear that certain distributions of colours for the
terminal points (which are not also initial points) are impossible for folded
survivors:

######  Corollary 1.

If $\mathcal{F}$ is a folded survivor, then the sequence of terminal points
which are not also initial points

  * •

may start with a sequence of consecutive blue points,

  * •

and every blue point not belonging to this starting sequence must be
immediately followed by a green point.

(In other words: After the first green terminal point, there can never follow
a pair of consecutive blue terminal points.)

####  3.6.11. The mapping $\xi$ from the lhs to the rhs

We showed that the planar graph $\overline{\mathcal{F}}$ corresponding to a
folded survivor $\mathcal{F}$ necessarily appears as a row of columns (where
consecutive columns are ascending adjacent): It is easy to see that every row
of columns

  * •

corresponds bijectively to a planar graph $\overline{\mathcal{F}}$ of some
folded overlay ${\mathcal{F}}$

  * •

which does not have an involutive bicoloured connection (in fact, bicoloured
connections correspond precisely to columns of type
${\color[rgb]{0,0,1}B}{\color[rgb]{0,1,0}G}$ or
${\color[rgb]{0,1,0}G}{\color[rgb]{0,0,1}B}$ in a folded survivor, and these
are not involutive since they end on the forbidden line),

so we have the following characterization: A folded overlay $\mathcal{F}$ is a
folded survivor if and only if its corresponding planar graph
$\overline{\mathcal{F}}$ appears as a row of columns.

The mapping $\xi$ from the lhs to the rhs now is best conceived by looking at
a sequence of pictures: The first picture shows our running example, where the
maximal descending chains of vertical strips are coloured:

In the next picture, chains of type
${\color[rgb]{0,1,0}G}{\color[rgb]{0,0,1}B}$ with their mandatory “right
neighbour” of type ${\color[rgb]{0,0,1}B}{\color[rgb]{0,1,0}G}$ are indicated
as crosshatched:

The next picture visualizes that the row of columns may be viewed as (segments
of) lattice paths (drawn in red):

Note that these red paths

  * •

are nonintersecting,

  * •

and end on the forbidden line,

  * •

and can never intersect the diagonal $\left(y=x\right)$:

So now the diagonal plays the role of the forbidden line for these red path
segments, and the forbidden line plays the role of the diagonal (in the sense
that it contains the terminal points for these paths).

In the next picture, the artificial slanted edges are removed and enforced
segments of green paths reaching the forbidden line from below are added:

This shows how the colour distribution of green or blue terminal points for a
folded survivor determines the green points on the forbidden line which must
be reached

  * •

from below (by the green segments of paths just added),

  * •

or from the left (by the red segments of paths).

Altogether, this shows that each row of columns which corresponds to some
folded survivor uniquely determines segments of nonintersecting lattice paths
(the red paths in the above picture) connecting

  * •

certain blue initial points

  * •

with certain points on the forbidden line,

(as illustrated in the above pictures).

In the following picture we added

  * •

the $01$–code for the lhs (corresponding to the colours of the blue and green
terminal points)

  * •

and the enforced terminal segments for the red and green paths ending on the
forbidden line together with the corresponding reflected $01$–code for these
terminal segments:

$0$$1$$1$$0$$1$$0$$1$$1$$1$$0$$1$$0$$1$$1$$1$$0$$0$$1$$1$$0$$0$$1$

This picture shows that

  * •

the (original) diagonal $\left(y=x\right)$ plays the role of the forbidden
line

  * •

and the (original) forbidden line plays the role of the diagonal (in the sense
that it contains the terminal points)

for the collection of red and green segments of paths.

####  3.6.12. The effect of $\xi$ on $01$–codes and their signs

The above picture also shows

  * •

the $01$–code $C$ for the lhs (implied by the blue and green terminal points,
in our example: $c=01101011101011$)

  * •

and the reflected $01$–code $c$ corresponding to the black and red or green
paths reaching the forbidden line, i.e.

    * –

$1$ for points reached from below,

    * –

$0$ for points reached from the left

(in our example: $c=10011001$).

(This swap of zeros and ones corresponds to the fact that we consider the
reflected situation for the rhs here.)

The bijective correspondence between these two $01$–codes is easy to see: For
the $i$–th zero in the $01$–code $C$ corresponding to the green and blue
terminal points, we count the number $z_{i}$ of ones to its left (in our
example, these numbers are $\left(0,2,3,6,7\right)$) and omit all zeros among
these numbers (in our example: $\left(2,3,6,7\right)$). Then these numbers are
precisely the indices (starting with one) of the zeros in the reflected
$01$–code $c$. But this simple observation already proves that the mapping
$\xi$ changes the sign of (the permutations corresponding to) these $01$–codes
by a constant factor: Recall (see section 3.1) that the number of inversions
of the permutation

  * •

corresponding to some $01$–code $c$ for the rhs (which is reflected in our
case, but we already accounted for the reflection by swapping ones and zeros)
is equal to the sum of the indices of the zeros in $c$ (in our example: the
permutation corresponding to $10011001$ has $2+3+6+7=18$ inversions), see
(10),

  * •

corresponding to some $01$–code $C$ for the lhs is

$\binom{m+k-1+\left[\text{even}\right]}{2}+\mathop{inv}\left(C\right),$

see (9), and $\mathop{inv}\left(C\right)$ (by definition) equals the sum of
the numbers $\sum_{i}z_{i}$ defined above (in our example: $0+2+3+6+7=18$).

####  3.6.13. Completion of the mapping $\xi$

Now by simply

  * •

omitting the folded survivor’s overlay of green and blue paths

  * •

and changing the colours of the red paths to green

in the above picture, we obtain the restriction to the essential region of
some survivor from the reflected rhs (in the picture, also segments of green
paths outside the essential regions are shown, in order to indicate that we
view the essential region now as part of a bigger picture):

If we restore the segments of green paths outside the essential regions (see
the first picture of our running example), then we obtain the following
“normal” survivor:

It is easy to see that the above picture corresponds to the situation of the
reflected rhs with $01$–code $01100110$, and it is obvious that the mapping
$\xi$ thus constructed is injective.

####  3.6.14. Surjectivity of the mapping $\xi$

To see that $\xi$ is also surjective, we shall exhibit its inverse mapping:
Consider a “normal” survivor with $01$–code $c$ from the reflected rhs, and
interpret the segments of its green paths inside the region considered for
folded overlays as red paths of a folded survivor with code $C$ corresponding
to $c$ (as described above). Then a unique row of columns (and thus a unique
folded survivor) is obtained “step by step”, starting at the diagonal
$\left(y=x\right)$, as illustrated in the following example:

The picture shows a section of a (“normal”) survivor for the reflected rhs
with (reflected) $01$–code $00011100$, where green path segments in the
essential region are coloured red. According to the considerations in section
3.6.12, the colouring of terminal points for the corresponding folded survivor
is uniquely determined by this $01$–code (since the graphics is cut at level
$6$, the terminal blue and green points above level $6$ are “shifted down”).

If we draw the row of columns “pending from the blue and green terminal
points” down to the the uppermost red path, then we obtain the following
picture:

Now recall that in a folded survivor, every descending chain must contain
vertical strips of the same type: So the second step of completing the
descending chains “rightwards–downwards” yields the following situation:

The third step yields:

And the fourth step finishes the construction, and yields a row of columns
which we may view as the restriction to the essential region of a folded
survivor :

So the mapping $\xi$ is indeed a bijection which changes the sign of survivors
by the constant factor

$\left(-1\right)^{\binom{m+k-1+\left[\text{even}\right]}{2}}$

This finishes our proof of (3) and (5).

## References

  * [1] Désiré André.  Solution directe du probleme résolu par M. Bertrand.  CR Acad. Sci. Paris, 105(436):7, 1887.
  * [2] J. Cigler.  Shifted Hankel determinants of Catalan numbers and related results II: Backward shifts.  arXiv:2306.07733.
  * [3] J. Cigler.  Some experimental observations about Hankel determinants of convolution powers of Catalan numbers.  arXiv:2308.07642v2.
  * [4] I.M. Gessel and X. Viennot.  Determinants, paths, and plane partitions.  preprint, 1989.
  * [5] B. Lindström.  On the vector representation of induced matroids.  Bull. London Math. Soc., 5:85–90, 1973.


# Assessing Group-level Gender Bias in Professional Evaluations: The Case of
Medical Student End-of-Shift Feedback

Emmy Liu
Language Technologies Institute
Carnegie Mellon University
<EMAIL_ADDRESS>
Michael Henry Tessler
MIT
Brain and Cognitive Sciences
<EMAIL_ADDRESS>
Nicole Dubosh
Beth Israel Deaconess Medical Center
Harvard Medical School
<EMAIL_ADDRESS>
Katherine Mosher Hiller
Indiana University
School of Medicine, Bloomington
<EMAIL_ADDRESS>
Roger P. Levy
MIT
Brain and Cognitive Sciences
<EMAIL_ADDRESS>
###### Abstract

Although approximately 50% of medical school graduates today are women, female
physicians tend to be underrepresented in senior positions, make less money
than their male counterparts and receive fewer promotions. There is a growing
body of literature demonstrating gender bias in various forms of evaluation in
medicine, but this work was mainly conducted by looking for specific words
using fixed dictionaries such as LIWC and focused on recommendation letters.
We use a dataset of written and quantitative assessments of medical student
performance on individual shifts of work, collected across multiple
institutions, to investigate the extent to which gender bias exists in a day-
to-day context for medical students. We investigate differences in the
narrative comments given to male and female students by both male or female
faculty assessors, using a fine-tuned BERT model. This allows us to examine
whether groups are written about in systematically different ways, without
relying on hand-crafted wordlists or topic models. We compare these results to
results from the traditional LIWC method and find that, although we find no
evidence of group-level gender bias in this dataset, terms related to family
and children are used more in feedback given to women.

##  1 Introduction

Female physicians and trainees have advanced considerably in the medical field
within recent years, and approximately 50% of medical school graduates are now
women Lautenberger et al. (2014). However, female physicians lag their male
counterparts in salary, promotions, and positions in senior leadership
Lautenberger et al. (2014); Carnes et al. (2008); Ash et al. (2004); Bennet et
al. (2019). A mechanism that perpetuates this inequality may be unequal
evaluations of male and female physicians. Past work has revealed gender bias
in several forms of evaluation. Evaluations of recommendation letters in
academia found that women tended to be described in communal traits (caring,
nurturing) whereas men were described in agentic terms (ambitious and self-
confident) Madera et al. (2009). The same trend holds in direct observation
comments given to Emergency Medicine (EM) residents, with feedback themes
varying by gender, particularly around the domains of authority and
assertiveness AS et al. (2017). In the same context, women were also found to
receive more contradictory and polarized assessments on their skills as
compared to men AS et al. (2017).

If there are systemic differences in evaluations for different genders, it may
be possible that these differences arise early in a student’s career and
snowball into fewer opportunities in late career, when they are quantitatively
detectable through metrics such as salary and number of promotions. It is
important to understand at what phases of a student’s career inequities arise,
so that interventions can be targeted toward supporting women or other
underrepresented minorities at these stages. Focus groups of female physicians
in the field find different experiences at early, mid, and late career stages,
with older women experiencing more overt discrimination, and younger women
reporting more implicit bias, though it is unknown if this is due to decreased
discrimination in recent years, or due to younger physicians not yet
recognizing signs of discrimination Chesak et al. (2022).

Findings on gender differences in language are mixed for students earlier in
their careers. A qualitative analysis of surgical residency letters of
recommendation, collected from before the students applied for residency,
found that male applicants’ letters contained more achievement-oriented terms,
whereas female applicants’ letters contained more care-oriented terms
Turrentine et al. (2019). However, a similar analysis on the EM standardized
letter of evaluation found no such difference S et al. (2017).

To investigate this question more thoroughly, we use a new dataset of written
assessments on medical students’ work based on individual shift performance
before their residencies. Most previous work from the medical community has
used relatively simple linguistic methods such as the Linguistic Inquiry and
Word Count dictionary (LIWC) Pennebaker et al. (2015); Madera et al. (2009); S
et al. (2017); Schmader et al. (2007), but using pretrained language models
may allow us to investigate bias in a more fine-grained manner Andrews et al.
(2021); Sarraf et al. (2021). Additionally, existing work on medical bias
within the NLP community mainly focuses on patients, rather than physicians
themselves van Aken et al. (2021).

We fine-tune a pretrained BERT model and use its predictions as a tool to try
to identify group-level prediction residuals. If such a difference exists on a
systematic level, it may indicate that assessors are writing about students in
different ways based on their gender, given the same objective performance.
Caution should be taken when using similar methods as language models can also
come imbued with biases of their own, but we outline the method in this work
and highlight its use in comparing model predictions and human judgments when
both text data and quantitative data are available.

Although we can replicate past work showing a significant difference in
social-communal terms used to describe women, we do not find as clear a
relationship between comments written about a student and the global score
given on a shift. We do not find a systemic difference between male and female
students when comparing group-wide residual differences. This indicates that
although male and female students may be written about differently, no gender
is written about in a systemically worse way. Due to privacy concerns, the
dataset is not available online, but the full dataset can be obtained through
emailing our medical co-author<EMAIL_ADDRESS>
##  2 Bias Statement

We study the relationship between text comments and numeric ratings of
performance given to male and female medical students. We introduce the method
of comparing language model residual predictions to numeric data to find
group-wide differences in language use. We fine-tune a language model to
predict the rating associated with a given comment about a student, and ask if
there is a cross-group difference in the residual error that the trained model
makes. For instance, are female students given less positive-sounding comments
than their male counterparts for the same level of clinical skills (as
measured by their numeric evaluation scores)?

Feedback from supervisors is used to make decisions on whether a student
receives a residency, or later on whether they get promoted to a higher
position within medicine. This has potential to address allocational harms to
women within medicine. The under-representation of women in senior positions
in medicine could also lead to wider harms in inequity as a result.

There are shortcomings in presenting gender as a binary, and in this dataset
gender information was not collected based on self-identification. We hope
that future work will explore a wider diversity of gender identification, but
we present this analysis as a first step.

##  3 Dataset

The dataset consists of evaluations of undergraduate medical students
conducted with the National Clinical Assessment Tool (NCAT-EM), the first
standardized assessment based on direct observation of skills in a clinical
setting of American Medical Colleges (2017); Jung et al. (2017). The NCAT-EM
was developed by EM educators, and has been implemented at 13 institutions in
the United States. Data was collected from departments participating in the
NCAT-EM Consortium from 2017-2019 Jung et al. (2017).

The dataset contains short free text comments on a student’s performance,
categorical assessments on multiple skill areas, a global competency score
(lower third, middle third, top third, and top 10%), as well as demographic
information about students and assessors: gender, age, rank of assessor
(junior vs senior faculty). These attributes are outlined in Figure 1.
Examples of free-text comments and associated scores are given in Table 1.

Figure 1: Data and features included in the NCAT-EM dataset. Global Score |  Comment
---|---
0 |  always seemed happy to help but did not reassess patients or follow up labs on own. also, came off as arrogant to multiple residents in the department.
1 |  good differential, interested, team player.
2 |  great job keeping up with your patients; we had a very sick one and you made sure you were on top of it.
3 |  i really enjoyed working with x, as x was a very thorough historian, and provided a brief focused history. x appears to have a good grip of emergency medicine at this point, and provides a good reasonable plan. x is going to be an exceptional resident, and will continue to improve significantly over the next year.
Table 1: Examples of free text comments written about students (after
preprocessing), with the associated global competency score (on a scale from 0
to 3).

After excluding samples with missing data, there were 3162 individual
assessments, where 1767 were evaluations of male students and 1395 were
evaluations of female students. Because students may work multiple shifts, and
the same supervisor may supervise multiple students, there are some students
and assessors who are repeated, although each sample represents a different
shift. Names and named entities were removed from comments using the spaCy
entity recognizer and replaced with the letter "x". Gendered pronouns were
removed and replaced with the gender-neutral pronoun "they".

This dataset consists mostly of short comments focused on student performance.
The mean number of words in a comment was 28.4, and the maximum number of
words in a comment was 187. The overall distribution of assessment ratings
was: 5% in bottom third, 35% in middle third, 45% in top third, and 15% in the
top 10%. A slightly higher density of female students received the top rating
compared to male students. We convert these to integer values from 0-3.

We use two main methods to identify possible biases in this dataset:
prediction residual analysis and word/topic based analysis. Previous work has
focused on word-level analysis, but since we have access to both comments as
well as a competency score, we investigate to what extent we can reconstruct
the mapping from text comment to the score a student receives by applying a
language model, and if there are differences in this mapping between male and
female students. We used 70% of the dataset to train, 15% to evaluate, and 15%
as the test set.

###  3.1 Language Model Prediction Residuals

Figure 2: Panel A illustrates the LM residual method (for illustration
purposes, the areas under the curve in this drawing are not necessarily the
same as they would be in reality). A language model is finetuned on text
evaluations without gender information to predict the global rating. Panel B
illustrates a case with no differences in residuals between the male and
female group, illustrating the case without textual bias. Panel C illustrates
a biased case. In this hypothetical case, female students received a score
that is consistently higher than the language in their comments would suggest.

In order to examine the relationship between text comments and the global
competency score, we finetune bert-base-uncased with early stopping on the
free text comments with gender and institution information removed, with a
linear layer trained to predict the global competency score 111We used the
Adam optimizer with a learning rate of 5e-6, epsilon of 1e-8, and weight decay
1e-10, and a batch size of 32. These parameters were taken from the default
settings of the transformers implementation of Adam at the time, with a
minimal hyperparameter search over learning rate.. We then examine the
prediction residuals of the finetuned model on a group level for group
$\mathcal{C}$:

$\delta_{\mathcal{C}}=\\{y_{i}-\hat{y_{i}}\\}_{i=0}^{|\mathcal{C}|}$ (1)

In the student-only setup the groups would be the set of male students,
$\mathcal{M}$, and the set of female students $\mathcal{F}$. In the student
and assessor setup, the groups would be the different assessor and student
gender combinations, namely $\mathcal{M}\times\mathcal{M}$,
$\mathcal{M}\times\mathcal{F}$, $\mathcal{F}\times\mathcal{M}$, and
$\mathcal{F}\times\mathcal{F}$. The null hypothesis is that there should be no
difference between these groups, for instance $\delta_{\mathcal{F}}$ and
$\delta_{\mathcal{M}}$. If there is a significant difference, it indicates
that there may be a difference in the relationship between text and global
score between these groups. For instance, if the $\delta_{F_{i}}$s are
significantly higher, this would indicate that scores given to female students
are significantly higher than expected given comments about them. Note that
$\hat{y_{i}}$ is based on text from which explicit gender markers were
removed.

###  3.2 LIWC

In order to check if previous results using LIWC replicated on this dataset,
we examined many categories of words from LIWC 222Specifically, we examined
these categories: Affect, Positive Emotion, Negative Emotion, Social,
Cognitive Processing, Insight, Achieve, Standout, Ability, Grindstone,
Teaching, Research, Communal, Social-Communal, and Agentic. The associated
words can be found in either the standard LIWC dictionary or in these
references: Pennebaker et al. (2015); Madera et al. (2009).

Additionally, we used user-defined dictionaries from previous studies of
letters of recommendation: grindstone words (e.g. diligent, careful), ability
words (e.g. talented, intelligent), standout adjectives (e.g. exceptional),
research terms (e.g. research, data), teaching terms (e.g. teach,
communicate), social-communal terms, (e.g. families, kids), and agentic terms
(e.g. assertive, aggressive) Madera et al. (2009); Eagly and Johannesen-
Schmidt (2001); Eagly and Karau (2002); Eagly et al. (2000); Wood and Eagly
(2002). The prevalence of these categories was found to differ in past studies
of recommendation letters. We used a coding scheme of 0 if a theme did not
show up in a comment, and 1 if it did. We used a Fisher exact test on comments
written about male or female students, with Holm-Bonferroni correction to
control for multiple comparisons.

##  4 Results

###  4.1 Residual Analysis

We present the results for the residual analysis first. We note first that the
language model achieved relatively low accuracy when its predictions were
rounded to the nearest integer (46%), but made comparable predictions to
humans (50.7% average across three annotators, on a randomly-sampled 20% of
the dataset. The annotator agreement was moderate (Krippendorff’s $\alpha$ =
0.491). 333Annotators were shown a text comment and assigned a global rating
from 0-3. They did not see the labels for that portion of the dataset, but
were allowed to look at labels for the remaining 80% to guide their judgment.
Additionally, annotators were all familiar with the dataset and rubric for
global score.), This indicates a noisy mapping between text and global score
in this dataset.

Results following the format of Figure 2 are found in Figure 3, and visual
inspection does not reveal differences in residuals. A T-test comparing male
and female global scores in the entire dataset confirmed that female students
had a slightly higher score (higher mean by 0.08, $p<0.004$). However, no
significant difference was found between residuals for male and female
students ($p=0.517$). There were also no significant differences between BERT
predictions themselves for male and female students ($p=0.152$).

Figure 3: Residual densities for male and female students by global score
(0-3). BERT did not achieve a high accuracy on this task, but there was no
significant difference in group-wise residuals, showing that male and female
students tended to receive comments of a similar valence for their associated
score.

When considering both assessor gender and student gender, we performed an
ANOVA test and found that two groups had statistically significant differences
in means: when comparing male assessor, male student pairs with male assessor,
female student pairs, the male assessor, female student pairs had marginally
higher ratings (0.0893 difference, $p=0.0485)$). When comparing male assessor,
male student pairs with female assessor, female student pairs, female assessor
and female student pairs also had higher mean ratings (0.114 difference,
$p=0.0411$). These effects are more marginal, but expected given the slightly
higher scores of female students.

When examining the residuals for the 4-way split, there was one statistically
significant difference, between male assessor, female student pairs and female
assessor, female student pairs. The residual mean was 0.1195 higher in male
assessor, female student pairs, and this was significant to a marginal degree
($p=0.0468$). This indicates that the actual score given by male assessors to
female students was higher than their comment would suggest, as compared to
female assessors giving comments to female students. However, this was a
marginal effect, and overall we find no clear evidence of gender bias in the
comments given to students, or the relationship of the comments given to
global score received.

###  4.2 LIWC

We examine LIWC themes by student gender and partially replicate previous
results showing that women tend to be described with more social-communal
language than men Madera et al. (2009). We did not find any significant
differences when dividing by assessor gender. However, we did not find that
women were described as less agentic in this dataset. A summary of the
percentage of comments in which themes occurred is summarized in Table 2. Only
the difference in the Social-communal theme is highly significant ($p<6\times
10^{-16}$) after Holm-Bonferroni correction. This theme consists of family
terms (families, babies, kids), e.g. "great proactive attitude in approaching
members of the team and interacting with patients and their families". There
is some variation in these comments, as some concern bedside manners with
patients and families, and some comment on ability to work with children,
which may be necessary in a pediatric unit. We did not see a significant
difference in the communal theme (which would describe a warm and nurturing
student), unlike in past work.

Theme |  Example words |  % comments with theme (M) |  % comments with theme (F) |  odds ratio (M/F) |  $p$ (corrected)
---|---|---|---|---|---
Affect |  amazing, arrogan*, apath*, interest |  93.1% |  92.7% |  1.11 |  1
Positive Emotion |  fantastic, improve, brilliant |  89.5% |  89.4% |  1.03 |  1
Negative Emotion |  angry, difficulty, fail |  42.67% |  41.36% |  1.06 |  1
Social |  advice, ask, commun* |  59.9% |  57.9% |  1.08 |  1
Cognitive Processing |  accura*, inquir*, interpret* |  76.6% |  75.0% |  1.09 |  1
Insight |  deduc*, explain, reflect* |  53.6% |  52.2% |  1.05 |  1
Achieve |  abilit*, ambition, leader* |  67.1% |  66.7% |  1.02 |  1
Standout |  outstanding, exceptional, amazing |  17.0% |  20.6% |  0.786 |  0.1309
Ability |  talen*, smart, skill |  18.4% |  19.1% |  0.960 |  1
Grindstone |  reliab*, hardworking, thorough |  45.3% |  46.2% |  0.965 |  1
Teaching |  teach, mentor, communicate* |  21.1% |  22.7% |  0.914 |  1
Research |  research*, data, study |  9.96% |  9.75% |  1.02 |  1
Communal |  kind, agreeable, caring |  4.07% |  4.87% |  0.829 |  1
Social-communal |  families, babies, kids |  8.26% |  18.4% |  0.401 |  $5.88\times 10^{-16}$*
Agentic (adjectives) |  assertive, confident, dominant |  1.75% |  1.72% |  1.02 |  1
Agentic (Orientation) |  do, know, think |  10.2% |  7.67% |  1.37 |  0.1789
Table 2: LIWC theme occurrence in comments given to male and female students.
A higher percentage of comments contained the social-communal theme for women
than for men. $p$-values were corrected with the Holm-Bonferroni correction.

##  5 Conclusion

Gender bias in medical education is a major barrier to women in the field, and
it is important to know in what circumstances and career stages it occurs in
order to create targeted training and intervention. Previous work has found
that there may be potential bias in medical student recommendation letters,
but we investigate whether there is systemic bias in an everyday setting in
feedback given to male and female medical students. We collect data using
NCAT-EM evaluations to answer this question, and use language model residuals
to investigate the relationship between free text comments and integer ratings
given to students. We find no evidence of bias using the residual definition,
although we find that there is a statistically significant difference in the
percentage of comments that mention social-communal themes, with women
receiving more mentions of family-oriented words in their evaluations.

One limitation of this dataset is that the mapping between text comment and
global score is quite noisy, as neither a fine-tuned language model nor human
judges were able to achieve a high score in classifying the text based on the
global rating. However, the prediction residual method can be used in any
dataset with both text data and outcome data, for instance applications to
educational programs, or employee evaluations. One caveat is that language
models themselves can be biased, so this method is best applied after
sensitive attributes have been obfuscated.

Additionally, this dataset is quite small and limited to a relatively small
set of samples. It is possible that biases could be found in a larger dataset
of shift evaluations, or in data collected from a different set of
institutions. However, we leave such data collection to future work, and hope
that this encourages the collection and analysis of similar data on a wide
scale. We hope that this work will inspire further research into how bias
manifests or does not manifest at different stages of professionals’ careers,
and how we can combine multiple sources of information together with text to
form a wider view of bias and fairness.

## Acknowledgements

We thank Lynnette Ng and Samantha Phillips for participating in the human
annotation task.

## References

  * Andrews et al. (2021) J Andrews, D Chartash, and S Hay. 2021.  Gender bias in resident evaluations: Natural language processing and competency evaluation.  _Medical Education_ , 55:1383–1387.
  * AS et al. (2017) Mueller AS, Jenkins TM, Dayal A, O’Connor DM, Osborne M, and Arora VM. 2017.  Gender differences in attending physicians’ feedback to residents: a qualitative analysis.  _J Grad Med Educ_ , 9:577–585.
  * Ash et al. (2004) Arlene S. Ash, Phyllis L. Carr, Richard Goldstein, and Robert H. Friedman. 2004\.  Compensation and advancement of women in academic medicine: is there equity?  _Ann Intern Med_ , 141:205–212.
  * Bennet et al. (2019) CL Bennet, AS Raja, N Kapoor, D Kass, Blumenthal DM, N Gross, and AM Mills. 2019\.  Gender differences in faculty rank among academic emergency medicine physicians in the united states.  _Acad Emerg Med_ , 26:281–285.
  * Carnes et al. (2008) Molly Carnes, Claudia Morrissey, and Stacie E. Geller. 2008.  _J Womens Health (Larchmt)_ , 17:1453–1462.
  * Chesak et al. (2022) Sherry S. Chesak, Manisha Salinas, Helayna Abraham, Courtney E. Harris, Elise C. Carey, Tejinder Khalsa, Karen F. Mauck, Molly Feely, Lauren Licatino, Susan Moeschler, and Anjali Bhagra. 2022.  Experiences of gender inequity among women physicians across career stages: Findings from participant focus groups.  _Women’s Health Reports_ , 3(1):359–368.
  * Eagly and Johannesen-Schmidt (2001) AH Eagly and MC Johannesen-Schmidt. 2001.  The leadership styles of women and men.  _journal of Social Issues_ , 57:781–797.
  * Eagly and Karau (2002) AH Eagly and SJ Karau. 2002.  Role congruity theory of prejudice toward female leaders.  _Psychological Review_ , 109:573–598.
  * Eagly et al. (2000) AH Eagly, W Wood, and AB Diekman. 2000.  Social role theory of sex differences and similarities: A current appraisal.  In T Ecks and HM Traunter, editors, _The developmental social psychology of gender_ , pages 123–174. Erlbaum, Mahwah, NJ.
  * Jung et al. (2017) J Jung, D Franzen, L Lawson, D Manthey, M Tews, and N et al. Dubosh. 2017.  The national clinical assessment tool for medical students in emergency medicine (ncat-em).  _West J Emerg Med_ , pages 66–74.
  * Lautenberger et al. (2014) DM Lautenberger, VM Dandar, CL Raezer, and RA Sloane. 2014.  The state of women in academic medicine: the pipeline and pathways to leadership.
  * Madera et al. (2009) JM Madera, MR Hebi, and RC Martin. 2009.  Gender and letters of recommendation for academia: agentic and communal differences.  _J Appl Psychol_ , 94:1591–1599.
  * of American Medical Colleges (2017) Association of American Medical Colleges. 2017.  Core competencies for entering medical students.
  * Pennebaker et al. (2015) James W. Pennebaker, Ryan L. Boyd, Kayla Jordan, and Kate G. Blackburn. 2015.  The development and psychometric properties of liwc2015.
  * S et al. (2017) Li S, AL Fant, Mcarthy DM, Miller D, Craig J, and Kontrick A. 2017.  Gender differences in language of standardized letter of evaluation narratives for emergency medicine residency applicants.  _AEM Educ. Train_ , 1:334–339.
  * Sarraf et al. (2021) D Sarraf, V Vasiliu, B Imberman, and B Lindeman. 2021.  Use of artificial intelligence for gender bias analysis in letters of recommendation for general surgery residency candidates.  222:1051–1059.
  * Schmader et al. (2007) T Schmader, J Whitehead, and VH Wysocki. 2007.  A linguistic comparison of letters of recommendation for male and female chemistry and biochemistry job applicants.  _Sex Roles_ , 57:509–514.
  * Turrentine et al. (2019) EF Turrentine, Dreisbach CN, St. Ivany AR, Hanks JB, and Schoren AT. 2019.  Influence of gender on surgical residency applicants’ recommendation letters.  _J Am Coll Surg_ , 228:356–365.
  * van Aken et al. (2021) Betty van Aken, Sebastian Herrmann, and Alexander Löser. 2021.  What do you see in this patient? behavioral testing of clinical nlp models.
  * Wood and Eagly (2002) W Wood and AH Eagly. 2002.  A cross-cultural analysis of the behavior of women and men: Implications for the origins of sex differences.  _Psychological Bulletin_ , 128:699–727.