# Precision at the indistinguishability threshold: a method for evaluating
classification algorithms

David J. T. Sumpter
Department of Information Technology, Uppsala University, Sweden

###### Abstract

There exist a wide range of single number metrics for assessing performance of
classification algorithms, including AUC and the F1-score (Wikipedia lists 17
such metrics, with 27 different names). In this article, I propose a new
metric to answer the following question: when an algorithm is tuned so that it
can no longer distinguish labelled cats from real cats, how often does a
randomly chosen image that has been labelled as containing a cat actually
contain a cat? The steps to construct this metric are as follows. First, we
set a threshold score such that when the algorithm is shown two randomly-
chosen images — one that has a score greater than the threshold (i.e. a
picture labelled as containing a cat) and another from those pictures that
really does contain a cat— the probability that the image with the highest
score is the one chosen from the set of real cat images is 50%. At this
decision threshold, the set of positively labelled images are
indistinguishable from the set of images which are positive. Then, as a second
step, we measure performance by asking how often a randomly chosen picture
from those labelled as containing a cat actually contains a cat. This metric
can be thought of as precision at the indistinguishability threshold. While
this new metric doesn’t address the tradeoff between precision and recall
inherent to all such metrics, I do show why this method avoids pitfalls that
can occur when using, for example AUC, and it is better motivated than, for
example, the F1-score.

##  1 Introduction

Imagine you have created an algorithm (a machine learning model) that assigns
a score, predicting whether an entity belongs to one of two classes (positive
and negative). For example, the input might be a picture and the output
whether or not the picture contains a cat. The scores are larger if your
algorithm evaluates the object as more likely to belong to the positive class
(i.e if it labels the image as more likely to contain a cat). Such a scoring
system explicitly underlies, for example, logistic regression, the output of a
neural network and discriminant analysis [1]. Other, non-parametric machine
learning methods, such as $k$-nearest neighbours [2], don’t have an explicit
score, but often have a parameter (e.g. $k$) which can be tuned in a way that
mimics a threshold.

Figure 1: Illustration of the method described in this paper

The method I suggest for evaluating performance in this article is as follows.
We start, in figure 1a, with a data set in which every image is assigned a
score. We first investigate what happens when we set a threshold score, $r$,
above which we label the image as containing a cat (positive), below which we
label the image as not containing a cat (negative). For any given threshold we
compare those images which we label as cats (given the threshold) with those
containing real cats. Specifically, we choose (with replacement) $n$ real cats
and $n$ labelled cats at random and compare scores (figure 1b). In cases where
we happen to pick the same two images, we pick two new images for that
particular comparison. This gives a measure $B(r)$: the probability a real cat
scores more than a labelled cat for threshold $r$.

We then identify a specific threshold score, $r_{b}$, such that if we were to
choose one image that the algorithm classifies as containing a cat and a
second image that really does contain a cat, then the probability that the
score of the image containing the cat is the largest of the two scores is 50%.
We define this as $r_{b}$, where $B(r_{b})\approx 0.5$. In the example, in
figure 1b $r_{b}=67$. A smaller threshold gives $B(r_{b})>0.5$ and a larger
threshold gives $B(r_{b})<0.5$ (figure 1c). We call $r_{b}$ the
indistinguishability threshold: because the set comprised of false positives
(FP) and true positives (TP) is indistinguishable from the set of TPs and true
negatives (TN). When $r=r_{b}$, if we pick (at random) two images from our
data set, one which is labelled as a cat and the other that is known to
contain a cat, then the probability that the algorithm will score assign the
image with the cat the highest score is one half.

To measure the performance of your algorithm, simply calculate the proportion
of images the algorithm classifies as containing a cat do actually contain a
cat. I denote this measure $C(r_{b})$ and call it precision at the
indistinguishability threshold.

There already exist a number of ways of evaluating classification algorithms.
Wikipedia lists a somewhat bewildering array of 17 tests, with a total of 27
different names, for such problems. The most commonly used method is the area
under the Receiver-Operator Curve, commonly referred to as AUC [3, 4, 5].
Another popular choice is the F1-score [6], which seeks to avoid a problem
inherent in AUC when applied to unbalanced data [1]. In this paper, I argue
that $C(r_{b})$ provides an easy to understand alternative to F1-score, which
avoids many of the problems inherent to AUC.

##  2 Data set

Figure 2: The score distributions for the nine example data sets we look at
here. Green are members of the negative class, yellow members of the positive
class. The dotted line shows $r_{b}$, the solution $B(r)=1/2$ (see equation 6)

I use nine artificial data sets, as shown in figure 2. The positive class
($Y_{i}=1$) is created by first generating 1000 input values, $X_{i}$, with a
mean $m_{p}=10$ and standard deviation $\sigma_{p}=2$. Similarly, the negative
class ($Y_{i}=-1$) consists of 1000 ‘difficult’ data points with values,
$X_{i}$, which have mean scores (a,d,g) $m_{n}=5$; (b,e,h) $m_{n}=7$; (c,f,i)
$m_{n}=9$ and (in all cases) standard deviation $\sigma_{n}=2$, along with
(a,b,c) 10000; (d,e,f) 1000; (d,e,f) 100 ‘easy’ data points, $X_{i}$, with
mean 2 and standard deviation 2. I then performed logistic regression on
$X_{i}$ to predict $Y_{i}$ and calculated the log-likelihood for every
individual point. These log-likelihoods are taken to be the scores, $S_{i}$,
output by the model and are plotted in figure 2.

The choice of these data sets is to give a range of difficulty levels. The
data in the left column correspond to relatively easy classification tasks.
The overlap between the green (negative) and yellow (positive) is small. The
data in the right column is much more difficult, with a large overlap in
scores for negative and positive. The datasets at the bottom include a large
number of ‘easy’ to classify negative values, but the size of the overlap is
only slightly increased over the datasets at the top. The data generation
method and the code are available at: https://github.com/soccermatics/ABC.git.

##  3 Results

###  3.1 Area under the curve

Let’s start by asking the following question about our data: how often does a
member of the positive class score higher than a member of the negative class?

To measure this we pick one member of the positive class at random and one
member of the negative class at random and we will look to see which of them
has the highest score. As a concrete example, imagine an algorithm is shown
two images, one which contains a cat, another which does not. The task is to
pick the image containing the cat. We call this probability

$A=P(S_{P}>S_{N})$

where $S_{P}$ is the score of a randomly chosen positive member and $S_{N}$ is
the score of a randomly chosen negative member. The value of $A$ can be
measured directly, simply by randomly picking pairs of members of negative and
positive classes and testing which scores higher. The test outcome is then the
proportion of cases in which the positive member receives a higher value than
the negative member.

We can also measure the paired comparison test over all our scores. Let
$F_{P}(r)$ be the cumulative distribution of scores of the positive class,
i.e.

$F_{P}(r)=P(S_{P}<r)=\int_{s=-\infty}^{r}f_{P}(s)ds$ (1)

where $f_{P}(r)$ is thus the probability density function of $S_{P}$.
Likewise, we let $F_{N}(r)$ to be the cumulative distribution of scores the
negative class, i.e.

$F_{N}(r)=P(S_{N}<r)=\int_{s=-\infty}^{r}f_{N}(s)ds$ (2)

The value $A=P(S_{P}>S_{N})$, can be written as the conditional probability
distribution

$A=\int_{r=-\infty}^{\infty}\int_{s=r}^{\infty}f_{N}(r)\cdot f_{P}(s)dsdr$ (3)

which is equivalent to

$A=\int_{r=-\infty}^{\infty}f_{N}(r)\int_{s=r}^{\infty}f_{P}(s)dsdr=\int_{r=-\infty}^{\infty}f_{N}(r)\cdot\left(1-F_{P}(r)\right)dr$
(4)

We can use this equation to calculate $A$ by numerical integration.

More importantly, we can also use this formulation to note an equivalence
between the $A$ test above and another commonly used measure of accuracy,
namely, AUC (the area under the ROC/receiver operator curve). ROC curves plot
the false positive rate against the true positive rate, as parametrised curves
of $r$. Note that the true positive rate for a given threshold $r$ is given by
$v(r)=1-F_{P}(r)$ and that the false positive rate for a given threshold $r$,
is given by $u(r)=1-F_{N}(r)$. Then we see that

$A=\int_{r=-\infty}^{\infty}v(r)f_{N}(r)dr$

which by change of variable gives

$A=\int_{u=0}^{1}v\left(u^{-1}(r)\right)du$ (5)

where $u^{-1}(r)$ denotes the inverse of $u(r)$. Thus $A$ is also the area
under the ROC curve (which is defined by the right hand side of equation 5).

Figure 3: The area under the curve for each of the scores in figure 2

The ROC curves are shown in figure 3 for our nine data sets. The area under
these curves (i.e. $A$) is shown as text within the figure. The value of $A$
is close to one when either the scores for the negative and positive class are
typically different (e.g. for the score distributions shown in figure 2 a, d
and g) or there are a large proportion of ’easy’ to score negative members
(e.g. for the score distributions shown in figure 2 h and i).

These examples illustrate both the power and the limitation of $A$ as a
measure. In the cases a, d and g – where the score accurately distinguishes
class members – $A$ reflects the fact it is more likely that the algorithm
picks out the positive cases correctly. But in the cases where there is an
overlap between the positive and ’difficult’ negative class (e.g. cases c, h
and i) we see that as we add more ’easy’ cases (i.e. go from c through f to i)
the accuracy of the model appears to increase, despite the fact that the
difficult cases are equally difficult in all three data sets. We could see
this as giving a possibility for ‘cheating’: by adding more easier cases to
our data set we can appear to be improving accuracy, as measured by $A$, while
no such improvement is actually occurring.

This is why we need to be very clear about what the AUC test tells us: it
tells us that if we pick one member of the positive class at random it has
probability $A$ of having a higher score than one member of the negative class
chosen at random. When there are a lot more ’easy’ to classify members of the
negative class then a high value of $A$ is not surprising: most of the time we
will randomly pick one of those members. Thus in figure 3i an $A$ close to one
tells us very little about how well our algorithm can distinguish more
difficult cases.

###  3.2 Indistinguishability threshold

We now look at how often a member of the positive class scored higher than a
member that has been labelled positive. To do this, we pick a random member of
the positive class and we compare its score to the score of a random
individual that has been labelled (predicted) positive. For example, in the
cat labelling problem, we first pick randomly from all images containing cats
and denote the score of this image as $S_{P}$. Then, for a given threshold
$r$, we choose randomly from all the images with that score or above,
irrespective of whether or not they contain a cat. We denote this score of
this image as $S_{R}$. We then calculate the probability

$B(r)=P(S_{P}>S_{R}|S_{R}>r)$

or, in words, the probability that a random member of the positive class
scores higher than a random member of the class we have labelled as positive
(i.e. has a score greater than $r$).

Unlike the paired comparison of negatives and positives we made in the
previous section, it is not immediately clear how this test will help us
construct a performance metric. To gain some more intuition, let’s think about
what happens as we change the threshold $r$. When $r$ is very large then the
positively labelled set will contain more positives than negatives, but very
few members of either class. As a result $P(S_{P}>S_{R}|S_{R}>r)$ will go
towards $0$. When $r$ is small (or negative), most images are labelled
positive. Nearly all members of the positive class will be included in the
positively labelled set, but so too will most members of the negative class.
Neither of these two situations is desirable. In the former, we will have a
lot of false positive errors and very low precision (or sensitivity): a high
proportion of those labelled positive will actually be negative. In the latter
case, we will have a large proportion of false negatives but very high
precision: most of those which are labelled positive are actually positive.

I suggest choosing $r_{b}$ such that

$B(r_{b})=P(S_{P}>S_{R}|S_{R}>r_{b})=1/2$ (6)

because this particular value of $r_{b}$ has a rather desirable property. It
means that, as far as the classifier is concerned the images in the positive
class are indistinguishable from those which we have labelled positive. If we
pick a random member of the images we have classified as positive and a random
member of the positives, these two images are equally likely to be classified
as positive. We can thus think of $r_{b}$ as being the threshold value at
which the model cannot distinguish between true positives and labelled
positives. The algorithm cannot distinguish reality from its own labelling. We
thus refer to $r_{b}$ as the indistinguishability threshold.

To understand why this is desirable, think about a situation where we have two
separate test sets of images, $Y_{1}$ and $Y_{2}$, and we want to check
whether or not they have a similar distribution of scores. A solution to this
problem might be to pick members from both $Y_{1}$ and $Y_{2}$ at random and
compare their scores. If roughly half of the time members of $Y_{1}$ scored
higher than members of $Y_{2}$ we might say that the two groups are
indistinguishable111There could still be differences between the distributions
of the sets not identified by such a test. For example $A$ might have larger
variance in scores than $B$. In the same way, by setting $r_{b}$ using
equation 6, we are finding a threshold so that the positive class is
indistinguishable from the set that is labelled positive. The vertical dotted
lines in figure 2 shows the value of $r_{b}$ for our nine example score
distribution sets. For all nine distributions the lines give a reasonable
separation between the scores, lying roughly halfway between the ‘difficult’
negative cases and the positive cases.

A common (but misguided) alternative to choosing $r=r_{b}$ is to instead
choose $r$ such that

$P(S_{P}=r)=1-P(S_{P}=r)$ (7)

or, equivalently,

$P(S_{P}=r)=1/2$ (8)

where we define an underlying model which converts scores in to probabilities.
For example, when the scores have been estimated by logistic regression then a
natural choice is the logistic function

$P(S_{P}=r)=\frac{1}{1+\exp(r)}=1/2$

which gives $r=0$ as the threshold. Looking again at the distribution of
scores in figure 2 we see that the size of the negative class shifts the
distribution of the scores generated by the logistic regression to the right.
This is undesirable, because it means that the algorithm will make more errors
when easy to categorise cases are added to the data set.

The limitations of using equation 8 to set a threshold are known, but often
they are referred to as being “caused by an unbalanced data set”. The
implication is that too many members in the negative class have somehow misled
us in to choosing a poor value of $r$. In my experience, students and even
experienced practitioners, when confronted with this problem, either start to
prune their data, removing ‘easy’ members of the negative class, or oversample
from the positive class in order to compensate. They might also draw an ROC
curve and a Precision-Recall curve (see below) and try to justify, in an ad-
hoc fashion, choosing a different value of the threshold $r$ on the basis of
what they see in these curves.

It is not the data set that is imbalanced. It is rather our way of looking at
it that is wrong! Specifically, it is the arbitrary choice of $r=0$ that is
imbalanced.

While both of the two measures — $A$ and $B(r)$ — that we have looked at so
far have sensible, method independent interpretations that give us a measure
performance, this is not the case for equation 7, which is simply the score
for which the probability of receiving a positive label equals that of
receiving a negative label. In logistic regression, the model is adjusting to
account for the fact that negative cases are more likely than positive cases:
negative cases are the more likely outcome and it requires more evidence to
persuade us otherwise. But in an application where, for example, we are
scanning for a medical condition, the number of negatives (be it 90% or
99.99999% of the population) should not influence how we decide that a case is
likely to be positive.

Figure 4: Plot of $B(r)$ for our 9 example data sets. The dotted line is at
$1/2$ indicates the value at which the model is balanced.

Neither $r_{b}$ nor $B(r)$ provide a measure of model performance, like $A$
does. Instead they are both measurements around which we can organise a
rigorous evaluation of our model. We will look at how $B(r)$ can be used to
construct such a measure in section 3.4. In this next section, which can be
skipped by readers who just want to know about the performance measure, we
look at some properties of $B(r)$.

###  3.3 Properties and implementation of $B(r)$

As with $A$ the pairwise nature of the test means it is straightforward to
implement a randomised version of $B(r)$. For each value of $r$ we sample,
with or without replacement, $n$ members of the positive class. Then we sample
$n$ members from the set labelled positive when the threshold is greater than
$r$. Pairwise comparison of the scores of these two sets gives $B(r)$ . This
method becomes less reliable for large values of $r$, since the size of the
positive labelled class becomes small and all the comparisons will be made to
a small number of positively labelled images.

Another way to calculate $B(r)$, following the AUC approach to estimating $A$,
is by integration over the true positive rate, $y(r)$, and the false positive
rate, $x(r)$. We now derive the appropriate integral. First, let $S_{R}$ be
the score of a randomly chosen positive member. The probability the members
has a score less than a randomly chosen member of the positive class with a
score greater than $r$ is then written as $P(S_{R}<S_{P}|S_{R}>r)$. It is this
probability we call $B(r)$.

Our approach to finding an expression for $B(r)$ is to look separately at the
case where $S_{R}$ is from a negative member and a positive member. We can use
the law of total probability to give

$\displaystyle B(r)$ $\displaystyle=$ $\displaystyle P(S_{R}<S_{P}|S_{R}>r)$
(9) $\displaystyle=$ $\displaystyle P(S_{R}<S_{P}|S_{R}>r,R=+)\cdot
P(R=+|S_{R}>r)$ $\displaystyle+P(S_{R}<S_{P}|S_{R}>r,R=-)\cdot P(R=-|S_{R}>r)$

where $+$ and $-$ are respectively the events that the chosen individuals are
in the positive and negative classes. If an individual is chosen at random
then

$P(R=+|S_{R}>r)=\frac{Pv(r)}{Nv(r)+Pu(r)}\mbox{ and
}P(R=-|S_{R}>r)=\frac{Nu(r)}{Nv(r)+Pu(r)}$ (10)

Furthermore,

$\displaystyle P(S_{R}<S_{P}|S_{R}>r,R=+)$ $\displaystyle=$
$\displaystyle\frac{P(S_{R}<S_{P}\cap S_{R}>r,R=+)}{P(S_{R}>r,R=+)}$ (11)
$\displaystyle=$
$\displaystyle\frac{\int_{t=r}^{\infty}\int_{s=t}^{\infty}f_{P}(t)f_{P}(s)dt}{\int_{t=r}^{\infty}f_{P}(t)dsdt}$
$\displaystyle=$ $\displaystyle\frac{\int_{t=r}^{\infty}f_{P}(t)v(t)dt}{v(r)}$

Since the derivative of $v(r)$ is equal to $-f_{P}(t)$ we can change variable
to $v$ in the integral in the numerator to get

$\displaystyle\int_{t=r}^{\infty}f_{P}(t)v(t)dt=\int_{t=r}^{\infty}v(t)\left(-v^{\prime}(t)\right)dt=\int_{v(r)}^{\infty}v(t)dv=\frac{v(r)^{2}}{2}$
(12)

and thus simplify to get

$P(S_{R}<S_{P}|S_{R}>r,R=+)=\frac{v(r)}{2}$ (13)

We can follow similar steps for the case that $R$ is negative to get,

$P(S_{R}<S_{P}|S_{R}>r,R=-)=\frac{\int_{t=r}^{\infty}f_{N}(t)u(t)dt}{u(r)}$
(14)

Substituting 10, 13 and 14 in to equation 9 gives

$B(r)=\frac{Pv(r)^{2}/2+N\int_{t=r}^{\infty}f_{N}(t)u(t)dt}{Nv(r)+Pu(r)}$ (15)

This equation is plotted as the black line in figure 4. We see that it goes
towards a maximum when $r\rightarrow-\infty$, taking the value

$B(-\infty)=\frac{P/2+NA}{N+P}$

and decreases to zero as $r$ increases, so that $B(\infty)=0$. The value
$r_{b}$, the solution $B(r_{b})=1/2$, is identified as the point in figure 4
where $B(r)$ crosses the dotted line at $1/2$. This is also the value of
$r_{b}$ plotted as the dotted line in figure 4. We will look in more detail at
the function $B(r)$ in more detail in section 3.6 and compare it to other
measures.

###  3.4 Precision at the indistinguishability threshold

How often is our positive labelling correct when reality and labelling are
indistinguishable? To answer this question, we define $C(r)$ to be the
precision: the probability that an individual with a score greater than $r$ is
in the positive class, i.e. $P(R=+|S_{R}>r)$ , or the probability that a
positive labelling is made correctly. Using Bayes law, we can rewrite
precision in terms of false positive rate and true positive rate.
Specifically,

$\displaystyle C(r)$ $\displaystyle=$ $\displaystyle P(R=+|S_{R}>r)$
$\displaystyle=$
$\displaystyle\frac{P(S_{+}>r|R=+)P(C=+)}{P(S_{+}>r|R=+)P(R=+)+P(S_{-}>r|R=-)P(R=-)}$

In this case, $P(R=+)=P/(P+N)$ is the proportion of individuals in the
positive class and $P(R=-)=N/(P+N)$ is proportion in the negative class.
Substituting $v(r)=P(S_{+}>r|R=+)$ (true positive rate) and
$u(r)=P(S_{-}>r|R=-)$ (false positive rate) gives

$C(r)=\frac{Pv(r)}{Pv(r)+Nu(r)}$ (16)

When $N$ is much larger than $P$ then $v(r)$ has to be significantly larger
than $u(r)$ for precision to have a large value. It is the ratio of true
positives, $v(r)$, to all positives, $v(r)$ and $u(r)$, weighted by the
frequency at which individuals are, respectively, positive and negative.

I propose measuring precision specifically with a value of $r=r_{b}$, i.e. for
a threshold whereby data classified as positive cannot be distinguished from
data which truly is positive, i.e. we calculate $C(r_{b})$. Evaluating this
for the data in figure 2 (a), (d) and (g) we get $C(r_{b})\approx 0.85$. This
could be considered a reasonably good performance: 85% of the pictures the
algorithm says are cats are in fact cats. For figure 2 (b), (e) and (h) we get
$C(r_{b})\approx 0.69$. This is not a great performance, but could be useable
in certain applications: 69% of the pictures the algorithm says are cats are
in fact cats. Finally, for the data in figure 2 5 (c), (f) and (i) we get
$C(r_{b})\approx 0.50$. This is poor performance, and is probably not very
useful in most applications: only 50% of the pictures the algorithm says are
cats are in fact cats.

We can now see why $C(r_{b})$ is preferable measure of performance over $A$.
When we calculated $A$, the value was highly dependent on the number of ‘easy’
cases. This is not the case with $C(r_{b})$. By evaluating precision when the
algorithm cannot distinguish reality from its own labelling, we obtain a
measure of performance that doesn’t depend on the number of ‘easy’ cases. The
choice of $r_{b}$ is theoretically motivated (in the previous section) and
gives reasonable results. In section 3.6 we will compare $C(r_{b})$ to other
known metrics for measuring performance, but before we do this, we look at how
we might be flexible about our choice of $r$.

###  3.5 Tuning false positive and true positive rates

There are two further questions we might ask.

  1. 1.

How often is a member of the positive class detected by the test? This is the
true positive rate, $v(r)$.

  2. 2.

How often is a member of the negative class labelled positive by the test?
This is the false positive rate, $u(r)$.

Typically, one of these rates will be more important than another. For
example, we might, in a medical screening task, accept a higher false positive
rate in order to make sure all those who are positive for a condition are
identified. In this case we set $r$ to be a smaller value so as to get a high
true positive rate, but also (possibly) a high false positive rate. In a
targeted advertising task, where people who might be interested in a product
should be identified, we might concentrate on having a lower false positive
rate and accept a lower true positive rate, identifying only individuals who
are very likely to be interested in the advertised product. In this case we
set $r$ to a larger value. In general, there is no escaping from the fact that
the measure of performance, and thus the choice of $r$, is informed by the
application area.

An alternative here is to set an acceptable range for having a threshold which
does not preserve the property that reality is indistinguishable from
labelling. A rule of thumb is 40/60. If, for example, we want to ensure a high
level of true positives, we find $r_{60}$ by solving $B(r_{60})=0.6$, so that
the probability a member classified as positive has a lower score than a truly
positive member is 60%. This is shown as the dotted lines in figure 5 to the
right of the solid line (at which $B(r_{b})=1/2$). Similarly, we can find
$r_{40}$ by solving $B(r_{40})=0.4$, which is given to the left. Note that,
while $B(r_{60})>B(r_{b})>B(r_{40})$, the thresholds have the relationship
$r_{60}<r_{b}<r_{40}$. A lower threshold leads to more true positives and more
false positives.

Figure 5: Plot of $B(r)$ against the precision $C(r)$ (black line), true
positive rate $v(r)$ (blue) and false positive rate $u(r)$ (red) for our 9
example data sets. These curves are parameterised by $r$.

Figure 5 shows $C(r)$ (black line) plotted against $r$ for our nine test data
sets. Again, the way we built $B(r)$ allows us to explain in words what we are
doing here. We can, for example, write about figure 5(e) that, "accepting a
60/40 imbalance in favour of positives our algorithm’s predictions in favour
of the positive class gave us a precision of $C(r_{60})=0.59$, compared to
$C(r_{b})=0.72$ at 50/50 balanced predictions."

###  3.6 Similarity to F1 score

This section is a few notes about how $B(r)$ relates to some other measures of
performance. To do this, I first break equation $B(r)$ in to two components,

$B(r)=B_{+}(r)+B_{-}(r)$ (17)

such that

$B_{+}(r)=\frac{Pv(r)^{2}/2}{Nv(r)+Pu(r)}=\frac{1}{2}v(r)C(r)$ (18)

and

$B_{-}(r)=\frac{N\int_{t=r}^{\infty}f_{N}(t)u(t)dt}{Nv(r)+Pu(r)}$ (19)

These terms are plotted in figure 6. We now look at these two terms
individually.

Figure 6: Plot of $B(r)$ for our 9 example data sets. The black line is
$B(r)$. The dotted line at $1/2$ indicates the value at which the model is
balanced. The yellow line is the component $B_{+}(r)$ (equation 18) and the
green line is $B_{-}(r)$ (equation 19). The red line is the $F_{1}(r)$ score
(equation 20).

Equation $B_{+}(r)$ is the recall multiplied by the true positive rate,
divided by two. This is related to the the F1-score which is defined as,

$F_{1}(r)=\frac{2C(r)v(r)}{C(r)+v(r)}$ (20)

In figure 6 we see that $F_{1}$ reaches a maximum at roughly the same point as
which $B_{+}(r)$ is maximized. Figure 6 shows that (with the exception of 6 g)
the F1 score reaches a maximum at roughly the same point that $B(r)=1/2$. I
have not derived the exact form of this relationship and it would be
interesting to look at this in more detail, since F1 is seen as a standard
test of model performance.

The measure $B_{-}(r)$ is similar to the integral which gives the area under
the Precision-Recall curve, which is

$\int_{s=-\infty}^{\infty}C(t)f_{N}(t)dt\int_{s=-\infty}^{\infty}\frac{Pv(t)}{Pv(t)+Nu(t)}f_{N}(t)dt$

The difference to $B_{-}(r)$, is that the integral includes the denominator.
The term for $B_{-}(r)$ can also be thought of as a sort of $A(r)$, an AUC for
those values with scores greater than $r$. Again, this needs to be looked at
in more detail.

##  4 Conclusions

The first test in this article, $A$, —how often is a randomly chosen member of
the positive class scored higher than randomly chosen member of the negative
class?—is equivalent to calculating the AUC. In many applications, discerning
between pairs of negative and positive cases might not be the most important
challenge. Clinicians, for example, aren’t usually presented with two people,
one of whom they know is sick and one who is healthy, and asked to find the
sick individual! Emphasising that $A$ answers a specific question about paired
comparison makes its limitation clear: knowing $A$ tells us about paired
comparisons between scores. It does not answer all questions we might have
about the accuracy of our approach.

The second test, $B(r)$, doesn’t, by itself, tell us about algorithm
performance. It instead provides a principled way of deciding on the
threshold, $r_{b}$ such that $B(r_{b})=1/2$, to choose for a decision. We tune
our threshold, so that the set of pictures the algorithm labels as containing
cats is indistinguishable from those which really do contain cats. In addition
to laying the basis for our next test, one potentially useful application of
this idea would be in boosting [7]. If we fit a model first on all images,
then we fit a new model on precisely the images with scores greater than
$r_{b}$ then we may be able to iteratively improve the model fit.

The third test, $C(r_{b})$, is the one I recommend for performance. We look at
how often the positive labelling is correct when reality and labelling by the
algorithm are indistinguishable. All tests of performance have a degree of
arbitrariness, but the advantage of this one is that the threshold for the
model is that the threshold is set on a single principle: that of
indistinguishability. In our examples, this method avoided the limitations of
$A$, where the addition of too many ’easy’ cases inflated the area under the
curve. Test $C(r_{b})$ answers the following question: when the algorithm is
tuned so that it can no longer distinguish labelled cats from real cats, how
often is a randomly chosen member that is labelled positive actually a member
of the positive class? A more technical short hand for this might be,
precision at the indistinguishability threshold.

A valid critique of the method outlined here is that there is no such thing as
a single metric for measuring model performance. This point has been
recognised since Neyman and Pearson’s showed that for tests of statistical
hypotheses there is always a trade-off between two possible error types (false
positives and false negatives) [8, 9]. The necessity of this tradeoff means
that any single metric (including AUC, F1 and precision at the
indistinguishability threshold) cannot claim generality. This limitation has
the potential to lead to problems, especially in medical applications [3],
where costs and benefits should be assigned to the two error types and the
algorithm should be assessed in light of this choice [10, 11].

That said, the development of many machine learning algorithms occurs in a way
that is decoupled from particular applications and, as such, the tradeoffs
between error types has not yet been specified. This article has argued that,
in such situations, precision at the indistinguishability threshold combines
the respective advantages of AUC – that it can be explained simply in words –
and F1– it does not inflate performance for unbalanced data sets – in a single
metric. I would thus encourage researchers to use $C(r_{b}$ instead of just
reporting AUC or F1 in settings where error type trade-offs have yet to be
specified.

##  5 Acknowledgements

Thanks to Daniel Gedon and Andre Teixeira for feedback.

## References

  * [1] A. Lindholm, N. Wahlström, F. Lindsten, and T. B. Schön, Machine Learning - A First Course for Engineers and Scientists.  Cambridge University Press, 2022.
  * [2] E. Fix and J. L. Hodges, “Discriminatory analysis. nonparametric discrimination: Consistency properties,” International Statistical Review/Revue Internationale de Statistique, vol. 57, no. 3, pp. 238–247, 1989\.
  * [3] N. A. Obuchowski and J. A. Bullen, “Receiver operating characteristic (roc) curves: review of methods with applications in diagnostic medicine,” Physics in Medicine & Biology, vol. 63, no. 7, p. 07TR01, 2018.
  * [4] S. Vanderlooy and E. Hüllermeier, “A critical analysis of variants of the auc,” Machine Learning, vol. 72, pp. 247–262, 2008.
  * [5] M. Majnik and Z. Bosnić, “Roc analysis of classifiers in machine learning: A survey,” Intelligent data analysis, vol. 17, no. 3, pp. 531–558, 2013\.
  * [6] Y. Sasaki et al., “The truth of the f-measure,” Teach tutor mater, vol. 1, no. 5, pp. 1–5, 2007.
  * [7] R. E. Schapire, “The boosting approach to machine learning: An overview,” Nonlinear estimation and classification, pp. 149–171, 2003.
  * [8] J. Neyman and E. S. Pearson, “Ix. on the problem of the most efficient tests of statistical hypotheses,” Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, vol. 231, no. 694-706, pp. 289–337, 1933.
  * [9] C. Scott, “Performance measures for neyman–pearson classification,” IEEE Transactions on Information Theory, vol. 53, no. 8, pp. 2852–2863, 2007\.
  * [10] K. Chu, “An introduction to sensitivity, specificity, predictive values and likelihood ratios,” Emergency Medicine, vol. 11, no. 3, pp. 175–181, 1999\.
  * [11] A. Care, F. A. Ramponi, and M. C. Campi, “A new classification algorithm with guaranteed sensitivity and specificity for medical applications,” IEEE Control Systems Letters, vol. 2, no. 3, pp. 393–398, 2018.


# Simple Relationships Between Lozenge Tiling Functions of Related Regions

Daniel Condon

###### Abstract

We give a formula for the number of symmetric tilings of hexagons on the
triangular lattice with unit triangles removed from arbitrary positions along
two non-adjacent non-opposite sides. We show that for certain families of such
regions, the ratios of their numbers of symmetric tilings are given by simple
product formulas. We also prove that for certain weighted regions which arise
when applying Ciucu’s Factorization Theorem, the formulas for the weighted and
unweighted counts of tilings have a simple explicit relationship.

##  1 Introduction

The triangular lattice induces a tiling of the plane with unit equilateral
triangles so that some of the lattice lines are horizontal. A region on the
triangular lattice is a connected bounded union of these
triangles.111Henceforth we will say “triangle” to mean a unit equilateral
triangle on the triangular lattice. We say triangles which share an edge are
adjacent. A lozenge is the union of two adjacent triangles, and a lozenge
tiling222Henceforth we will simply say “tiling” to mean a lozenge tiling. of a
region is a covering of that region with lozenges within that region so that
pairwise the lozenges do not overlap except on their boundaries.

We may associate a weight function to a region which assigns a weight to each
lozenge within that region. This induces a weight on each tiling of the
region, which is the product of the weights of the lozenges in that tiling. We
say a region is unweighted if each lozenge (and therefore each tiling) has
weight 1. A region with no specified weight function is assumed to be
unweighted. We consider the weight function a feature of the region.

Given a region $R$ we let $M(R)$ denote the sum of weights of tilings of $R$;
thus if $R$ is unweighted, $M(R)$ simply counts the tilings of $R$. We use the
letter $M$ because a natural bijection exists between tilings of a region on
the triangular lattice and perfect matchings on a corresponding graph, namely
the region’s planar dual. Kasteleyn’s paper [Ka], and Temperley and Fisher’s
paper [TeFi], are an excellent introduction to matching theory.

Given a family of regions $R_{\bar{x}}$ indexed by parameters $\bar{x}$, the
function $f(\bar{x}):=M(R_{\bar{x}})$ is called the tiling function of that
family. For example, let $H_{a,b,c}$ denote a region which is a semiregular
hexagon, with horizontal sides of length $a$, sides immediately clockwise from
these of length $b$, and sides immediately clockwise from these of length $c$.
Then

$P(a,b,c):=M(H_{a,b,c})=\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c}\frac{i+j+k-1}{i+j+k-2}$
(1)

and we say that $P(a,b,c)$ is the tiling function for semiregular hexagons.
This result is by MacMahon [Ma] who was studying lozenge tilings from the
perspective of plane partitions, hence our use of the letter $P$. Figure 1
depicts an example of a tiling of one such hexagon. The simple elegance of
MacMahon’s formula has inspired a search for other families of regions with
tiling functions given by simple product formulas.

Figure 1: The region $H_{6,4,5}$ and a tiling of that region. Tilings of
semiregular hexagons have a natural bijection with plane partitions, namely
the tilings of $H_{a,b,c}$ depict the plane partitions within a box of
dimension $a\times b\times c$. An appropriate weight function for $H_{a,b,c}$
yields a tiling function that enumerates plane partitions in the box by
volume.

Note that since $H_{a,b,c}$ is congruent to the hexagon with the parameters
$a,b,c$ given in any order, $P(a,b,c)$ is symmetric on its parameters;
nonetheless, being strict about the orientation of our figures will be helpful
as they become more complex. For example, we will restrict our study of
figures which are symmetric across a lattice line to just those which are
symmetric across a horizontal lattice line, and we will say these are
horizontally symmetric. Similarly, we will study figures that are symmetric
across a vertical line, calling these vertically symmetric. When $R$ is a
region with at least one of these symmetries, we will let $M_{-}(R)$ give the
weighted count of horizontally symmetric tilings of $R$, and $M_{|}(R)$ denote
the weighted count of vertically symmetric tilings of $R$. Since $H_{a,b,b}$
is both horizontally and vertically symmetric, we will denote:

$\displaystyle P_{-}(a,b):=M_{-}(H_{2a,b,b})=$
$\displaystyle\binom{2a+b}{b}\prod_{1\leq i<j\leq b}\dfrac{2a+i+j}{i+j}$ (2)
$\displaystyle P_{|}(a,b):=M_{|}(H_{2a,b,b})=$
$\displaystyle\dfrac{(a+1)_{b-1}}{(2a+1)_{b-1}}\prod_{1\leq i\leq j\leq
b-1}\dfrac{2a+i+j-1}{i+j-1}.$ (3)

The formula for $P_{-}(a,b)$ was proven independently in various forms by
Andrews [An78], Gordon [Go83], Macdonald [MD], and Proctor [Pr84]. The formula
for $P_{|}(a,b)$ is due to Proctor [Pr88]. Notably,

$P_{-}(a,b)\cdot P_{|}(a,b)=P(a,b,b),$

an observation by Ciucu, who noticed the relationship after these three
formulas were known. So far there is no known bijective proof of this fact.

Recently a new type of result has gained prominence; identifying simple
relationships between tiling functions which themselves might not have a known
simple expression. This paper will explore relationships such as these.
Descriptions of the regions we will discuss follow.

We use $H_{a,b,c,t}$ to denote the equiangular hexagon(al region) with side
lengths $a,b+t,c,a+t,b,c+t$ clockwise starting from the northern side. For
$(u_{i})_{1}^{m},(v_{j})_{1}^{n}$ integer vectors with $1\leq
u_{i}<u_{i+1}\leq b+t$ and $1\leq v_{i}<v_{i+1}\leq c+t$, we use
$H_{a,b,c,t,(u_{i})_{1}^{m},(v_{j})_{1}^{n}}$ to denote the region obtained by
modifying $H_{a,b,c,t}$ as follows: remove each $u_{i}$th unit triangle along
the northeast border, counting those triangles which share an edge with the
border and starting from the north; remove also each $v_{j}$th unit triangle
along the northwest border, counting those triangles which share an edge with
the border and starting from the north. We call regions of this kind dented
hexagons, and an example of such a region is given in the top left of Figure
2. We discuss these regions at length in [Co]. Regions constructed by removing
dents from hexagons have been studied before. In [Ei] Eisenkölbl gave a tiling
function for a region constructed from $H_{a,b,c,1}$ by removing a dent from
each of three alternating sides, and in [Ci96] Ciucu and Fischer give a tiling
function for hexagons with dents removed in arbitrary positions along the
border, presented as the Pfaffian of a matrix. In [Gi] Gilmore gives a tiling
function for regions with dents removed from arbitrary positions along the
border and within the interior.

$H_{4,3,3,4,(3,5),(3,5)}$

$V_{2,3,2,(3,5)}$

$V^{+}_{2,3,2,(3,5)}$

$\overline{V}^{+}_{2,3,2,(3,5)}$

Figure 2: The vertically symmetric dented hexagon $H_{4,3,3,4,(3,5),(3,5)}$,
with its axis of symmetry depicted, and its various subregions: $V$, $V^{+}$,
and $\overline{V}^{+}$. The ovals in the depiction of $\overline{V}^{+}$
represent that the lozenges they cover have weight 1/2. In each of these
regions, $\underline{u}_{1}=3$ and $\underline{u}_{2}=2$.

Consider a vertically symmetric dented hexagon
$H:=H_{2a,b,b,2t,(u_{i})_{1}^{n},(u_{i})_{1}^{n}}$. We use
$V_{a,b,t,(u_{i})_{1}^{n}}$ to denote the region consisting of triangles
within $H$ with interiors strictly west of its vertical axis of symmetry. We
use the letter $V$ because tilings of this region exactly correspond to the
vertically symmetric tilings of $H$. We call these dented half-hexagons.
Similarly, we will use $V^{+}_{a,b,t,(u_{i})_{1}^{n}}$ to denote the region
consisting of triangles within $H$ with interiors weakly west of its vertical
axis of symmetry; note $V^{+}$ is congruent to the complementary subregion of
$V$ within $H$. We will also use $\overline{V}^{+}_{a,b,t,(u_{i})_{1}^{n}}$ to
denote this region with a special weighting of lozenges: those
vertical333Meaning vertically symmetric. lozenges on the symmetry axis of $H$
are assigned weight 1/2. We will also use an overline to denote an analogous
weighting scheme for other regions. An example of these three regions appears
in Figure 2.

A useful statistic of these regions is the distance from a dent to the corner
of the hexagon beneath it minus the number of other dents between that dent
and that corner: for the dent indexed by $u_{i}$, this statistic is
$\underline{u_{i}}:=b+n+i-u_{i}$.

$R$

$T(3,4)$ and $T(3.5,4)$

$R_{z}(3)$

$\overline{R}_{z}(3.5)$

Figure 3: Top Left: a region $R$ depicted within its symmetrization. Its
eastern boundary is the same shape as the western boundary of a tube of height
4. Top Right: two tubes of height 4. Bottom: tubey regions constructed from
$R$, where $z$ is the eastern boundary of $R$. Note that these constructions
are not unique.

For $a\in\mathbb{N}/2$ and $h\in\mathbb{Z}$, Let $T(a,h)$ denote the region of
triangles within the rectangle consisting of line segments of horizontal
lattice lines which are $a+1/2$ units long, and vertical line segments which
are $h\sqrt{3}$ units long,444Since adjacent parallel lattice lines are
$\frac{\sqrt{3}}{2}$ units apart, this rectangle is $2h$ times the height of a
triangle. so that the top left corner of the rectangle is in the middle of the
base of a triangle. We call this the tube of length $a$ and height $h$. Two
tubes are depicted in the top right of Figure 3.

Consider a set of tubes $\mathcal{T}=\\{T(a,h):a\in\mathbb{N}\\}$ which share
a fixed western boundary which is denoted $z$. Let $R$ be a region with a
fixed relative position to $z$ so that $R$ does not intersect any tube in
$\mathcal{T}$ except along $z$. Then we say $R_{z}(0):=R$ and $R_{z}(a)$ is
the union of $R$ and the tube $T(a,h)\in\mathcal{T}$. We call a region (or
family of regions) which is constructed in this way tubey. Two examples are
depicted in the bottom of Figure 3.

It is natural to describe a tubey region in terms of $R$ and $z$. For example,
$\\{V_{a,b,n,(u_{i})_{1}^{n}}:a\in\mathbb{N}\\}$ is $R_{z}(a)$, and
$\\{V^{+}_{a,b,n,(u_{i})_{1}^{n}}:a\in\mathbb{N}\\}$ is $R_{z}(a+1/2)$, where
$R$ is $V_{0,b,n,(u_{i})_{1}^{n}}$ and $z$ is the eastern boundary of $R$
extended by two edges. Tubey families thus generalize families of dented half-
hexagons, and are characterized by “stretching.” When $a$ is sufficiently
large that the tube extends east of $R$, the tubey regions $R_{z}(a)$ and
$R_{z}(a+1/2)$ are congruent to complementary halves of a vertically symmetric
region.

We will discuss tubey regions with an unusual weighting. We use the notation
$\overline{R}_{z}(a)$ to denote the tubey region $R_{z}(a)$ where the vertical
lozenges along555“Along” here meaning sharing two edges with. the eastern
boundary of the tube are assigned weight $\frac{1}{2}$. Observe this notation
is consistent with the notation for the weighted region
$\overline{V}^{+}_{a,b,n,(u_{i})_{1}^{n}}$ interpreted as a tubey region. This
weighting scheme is natural for certain symmetrizable regions which arise when
applying Ciucu’s Factorization Theorem, which we discuss in Section 2.

The results of this paper yield simple product formulas for the ratios of the
tiling functions of $V_{a,b,n,(u_{i})_{1}^{n}}$ and
$V_{0,b,n,(u_{i})_{1}^{n}}$, as well as $V^{+}_{a,b,n,(u_{i})_{1}^{n}}$ and
$V^{+}_{0,b,n,(u_{i})_{1}^{n}}$. This is the second paper by this author and
one of many in the field which identify simple relationships between related
tiling functions which may not themselves be simple. Similar results have been
given by Lai, Ciucu, Rohatgi, and Byun [By19], [Ci19a], [Ci19b], [La19a],
[La19b], [La19c]. In fact, in [La21], Lai independently studies dented
hexagons and dented half-hexagons with some equivalent or more general results
to this paper, and in [Fu] Fulmek gives alternative proofs of some of these.
This paper gives alternative proofs of those results, and also gives a new
type of result which expresses a close relationship between the tiling
functions of certain weighted tubey regions which arise when applying Ciucu’s
Factorization Theorem and their unweighted counterparts. A similar
relationship was observed in [Ci13], see Theorem 15 of this paper and the note
that follows.

##  2 Further Background

In this section we discuss some of the ideas and techniques from this area
that will be useful in the sections ahead.

The partition of the region’s triangles into those which are up-pointing and
those which are down-pointing corresponds to a proper 2-coloring of the
region’s planar dual graph; thus, borrowing notions from matching theory on
bipartite graphs, we say a region is balanced if it contains the same number
of up-pointing and down-pointing triangles. An unbalanced region has no
tilings.

For some regions, every possible tiling of that region includes a particular
lozenge. For example, if a triangle in a region is adjacent to only one other
triangle then all tilings of that region must include the lozenge covering
those two triangles. Given a region $R$ with a forced lozenge $l$, if one
constructs $R^{\prime}$ by removing from $R$ the triangles covered by $l$,
then the tilings of $R$ and $R^{\prime}$ are in a natural bijection (tilings
of $R$ restrict to tilings of $R^{\prime}$ by the exclusion of $l$). Then if
$\operatorname{wt}(l)$ denotes the weight of lozenge $l$,
$M(R)=\operatorname{wt}(l)M(R^{\prime}).$ Thus when we wish to study $R$ it
will sometimes behoove us to study $R^{\prime}$ instead, especially when
$\operatorname{wt}(l)=1.$

The lozenge tilings of a region are in bijection with families of
nonintersecting paths on a subgraph of the north-east directed square lattice.
The particular subgraph depends on the region (but is essentially shaped like
the region), and the paths start at the subgraph’s sources and end at its
sinks.

Given a lozenge tiling of a region, we mark the middle of the east edge of
each up-pointing triangle with a dot; we decorate each lozenge which has dots
on its boundary by drawing a line connecting these dots. An appropriate linear
transformation of this image moves the dots to vertices on the square lattice,
so that the lines decorating certain lozenges form north-east paths starting
from the region’s southwest boundaries and ending at the region’s northeast
boundaries. Figure 4 depicts this transformation. The other possible tilings
of the region correspond to the other nonintersecting families of lattice
paths on the subgraph of the north-east directed square lattice which lies
within the distorted region. Using this bijection to enumerate lozenge tilings
is a standard technique, and is explained in greater detail in Sections 4 and
5 of [Ci01].

Figure 4: Left: a lozenge tiling of a region is decorated. Right: that image
is linearly transformed so that its decorations depict a nonintersecting
family of paths on a particular subgraph of the north-east directed square
lattice.

A signed count of families of nonintersecting lattice paths on an acyclic
digraph from $n$ indexed sources to $n$ indexed sinks is given by the
determinant of an $n\times n$ matrix, where the $(i,j)$th entry is the number
of paths from the $i$th source to the $j$th sink. We henceforth refer to this
as the path matrix of a region. This result has been discovered independently
at least three times. A version was published in 1959 by Karlin and McGregor
((B) from [Ka]) who were studying the paths of multiple particles through
certain discrete Markov processes, so that the particles never coincided in a
state. In 1973 Lindström published the result, as described above, in [Li].
The result again appeared in a paper in 1985 [Ge85] by Gessel and Viennot, and
again in a 1989 preprint [Ge89], in the context that the digraph is a portion
of the north-east directed square lattice, so that the $(i,j)$th entry of the
path matrix is a simple binomial. For Gessel and Viennot (as for us) the sign
of each nonintersecting family can be assumed to be positive, so that the
determinant of the matrix gives the total number of such families.

In one case where we apply this result, the path matrix is naturally the
product of two other path matrices. In this case, we will apply the Cauchy-
Binet formula (Theorem 4.15 in Section 4.6 of [Br]). This method has also been
used by Ciucu. [Ci21]

######  Theorem 1 (The Cauchy Binet formula).

Let A be an $m\times n$ matrix and B an $n\times m$ matrix. For $S,T$ sets of
integers, let $X_{S,T}$ denote the minor of matrix $X$ consisting of its rows
indexed by $S$ and columns indexed by $T$. Then

$\det(AB)=\sum_{S\in\binom{[n]}{m}}\det(A_{[m],S})\det(B_{S,[m]}).$

We will also apply the following results by Kuo, which are slight variations
on Theorems 2.4 and 2.5 from [Ku04]. These results were later given in much
greater generality by Yan, Yeh, and Zhang [Ya].

######  Lemma 2.

Let $R$ be a simply connected region of the triangular lattice, and let
$\alpha,\beta,\gamma,\delta$ be triangles in $R$ of the same orientation which
touch the boundary of $R$ at a corner or edge, so that the places they touch
the boundary appear in the cyclic order $\alpha,\beta,\gamma,\delta$. Then

$\displaystyle M(R-\alpha-\beta)\cdot M(R-\gamma-\delta)$ $\displaystyle=$
$\displaystyle M(R-\alpha-\delta)\cdot
M(R-\beta-\gamma)-M(R-\alpha-\gamma)\cdot M(R-\beta-\delta)$ (4)

and

$\displaystyle M(R-\alpha)\cdot M(R-\beta-\gamma-\delta)+M(R-\gamma)\cdot
M(R-\alpha-\beta-\delta)$ $\displaystyle=$ $\displaystyle M(R-\beta)\cdot
M(R-\alpha-\gamma-\delta)+M(R-\delta)\cdot M(R-\alpha-\beta-\gamma).$ (5)

The following is a generalization of the Graph Splitting Lemma, which appears
as Lemma 2.1 in a 2014 paper by Ciucu and Lai [Ci14], and is implicit in
earlier work by Ciucu [Ci97]. This more general result is also implicit in
earlier work. The proof given here generalizes the proof from the 2014 paper.

######  Lemma 3.

Let $G=(V,E)$ be a connected balanced bipartite finite graph, with a proper
coloring of vertices either black or white. Let
$G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$ be disjoint induced subgraphs of $G$
so that $V=V_{1}\sqcup V_{2}$, and $E=E_{1}\sqcup E_{2}\sqcup E_{3}$. Suppose
that all vertices in $V_{1}$ which are incident to an edge in $E_{3}$ are
colored black, and let $n$ denote the number of black vertices in $V_{1}$
minus the number of white vertices in $V_{1}$. Then all perfect matchings of
$G$ include $n$ edges from $E_{3}$; in particular if $n<0$ then $M(G)=0$, if
$n>|E_{3}|$ then $M(G)=0$, and if $n=0$ then $M(G)=M(G_{1})\cdot M(G_{2})$.

###### Proof.

Let $G,G_{1},G_{2},E_{3},$ and $n$ be as defined above. We remark that all
vertices in $G_{2}$ incident to an edge in $E_{3}$ must be white, and there
must be $n$ more white vertices than black vertices in $G_{2}$. Let
$\mu\subset E$ be a perfect matching of $M$.

Suppose $n<0$. Each white vertex in $V_{1}$ must be matched to a black vertex
in $V_{1}$. Since there are fewer black vertices than white vertices in
$V_{1}$, no such matching $\mu$ exists.

Suppose instead $n\geq 0$. Then each white vertex in $V_{1}$ must be matched
to a black vertex in $V_{1}$, leaving the other $n$ black vertices in $V_{1}$
which are matched to white vertices in $V_{2}$; thus exactly $n$ edges are in
$\mu\cap E_{3}$. Therefore if $n>|E_{3}|$, no such matching $\mu$ exists.

In the case where $n=0$, $\mu$ must induce a perfect matching on each of
$G_{1}$ and $G_{2}$, and similarly any pair of perfect matchings $\mu_{1}$ on
$G_{1}$ and $\mu_{2}$ on $G_{2}$ together form a matching on $G$, so the
perfect matchings on $G$ and the pairs of perfect matchings on $G_{1},G_{2}$
are in bijection.

∎

We apply this to a specific type of partition of regions on the triangular
lattice:

######  Corollary 4 (Region Splitting Lemma).

Let $R$ be a balanced region of the triangular lattice, and $L$ a lattice line
passing through $R$, so that $P$ and $Q$ are the subregions of $R$ on each
side of the lattice line. Suppose the triangles in $P$ along $L$ are all up-
pointing, and let $n$ denote the number of up-pointing triangles in $P$ minus
the number of down-pointing triangles in $P$. Then all tilings of $R$ have
exactly $n$ lozenges which cross $L$. In particular, if $n<0$ then $R$ is
untileable, if fewer than $n$ lozenges cross $L$ then $R$ is untileable, and
if $n=0$ then $M(R)=M(P)\cdot M(Q).$

The following theorem is a special case of the Factorization Theorem by Ciucu
[Ci97], expressed in the language and context of this paper.

######  Theorem 5 (Factorization Theorem (Ciucu)).

Let $R$ be a balanced vertically symmetric region with symmetry axis $L$.
Label the triangles within $R$ on $L$ from top to bottom,
$a_{1},b_{1},...,a_{k},b_{k}$. Let $R^{-}$ denote the subregion of $R$
consisting of triangles strictly west of $L$, along with triangles labeled
$a_{i}$ which are down-pointing, and those labeled $b_{i}$ which are up-
pointing. Let $R^{+}$ denote the subregion of $R$ complementary to $R^{-}$.
Say the weight functions for $R^{-}$ and $R^{+}$ are the restrictions of the
weight function of $R$ to those regions, but with the weights of any vertical
lozenges on $L$ cut in half. Then

$M(R)=2^{k}M(R^{-})M(R^{+}).$

For example when Theorem 5 is applied to
$H_{a,b,b,2n,(u_{i})_{1}^{n},(u_{i})_{1}^{n}}$, $R^{-}$ is
$V_{a,b,n,(u_{i})_{1}^{n}}$ and $R^{+}$ is congruent to
$\overline{V}^{+}_{a,b+1,n,(u_{i}+1)_{1}^{n}}$.

The author proved in [Co] the following results for dented hexagons.

######  Theorem 6.

Let a balanced dented hexagon $H_{a,b,c,t,\vec{u},\vec{v}}$ be given. Let
$L_{N}$ be the Nth horizontal lattice line south of the northern
side666$L_{N}$ is then $\frac{\sqrt{3}}{2}N$ units south of the northern side
of $H_{a,b,c,t,\vec{u},\vec{v}}$. of $H_{a,b,c,t,\vec{u},\vec{v}}$, and
$\mu_{N}$ be the number of dents north of $L_{N}$. Then $H$ has a tiling iff
$\mu_{N}\leq N$ for all $N\in\mathbb{N}$.

######  Theorem 7.

For $H_{a,b,c,m+n,(u_{i})_{1}^{m},(v_{j})_{1}^{n}}$ a dented hexagon,

$\displaystyle{M(H_{a,b,c,m+n,(u_{i})_{1}^{m},(v_{j})_{1}^{n}})}$
$\displaystyle={M(H_{0,b,c,m+n,(u_{i})_{1}^{m},(v_{j})_{1}^{n}})}\prod_{i=1}^{m}(u_{i})_{\underline{u_{i}}}\prod_{j=1}^{n}(v_{j})_{\underline{v_{j}}}$
$\displaystyle\times\frac{P({a,b+n,c+m})}{\prod_{i=1}^{m}(a+u_{i})_{\underline{u_{i}}}\prod_{j=1}^{n}(a+v_{j})_{\underline{v_{j}}}}.$

This is equivalent to the following:

######  Corollary 8.

For $H_{a,b,c,m+n,(u_{i})_{1}^{m},(v_{j})_{1}^{n}}$ a dented hexagon, there
exists some $k:=k(b,c,(u_{i})_{1}^{m},(v_{j})_{1}^{n})$ independent of $a$ so
that

$M(H_{a,b,c,m+n,(u_{i})_{1}^{m},(v_{j})_{1}^{n}})=k\cdot\frac{P({a,b+n,c+m})}{\prod_{i=1}^{m}(a+u_{i})_{\underline{u_{i}}}\prod_{j=1}^{n}(a+v_{j})_{\underline{v_{j}}}}.$

##  3 Main Results

In this section we describe the main results of this paper, and where proofs
can be found. The following results about tileability can be found in Section
4.

######  Proposition 9.

The dented hexagon $H_{a,b,b,2n,(u_{i})_{1}^{n},(u_{i})_{1}^{n}}$ has
vertically symmetric tilings iff $a$ is even and $2i\leq u_{i}$ for all
$i\in[n]$.

######  Corollary 10.

The region $V_{a,b,n,(u_{i})_{1}^{n}}$ is tileable iff $2i\leq u_{i}$ for all
$i\in[n]$.

######  Corollary 11.

Consider the dented half-hexagons $V_{a,b,n,(u_{i})_{1}^{n}}$ and
$V_{a^{\prime},b^{\prime},n,(u^{\prime}_{i})_{1}^{n}}$ with $u_{i}\leq
u_{i}^{\prime}$ for all $i\in[n]$. If $V_{a,b,n,(u_{i})_{1}^{n}}$ is tileable,
then so is $V_{a^{\prime},b^{\prime},n,(u^{\prime}_{i})_{1}^{n}}$.

Next, we give the tiling function for a dented half hexagon, with proof in
Section 5. We use $f_{b,n,(u_{i})_{1}^{n}}(a)$ to denote the tiling function
for the family of dented half-hexagons $\\{V_{a,b,n,(u_{i})_{1}^{n}}\ |\
a\in\mathbb{N}\\}$.

######  Theorem 12.

For $V_{a,b,n,(u_{i})_{1}^{n}}$ a dented half-hexagon,
$f_{b,n,(u_{i})_{1}^{n}}(a)$ is a polynomial in $a$, satisfying

$f_{b,n,(u_{i})_{1}^{n}}(a)=f_{b,n,(u_{i})_{1}^{n}}(0)\cdot\prod_{i=1}^{n}(u_{i})_{\underline{u_{i}}}\cdot\dfrac{P_{|}(a,b+n)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}.$
(6)

Lastly, in Section 6, we prove the following results regarding a relationship
between the tiling functions of symmetrizable regions and their complements in
the symmetrization. We use $f^{+}_{b,n,(u_{i})_{1}^{n}}(a)$ to denote the
tiling function for the family $\\{V^{+}_{a,b,n,(u_{i})_{1}^{n}}\ |\
a\in\mathbb{N}\\}$, and $\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)$ to denote
the tiling function for the weighted family
$\\{\overline{V}^{+}_{a,b,n,(u_{i})_{1}^{n}}\ |\ a\in\mathbb{N}\\}$. We will
show

######  Corollary 13.

For $V_{a,b,n,(u_{i})_{1}^{n}}$ a dented half-hexagon,
$f^{+}_{b,n,(u_{i})_{1}^{n}}(a)$ is a polynomial in $a$, satisfying

$\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)=\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(0)\cdot\prod_{i=1}^{n}(u_{i})_{\underline{u_{i}}}\cdot\dfrac{P_{-}(a,b+n)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}.$
(7)

As $f^{+}$ and $\overline{f}^{+}$ are polynomials in $a$, they can be
evaluated for real values of $a$ which are not integers. Theorem 14 is to be
understood in that context.

######  Theorem 14.

For $V_{a,b,n,(u_{i})_{1}^{n}}$ a dented half-hexagon,

$\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)=f^{+}_{b,n,(u_{i})_{1}^{n}}(a-1/2).$

Remarkably, Theorem 14 holds in much greater generality, as expressed in
Theorem 15.

######  Theorem 15.

Given a family of tileable tubey regions $R_{z}(a)$, let $g(a)$ be the tiling
function for $\\{R_{z}(a+1/2):a\in\mathbb{N}\\}$, and $\overline{g}(a)$ be the
tiling function of $\\{\overline{R}_{z}(a+1/2):a\in\mathbb{N}\\}$. Then both
$g(a)$ and $\overline{g}(a)$ are polynomials in $a$ and

$\overline{g}(a)=g(a-1/2).$

A similar phenomenon was observed by Ciucu and Fischer, see Remark 1 at the
end of Section 2 of [Ci13].

##  4 Proof of Tileability Results

In this section we show that vertically symmetric regions are tileable iff
they have tilings which are themselves vertically symmetric. In particular,
tileability conditions for dented half-hexagons are equivalent to tileability
conditions for dented hexagons.

######  Lemma 16.

Let $R$ be a vertically symmetric region with symmetry axis $L$, whose
subregion of triangles on $L$ is also a tileable region. Then $R$ has a tiling
iff it has a vertically symmetric tiling.

###### Proof.

It suffices to show that if $R$ has a tiling it must also have a vertically
symmetric tiling. We proceed using the notation of Theorem 5.

Since $R$ has a tiling, $M(R)$ is nonzero, and so $M(R^{-})$ and $M(R^{+})$
must both be nonzero, by Theorem 5.

Since the subregion of triangles on $L$ is tileable, it must be the union of
interior-disjoint vertical lozenges on $L$: then each $a_{i}$ is up-pointing,
each $b_{i}$ is down-pointing, and $R^{-}$ contains no triangles on $L$.

Let $\mu$ be any tiling on $R^{-}$, and let $\mu^{\prime}$ be its reflection
across $L$ (interpreted as a tiling of the subregion of triangles strictly
east of $L$). Let $\nu$ be the tiling of the subregion of triangles on $L$.
Then $\mu\cup\mu^{\prime}\cup\nu$ is a tiling of $R$ which is symmetric across
$L$.

∎

We are now ready to prove Proposition 9.

###### Proof of Proposition 9.

Let $H:=H_{a,b,b,2n,(u_{i})_{1}^{n},(u_{i})_{1}^{n}}$ be a dented hexagon.
Then $H$ is symmetric across a vertical axis $L$, as displayed in the Figure
5.

Figure 5: Left: a vertically symmetric dented hexagon with $a$ odd. Right: a
vertically symmetric dented hexagon with $a$ even, and the outline of $R^{-}$
drawn thickly, and the weighted lozenges of $R^{+}$ shaded. Both figures’
symmetry axes are depicted as a dashed line.

The vertices along the northern side of $H$ are down-pointing. In the case
that $a$ is odd the top triangle on $L$ is down-pointing, and is only adjacent
to triangles strictly left or right of $L$: this triangle cannot be matched to
either in a vertically symmetric tiling. Then $H$ has no vertically symmetric
tilings.

In the case that $a$ is even, $H$ satisfies the conditions in Lemma 16 and
thus has a symmetric tiling iff it has a tiling. By Theorem 6, this occurs if
each $N$th lattice line south of $H$’s northern side has at most $N$ dents
lying north of it. This is equivalent to the condition $2i\leq u_{i}$ for each
$i\in[n]$.

∎

We are now ready to prove Corollaries 10 and 11.

###### Proof of Corollary 10.

It suffices to show that perfect matchings of $V_{a,b,n,(u_{i})_{1}^{n}}$ are
in bijection with vertically symmetric perfect matchings of
$H_{a,b,b,2n,(u_{i})_{1}^{n},(u_{i})_{1}^{n}}$.

In any vertically symmetric perfect matching of a dented hexagon, triangles on
the axis of symmetry must be covered by vertical lozenges. So the tiling of
$H_{a,b,b,2n,(u_{i})_{1}^{n},(u_{i})_{1}^{n}}$ is uniquely determined by the
tiling of its subregion strictly left of the axis of symmetry; this region is
$V_{a,b,n,(u_{i})_{1}^{n}}$.

∎

###### Proof of Corollary 11.

Since $V_{a,b,n,(u_{i})_{1}^{n}}$ is tileable, $2i\leq u_{i}\leq
u_{i}^{\prime}$ for each $u_{i}^{\prime}$.

∎

##  5 Proof of Theorem 12

Our Theorem 12 has been proven independently by Lai in [La21] and Fulmek in
[Fu], in fact in more generality, but we give an alternate proof in this
section for completeness.

######  Lemma 17.

Where $V_{a,b,n,(u_{i})_{1}^{n}}$ is a tileable dented half-hexagon,
$f_{b,n,(u_{i})_{1}^{n}}(a)$ is a polynomial in $a$.

###### Proof.

Per the transformation discussed briefly at the beginning of section 2, the
tilings of $V_{a,b,n,(u_{i})_{1}^{n}}$ are in bijection with nonintersecting
lattice paths on a subgraph of the north-east directed square lattice. As
depicted in Figure 6, the sources of that digraph can be said to have
coordinates $\\{(i-1,b-i):i\in[b]\\}$ and $\\{(0,2b+2n-u_{i}):i\in[n]\\}$, in
which case the sinks have coordinates $\\{(a+b+n-j,2j-2):j\in[b+n]\\}$. The
entries in the path matrix are then of either form:

$\binom{a+n+j-1}{2j-2-b+i}\quad\mbox{ or
}\quad\binom{a-b-n-2+j+u_{i}}{2j-2-2b-2n+u_{i}}.$ (8)

So, treating $a$ as an indeterminate each entry in the path matrix is a
polynomial on $a$ of degree $2j-2-b+i$ or $2j-2-2b-2n+u_{i}$, or is
identically zero. The determinant of the path matrix is thus a signed sum over
products of polynomials on $a$, and is therefore a polynomial on $a$.

∎

(0,0)

(0,0)$b-1$$b+2n$$b-1$$a+n$

Figure 6: Left: A dented half-hexagon with the east-northeast square lattice
superimposed. We are interested in paths on the directed subgraph of the
lattice that lies within the region; sources for this graph are depicted as
black circles, and sinks are shown as white circles. Right: We take a linear
transformation of the left image so that lattice lines lie vertically and
horizontally. We choose Cartesian coordinates for the points where lattice
lines intersect, so that the intersection in the bottom left corner of the
picture has coordinates $(0,0)$ and points in the dented hexagon have
nonnegative coordinates. Sources lie along the southwest side of the region at
coordinates $\\{(i-1,b-i):i\in[b]\\}$ and along dents at coordinates
$\\{(0,2b+2n-u_{i}:i\in[n]\\}$. Sinks lie at coordinates
$\\{(a+b+n-j,2j-2):j\in[b+n]\\}$.

We denote the normalization777A normalization in the sense that it differs
from the actual tiling function by a factor independent of $a$, but is simpler
to express. of the proposed tiling function for dented half-hexagons

$F_{b,n,(u_{i})_{1}^{n}}(a):=\dfrac{P_{|}(a,b+n)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}.$

We will proceed using the nonstandard notation $\equiv$ $a$ to denote
proportionality between rational functions which are polynomials in $a$. That
is, for $g_{1},g_{2}$ two rational functions (possibly of several variables)
which are polynomials in $a$, we will write

$g_{1}\ \hbox to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ g_{2}$

to mean there exists some (not identically zero) $c$ independent of $a$ so
that

$g_{1}=c\cdot g_{2}.$

It is easy to check $\equiv$ $a$ is an equivalence relation of rational
functions which are polynomials in $a$, satisfying the following properties
where $p_{1},p_{2},$ and $q$ are polynomials in $a$, and $q$ is not
identically zero.

$\displaystyle p_{1}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ p_{2}(a)$
$\displaystyle\Rightarrow p_{1}(a)+p_{2}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ p_{1}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ p_{2}(a)$ (9)
$\displaystyle p_{1}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ p_{2}(a)$
$\displaystyle\iff p_{1}(a)q(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ p_{2}(a)q(a)$ (10)

The method of our proof is to show that

$F_{b,n,(u_{i})_{1}^{n}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
f_{b,n,(u_{i})_{1}^{n}}(a).$ (11)

We will do this by induction, and we start by stating a lemma that will be
important to the inductive step. A dented half-hexagon with $u_{1}=2$
(respectively $u_{n}=b+2n$) has forced lozenges covering the entire region
weakly north of that dent (respectively along its southwest side) which when
removed leave dented half-hexagons with different parameters, as depicted in
Figure 7.

Figure 7: Each image depicts the region $V_{a,b,n,(u_{i})_{1}^{n}}$ with some
of its forced lozenges shaded gray. Left: a dented half-hexagon with $u_{1}=2$
has forced lozenges weakly north of that dent; removing these leaves the
region $V_{a+1,b,n-1,(u_{i}-2)_{2}^{n}}$. Right: a dented half-hexagon with
$u_{n}=b+2n$ has forced lozenges along the southwestern side of the region;
removing these leaves the region $V_{a,b+1,n-1,(u_{i})_{1}^{n-1}}$.

######  Lemma 18.

  1. 1.

Where $V_{a,b,n,(u_{i})_{1}^{n}}$ is a tileable dented half-hexagon, and
$u_{1}=2$,

$F_{b,n,(u_{i})_{1}^{n}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
F_{b,n-1,(u_{i}-2)_{2}^{n}}(a+1),$
$f_{b,n,(u_{i})_{1}^{n}}(a)=f_{b,n-1,(u_{i}-2)_{2}^{n}}(a+1).$

  2. 2.

Where $V_{a,b,n,(u_{i})_{1}^{n}}$ is a tileable dented half-hexagon, and
$u_{n}=b+2n$,

$F_{b,n,(u_{i})_{1}^{n}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
F_{b+1,n-1,(u_{i})_{1}^{n-1}}(a),$
$f_{b,n,(u_{i})_{1}^{n}}(a)=f_{b+1,n-1,(u_{i})_{1}^{n-1}}(a).$

###### Proof.

Both statements regarding $f$ follow from the removal of forced lozenges as
depicted in Figure 7. Both statements regarding $F$ are straightforward to
check from the definition of $F$.

∎

We now show that Theorem 12 holds for dented half-hexagons with at most one
dent. This will serve as a base case when we show relation 11 holds in
general. We let $\vec{\emptyset}$ denote the empty vector.

######  Lemma 19.

For $V_{a,b,n,\vec{u}}$ a tileable dented half-hexagon with
$\vec{u}=\vec{\emptyset}$ and $n=0$, or $\vec{u}=(u)$ and $n=1$, relation 11
holds.

###### Proof.

We first address some specific cases.

  * •

The region has no dents: in this case,

$f_{b,0,\vec{\emptyset}}(a)=M(V_{a,b,0,\vec{\emptyset}})=P_{|}(a,b)=F_{b,0,\vec{\emptyset}}(a).$

  * •

$u=2$; then there are forced lozenges at the top of the region, and

$f_{b,1,(2)}(a)=f_{b,0,\vec{\emptyset}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
F_{b,0,\vec{\emptyset}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ F_{b,1,(2)}(a)$

by reference to the case with no dents and Lemma 18.1.

  * •

$u=b+2$; then there are lozenges along the southwest boundary of the region,
and

$f_{b,1,(b+2)}(a)=f_{b+1,0,\vec{\emptyset}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
F_{b+1,0,\vec{\emptyset}}\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ F_{b,1,(b+2)}$

by reference to the case with no dents and Lemma 18.2.

  * •

$b=0$; then the region is only tileable if $u=2$; in this case the region has
one tiling, and $F_{0,1,(u)}(a)=1$ also.

  * •

$b=1$; then either $u=2$ or $u=3=b+2$, both cases of which are addressed
earlier.

With these cases addressed, we proceed to discuss regions with one dent,
$b\geq 2$, and $2<u<b+2$. We proceed by induction on $u$, using the cases
addressed above as base cases.

Assume that relation 11 holds for dented half-hexagons $V_{a,b,1,(v)}$ with
$v<u$, and consider a tileable family of dented half-hexagons
$\\{V_{a,b,1,(u)}:a\in\mathbb{Z}\\}.$

Regard $V_{a,b,1,(u)}$ as a subregion of the (unbalanced) region
$R:=V_{a,b,1,\vec{\emptyset}}$. With each region $R$ say: $\alpha$ denotes the
$u$th triangle from the top lying along the northwest side; $\beta$ denotes
the 2nd triangle from the top lying along the northwest side; $\gamma$ denotes
the southmost down-pointing triangle along the eastern side; $\delta$ denotes
the southmost triangle along the northwest side. These positions are depicted
within Figure 8.

$\alpha$$\beta$$\gamma$$\delta$ Figure 8: $R$ defined with respect to the
region $V_{4,3,1,(4)}$ with $\alpha$, $\beta$, $\gamma$, $\delta$ marked. The
outline of $V_{4,3,1,(4)}$ is drawn thickly. Note $R$ is the original region
with its dent “filled in.”

We will apply Kuo’s condensation method (Lemma 2, equation 5) to $R$,
$\alpha$, $\beta$, $\gamma$, $\delta$. We use subscript to denote triangles
that are removed from $R$, so that $R_{\alpha}=V_{a,b,1,(u)}$ and the
condensation formula reads

$M(R_{\alpha})M(R_{{\beta},{\gamma},{\delta}})+M(R_{\gamma})M(R_{{\alpha},{\beta},{\delta}})=M(R_{\beta})M(R_{{\alpha},{\gamma},{\delta}})+M(R_{\delta})M(R_{{\alpha},{\beta},{\gamma}}).$
(12)

$\alpha$$\beta$$\gamma$$\delta$

$R_{\alpha}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{{\beta},{\gamma},{\delta}}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{\beta}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{{\alpha},{\gamma},{\delta}}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{\gamma}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{{\alpha},{\beta},{\delta}}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{\delta}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{{\alpha},{\beta},{\gamma}}$

Figure 9: Each of the regions defined by removing an odd subset of
$\\{\alpha,\beta,\gamma,\delta\\}$ from $R$. Each region with
$\beta,\gamma,\delta$ removed has forced lozenges along the top, bottom, and
southwest respectively.

It is worth noting that $R_{\alpha,\beta,\gamma}$ may be untileable, and
$R_{\gamma}$ and $R_{\alpha,\beta,\delta}$ are unbalanced. Since each of the
other regions among these is tileable and has forced lozenges that leave half-
hexagons or dented half-hexagons once removed (as depicted in Figure 9), we
can rewrite equation 12 in context.

$f_{b,1,(u)}(a)P_{|}(a+1,b-1)=P_{|}(a+1,b)f_{b-1,1,(u)}(a)+P_{|}(a,b+1)f_{b-2,1,(u-2)}(a+1)$

By the inductive hypothesis $f_{b-1,1,(u)}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ F_{b-1,1,(u)}(a)$ and
$f_{b-2,1,(u-2)}(a)\ \hbox to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\
$a$}}\ F_{b-2,1,(u-2)}(a)$. By relations 9 and 10, in order to show
$f_{b,1,(u)}(a)\ \hbox to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\
$a$}}\ F_{b,1,(u)}(a)$ it suffices to show888In the case that
$R_{\alpha,\beta,\gamma}$ is untileable, the last term in relation 13 is
identically zero. In this case it is neither possible nor necessary to show it
is $\equiv$ $a$ -equivalent to the other terms, so we proceed assuming it is
not identically zero. that

$F_{b,1,(u)}(a)P_{|}(a+1,b-1)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
P_{|}(a+1,b)F_{b-1,1,(u)}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
P_{|}(a,b+1)F_{b-2,1,(u-2)}(a+1).$ (13)

We check that the first and last products are $\equiv$ $a$ -equivalent by
expanding $F$.

$\displaystyle F_{b,1,(u)}(a)P_{|}(a+1,b-1)$ $\displaystyle\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
P_{|}(a,b+1)F_{b-2,1,(u-2)}(a+1)$
$\displaystyle\dfrac{P_{|}(a,b+1)}{(2a+u)_{b+2-u}}P_{|}(a+1,b-1)$
$\displaystyle\ \hbox to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
P_{|}(a,b+1)\dfrac{P_{|}(a+1,b-1)}{(2a+u)_{b+2-u}}$

It remains to show that $P_{|}(a+1,b)F_{b-1,1,(u)}(a)$ is $\equiv$ $a$
-equivalent to these. We will make liberal use of the following identity,
which is straightforward to check.

$\dfrac{P_{|}(a,b)}{P_{|}(a,b-1)}\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ (a+b-1)(2a+b)_{b-2}$
(14)

We apply this identity twice in turn.

$\displaystyle\dfrac{P_{|}(a,b+1)}{P_{|}(a,b)(2a+b+1)}\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ $
$\displaystyle(a+b)(2a+b+2)_{b-2}$ (15)
$\displaystyle\dfrac{P_{|}(a+1,b)}{P_{|}(a+1,b-1)}\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ $
$\displaystyle(a+b)(2a+b+2)_{b-2}$ (16)

Now we rewrite the first and second product from 13 explicitly.

$\dfrac{P_{|}(a,b+1)}{(2a+u)_{b+2-u}}P_{|}(a+1,b-1)=P_{|}(a+1)\dfrac{P_{|}(a,b)}{(2a+u)_{b+1-u}}$
(17)

We multiply both sides by $\frac{(2a+u)_{b+1-u}}{P_{|}(a,b)P_{|}(a+1,b-1)}$.

$\dfrac{P_{|}(a,b+1)}{P_{|}(a,b)(2a+b+1)}\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
\dfrac{P_{|}(a+1,b)}{P_{|}(a+1,b-1)}$ (18)

We apply relations 15 and 16 to get

$\dfrac{(a+b)(2a+b+1)_{b-1}}{(2a+b+1)}\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ (a+b)(2a+b+2)_{b-2}$
(19)

which holds since both sides are equal. Thus, $f_{b,1,(u)}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ F_{b,1,(u)}(a)$
whenever $2\leq u\leq b+2n$.

∎

Our full proof of Theorem 12 is quite similar to the previous proof of the
special case.

###### Proof of Theorem 12.

We will first show relation (11) holds in general, by inducting on the number
of dents, with regions with one or no dents as a base case which is covered by
Lemma 19.

For our inductive hypothesis, assume that relation (11) holds for dented half-
hexagons with fewer than $n$ dents, and consider a tileable family of dented
half-hexagons $\\{V_{a,b,n,(u_{i})_{1}^{n}}:a\in\mathbb{Z}\\}$.

In the case $u_{1}=2$, there are forced lozenges at the top of the region, and

$f_{b,n,(u_{i})_{1}^{n}}(a)=f_{b,n-1,(u_{i}-2)_{2}^{n}}(a+1)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
F_{b,n-1,(u_{i}-2)_{2}^{n}}(a+1)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
F_{b,n,(u_{i})_{1}^{n}}(a)$

by the inductive hypothesis and Lemma 18.1.

In the case $u_{n}=b+2n$, there are forced lozenges along the southwest
boundary of the region, and

$f_{b,n,(u_{i})_{1}^{n}}(a)=f_{b+1,n-1,(u_{i})_{1}^{n-1}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
F_{b+1,n-1,(u_{i})_{1}^{n-1}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
F_{b,n,(u_{i})_{1}^{n}}(a)$

by the inductive hypothesis and Lemma 18.2.

In the case that $2<u_{1}<u_{n}<b+2n$ we proceed using Kuo’s condensation
method. Regard each $V_{a,b,n,(u_{i})_{1}^{n}}$ as a subregion of
$R:=V_{a,b,n,(u_{i})_{2}^{n-1}}$, that is, the original region without its
first and last dent. Within each $R$, say: $\alpha$ denotes the second
triangle from the top along the northwest side; $\beta$ denotes the $u_{1}$st
triangle from the top along the northwest side; $\gamma$ denotes the $u_{n}$th
triangle from the top along the northwest side; and $\delta$ denotes the
bottom triangle along the northwest side. These positions are depicted within
Figure 10.

$\alpha$$\beta$$\gamma$$\delta$ Figure 10: $R$ defined with respect to the
region $V_{4,3,3,(4,5,7)}$ with that region’s outline drawn thickly and
$\alpha$, $\beta$, $\gamma$, $\delta$ marked. Note, $R$ is the original region
with its first and last dent “filled in.”

We will apply Kuo’s condensation method (Lemma 2, equation 4) to $R$,
$\alpha$, $\beta$, $\gamma$, $\delta$. We use subscript to denote triangles
that are removed from $R$, so that
$R_{{\beta},{\gamma}}=V_{a,b,n,(u_{i})_{1}^{n}}$ and the condensation formula
reads

$M(R_{{\beta},{\gamma}})M(R_{{\alpha},{\delta}})=M(R_{{\alpha},{\gamma}})M(R_{{\beta},{\delta}})-M(R_{{\alpha},{\beta}})M(R_{{\gamma},{\delta}})$
(20)

$\alpha$$\beta$$\gamma$$\delta$

$R_{{\alpha},{\beta}}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{{\gamma},{\delta}}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{{\alpha},{\gamma}}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{{\beta},{\delta}}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{{\alpha},{\delta}}$

$\alpha$$\beta$$\gamma$$\delta$

$R_{{\beta},{\gamma}}$

Figure 11: Each of the regions defined by removing an two of
$\\{\alpha,\beta,\gamma,\delta\\}$ from $R$. Each region with $\alpha,\delta$
removed has forced lozenges along its top and southwest respectively.

Since each of these regions has forced lozenges that leave dented half-
hexagons once removed (as depicted in Figure 11), we can rewrite equation 20
in context.

$\displaystyle f_{b,n,(u_{i})_{1}^{n}}(a)\cdot
f_{b+1,n-2,(u_{i}-2)_{2}^{n-2}}(a+1)$ $\displaystyle=$ (21) $\displaystyle
f_{b,n-1,(u_{i}-2)_{2}^{n}}(a+1)\cdot f_{b+1,n-1,(u_{i})_{1}^{n-1}}(a)$
$\displaystyle-$ (22) $\displaystyle f_{b,n-1,(u_{i}-2)_{1}^{n-1}}(a+1)\cdot
f_{b+1,n-1,(u_{i})_{2}^{n}}(a)$ (23)

It is worth noting that while the first term in line 23 may refer to an
untileable region, and thus may be identically zero, the rest of the terms are
not identically zero. By the inductive hypothesis, we can rewrite this as
follows.

$\displaystyle f_{b,n,(u_{i})_{1}^{n}}(a)\cdot
F_{b+1,n-2,(u_{i}-2)_{2}^{n-2}}(a+1)$ $\equiv$ $a$ $\displaystyle
F_{b,n-1,(u_{i}-2)_{2}^{n}}(a+1)\cdot F_{b+1,n-1,(u_{i})_{1}^{n-1}}(a)$
$\displaystyle-$ $\displaystyle F_{b,n-1,(u_{i}-2)_{1}^{n-1}}(a+1)\cdot
F_{b+1,n-1,(u_{i})_{2}^{n}}(a)$

By relations 9 and 10, in order to show $f_{b,n,(u_{i})_{1}^{n}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
F_{b,n,(u_{i})_{1}^{n}}(a)$ it suffices to show999As in the previous proof, in
the case that the third term is identically zero it is unnecessary to show it
is $\equiv$ $a$ -equivalent to the other terms, so we proceed assuming it is
not identically zero.  that

$\displaystyle F_{b,n,(u_{i})_{1}^{n}}(a)\cdot
F_{b+1,n-2,(u_{i}-2)_{2}^{n-1}}(a+1)$ $\equiv$ $a$ (24) $\displaystyle
F_{b,n-1,(u_{i}-2)_{2}^{n}}(a+1)\cdot F_{b+1,n-1,(u_{i})_{1}^{n-1}}(a)$
$\equiv$ $a$ (25) $\displaystyle F_{b,n-1,(u_{i}-2)_{1}^{n-1}}(a+1)\cdot
F_{b+1,n-1,(u_{i})_{2}^{n}}(a)$ . (26)

We write these terms out explicitly.

$\displaystyle\dfrac{P_{|}(a,b+n)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}\cdot\dfrac{P_{|}(a+1,b+n-1)}{\prod_{i=2}^{n-1}(2a+u_{i})_{\underline{u_{i}}}}$
$\equiv$ $a$ (27)
$\displaystyle\dfrac{P_{|}(a+1,b+n-1)}{\prod_{i=2}^{n}(2a+u_{i})_{\underline{u_{i}}}}\cdot\dfrac{P_{|}(a,b+n)}{\prod_{i=1}^{n-1}(2a+u_{i})_{\underline{u_{i}}}}$
$\equiv$ $a$ (28)
$\displaystyle\dfrac{P_{|}(a+1,b+n-1)}{\prod_{i=1}^{n-1}(2a+u_{i})_{\underline{u_{i}}+1}}\cdot\dfrac{P_{|}(a,b+n)}{\prod_{i=2}^{n}(2a+u_{i})_{\underline{u_{i}}-1}}$
(29)

Since the numerators of each expression are identical, it suffices to check
the denominators are $\equiv$ $a$ -equivalent. We write down this condition.

$\displaystyle{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}\cdot{\prod_{i=2}^{n-1}(2a+u_{i})_{\underline{u_{i}}}}$
$\equiv$ $a$ (30)
$\displaystyle{\prod_{i=2}^{n}(2a+u_{i})_{\underline{u_{i}}}}\cdot{\prod_{i=1}^{n-1}(2a+u_{i})_{\underline{u_{i}}}}$
$\equiv$ $a$ (31)
$\displaystyle{\prod_{i=1}^{n-1}(2a+u_{i})_{\underline{u_{i}}+1}}\cdot{\prod_{i=2}^{n}(2a+u_{i})_{\underline{u_{i}}-1}}$
(32)

The products in lines 30 and 31 are equal. The product in line 32 can be
rewritten

$\displaystyle\prod_{i=1}^{n-1}\left((2a+b+n+i)(2a+u_{i})_{\underline{u_{i}}}\right)\cdot\prod_{i=2}^{n}\dfrac{(2a+u_{i})_{\underline{u_{i}}-1}}{(2a+b+n+i-1)}$
$\displaystyle=$ (33)
$\displaystyle{\prod_{i=1}^{n-1}(2a+u_{i})_{\underline{u_{i}}+1}}\cdot{\prod_{i=2}^{n}(2a+u_{i})_{\underline{u_{i}}-1}}$
(34)

to show it is also equal to the product in lines 30, 31. This completes our
proof that $F_{b,n,(u_{i})_{1}^{n}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
f_{b,n,(u_{i})_{1}^{n}}(a)$ for any tileable dented half-hexagon
$V_{a,b,n,(u_{i})_{1}^{n}}.$

To complete our proof of Theorem 12, consider any dented half-hexagon
$V_{a,b,n,(u_{i})_{1}^{n}}$. If this region is untileable then equation 6
holds trivially. If the region is tileable, then there exists some $c$
independent of $a$ so that $M(V_{a,b,n,(u_{i})_{1}^{n}})=c\cdot
F_{b,n,(u_{i})_{1}^{n}}(a)$. Then

$\displaystyle\dfrac{f_{b,n,(u_{i})_{1}^{n}}(a)}{f_{b,n,(u_{i})_{1}^{n}}(0)}$
$\displaystyle=\dfrac{c\cdot F_{b,n,(u_{i})_{1}^{n}}(a)}{c\cdot
F_{b,n,(u_{i})_{1}^{n}}(0)}=\dfrac{F_{b,n,(u_{i})_{1}^{n}}(a)}{F_{b,n,(u_{i})_{1}^{n}}(0)}=\prod_{i=1}^{n}(u_{i})_{\underline{u_{i}}}\cdot\dfrac{P_{|}(a,b+n)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}$

and equation 6 follows by multiplying across by
${f_{b,n,(u_{i})_{1}^{n}}(0)}$.

∎

##  6 Proofs of Theorems 14 and 15

Recall, we denote the tiling functions

$f^{+}_{b,n,(u_{i})_{1}^{n}}(a):=M\left(V^{+}_{a,b,n,(u_{i})_{1}^{n}}\right),\quad\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a):=M\left(\overline{V}^{+}_{a,b,n,(u_{i})_{1}^{n}}\right).$

In this section we will prove Corollary 13, Theorem 14, and Theorem 15 in
sequence, as each proof depends on the previous result.

###### Proof of Corollary 13.

First we will use Theorem 5 to show

$\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
\dfrac{P_{-}(a,b+n)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}.$

Applying Theorem 5 to $H_{2a,b,b,2n,(u_{i})_{1}^{n},(u_{i})_{1}^{n}}$, $R^{-}$
is $V_{a,b,n,(u_{i})_{1}^{n}}$ whereas $R^{+}$ is congruent to
$\overline{V}^{+}_{a,b,n,(u_{i})_{1}^{n}}$. See Figure 12, Left. Then

$M(H_{a,b,b,2n,(u_{i})_{1}^{n},(u_{i})_{1}^{n}})=2^{b+n}\cdot
f_{b,n,(u_{i})_{1}^{n}}(a)\cdot\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a).$
(35)

Figure 12: Left: In the language of Theorem 5 applied to
$H_{2a,b,b,2n,(u_{i})_{1}^{n},(u_{i})_{1}^{n}}$, the region $R^{-}$ is
$V_{a,b,n,(u_{i})_{1}^{n}}$ and $R^{+}$ is
$\overline{V}^{+}_{a,b,n,(u_{i})_{1}^{n}}$. Right: The region
$V^{+}_{a,b,n,(u_{i})_{1}^{n}}$ is congruent to the region which remains after
removing forced lozenges from $V_{a,b+1,n,(u_{i}+1)_{1}^{n}}$.

It follows from Theorems 7 and 12 that

$\dfrac{P(2a,b+n,b+n)}{\left(\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}\right)^{2}}\
\hbox to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
\dfrac{P_{|}(a,b+n)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}\cdot\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a).$
(36)

Then

$\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
\dfrac{P(2a,b+n,b+n)/P_{|}(a,b+n)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}=\dfrac{P_{-}(a,b+n)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}.$
(37)

Then

$\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
\dfrac{P_{-}(a,b+n)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}.$

The rest of the proof follows as in the proof of Theorem 12, by calculating

$\dfrac{\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)}{\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(0)}.$

∎

We will now prove a technical lemma to assist in the proof of Theorem 14.

######  Lemma 20.

For $V_{a,b,n,(u_{i})_{1}^{n}}$ a tileable dented half-hexagon,

$\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
f^{+}_{b,n,(u_{i})_{1}^{n}}(a-1/2).$

###### Proof.

As Figure 12, Right, demonstrates, $V^{+}_{a,b,n,(u_{i})_{1}^{n}}$ is
congruent to $V_{a,b+1,n,(u_{i}+1)_{1}^{n}}$ with forced lozenges removed, and
therefore has the same tiling function as $V_{a,b+1,n,(u_{i}+1)_{1}^{n}}$. It
follows from this fact and Theorem 12 that

$f^{+}_{b,n,(u_{i})_{1}^{n}}(a-1/2)=f_{b+1,n,(u_{i}+1)_{1}^{n}}(a-1/2)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
\dfrac{P_{|}(a-1/2,b+n+1)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}.$

Since

$\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
\dfrac{P_{-}(a,b+n)}{\prod_{i=1}^{n}(2a+u_{i})_{\underline{u_{i}}}}$

it suffices to show $P_{|}(a-1/2,b+1)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\ P_{-}(a,b)$. It is
straightforward to check

$P_{-}(a,b)\ \hbox to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
(2a+1)_{b}\prod_{1\leq i<j\leq b}(2a+i+j).$

We can rewrite

$\displaystyle P_{|}(a-1/2,b+1)$ $\displaystyle\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
\dfrac{(a+1/2)_{b}}{(2a)_{b}}\prod_{1\leq i\leq j\leq b}(2a+i+j-2)$
$\displaystyle=\dfrac{(a+1/2)_{b}}{(2a)_{b}}\prod_{1\leq i\leq j\leq
b}\dfrac{(2a+i+j-2)}{(2a+i+j)}(2a+i+j).$

It is straightforward to check that

$\prod_{1\leq i\leq j\leq
b}\dfrac{x+i+j-1}{x+i+j}=\prod_{k=1}^{b}\dfrac{x+k}{x+2k}$

and therefore

$\prod_{1\leq i\leq j\leq b}\dfrac{2a+i+j-2}{2a+i+j}=\prod_{1\leq i\leq j\leq
b}\dfrac{(2a+i+j-2)(2a+i+j-1)}{(2a+i+j-1)(2a+i+j)}=\dfrac{(2a)_{b}(2a+1)_{b}}{(2a+1)_{2b}}.$

Then

$\displaystyle P_{|}(a-1/2,b+1)$ $\displaystyle\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
\dfrac{(a+1/2)_{b}}{(2a)_{b}}\cdot\dfrac{(2a)_{b}(2a+1)_{b}}{(2a+1)_{2b}}\prod_{1\leq
i\leq j\leq b}(2a+i+j)$
$\displaystyle=\dfrac{(a+1/2)_{b}}{(2a+b+1)_{b}}\prod_{1\leq i<j\leq
b}(2a+i+j)\prod_{1\leq k\leq b}(2a+2k)$
$\displaystyle=\dfrac{1}{(2a+b+1)_{b}}\prod_{1\leq i<j\leq
b}(2a+i+j)\prod_{1\leq k\leq b}(2a+2k)(a-1/2+k)$ $\displaystyle\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
\dfrac{1}{(2a+b+1)_{b}}\prod_{1\leq i<j\leq b}(2a+i+j)\prod_{1\leq k\leq
b}(2a+2k)(2a+k)$ $\displaystyle=\dfrac{(2a+1)_{2b}}{(2a+b+1)_{b}}\prod_{1\leq
i<j\leq b}(2a+i+j)$ $\displaystyle=(2a+1)_{b}\prod_{1\leq i<j\leq b}(2a+i+j)$

which is $\equiv$ $a$ -equivalent to $P_{-}(a,b)$.

∎

We can now prove Theorem 14 directly.

(0,0)

(0,0)$b-1$$b+2n$$b-1$$a+n$

Figure 13: Left: The region $V_{a,b,n,\vec{u}}=V_{3,5,3,(3,6,9)}$ with the
east-northeast square lattice superimposed. Right: As with Figure 6 we take a
linear transformation of the figure to give Cartesian coordinates for the
lattice’s vertices. Sources lie along the southwest side of the region at
coordinates $\\{(i-1,b-i):i\in[b]\\}$ and along dents at coordinates
$\\{(0,2b+2n-u_{i}:i\in[n]\\}$. Sinks lie at coordinates
$\\{(a+b+n-j,2j-1):j\in[b+n]\\}$.

###### Proof of Theorem 14.

Recall we wish to show that

$\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)=f^{+}_{b,n,(u_{i})_{1}^{n}}(a-1/2).$
(38)

Lemma 20 shows that $\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)\ \hbox
to0.0pt{$\equiv$\hss}{\raisebox{5.50003pt}{\tiny\ $a$}}\
f^{+}_{b,n,(u_{i})_{1}^{n}}(a-1/2).$ We will show that the leading
coefficients of $\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}$ and
$f^{+}_{b,n,(u_{i})_{1}^{n}}$ are the same, and thus the polynomials are
equal.

Since individual regions’ tiling numbers are given by determinants of
corresponding path matrices, the tiling functions
$f^{+}_{b,n,(u_{i})_{1}^{n}}(a)$ , $\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)$
are given by determinants of appropriate path matrices whose entries are
functions of $a$. Let $M$ denote the path matrix for
$V^{+}_{a,b,n,(u_{i})_{1}^{n}}$, whose $(i,j)$th entry counts paths from the
$i$th source to the $j$th sink. This entry is then of the form

$\binom{a+k_{1,i,j}+k_{2,i,j}}{k_{2,i,j}}.$

The value of $k_{1,i,j}$ can be computed by subtracting the $x$-coordinate of
the the $i$th source from the $x$-coordinate of the $j$th sink, using the
coordinate scheme from Figure 13. Similarly, $k_{2,i,j}$ can be computed by
subtracting the $y$-coordinate of the $i$th source from the $y$-coordinate of
the $j$th sink using that coordinate scheme. Thus, when there exists an east-
northeast lattice path from the $i$th source to the $j$th sink, $a+k_{1,i,j}$
counts the east-directed steps on that path, and $k_{2,i,j}$ counts the
northeast-directed steps.

Let $\overline{M}$ be the analogous path matrix for
$\overline{V}^{+}_{a,b,n,(u_{i})_{1}^{n}}$. Then the $(i,j)$th entry of this
matrix is

$\binom{a+k_{1,i,j}+k_{2,i,j}-1}{k_{2,i,j}}+\frac{1}{2}\binom{a+k_{1,i,j}+k_{2,i,j}-1}{k_{2,i,j}-1}.$

This calculation separates the lattice paths according to their last step; for
each lattice path in a nonintersecting family whose last step is northeast,
the tiling induced by the family includes a lozenge of weight $1/2$, and the
calculation above gives a weighted count of lattice paths accordingly. It is
straightforward to check that when the $(i,j)$th entry from each matrix is
expanded as a polynomial in $a$, the two polynomials have the same leading
coefficient. It suffices to show the leading coefficients of the determinants
of these matrices are also the same.

We will show for $\pi$ any permutation of $[b+n]$, that
$\prod_{i=1}^{b+n}M[i,\pi(i)]$ and $\prod_{i=1}^{b+n}\overline{M}[i,\pi(i)]$
are either both 0, or both polynomials in $a$ of degree

$b+n+\binom{b+n}{2}-\sum_{i=1}^{n}\underline{u_{i}}.$

The $(i,j)$th entry of $M$ is nonzero if $k_{2,i,j}$ is nonnegative. For any
permutation $\pi$ such that each $k_{2,i,\pi(i)}$ is nonnegative, the degree
of the polynomial $\prod_{i}M[i,\pi(i)]$ is the sum of entries
$\sum_{i}k_{2,i,\pi(i)}$; this is the sum of the $y$-coordinates of the sinks,
minus the sum of the $y$-coordinates of the sources. The sum of sink
$y$-coordinates is

$\sum_{j=1}^{b+n}(2j-1)=b+n+2\sum_{j=0}^{b+n-1}j=b+n+2\binom{b+n}{2}.$

The sum of source $y$-coordinates is

$\displaystyle\sum_{i=0}^{b-1}i+\sum_{i=1}^{n}\left(2b+2n-u_{i}\right)$
$\displaystyle=\sum_{i=0}^{b-1}i+\sum_{i=1}^{n}(b+n-i)+\sum_{i=1}^{n}\left(b+n+i-u_{i}\right)$
(39)
$\displaystyle=\binom{b}{2}+bn+n^{2}-\binom{n+1}{2}+\sum_{i=1}^{n}\underline{u_{i}}$
(40) $\displaystyle=\binom{b+n}{2}+\sum_{i=1}^{n}\underline{u_{i}}.$ (41)

The difference is then

$b+n+\binom{b+n}{2}-\sum_{i=1}^{n}\underline{u_{i}}.$

Since this is also the degree of $f^{+}_{b,n,(u_{i})_{1}^{n}}(a)$ and
$\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)$, both
$f^{+}_{b,n,(u_{i})_{1}^{n}}(a)$ and
$\overline{f}^{+}_{b,n,(u_{i})_{1}^{n}}(a)$ must have the same leading
coefficient.

∎

We will consider how the path matrices of tubey regions relate to those of
dented half-hexagons, to show that Theorem 15 follows from Theorem 14. Toward
this end we will develop some vocabulary for tubey regions. We say $R$ is the
core of $R_{z}(a)$. We say the height of a tubey region is half the number of
edges in $z$. Recall that the construction of a tubey region is not
necessarily unique, and note that both the core and height of a region depend
on its specific construction.

We include the following proof of a special case of Theorem 15, where the
number of southwest boundary edges of a simply connected tubey region is the
same as its height, because we feel the proof is illustrative. This is the
case where all lattice paths of lozenges in tilings of the region cross $z$
and end within the tube.

###### Proof of Theorem 15, special case.

Let $R_{z}(0)$ be a simply connected tileable tubey region of height $h$, and
let $g(a)$ be the tiling function for $\\{R_{z}(a+1/2):a\in\mathbb{N}\\}$ and
$\overline{g}(a)$ be the tiling function of
$\\{\overline{R}_{z}(a+1/2):a\in\mathbb{N}\\}$. Assume for the purposes of
this special case that the number of southwest boundary edges of $R$ is $h$.

For $a\geq h$, the southeast-directed lattice line which passes through the
top of $z$ also passes through the southern boundary of the tube (rather than
its eastern boundary), as depicted in Figure 14. We call the subregion of
$R_{z}(a+1/2)$ west of that lattice line $W$ and the subregion east of the
line $E(a)$, since $W$ is the same for each $a$ but $E(a)$ grows with $a$; we
let $\overline{E}(a)$ denote the analogous weighted subregion of
$\overline{R}_{z}(a+1/2)$.

Figure 14: A tubey region whose core is shaded grey, separated into subregions
$W$ (west of the line) and $E$ (east of the line) by the southeast-directed
lattice line descending from the top of $z$.

Let $N$ denote the path matrix with polynomial entries in $a$ for lattice
paths starting from the southwest boundary edges of $R_{z}(a+1/2)$ and ending
at the northeast boundary edges; we take the indexing of rows and columns to
be increasing from sources and sinks at the bottom of the region to the top.
We let $\overline{N}$ denote the analogous path matrix for
$\overline{R}_{z}(a+1/2)$. We will show that these path matrices have natural
decompositions under the Cauchy-Binet formula into a linear combination of
tiling functions of dented half-hexagons.

Let $N^{W}$ be the path matrix for east-northeast paths on $W$, and $N^{E}$
the path matrix with polynomial entries in $a$ for east-northeast paths on
$E(a)$, using the same bottom-to-top indexing scheme as with $N$. Since
$R_{z}(a+1/2)$ is tileable with height $h$, $N$ is an $h\times h$ matrix
whereas $N^{W}$ is an $h\times 2h$ matrix and $N^{E}$ is a $2h\times h$
matrix. Furthermore,

$N=N^{W}\cdot N^{E}.$ (42)

By Theorem 1 (Cauchy-Binet),

$\displaystyle\det(N)$
$\displaystyle=\sum_{v\in\binom{[2h]}{h}}\det(N^{W}_{[h],v})\cdot\det(N^{E}_{v,[h]})$
(43) $\displaystyle\mbox{similarly,}\quad\det(\overline{N})$
$\displaystyle=\sum_{v\in\binom{[2h]}{h}}\det(N^{W}_{[h],v})\cdot\det(N^{\overline{E}}_{v,[h]}).$
(44)

In fact, $N^{E}_{v,[h]}$ is the path matrix for an upside-down copy of the
dented half-hexagon $V^{+}_{a-h,0,h,\vec{v}}$ where $\vec{v}$ denotes the
vector of elements of $[2h]-v$ in increasing order. This is demonstrated in
Figure 15. Then

Figure 15: Left: $E(a)$ corresponding to $R_{z}(a)$ from Figure 14; note it is
defined entirely by $a$ and $h$. The entries of $N^{E}_{v,[h]}$ count east-
northeast lattice paths starting from points indexed by $v$ on the west
boundary and ending at the eastern boundary. Center: For $v=\\{1,2,5,7,8\\}$
the vertices on the square lattice are depicted and color coded: sources are
drawn as black circles; vertices accessible from these by east and northeast
steps are depicted as blue squares; vertices inaccessible from the sources are
drawn as white circles. Right: The region whose tilings are enumerated by
families of nonintersecting lattice paths on the black and blue vertices is an
upside-down copy of $V^{+}_{a-h,0,h,\vec{v}}$ with some forced lozenges
removed, where the entries of $\vec{v}$ are $[2h]-v$ in increasing order. The
outline of this region is drawn thickly over the whole region; the large
triangular omissions come from forced lozenges where dents are grouped
together.

$\displaystyle g(a)$
$\displaystyle=\sum_{v\in\binom{[2h]}{h}}\det(N^{W}_{[h],v})\cdot
f^{+}_{0,h,\vec{v}}(a-h)$ $\displaystyle\mbox{similarly,}\quad\overline{g}(a)$
$\displaystyle=\sum_{v\in\binom{[2h]}{h}}\det(N^{W}_{[h],v})\cdot\overline{f}^{+}_{0,h,\vec{v}}(a-h),$

so that this case of Theorem 15 follows from Theorem 14.

∎

As the determinants of path matrices do not reliably count the tilings of
regions which are not simply connected, the more general case does not follow
directly from an argument about path matrices. However, we may reinterpret
equations 43 and 44 in a way that does not refer to path matrices to get a
more general proof.

###### Proof of Theorem 15.

We continue using the language of the previous proof. It follows from Lemma 4
(Region Splitting Lemma), that all tilings of $R_{z}(a+1/2)$, which has height
$h$, must include exactly $h$ lozenges which cross the lattice line between
$W$ and $E(a)$. Where $v$ indexes the possible positions of this set of
lozenges, indexing along the border from bottom to top, we thus have

$M(R_{z}(a+1/2))=\sum_{v\in\binom{2h}{h}}M(W_{v})M(E_{v}(a))$ (45)

where $W_{v}$ is the subregion of $W$ omitting those triangles covered by
lozenges in positions indexed by $v$, and $E_{v}(a)$ is the analogous
subregion of $E(a)$. In fact, $M(E_{v}(a))=\det(N^{E}_{v,[h]})$, and under the
conditions of the previous proof $M(W_{v})=\det(N^{W}_{[h],v})$ so that
equation 45 generalizes 43. As before, $M(E_{v}(a))$ is the tiling function
for a dented half-hexagon, and the rest of the proof follows as in the
previous special case.

∎

We remark that Theorem 15 then holds for families of tubey regions where the
core may be quite strange in shape and weighting scheme, though the tube
should be unweighted except for the vertical lozenges along its eastern
boundary which have weight 1/2.

##  7 Final Remarks

While writing this paper we solved some problems, not yet mentioned, with
uninteresting answers. Seeking to generalize Theorem 15, one might consider
tubey regions with vertical lozenges along the eastern boundary having weight
$q$, denoting these $\overline{R}_{z}(a;q)$ so that
$\overline{R}_{z}(a)=\overline{R}_{z}(a;1/2)$. Defining $g(a;q)$ to be the
tiling function for $\\{\overline{R}_{z}(a+1/2;q):a\in\mathbb{N}\\}$, one
might then ask whether there is any relation

$g(a+d;1)=g(a;q),$

for $R$ general and $d$ independent of $a$, generalizing Theorem 15. In fact,
no such relation exists except for $q\in\\{0,1/2,1\\}$, even when $R$ is
restricted to vertically symmetric dented half-hexagons.

Moving forward we are interested in regions that can be constructed in a
similar manner to tubey regions, in the sense that one can add (possibly
weighted) layers to a region.

### Acknowledgements

The author would like to express many thanks to M. Ciucu for his advice on
this problem and this paper.

## References