\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}
\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.0 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newcommand{\bin}[2]{\left( #1 \atop #2 \right)}
\title{The Art of Counting}
\author{David M. Bressoud}
\begin{document}
\maketitle
\section{Introduction}
Counting is the most basic mathematical activity we do, yet it can also be one of the most complex. It lies at the heart of any calculation of probabilities with discrete objects. Finding the number of configurations that satisfy a given set of rules is a recurring problem that one finds in chemistry, in physics, and in almost every discipline of mathematics. Following a short refresher on binomial coefficients, this paper will focus on two of my favorite counting problems, problems that illustrate the power of recursion:
\begin{enumerate}
\item Slicing cheese: Given a large block of cheese, how many pieces can we get with six straight slices?
\item Square ice: How many ways can we place 25 water molecules (H$_2$O) into a square lattice so that each oxygen atom along the top or bottom is adjacent to three hydrogen atoms, and all other oxygen atoms are surrounded by exactly four hydrogen atoms?
\end{enumerate}
The title of this article is borrowed from a book of selected writings by Paul Erd\"os \cite{Erdos:1973}, one of the great counters of all time.
\section{Binomial Coefficients}
Recursion is a basic technique of counting. Any formula that connects previous calculations to the next is called ``recursive." A good example of this is given by binomial coefficients such as $\bin{5}{2}$ which represents the number of ways of choosing two objects from a selection of five. If our objects are the five letters $\{A,B,C,D,E\}$, then the possible choices can be listed as
\[ \begin{array}{llllll} AB, & AC, & AD, & AE, \\ BC, & BD, & BE, & CD, & CE, & DE. \end{array} \]
I have intentionally separated these. The first line consists of those choices that include the letter $A$, the second line those that do not include $A$. If we include $A$, then there are four ways of choosing because there are four other letters, and we must select one of them, $\bin{4}{1} = 4$. If our choice does not include $A$, then we must pick two letters from the remaining four: $\bin{4}{2} = 6$.
This idea works in general. Given $n$ letters from which we must choose $k$, either we do choose the first letter, leaving $k-1$ choices from $n-1$ letters, or we do not choose the first letter, leaving $k$ choices from $n-1$ letters:
\[ \bin{n}{k} = \bin{n-1}{k-1} + \bin{n-1}{k}. \]
When we combine this recursive formula with the observation that there is always one way of choosing nothing and one way of choosing everything, we can build Pascal's triangle, obtaining each row from the row above by adding pairs of adjacent entries (see Figure~\ref{fig:2.1}).
\begin{figure}
\begin{center}
\scalebox{0.6}{\includegraphics[trim= 50 350 50 0]{fig-1.pdf}}
\end{center}
\caption{The recursion that generates Pascal's triangle. \label{fig:2.1}}
\end{figure}
This triangle carries Pascal's name because of the book he wrote in 1654, {\it Treatise on the Arithmetical Triangle\/}, that both explained and popularized this triangular arrangement of binomial coefficients, but it is much older. Figure~\ref{fig:2.2}
\begin{figure}
\begin{center}
\scalebox{0.6}{\includegraphics[trim= 50 20 50 50]{fig-2.jpg}}
\end{center}
\caption{``Pascal's'' triangle from {\it Siyuan yujian\/}, by Zhu Shijie, written in 1303. Reprinted from \cite[p.\ 135]{Needham:1959}. \label{fig:2.2}}
\end{figure}
shows a page from {\it Siyuan yujian\/} by the Chinese mathematician Zhu Shijie, written in 1303. He refers to it as an ancient method. The earliest reliable reference is to a work of Jia Xian from around 1100. There are hints that it might have been known as much as a hundred years earlier in China, in India, and/or in the Islamic Baghdad-Cairo axis.
\section{Slicing Cheese}
How many regions in space can we get if we cut space by six planes? This, our first counting problem, was popularized by George P\'olya in the short film he created for the Mathematical Association of America in 1965, {\it Let Us Teach Guessing\/} \cite{Polya:1965}. The first published solution was by Jakob Steiner \cite{Steiner:1826} in 1826. See also articles by Alexanderson and Wetzel \cite{AlexandersonWetzel:1978, AlexandersonWetzel:1981}. This problem is related to the one studied by Jean Pederson in an earlier {\it Mathematical Adventure\/} \cite{Pederson:2004}, but in her case, many of the planes were parallel. Here we want no two planes to be parallel and no more than three planes to meet in any single point. In other words, we want to get as many regions as we can.
The situation starts out simply (see Figure~\ref{fig:3.3}):
\begin{figure}
\begin{center}
\scalebox{0.6}{\includegraphics[trim= 50 350 50 100]{fig-3.pdf}}
\end{center}
\caption{Space sliced by three planes. \label{fig:3.3}}
\end{figure}
\begin{center}\begin{tabular}{ll}
0 planes: & 1 region \\
1 plane:& 2 regions \\
2 planes: & 4 regions \\
3 planes: & 8 regions.
\end{tabular}\end{center}
But the fourth plane does not leave us with 16 regions, but rather only 15.
To understand what happens, it is useful to back up and look at a simpler situation. Simpler than space cut by planes would be a plane cut by lines, but we are going to back up even further, to the number of pieces of a line cut by points. An uncut line consists of one piece. Each new cut point increases the number of pieces by one. So a line cut by $n$ points has $n+1$ pieces. We now consider a plane cut by lines. The first line gives us one additional piece. The second line gives us two additional pieces, and the third line gives us three additional pieces.
\begin{figure}
\begin{center}
\scalebox{0.6}{\includegraphics[trim= 50 430 50 100]{fig-4.pdf}}
\end{center}
\caption{A fifth line cuts through a plane already cut by four lines. \label{fig:3.4}}
\end{figure}
A fourth line gives us four new pieces, and so on. When we add a new line, say the $n$th line, it cuts each of the previous $n-1$ lines. The new line is cut into $n$ pieces. Each of those pieces cuts one region in the plane into two regions (see Figure~\ref{fig:3.4}). Since the $n$th line adds $n$ new regions, the total number of regions on a plane cut by $n$ lines is
\[ 1 + 1 + 2 + 3 + \cdots + n. \]
What happens when our fourth plane cuts through space? It meets each of the previous three planes. Each of the previous planes cuts the new plane along a line. Our new fourth plane is cut by three lines. It will be cut into seven pieces, each of which creates one new region in space. We had eight regions in space. The fourth plane adds seven new regions. We now have fifteen regions. You should be able to see the pattern that enables us to construct the following table:
\begin{center}\begin{tabular}{l|ccc}
$n$ & line by point & plane by line & space by plane \\ \hline\hline
0 & 1 & 1 & 1 \\ \hline
1 & 2 & 2 & 2 \\ \hline
2 & 3 & 4 & 4 \\ \hline
3 & 4 & 7 & 8 \\ \hline
4 & 5 & 11 & 15 \\ \hline
5 & 6 & 16 & 26 \\ \hline
6 & 7 & 22 & {\bf ?}
\end{tabular}\end{center}
I leave it to you to determine the number of regions in space cut by six planes.
Something else is going on here. You should be very suspicious that each entry in this table is the sum of the entry directly above and the entry above and to the left. That is exactly the recursion of Pascal's triangle. If we list of elements of Pascal's triangle so that they line up according to this recursion, we can see what is happening:
\begin{center}\begin{tabular}{l|ccccccccccc}
$n$ & line/point & plane/line & space/plane & \quad & $k=0$ & $=1$ & $=2$ & $=3$ & $=4$ & $=5$ & $=6$\\ \hline\hline
0 & 1 & 1 & 1 && 1 \\ \hline
1 & 2 & 2 & 2 && 1 & 1 \\ \hline
2 & 3 & 4 & 4 && 1 & 2 & 1 \\ \hline
3 & 4 & 7 & 8 && 1& 3 & 3 & 1 \\ \hline
4 & 5 & 11 & 15 && 1 & 4 & 6 & 4 & 1 \\ \hline
5 & 6 & 16 & 26 && 1 & 5 & 10 & 10 & 5 & 1 \\ \hline
6 & 7 & 22 & {\bf ?} && 1 & 6 & 15 & 20 & 15 & 6 & 1
\end{tabular}\end{center}
The number of pieces on a line cut by points is the sum of the first two columns of Pascal's triangle. For a plane cut by lines, it is the sum of the first three columns. The formula for the number of pieces in space cut by $n$ planes is
\[ \bin{n}{0} + \bin{n}{1} + \bin{n}{2} + \bin{n}{3}. \]
This leaves several questions that I invite you to explore:
\begin{enumerate}
\item Can you make sense of this formula? Given $n$ planes in space, why should the number of regions equal the number of ways choosing none of the planes plus the number of ways of choosing one of the planes plus the number of ways of choosing two of the planes plus the number of ways of choosing three of the planes?
\item What is the formula for the number of {\it finite\/} regions formed by $n$ planes?
\item What happens in higher dimensions, and what does that mean?
\end{enumerate}
\section{Square Ice}
A sheet of square ice (see Figure~\ref{fig:5}) is a grid of oxygen atoms (O)
\begin{figure}
\begin{center}
\scalebox{0.8}{\includegraphics[trim= 50 450 50 50]{fig-5.pdf}}
\end{center}
\caption{A $5 \times 5$ sheet of square ice. \label{fig:5}}
\end{figure}
and hydrogen atoms (H). Except along the top and bottom rows, each oxygen atom is surrounded by four hydrogen atoms. Along the top and bottom, there are three hydrogen atoms next to each oxygen atom. If we have a square arrangement of oxygen atoms, then there will be exactly twice as many hydrogen atoms as oxygen atoms. Each oxygen atom must connect to exactly two of the neighboring hydrogen atoms. How many ways can this be done?
As stated, this problem is artificial. It is extremely difficult to get water to freeze into such a square lattice. But other materials do form square lattices, and this model is a useful description for other physical phenomena. David Robbins, a mathematician at the Institute for Defense Analysis, stumbled upon this question in 1980 when studying an algorithm for evaluating determinants, an algorithm that had been devised by Charles Dodgson \cite{Dodgson:1866}, better known as Lewis Carroll, the author of {\it Through the Looking Glass\/} and {\it Alice's Adventures in Wonderland\/}. Robbins own account of his discovery can be found in \cite{Robbins:1991}.
We shall follow Robbins's approach and start by changing this into another, equivalent problem. In each row, we record the molecules for which the oxygen atom is not connected to the hydrogen atom immediately below. We have one such molecule in the first row, two in the second, and so on. For the sheet of square ice in Figure~\ref{fig:5}, this is molecule 2 in the first row, molecules 1 and 4 in the second row, and molecules 1, 2, and 5 in the third row. This sheet of square ice corresponds to the triangle:
\begin{center}\begin{tabular}{ccccccccc}
&&&& 2 \\
&&& 1 && 4 \\
&& 1 && 2 && 5 \\
&1 && 2 && 4 && 5 \\
1 && 2 && 3 && 4 && 5
\end{tabular}\end{center}
Which triangles correspond to sheets of square ice? If a number appears in one row and not in the row below, then the oxygen atom in the row from which it disappeared must be connected to the hydrogen atoms directly above and below. We call this a {\bf vertical molecule}. If a number does not appear in one row but does appear in the row below, the the oxygen atom in the row in which it appears must be connected to the hydrogen atoms to the left and the right. We call this a {\bf horizontal molecule}. Knowing where the horizontal and vertical molecules are located uniquely determines our triangle, and vice-versa.
Notice that in any row or column, any two vertical molecules must be separated by a horizontal molecule. And any two horizontal molecules must be separated by a vertical molecule. Furthermore, once we have placed our horizontal and vertical molecules, all of the remaining molecular bonds are uniquely determined. If a number in one of the rows of our triangle does not appear in the next row, then there must be two new numbers in that next row, one of which is smaller than the number that disappeared, one of which is larger. In general, if $k$ numbers in a given row do not appear in the next row, then $k+1$ new numbers must appear, and for the $j$th number from the left that disappears, $1 \leq j \leq k$, there will be $j$ new smaller numbers that appear, $k-j+1$ new larger numbers that appear.
This is the same as saying that for any three adjacent numbers in the triangle,
\begin{center}\begin{tabular}{c}
\hspace{1mm} a \\\
b \quad c
\end{tabular}\end{center}
we always have
$ b \leq a \leq c$ and $b < c$.
These inequalities guarantee that there will be a corresponding sheet of square ice. We call a triangle that meets these conditions a {\bf monotone triangle}. Our example is a monotone triangle of size 5.
Now, how many monotone triangles of size 5 are there?
We start by listing all of the possible rows of each length (see Figure~\ref{fig:6}).
\begin{figure}
\begin{center}
\scalebox{0.5}{\includegraphics[trim= 50 300 50 50]{fig6.pdf}}
\end{center}
\caption{A choice of rows for the monotone triangles of size 5. \label{fig:6}}
\end{figure}
Each monotone triangle corresponds to a choice of rows. In the figure, the choices that correspond to our example are marked as a path that starts at 12345 and ends at 2. How many such paths are there? Each path must go through one row of each length, but we are not free to take any row we want. The rows of length $k$ that are allowed will depend on the the row of length $k+1$ from which the path is coming.
For the row of length 4: 1245, there is only one path from 12345. But for the row of length 3: 125, we could go through 1235 or 1245. To get to 124, we could go through 1234, 1235, or 1245. There are four paths to 134, and five paths to 234.
Consider 14, a row of length 2. Any path to 14 must pass through 124, 125, 134, 135, or 145. We can calculate the number of paths to each of these: 3, 2, 4, 3, and 2, respectively. There are a total of $3+2+ 4+3+2=14$ different paths from 12345 to 14. Figure~\ref{fig:7} shows the number of paths to each possible row.
\begin{figure}
\begin{center}
\scalebox{0.5}{\includegraphics[trim= 50 300 50 50]{fig7.pdf}}
\end{center}
\caption{The number of configurations that can lie below each row of a monotone triangles of size 5. \label{fig:7}}
\end{figure}
When we add up the number of paths to 1, 2, 3, 4, or 5, we get $42+105+135+105+42 = 429.$ There are 429 possible monotone triangles of size 5.
This recursion can be programmed fairly easily ({\it Mathematica\/} code can be found in \cite[pp. 62--63]{Bressoud:1999} or downloaded from {\tt www.macalester.edu/$\sim$bressoud/books/PnC/prf-n-con.nb}, section~2.3). If $A_n$ is the number of monotone triangles of size $n$, then the first ten values are
\[ \begin{array}{rcll}
A_1 & = & 1, \\
A_2 & = & 2, \\
A_3 & = & 7, \\
A_4 & = & 42, & (2\cdot 3 \cdot 7), \\
A_5 & = & 429, & (3 \cdot 11 \cdot 13), \\
A_6 & = & 7436, & (2^2 \cdot 11 \cdot 13^2), \\
A_7 & = & 218348, & (2^2 \cdot 13^2 \cdot 17\cdot 19), \\
A_8 & = & 10850216, & (2^3\cdot 13 \cdot 17^22\cdot 19^22), \\
A_9 & = & 911835460, & (2^2\cdot 5\cdot 17^22\cdot 19^3\cdot 23), \\
A_{10} & = & 129534272700, & (2^2 \cdot 3 \cdot 5^2 \cdot 7 \cdot 17 \cdot 19^3 \cdot 23^2).
\end{array} \]
The factorizations of these numbers are included because they are quite remarkable and suggest that something very interesting is happening. Most numbers as large as 129534272700 have large prime divisors. The numbers we have found all have small prime divisors. There is hope that there might be a nice formula for $A_n$.
David Robbins next step was to work not with the numbers $A_n$, the number of monotone triangles of size $n$, but to use the values he had found for $A_{n,k}$, $1 \leq k \leq n$, the number of monotone triangles of size $n$ with a $k$ at the apex. As we have seen,
\[ A_{5,1} = 42,\ A_{5,2} = 105,\ A_{5,3} = 135,\ A_{5,4} = 105,\ {\rm and}\ A_{5,5} = 42. \]
We build a triangle of the values $A_{n,k}$:
\begin{center}\scalebox{0.9}{\begin{tabular}{ccccccccccccc}
&&&&&& 1 \\
&&&&& 1 && 1 \\
&&&& 2 && 3 && 2 \\
&&& 7 && 14 && 14 && 7 \\
&& 42 && 105 && 135 && 105 && 42 \\
&429 && 1287 && 2002 && 2002 && 1287 && 429\\
7436 && 26026 && 47320 && 56784 && 47320 && 26026 && 7436
\end{tabular}}\end{center}
Notice that the first entry in each row is the sum of the entries in the row above. This is easy to explain. A monotone triangle with a 1 at the apex must have all 1s down the left-hand edge. The number of ways of filling in the rest of the triangle is just the number of monotone triangles of the next smaller size. What about the second entry in each row? If we look at the ratio of the second entry to the first, we see that the ratios increase by 1/2: $1, 3/2, 2, 5/2, 3, 7/2, \ldots$. There are many representations for each of the other ratios, but Robbins realized that they could be written as shown below:
\begin{center}\scalebox{0.9}{\begin{tabular}{ccccccccccccc}
&&&&&& 1 \\
&&&&& 1 & $\mathbf{ 2/2}$ & 1 \\
&&&& 2 &$\mathbf{ 3/2}$ & 3 & $\mathbf{ 2/3}$ & 2 \\
&&& 7 & $\mathbf{ 4/2}$ & 14 & $\mathbf{ 5/5}$ & 14 & $\mathbf{ 2/4}$ & 7 \\
&& 42 & $\mathbf{ 5/2}$ & 105 & $\mathbf{ 9/7}$ & 135 & $\mathbf{ 7/9}$ & 105 & $\mathbf{ 2/5}$ & 42 \\
&429 & $\mathbf{ 6/2}$ & 1287 & $\mathbf{ 14/9}$ & 2002 & $\mathbf{ 16/16}$ & 2002 & $\mathbf{ 9/14}$ & 1287 & $\mathbf{ 2/6}$ & 429\\
7436 & $\mathbf{ 7/2}$ & 26026 & $\mathbf{ 20/11}$ & 47320 & $\mathbf{ 30/25}$ & 56784 & $\mathbf{ 25/30}$ & 47320 & $\mathbf{ 11/20}$ & 26026 & $\mathbf{ 2/7}$ & 7436
\end{tabular}}\end{center}
Take a moment to look at those ratios and see if you can pick out the pattern.
Once we know the values of $A_{n-1,k}$ for $1 \leq k \leq n-1$, we know that
\begin{equation}
A_{n,1} = \sum_{k=1}^{n-1} A_{n-1,k}, \label{eqn:1}
\end{equation}
so we know the first entry in the next row. If we know the values of the ratios, then the first entry uniquely determines the remaining entries in that row. We can compute any value of $A_{n,k}$.
Isolating just the numerators of our ratios, we get yet another triangle,
\begin{center}\scalebox{0.9}{\begin{tabular}{cccccccccccc}
&&&& & $\mathbf{ 2}$ & \\
&&& &$\mathbf{ 3}$ & & $\mathbf{ 2}$ & \\
&& & $\mathbf{ 4}$ & & $\mathbf{ 5}$ & & $\mathbf{ 2}$ & \\
& & $\mathbf{ 5}$ & & $\mathbf{ 9}$ & & $\mathbf{ 7}$ & & $\mathbf{ 2}$ & \\
& $\mathbf{ 6}$ & & $\mathbf{ 14}$ & & $\mathbf{ 16}$ & & $\mathbf{ 9}$ & & $\mathbf{ 2}$ &\\
$\mathbf{ 7}$ & & $\mathbf{ 20}$ & & $\mathbf{ 30}$ & & $\mathbf{ 25}$ & & $\mathbf{ 11}$ & & $\mathbf{ 2}$ &
\end{tabular}}\end{center}
The denominators are simply the vertical reflection of these numerators. Each numerator is the sum of the two numerators lying directly above it, which suggests that Pascal's triangle has appeared once again. In fact, the triangle of numerators can be represented as
\begin{center}\scalebox{0.9}{\begin{tabular}{cccccccccccc}
&&&& & $\mathbf{ 1+1}$ & \\
&&& &$\mathbf{ 1+2}$ & & $\mathbf{ 1+1}$ & \\
&& & $\mathbf{ 1+3}$ & & $\mathbf{ 2+3}$ & & $\mathbf{ 1+1}$ & \\
& & $\mathbf{ 1+4}$ & & $\mathbf{ 3+6}$ & & $\mathbf{ 3+4}$ & & $\mathbf{ 1+1}$ & \\
& $\mathbf{ 1+5}$ & & $\mathbf{ 4+10}$ & & $\mathbf{ 6+10}$ & & $\mathbf{ 4+5}$ & & $\mathbf{ 1+1}$ &\\
$\mathbf{ 1+6}$ & & $\mathbf{ 5+15}$ & & $\mathbf{ 10+20}$ & & $\mathbf{ 10+15}$ & & $\mathbf{ 5+6}$ & & $\mathbf{ 1+1}$ &
\end{tabular}}\end{center}
Each numerator and each denominator is a sum of two binomial coefficients,
\begin{equation}
\frac{A_{n,k+1}}{A_{n,k}} = \frac{\bin{n-2}{n-k-1} + \bin{n-1}{n-k-1}}{\bin{n-2}{k-1} + \bin{n-1}{k-1}}. \label{eqn:2}
\end{equation}
We have not proven equation~\ref{eqn:2}. In fact, its proof would turn out to be very difficult, not completed until 1996 \cite{Zeilberger:1996b}. But it should be clear that it {\it must\/} be true. Equipped with equations~(\ref{eqn:1}) and (\ref{eqn:2}), we can find an explicit formula for $A_n$, the number of monotone triangles of size $n$.
We first express $A_n$ in terms of $A_{n-1}$ and the ratios:
\begin{eqnarray}
A_n & = & A_{n,1} + A_{n,2} + A_{n,3} + \cdots + A_{n,n} \nonumber \\[3pt]
& = & A_{n,1}\left( 1 + \frac{A_{n,2}}{A_{n,1}} + \frac{A_{n,2}}{A_{n,1}}\cdot \frac{A_{n,3}}{A_{n,2}} + \cdots + \frac{A_{n,2}}{A_{n,1}} \cdots \frac{A_{n,n}}{A_{n,n-1}} \right) \nonumber \\[5pt]
& = & A_{n-1}\left( 1 + \frac{A_{n,2}}{A_{n,1}} + \frac{A_{n,2}}{A_{n,1}}\cdot \frac{A_{n,3}}{A_{n,2}} + \cdots + \frac{A_{n,2}}{A_{n,1}} \cdots \frac{A_{n,n}}{A_{n,n-1}} \right). \label{eqn:2.21}
\end{eqnarray}
Our next step is to simplify the ratio $A_{n,k+1}/A_{n,k}$,
\begin{eqnarray}
\frac{A_{n,k+1}}{A_{n,k}}& = & \frac{\bin{n-2}{n-k-1} + \bin{n-1}{n-k-1}}{\bin{n-2}{k-1} + \bin{n-1}{k-1}} \nonumber \\[5pt]
& = & \frac{ \frac{(n-2)!}{(n-k-1)!(k-1)!} + \frac{(n-1)!}{(n-k-1)! k!}}{\frac{(n-2)!}{(n-k-1)!(k-1)!} + \frac{(n-1)!}{(k-1)!(n-k)!}} \nonumber \\[5pt]
& = & \frac{ \frac{(n-2)!}{(n-k-1)!k!}(k+n-1)}{\frac{(n-2)!}{(n-k)!(k-1)!}(n-k+n-1)} \nonumber \\[5pt]
& = & \frac{(n-k)(n+k-1)}{k(2n-k-1)}.
\end{eqnarray}
Now we simplify the product of ratios,
\begin{eqnarray}
\prod_{k=1}^t \frac{A_{n,k+1}}{A_{n,k}} & = & \frac{(n-1)(n-2)\cdots (n-t)\cdot n (n+1) \cdots (n+t-1)}{1\cdot 2 \cdots t \cdot (2n-2)(2n-3) \cdots (2n-t-1)} \nonumber \\[3pt]
& = & \frac{(n+t-1)! (2n-t-2)!}{t!\,(n-t-1)!\,(2n-2)!} \nonumber \\[3pt]
& = & \frac{(n-1)!^2}{(2n-2)!} \cdot \frac{(n+t-1)!}{t!\,(n-1)!} \cdot \frac{(2n-t-2)!}{(n-t-1)!(n-1)!} \nonumber \\[3pt]
& = & \frac{(n-1)!^2}{(2n-2)!} \cdot \bin{n+t-1}{n-1} \cdot \bin{2n-t-2}{n-1}
\end{eqnarray}
Combining this with equation~(\ref{eqn:2.21}), we have that
\begin{eqnarray}
A_n & = & A_{n-1} \sum_{t=0}^{n-1} \frac{(n-1)!^2}{(2n-2)!} \cdot \bin{n+t-1}{n-1} \cdot \bin{2n-t-2}{n-1} \nonumber \\[3pt]
& = & A_{n-1}\ \frac{(n-1)!^2}{(2n-2)!}\ \sum_{t=0}^{n-1} \bin{n+t-1}{n-1} \cdot \bin{2n-t-2}{n-1}
\end{eqnarray}
We next prove that
\begin{equation}
\bin{3n-2}{2n-1} = \sum_{t=0}^{n-1} \ \bin{n+t-1}{n-1} \cdot \bin{2n-t-2}{n-1}. \label{eqn:2.25}
\end{equation}
The left side of this equation counts the number of ways of choosing $2n-1$ objects from a set of $3n-2$. Let the set from which we are choosing consist of the integers $\{1, 2, 3, \ldots, 3n-2\}$. What is the $n^{\rm th}$ integer that we choose? It cannot be smaller than $n$ or larger than $2n-1$ (because we still have to choose $n-1$ more integers). Let the $n$th integer that we choose be $n+t$ where $0 \leq t \leq n-1$. For this choice of $t$, we still need to choose $n-1$ integers from first $n+t-1$ and $n-1$ integers from the last $2n-t-2$. That is precisely what the $t^{\rm th}$ summand counts.
We now use equation~(\ref{eqn:2.25}) to finish the formula for $A_n$:
\begin{eqnarray}
A_n & = & A_{n-1}\ \frac{(n-1)!^2}{(2n-2)!}\ \bin{3n-2}{2n-1} \nonumber \\
& = & A_{n-1}\ \frac{(n-1)!^2\,(3n-2)!}{(2n-2)!\,(2n-1)!\,(n-1)!} \nonumber \\
& = & A_{n-1}\ \frac{(n-1)!\,(3n-2)!}{(2n-2)!\,(2n-1)!}.
\end{eqnarray}
We know that $A_1 = 1$, and so
\begin{eqnarray}
A_n &=&\frac{1! \cdot 4!}{2! \cdot 3!} \cdot \frac{2! \cdot 7!}{4! \cdot 5!} \cdot \frac{3! \cdot 10!}{6! \cdot 7!} \cdots \frac{(n-1)!\,(3n-2)!}{(2n-2)!\,(2n-1)!} \nonumber \\
&=&\frac{1! \cdot 2! \cdots (n-1)!\ \cdot \ 4! \cdot 7! \cdots (3n-2)!}{1!\cdot 2! \cdot 3! \cdots (2n-1)!} \nonumber \\
&=& \frac{4! \cdot 7! \cdots (3n-2)!}{n!\cdot (n+1)! \cdots (2n-1)!} \nonumber \\
& = & \prod_{j=0}^{n-1} \frac{(3j+1)!}{(n+j)!}.
\end{eqnarray}
And there it is! We have found a simple formula for the number of monotone triangles of size $n$. For example,
\[ A_5 =\frac{1!}{5!} \cdot \frac{4!}{6!} \cdot \frac{7!}{7!} \cdot \frac{10!}{8!} \cdot \frac{13!}{9!} = \frac{9 \cdot 10 \cdot 10 \cdot 11 \cdot 12\cdot 13}{2 \cdot 3 \cdot 4 \cdot 5 \cdot 5 \cdot 6} = 3 \cdot 11 \cdot 13 = 429.\]
For more on this problem and an explanation of the proof of equation~(\ref{eqn:2}), see \cite{Bressoud:1999}. Again, I leave you with several questions to explore:
\begin{enumerate}
\item In Figure~\ref{fig:7}, count the number of paths by starting at the top. For each possible row, find the numbers of paths from 1, 2, 3, 4, or 5 to that row.
\item Every time we have a vertical molecule, its position is marked by an integer that appears in one row of a monotone triangle but not in the row below. When we trace the path that corresponds to this monotone triangle, we will have a path segment for which the row at the upper end has at least one integer that does not appear in the row at the bottom end. We assign a {\bf weight} to each path segment, equal to the number of integers in the row above that do not appear in the row below. The number of vertical molecules in the sheet of square ice is the sum of the weights along the corresponding path. In Figure~\ref{fig:7}, find all paths of weight 4.
\item In Figure~\ref{fig:7}, instead of finding the total number of paths from 12345 to each row, break it down so that at each row you record the number of paths of each possible weight. How many of the monotone triangles of size 5 correspond to paths of weight 0, 1, 2, 3?
\item For any size monotone triangle, how many paths of weight 0 are there?
\item Let $\mathcal{M}_n$ denote the set of monotone triangles of size $n$. For each $M$ in $\mathcal{M}_n$, let $w(M)$ be the weight of the corresponding path. Calculate the sum
\[ \sum_{M\in\mathcal{M}_n} 2^{w(M)} \]
for $n =$ 1, 2, 3, 4, and 5. Guess the general formula for this sum.
\end{enumerate}
\bibliographystyle{plain}
\bibliography{ASM-MTF}
\end{document}