
  
%guess.tex: 
%%a Plain TeX file by Doron Zeilberger (xx pages)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%end macros
 
\bf
\centerline
{
Dave ROBBINS's ART of GUESSING
}
\rm
\bigskip
\centerline{ {\it 
Doron ZEILBERGER
}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg@math.rutgers.edu} , 
%\hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/.}
First version: April 23, 2004 .
Transcript of an invited talk given
on June 30, 2003, 9:30-10:22 am,
at the Conference celebrating Dave Robbins (Aug. 12, 1942-Sept. 4, 2003),
held (June 29-30, 2003) at the Center
for Communication Research of the Institute for Defense Analyses,
Princeton, NJ.
Accompanying Maple programs, as well as input and output
files discussed in this article, can be viewed and downloaded from
\hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/DaveRobbins/guess.html.}
Supported in part by the NSF.\hfill\break
This version: Feb. 21, 2015, correcting typos in the expressions for $b(n)$ and $a(n)$ in page 9, kindly pointed out by Olivier G\'erard.
} 
}

{\bf Abstract}: {\it I will try to guess how Dave Robbins
guesses such beautiful mathematical results.}

{\bf Dave Robbins}'s $22$ items in {\bf Mathscinet} are but
the tip of an iceberg. At least ninety percent of his work
is classified, and we will have to wait fifty years
to enjoy it. Most people are unaware how much we owe to
such classified work. Everybody knows who Hellman and Diffie,
and Rivest, Shamir, and Adelman are, but how many people ever heard
of their shadow analogs, Malcolm Williamson, Cliff Cocks, and James
Ellis? How many people heard of Oscar Rothaus, who recently passed
away? Yet, his brainchild, {\it Hidden Markov Models}, is a household
name in speech recognition, bioinformatics and elsewhere.

 Luckily, the unclassified ten percent of Dave's work 
is more than enough to make him immortal. Besides, Dave is one of
the greatest problem posers and problem solvers I know,
and I am sure that the classified work presents to him lots
of challenges that he so excels in.


Our story starts a long long time ago, with {\bf Patriarch Abraham},
who, at least according to tradition, authored {\it Sefer Yetsira},
``The book of Creation'', a Cabalistic text that was compiled
about 1700 years ago. The Cabala is a Combinatorial 
`Theory of Everything', both spiritual and physical, and
anagrams (of Hebrew letters), called {\it temurot} are
of fundamental importance.

There you can find the following assertions.

``{\it two stones make two houses},\hfill\break
{\it three stones make six houses },\hfill\break
{\it four stones make four and twenty houses},\hfill\break
{\it five stones make a hundred and twenty  houses},\hfill\break
{\it six stones make twenty and seven hundred  houses},\hfill\break
{\it seven stones make forty and five thousand houses}'',\hfill\break
and it concludes: \hfill\break
``{\it from then on, you get what
the mouth can't utter and the ear can't hear''.}

This was generalized many years later by Rabbi Levi
Ben Gerson, who in his 1321 `Book of Number' stated and
{\it proved} a very general theorem.

{\bf Theorem:} The number of houses one can build from $N$ stones
equals one times two times $\dots$ times $N$.

Levi's proof is one page long, and would meet the standards
of rigor of the strictest contemporary referee.

Levi Ben Gerson, whom I doubt any of you ever heard of, was one
of the greatest mathematicians and astronomers of the late middle ages,
and was also a great expositor. No one in this audience, from
Reformer Andy Gleason all the way to Counter-Reformer George
Andrews, could disagree with Levi's following quote:

``{\it In order to be a good computer it is necessary to
Understand the methods of calculations.}''

Of course, by `computer' he meant a {\it human} computer. In order
to achieve this pedagogical goal, Levi Ben Gerson divided his
book into a theoretical part, complete with rigorous proofs
\`a la Euclid, and an algorithmic part, with detailed examples.

Five hundred and forty five years later, another cleric,
{\it Reverend Charles Lutwidge Dodgson} wrote
({\it Proc. Royal Soc.} {\bf 84} (1866), 150-155) an
article entitled {\it Condensation of Determinants} 
and subtitled
{\it Being a new and brief method for computing their
arithmetical values}.

Here is an example, taken from Dodgson's paper:





$$
\pmatrix{
-2 & -1 & -1 & -4 \cr
-1 & -2 & -1 & -6 \cr
-1 & -1 & 2 & 4 \cr
2 & 1 & -3 & -8 \cr} \quad 
\rightarrow \quad
\pmatrix{
3 & -1 & 2 \cr
-1 & -5 & 8 \cr
1 & 1 & -4 \cr} \quad 
\rightarrow \quad
\pmatrix{
8 & -2 \cr
-4 & 6 \cr} \quad 
\rightarrow \quad -8 .
$$
Each iteration consists of forming a new matrix by
 taking consecutive $2$ by $2$ minors of the current matrix,
and dividing by the corresponding entry of the previous matrix
(where the $0^{th}$ matrix consists of all $1$'s).

The obvious drawback of this method, as a numerical procedure,
is that, as Dodgson put it, ``{\it The process cannot be continued when
ciphers occur}''. To get around this, our dear Reverend `cheats' and
uses row and/or column operations, in other words, Gaussian elimination,
that by the way has the same computational complexity. The advantage
of Dodgson's method is that all divisions are exact, so if the entries
of our matrix are integers, all intermediate results will be integers
as well.

Dodgson's method can be phrased, symbolically, as follows.

{\bf Initial Conditions:} 
$$
A^{(0)}_{i,j}=1 \quad ; \quad
A^{(1)}_{i,j}=a_{ij} \quad, \quad 1 \leq i, j \leq n \quad .
$$

{\bf Iteration Step:} For $2 \leq k \leq n$, $1 \leq i,j \leq n-k+1$,
$$
A^{(k)}_{ij}=
{
{A^{(k-1)}_{ij} A^{(k-1)}_{i+1,j+1}-A^{(k-1)}_{i,j+1} A^{(k-1)}_{i+1,j} }
\over
{A^{(k-2)}_{i+1,j+1} }
} \quad .
\eqno(CLD) 
$$
{\bf Final Output:} $\det A=A_{1,1}^{(n)}$.

If $A=(a_{ij})$ is a {\it symbolic} (generic) matrix, then
the final output would be the symbolic determinant:
$$
\det A =
\sum_{\pi \in S_n} (sgn \, \pi) \prod_{i=1}^{n} a_{i,\pi(i)} \quad,
$$
which is a sum parameterized by permutations. Of course
using this formula to actually compute numerical determinants
could cost you your job, as I found out the hard way\footnote{$^2$}
{\eightrm \raggedright
In the Summer and Fall of 1968, between high-school and the
army, I worked, as a Fortran programmer, at the Applied
Math Dept. of the Weizmann Inst. of Science, and implemented
this formula in order to compute numerical determinants.
My mentor, a graduate student, was so shocked that he
decided not to use me any more. But this turned out
for the best, since I immediately
found a nicer and more patient mentor, that lead to my first
publication at the tender age of 18.}.

About $115$ years later (ca. 1980), another genius, 
Dave Robbins, our birthday boy, in collaboration with
Howard Rumsey, had a brilliant idea.

Replace the ${\bf -1}$ by ${\bf lambda}$ and let
$$
A^{(k)}_{ij}=
{
{A^{(k-1)}_{ij} A^{(k-1)}_{i+1,j+1}+\lambda
A^{(k-1)}_{i,j+1} A^{(k-1)}_{i+1,j} }
\over
{A^{(k-2)}_{i+1,j+1} }
} \quad ,
\eqno(\lambda-CLD)
$$
and {\it define} the $\lambda$-determinant, $\det_\lambda A$,
to be equal to the final output, $A_{1,1}^{(n)}$.
Surprisingly, this turns out to be a (Laurent) polynomial in the entries!

Using the now long-defunct computer-algebra program {\bf Altran},
Dave Robbins and Howard Rumsey first conjectured, and then
{\it proved}, the amazing generalization of the expanded form
of the symbolic determinant:
$$
det_{\lambda} (A)=
\sum_{B \in ASM(n)}
\lambda^{I(B)} (1+ \lambda^{-1})^{N(B)} \prod_{1\leq i,j \leq n}
a_{ij}^{B_{ij}} \quad,
\eqno(DaveHoward)
$$
where $ASM(n)$ is the set of now famous {\it alternating sign matrices},
to be described shortly, $I(B)$ is the so-called 
{\it number of inversions} and $N(B)$ is the number of $(-1)s$.
Note that when $\lambda=-1$, only those ASMs with
$N(B)=0$ contribute to the sum, and one gets back the
formula for the traditional determinant.

The {\it discovery} of this natural object was a beautiful example
of what today is called {\it Experimental Mathematics}, 
that is becoming increasingly fashionable.
But Dave was an `Experimental Mathematician when Experimental Math
was not yet cool'. Also his tools, about 25 years ago, were
much more primitive. With the benefit of hindsight, and much
more powerful software and hardware, it is fun to `re-enact'
in Maple (for example), his beautiful discovery, {\it ab initio}.

Here are the few lines of Maple code needed:

{\tt
Tg:=proc(A,B,n,g) local i,j: \hfill\break
[seq([seq(normal(expand((B[i][j]*B[i+1,j+1]+ \hfill\break
g*B[i+1][j]*B[i][j+1])/A[i+1][j+1])),j=1..n-1)],i=1..n-1)]: end: 

det1g:=proc(B,g) local A,n,i,B1,B1o: \hfill\break
n:=nops(B): A:=[[1\$n]\$n]: B1:=B: for i from 1 to n-1 do \hfill\break
B1o:=B1:  B1:= expand(Tg(A,B1,n-i+1,g)): A:=B1o: od: \hfill\break
expand(B1[1][1]):end:

Detg:=proc(n,b,g) local i,j:
expand(det1g([seq([seq(b[i,j],i=1..n)],j=1..n)],g)):end: 

Dave:=proc(t,b,n) local i,j: 
[seq([seq(degree(t,b[i,j]),j=1..n)],i=1..n)]:end: 

MRR:=proc(n) local b,g,A,i: 
A:=Detg(n,b,g): {seq(Dave(op(i,A),b,n),i=1..nops(A))}:end:

MRRp:=proc(n) local A,i: with(linalg):A:=MRR(n): \hfill\break
seq(print(matrix(n,n,A[i])),i=1..nops(A)):end:
}

Procedure {\tt Tg} is an implementation of $(CLD)$ with
$A=A^{(k-2)}$ and  $B=A^{(k-1)}$, outputting $A^{(k)}$.

Procedure {\tt det1g} iterates {\tt Tg} $\,\, n-1 \,\,$ times, thereby
computing the $\lambda-$ determinant of an arbitrary
(square) matrix $B$. I represent matrices in Maple as
lists of lists, to preserve their combinatorial nature, in order
not to get contaminated with irrelevant linear-algebra data structures.

Procedure {\tt Detg} applies Dodgson's rule (i.e. Procedure
{\tt det1g}) to the {\it generic} $n \times n$ matrix
$(b[i,j])_{1 \leq i, j \leq n}$, where the
$b[i,j]$ are {\it symbolic}, i.e. {\it commuting indeterminates}.

For any specific integer $n$, $Detg(n,b,g)$ is a huge 
{\it Laurent polynomial} in the $n^2+1$ variables
$b_{i,j}$ and $g$. Let's forget about the $g$ for now,
and consider it as a Laurent polynomial in the $b_{i,j}$
with coefficients that are polynomials in $g$. But
a {\it poly}-nomial is a linear combination of
{\it mono}-mials, and a natural question is: which of the
monomials show up?
Given a monomial, we can look at the exponents of the
variables $b_{i,j}$, and get a certain matrix. Hence
characterizing the monomials 
$$
\prod_{1 \leq i, j \leq n} b_{i,j}^{B_{i,j}}
$$
is equivalent to characterizing the integer-matrices
$(B_{i,j})_{1 \leq i,j \leq n}$.
Procedure {\tt Dave} is simply the translation from
monomials to exponent-matrices.

Finally, Procedure {\tt MRR} lists all the exponent-matrices of
the monomials that show up in {\tt Detg(n,b,g)}, and
{\tt MRRp(n)} prints them out `nicely'.


Once I finished writing the above Maple code ,
my computer
was ready to re-enact the historic discovery of
Alternating Sign Matrices by Dave Robbins, that he did about
twenty-five years ago.

For example, typing {\tt MRRp(3) } yields:
$$
\pmatrix{
1 & 0 & 0 \cr
0 & 1 & 0 \cr
0 & 0 & 1 \cr} \quad 
\pmatrix{
1 & 0 & 0 \cr
0 & 0 & 1 \cr
0 & 1 & 0 \cr} \quad 
\pmatrix{
0 & 1 & 0 \cr
1 & 0 & 0 \cr
0 & 0 & 1 \cr} \quad 
\pmatrix{
0 & 1 & 0 \cr
0 & 0 & 1 \cr
1 & 0 & 0 \cr} \quad 
$$
$$
\pmatrix{
0 & 0 & 1 \cr
1 & 0 & 0 \cr
0 & 1 & 0 \cr} \quad 
\pmatrix{
0 & 0 & 1 \cr
0 & 1 & 0 \cr
1 & 0 & 0 \cr} \quad 
\pmatrix{
0 & 1 & 0 \cr
1 & -1 & 1 \cr
0 & 1 & 0 \cr} \quad .
$$
Perhaps the case $n=3$ is not enough to see what is going on, but
you don't have to be a Dave Robbins to be able, after
glancing at the output of ``{\tt MRRp(5);}'' \hfill\break
(see {\tt http://www.math.rutgers.edu/~zeilberg/DaveRobbins/oMRR5}),
to notice that these matrices have

(i) entries that are taken from $\{-1,0,1\}$ ,\hfill\break 
(ii) row- and column- sums equal to $1$, \hfill\break
(iii) in each row and column, the non-zero entries
alternate in sign,

{\it et voil\`a}, we have re-discovered Dave Robbins's
immortal object, that he named {\it Alternating Sign Matrices}
(henceforth ASM).

Once we have the notion of ASM, it is not hard, with Maple once again,
to conjecture $(DaveHoward)$. Just
find the coeff. corresponding to each of the monomials,
and {\tt factor} it, and realize that the coeff. of the
monomial that corresponds to $B_{i,j}$ is
$g^{I(B)} (1+1/g)^{N(B)}$, where $I(B)$ is the
{\it number of inversions} (appropriately defined) and
$N(B)$, even more simply, is the number of $-1$'s in $(B_{i,j})$.

An $n \times n$ ASM with no $-1$'s is simply a {\it permutation-matrix}
of order $n$, and their number, thanks to Levi Ben Gerson, equals
$n!$. The next natural question that Dave and his collaborators asked
was: How many $n \times n$ ASM's are there?
The Mills-Robbins-Rumsey conjecture was yet another tour-de-force
in {\it experimental mathematics}, long before that term existed.

Before anyone, even Dave, can conjecture an explicit expression
for an enumerating sequence, we need at least ten terms
(unless the sequence is really trivial). How can we crank out, say,
$\{ \vert ASM(n) \vert \}_{n=1}^{20}$? Definitely {\bf not} by
typing

{\tt seq(nops(MRR(n)),n=1..20)} \quad.

This will explode by $n=8$ (even nowadays), because of the
super-exponential growth of the enumerating sequence, that
by the way, looks like
$$
\matrix{
1  \cr
2  \cr
7  \cr
42 \cr
429 \cr
7436 \cr
218348 \cr
10850216 \cr
911835460 \cr
129534272700 \cr
31095744852375 \cr
12611311859677500 \cr
8639383518297652500 \cr
9995541355448167482000 \cr
19529076234661277104897200 \cr
64427185703425689356896743840 \cr
358869201916137601447486156417296 \cr
3374860639258750562269514491522925456 \cr
53580350833984348888878646149709092313244 \cr
1436038934715538200913155682637051204376827212 \cr
64971294999808427895847904380524143538858551437757 \cr
} \quad .
$$
Note the parabolic shape 
indicating that the rate of growth is $10^{O( n^2)}$.

How did Dave et. al. actually find the first $20$ or so
members of the enumerating sequence for ASMs, that enabled
them to make their beautiful conjecture? First they needed
a more {\bf enumeration-friendly data-structure}.
Starting with an ASM, Dave first formed the partial
column-sums (for each and every column) yielding, e.g.
$$
\pmatrix{
0 & 0 & 1 & 0 & 0 \cr
0 & 0 & 0 & 1 & 0 \cr
1 & 0 & 0 & -1 & 1 \cr
0 & 1 & -1 & 1 & 0 \cr
0 & 0 & 1 & 0 & 0 \cr
} 
\quad \rightarrow
\pmatrix{
0 & 0 & 1 & 0 & 0 \cr
0 & 0 & 1 & 1 & 0 \cr
1 & 0 & 1 & 0 & 1 \cr
1 & 1 & 0 & 1 & 1 \cr
1 & 1 & 1 & 1 & 1 \cr
} \quad .
$$
Because of the {\it alternating} condition, the new matrix has
all its entires  $0$'s and $1$'s, and because every column
starts and ends with a $1$, the bottom row (that gives the
respective column-sums), is the `all-ones' row.
The next thing to do is to {\it compactify} the information 
by recording, for
each row, the location of the $1$'s. In this example we get
$$
\matrix{
 & & & &3 & & &  & \cr
 & & & 3& &4 & &  &  \cr
 & & 1& &3 & &5 & & \cr
 &1 & &2 & &4 & & 5 &  \cr
1 & &2 & & 3&  &4 &  & 5  \cr
} \quad .
$$
Dave called these triangles {\bf monotone triangles}.
The ASM conditions are easily seen to translate to the
conditions that the entries in each row are {\bf strictly}
increasing, and every entry is weakly between the two entries
right below it. If you relax the condition that the
the entires in every row are {\it strictly} increasing, and
only insist on {\it weak}-increase, then these `new' creatures
are classical: the so-called {\bf Gelfand-Zeitlin} patterns,
that, in turn, are equivalent to even more classical 
algebraic-combinatorial objects: Young-tableaux!
Using classical stuff about Schur
functions, one easily gets that the number of Gelfand-Zeitlin
patterns with bottom row equaling $1 2 \dots n$ is 
$$
2^{n(n-1)/2} \quad.
$$
Is there a `nice' formula for the {\bf strict} analog?
Well, let's continue in our efforts to compile a table
of the first $20$ entries, and perhaps we'll see some `pattern'
in the enumerating sequence for these patterns.

As almost always in enumeration (and elsewhere), one needs
to consider a more {\it general} problem, that would hopefully
enable a {\bf recurrence scheme}.

So let's not be so narrow-minded and only try to find
the number of monotone-triangles whose bottom row is
$1 2\dots (n-1) n$, and instead define
$F(a_1, \dots, a_n)$ to be the number of monotone triangles
whose bottom row is $a_1 \dots a_n$.

Now once the bottom row is fixed at $a_1 \dots a_n$,
what can the second-row from the bottom be?
Let it be $b_1 \dots b_{n-1}$, then, clearly:
$$
a_1 \leq b_1 \leq a_2 \leq b_2 \leq \dots \leq b_{n-1} \leq a_n
\eqno(Cond1)
$$
and
$$
b_1 < b_2 < \dots < b_{n-1} \quad .
\eqno(Cond2)
$$
and
$$
F(a_1, \dots, a_n)=
\sum_{(b_1, \dots , b_{n-1})}
F(b_1, \dots, b_{n-1}) \quad,
\eqno(Recurrence)
$$
where the summation is over all the $b$'s that satisfy $(Cond1)$ and
$(Cond2)$.

Now, of course, $F(a_1, \dots, a_n)$ was only a
{\it stepping-stone} for computing $\vert ASM(n) \vert $, and
$$
\vert ASM(n) \vert =
F(1,2, \dots, n) \quad .
$$

Equipped with $(Recurrence)$, it was not too hard to
compute $\vert ASM(n)\vert$ for $n \leq 20$ even way back
in 1980.

The next thing Dave did was to factorize these integers,
and lo and behold, they seemed to be `round', i.e. their
prime factors are small. Assuming that you have already
implemented the above procedure to enumerate ASMs, and called
it {\tt a(n) }, then typing

{\tt seq(ifactor(a(i)),i=1..7);}

would yield

$$
1,  (2),  (7),  (2)  (3)  (7),  (3)  (11)  (13),  (2)^2   (11) (13)^2 ,
(2)^2(13)^2(17)(19)  \quad .
$$
So there must be something going on here. But how did Dave {\it conjecture}
the right formula? Well, `roundness' usually means that there is
an expression featuring factorials. The claim to fame of the
factorial function $f(n):=n!$ is that the {\it ratio}
$f(n+1)/f(n)$ equals $n$, and in general, any product and/or quotient of
factorials of affine-linear expressions has the property that
$f(n+1)/f(n)$ is a {\it rational function} of $n$.

So let's investigate the ratios
$$
b(n):={{a(n+1)} \over {a(n)} } \quad,
$$
but, alas, they still do not seem to be given by a rational function.
But why not {\it do it again?}. Let's take the
`ratios of ratios', and investigate
$$
c(n):={{b(n+1)} \over {b(n)}}={{a(n) a(n+2)}  \over {a(n+1)^2}}
 \quad,
$$
and try the {\it ansatz} of rational functions.
After trying, in vain, rational functions of degree $1$,
we are naturally lead to try 
$$
c(n)= {{\alpha n^2 + \beta n + \gamma}
\over {\alpha' n^2 + \beta' n + \gamma'}} \quad,
\eqno(Ansatz)
$$
for some, as yet, {\it undetermined} coefficients
$\{\alpha, \beta, \gamma, \alpha', \beta', \gamma'\}$.
Now all we need is six equations to determine
these six unknowns. But, just like in curve-fitting in
experimental science, or sequence-guessings
in IQ tests,  we need some over-determination, so let's plug in
$(Ansatz)$, $n=0,1,2,,3,4,5,6$ getting the system of equations
(I am reproducting them here for pedagogical reasons, of course,
in real life it is all done automatically and internally on the
computer):
$$
{{1\cdot 7} \over {2^2}} =
{{\alpha \cdot 1^2 + \beta \cdot 1 + \gamma}
\over {\alpha' \cdot 1^2 + \beta' \cdot 1 + \gamma'}} \quad, \quad
{{2 \cdot 42} \over {7^2}} =
{{\alpha \cdot 2^2 + \beta \cdot 2 + \gamma}
\over {\alpha' \cdot 2^2 + \beta' \cdot 2 + \gamma'}} \quad, \quad
{{7\cdot 429} \over {42^2}} =
{{\alpha \cdot 3^2 + \beta \cdot 3 + \gamma}
\over {\alpha' \cdot 3^2 + \beta' \cdot 3 + \gamma'}} \quad, 
$$
$$
{{42 \cdot 7436} \over {429^2}} =
{{\alpha \cdot 4^2 + \beta \cdot 4 + \gamma}
\over {\alpha' \cdot 4^2 + \beta' \cdot 4 + \gamma'}} \quad, \quad
{{429 \cdot 218348} \over {7436^2}} =
{{\alpha \cdot 5^2 + \beta \cdot 5 + \gamma}
\over {\alpha' \cdot 5^2 + \beta' \cdot 5 + \gamma'}} \quad, 
$$
$$
{{7436 \cdot 10850216} \over {218348^2}}=
{{\alpha \cdot 6^2 + \beta \cdot 6 + \gamma}
\over {\alpha' \cdot 6^2 + \beta' \cdot 6 + \gamma'}} \quad .
$$
Clearing denominators, and {\tt solve}-ing the resulting
system of linear equations, Maple answers with the
{\it conjecture} 
$$
c(n)= {{3(3n+4)(3n+2)}
\over {4(2n+3)(2n+1) }} \quad.
\eqno(ConjectureRatRat)
$$
To give it more plausibility, we can now test it for the
first $20$ or whatever values of $c(n)$ that we have.

Unfolding the ratio, we get immediately 
$$
b(n)= {
{{3n+1 \choose {2n+1}}}
\over {{2n} \choose {n} }} \quad,
\eqno(ConjectureRat)
$$
that, in turn, implies
$$
a(n)=\prod_{j=1}^{n}
{
{
{{3j-2} \choose {2j-2}}
}
\over 
{
{{2j-2} \choose {j-1} }
} 
}
\quad, 
$$
or equivalently:
$$
a(n)=\prod_{j=0}^{n-1}
{{(3j+1)!} \over {(n+j)!}} \quad.
\eqno(MRRconjecture)
$$

But, if this is not evidence enough for you, Dave et. al.
found much more compelling evidence, by discovering a
beautiful {\it refinement} of their amazing conjecture.

It is obvious that the bottom row of any ASM can only
have one $1$ and no $-1$'s (or else it wouldn't be
{\it alternating}). Let $A(n,k)$ be the number of
$n \times n$ alternating sign matrices with the
sole $1$ of the bottom row residing at the $k$-th column.
Equivalently, $A(n,k)$ is the number of {\it monotone triangles}
whose bottom row is $1,2, \dots, \hat{k}  \dots, n$.
In terms of $F$ defined above by $(Recurrence)$, we have
$$
A(n,k)=F(1, 2, \dots, k-1,k+1, \dots , n ) \quad .
$$
Now Dave formed the famous {\it Robbins triangle},
whose rows list
$A(n,1),A(n,2), \dots, A(n,n)$ ($n \geq 2$):
$$
1,1
$$
$$
2,3,2
$$
$$
7,14,14,7
$$
$$
42,105,135,105,42
$$
$$
429,1287,2002,2002,1287,429  \quad.
$$
Next Dave took the {\it ratios} of neighbors in each row,
getting
$$
1
$$
$$
2/2
$$
$$
2/3 \quad 3/2
$$
$$
2/4 \quad 5/5 \quad 4/2
$$
$$
2/5 \quad 7/9 \quad 9/7 \quad 5/2 \quad.
$$
Let's take a look at the second and fourth row. Why write
$2/2$ and not $1/1$, $2/4$ and not $1/2$, $5/5$ and not $1/1$
(and similarly for ratios in rows further down, that I did not
display). After all, once you renounce writing fractions in their
reduced (canonical) forms, there are {\it infinitely} many
possibilities (why not write $1/2$ as $1003/2006$, say?).
According to Dave, this was `the only creative part', i.e.
deciding {\it how} to express the fractions so that a  {\it pattern}
emerges. According to some human supremacists, it is this gift
that distinguishes human-kind from machine-kind. A priori we have
a `search-space' that is infinitely  large, but smart humans
like Dave Robbins have a knack for cutting this infinite haystack
to a very manageable one.

Anyway, once Dave `reduced' the fractions in the `right' way, 
both numerators and denominators formed, amazingly, Pascal-like
triangles, with the same rule of formation, only different
initial conditions, and it followed immediately that
$$
{{A(n,k)} \over {A(n,k+1)}}=
{
{ 
{{n-2} \choose {k-1}} + {{n-1} \choose {k-1}} 
} 
\over 
{ 
{{n-2} \choose {k-1}} + {{n-1} \choose {k}}
} 
}  \quad,
$$
which easily simplifies to
$$
{{A(n,k)} \over {A(n,k+1)}}=
{{k(2n-k-1)} \over {(n-k)(n+k-1)}} \quad .
$$

With the benefit of hindsight, it turns out that Dave's
very creative human heuristic guessing was a
{\bf red herring}, even a {\bf category mistake}, since
the ratios turned out to be {\it rational functions}, not
{\it quotients of binomials}.

Nowadays, if you suspect that a discrete function of two
variables, in our case
$$
B(n,k):={{A(n,k)} \over {A(n,k+1)}} \quad ,
$$
is a rational function, just use a Maple procedure like
my own {\tt GuessRat}, to guess the rational function, 
by plugging-in specific values, just like we did above for 
$c(n)$, the `ratio of ratios' sequence of $a(n)$.

Here are the few lines of Maple code needed to {\it re-enact}
the discovery of the {\it Refined Alternating Sign Matrix Conjecture}.

{\tt
U:=proc(a) local n,i,j,lu:option remember: \hfill\break
n:=nops(a): if n=1 then  RETURN({[]}) : elif n=2 then \hfill\break
RETURN({seq([i],i=a[1]..a[2])}) : \hfill\break
else lu:=U([op(1..n-1,a)]): \hfill\break
{seq(seq([op(lu[i]),j],j=max(lu[i][n-2]+1,a[n-1])..a[n]),
i=1..nops(lu))}: \hfill\break
fi:  end:\hfill\break

F:=proc(a) local gu,i: option remember: \hfill\break
if nops(a)=1 then 1 else gu:=U(a): add(F(gu[i]),i=1..nops(gu)):fi:end:

An:=proc(n) local i: F([seq(i,i=1..n)]):end: 

Ank:=proc(n,k) local i: F([seq(i,i=1..k-1),seq(i,i=k+1..n)]):end:

Bnk:=proc(n,k): Ank(n,k)/Ank(n,k+1):end:

GuessASM:=proc(n,k,d) local x,y: \hfill\break
subs({y=k, x=n-k}, GuessRat((x,y)->Bnk(x+y,y),[x,y],d,1)):
end:

}

Here, procedure {\tt U(a)} recursively finds the set of $b$'s
satisfying $(Cond1)$ and $(Cond2)$ above, while
procedure {\tt F(a)} implements $(Recurrence)$.
{\tt An(n), Ank(n,k)} and {\tt Bnk(n,k)} output
$a(n), A(n,k)$ and $B(n,k)$ respectively, and finally
{\tt GuessASM} guesses the rational function for $B(n,k)$.
It uses procedure {\tt GuessRat}, a guessing
program that uses linear algebra to guess the form of a conjectured
rational function from sufficient data, that can be downloaded from
the webpage of this paper. 

After typing the above lines of code, modulo {\tt GuessRat}
(that is fairly short), typing

{\tt GuessASM(n,k,4) ; }

would immediately return
$$
{{k (2n-k-1)} \over {(n-k)(n+k-1)}} \quad,
\eqno(RefinedRatio)
$$
that is equivalent to the statement of the {\it refined}
Alternating Sign Matrix Conjecture that, in turn, 
implies the original, unrefined, ASM conjecture.

Indeed $(RefinedRatio)$ implies
$$
A(n,k)=
{
{
{{n+k-2} \choose {k-1}}
{{2n-k-1} \choose {n-k}}
}
\over
{
{{2n-2} \choose {n-1}}
}
}\cdot A(n,1) \quad .
$$
But, of course, $A(n,1)=a(n-1)$, so we get,
thanks to the {\it Chu-Vandermonde identity} ,
$$
a(n)=\sum_{k=1}^{n} A(n,k)=
{
{ {{3n-2} \choose {2n-1}}}
\over
{ {{2n-3} \choose {n-2}}}
}a(n-1) \quad,
$$
that enables one to crank out as many terms of the
{\it conjectured} sequence as desired.


Today, whenever you discover a new {\bf integer sequence} you 
go to

{\tt http://www.research.att.com/\Tilde njas/sequences} \quad ,

that gets updated {\bf daily}, and you can find out right away whether
your alleged discovery is indeed new or a {\it re}-discovery.	
Yesterday I went there and entered:

{\tt
1,1,2,7,42,429
}

and immediately got a full description, with lots of references.
But what {\it pleased} me most was the {\it name}:

{\bf Name: Robbins Numbers} .

So Neil Sloane, the Guardian of the 
Integer Sequence Treasure Trove, did the right thing
and named $1,1,2,7,42,429 \dots$ after Dave, thereby
immortalizing him by inducting him  into the class of Fibonacci,
Catalan, Lucas, Bell, and other luminaries. 
This is in spite of the fact that the paper was co-authored with
Bill Mills and Howard Rumsey, and that the Robbins Numbers
were anticipated by George Andrews. I am sure that Bill
and George whole-heartedly agree with Neil's decision
(and Howard would have, had he been alive).

Anyway, in the pre-web {\bf bad old days} of the paper tyranny,
the {\it Handbook of Integer Sequences} 
got updated every $21$ years (the first edition was
1974, the second 1995). But even though there was no Sloane website
back in 1980,
the phone had already been invented, so one could call the
{\it Godfather}, {\bf Richard Stanley}, who, in Dave's words:
{\bf startled} them by telling them that Partitions guru
{\bf George Andrews} has discovered (or rather invented!)
this sequence when he invented {\bf Descending Plane Partitions}.

There is  a very old, still unresolved, philosophical problem.
Is math {\bf invented} or {\bf discovered}? According to my 
Patron  Saint, James Joseph Sylvester, 
some is invented and some is discovered.
I believe that Andrews's descending plane-partitions
belong to the invented part. The definition (that I will
spare you!) is amongst the most contrived and ugly in the whole
of combinatorics. But how could someone with such good taste as
George Andrews even think of inventing a new and artificial
kind of partitions, when they are so many natural kinds to keep
us busy? The answer is the good old {\bf publish or perish} syndrome,
or rather, in George's case (who never had to worry about
perishing with his quality and {\it quantity} of publications):
``{\it I have to publish or else I won't meet my self-imposed quota
of at least ten papers per year}.''

What happened is that George found a powerful new method, that
helped him prove the 80-year-old MacMahon conjecture about
Symmetric Plane Partitions. Having done so, he was looking
for other customers to sell the new method to. Not finding any,
he invented this new nail, that was ideally suited to be hammered
by his new method.

But it was just as well! So one shouldn't look down at
`generalizations for the sake of generalizations', and
`new combinatorial objects for the sake of being enumerable
by an existing method'. Math, like, money, does not smell,
and sometimes the most artificial (to human eyes) math can lead,
directly or indirectly, to exciting and {\bf natural} new math.

In this case, Mills, Robbins, and Rumsey got {\bf hooked}
on plane-partitions, and soon found out about the then
open {\bf Macdonald Conjecture}, that $q$-enumerates the {\bf natural}
class of {\bf Cyclically Symmetric Plane Partitions}.
George Andrews (who else) had then recently accomplished the
`straight enumeration' (the case $q=1$), in a very
complicated {\it Inventionae} paper, but the general
case remained wide open. This conjecture was stated in Ian Macdonald's
classic `{\it Symmetric Functions}', that just came out then, and in
Richard Stanley's book review, in the Bulletin (of the Amer. Math. Soc.), 
Stanley called it 
``{\bf The most interesting conjecture in Enumeration}''.

Dave, being a compulsive (and of course, brilliant) {\bf problem-solver},
taped Stanley's quote on his office door, and assisted by Bill Mills
and Howard Rumsey, proved Macdonald's full conjecture in a seminal
{\it Inventionae} paper.
It was one of the very few papers on combinatorics published back then
by that snooty and fussy periodical.

So MRR never proved their ASM conjecture, but in the process,
proved something at least as interesting. This is the beauty
of math (and life). It is good to have goals, but it is not
so important to achieve them, since in your search for the initial
goals you might find even greater treasures!

I must also mention that Descending Plane Partitions are not so
artificial after all. Later on, Mills, Robbins and
Rumsey found amazing refinements
of the fact that the number of descending plane partitions 
equals the number of ASMs
of the same size, by finding a three-parameter refinement.
This conjecture is still open, as far as I know.

{\bf Postscript: How I Proved the ASM Conjecture}

So far, my account was based on hearsay, conversations with Dave, and his
published works. But now I can start an {\bf eye-witness} account.

		
In May 1982 I was just recently converted to combinatorics, and thanks
to my late mentor, Joe Gillis, I was invited to participate at the
combinatorics Oberwolfach meeting, organized by Dominique Foata.
Now if you know Dominique, you would
know that he always begs people {\bf not} to talk,
and laments that people always insist on giving talks, while it is
much better to have less talks and more time for informal discussions and
interactions (what Foata calls the `spirit of the early Oberwolfach',
before it got ruined by the establishment). So Foata very
reluctantly agrees to have anyone speak for the full $50$ minutes.

But Dave's first talk, about the MRR proof of Macdonald's CSPP conjecture,
was so good, and it hinted at the intriguing ASMs, that Dominique,
(and everyone else!) {\it begged} Dave to give a second fifty-minute
talk, about ASMs and their conjectured enumeration.

So Dave was the first (and as far as I know only) person to give
{\bf two} hour-talks at the {\bf same} Oberwolfach combinatorics meeting.
I remember these talks like they were given yesterday. They were
definitely in the top ten talks that I have ever heard. What is so
captivating about Dave's lecture-style is that  unlike the rest of us,
that try to state things in the most general setting (thereby 
completely obscuring the ideas), Dave went the other way, and made things
as concrete as possible and actually had {\bf numbers} in his talk,
not general formulas. The formulas only came at the end, after the
ideas and concepts were internalized.

On the way back, I was fortunate to share a train-cabin with Dave,
and I asked him lots of questions, and thus started my love-hate
relationship with the  ASM conjecture.

Meanwhile, MRR  found yet another conjecture, that the so-called
{\it Totally Symmetric Self Complementary Plane Partitions}
(TSSCPP) are also enumerated by the Robbins numbers.
Around 1987, I had some rudimentary ideas for proving
ASM=TSSCPP, but since the details seemed daunting,
and proving them equal, while a nice result,  would not yield
the original ASM conjecture, I abandoned the attempt, focusing on more
promising (i.e. easier) problems.

Then came George Andrews's amazing announcement, and proof, of the
TSSCPP conjecture (that these too are enumerated by the Robbins
numbers $1,2,7,42, 429, \dots$), and to my personal delight, George used,
among other tricks of the trade, the so-called 
{\bf Wilf-Zeilberger method}. Anyway, after George's amazing proof,
it made sense to resume my attempts at proving  ASM=TSSCPP, since
it would entail, thanks to George Andrews,
the original conjecture that ASMs are enumerated by
the Robbins numbers.

After a few months, in December 1992, I produced the first version
(about twenty pages), and sent it to yet another snobbish
journal, {\it Journal of the Amer. Math. Soc.}, whose editor was
Andrew Odlyzko, and sure enough, the `anonymous' referee was
Dave (as I immediately suspected and Dave confessed later).
It was then that I started to `hate' Dave. He very quickly found
some {\it gaps}. I then fixed (or rather believed that I did) these gaps,
and Dave found new ones. This process underwent three iterations,
until Andrew Odlyzko sent me a {\it polite-but-firm} E-mail,
that he kindly permitted me to quote.

{\tt
From amo@research.att.com Wed May 11 06:35:00 1994\hfill\break
Date: Wed, 11 May 94 06:34 EDT\hfill\break
To: zeilberg@euclid.math.temple.edu\hfill\break
Subject: paper for JAMS

Dear Doron,

The next message will contain a report on the latest version
of your alternating sign matrix conjecture.  As you can tell
from the tone of the report, this referee is getting a bit
tired of dealing with your manuscript.  Please make sure that
the next revision is really solid before submitting it.

Best regards,\hfill\break
Andrew
}

But Dave was not the only one who was getting tired.
Here is my reply to Andrew Odlyzko.

{\tt
Dear Andrew,\hfill\break
$\quad$ Thanks for the report. I will look at it and 
spend at most a day trying to ``fix'' the ``serious'' ``errors''.
If it would take me more than that, I will resubmit it elsewhere.
I am sure that the proof is very robust. No human 
proof can be ever completely formally correct,
and because of the depth and complexity of this proof it may be NP-complete
to make it water-tight. However, all the ``holes'', if holes there
are, should be a routine thing to fix, albeit time-consuming and
extremely boring.

I will let you know in a day whether I plan to submit a 4th revised
version.  

I am getting tired too from the pedantry of the referee, who very
possibly is David Robbins, who has a vested interest in his
conjecture enjoying a longer longevity than it did, and is
playing the filibuster.

          Best Wishes, Doron
}

(In retrospect, my `filibuster' accusation was wrong.
Dave gave the same careful, `I want to see all the details',
treatment to {\it every} document that he refereed or reviewed, as
I just found out yesterday in the short talks about him by
his colleagues.)

And, finally, here is Andrew Odlyzko's defense of referee
Dave.

{\tt                         
From amo@research.att.com Wed May 11 12:58:27 1994 \hfill\break
To: zeilberg@math.temple.edu \hfill\break
Subject: ASM \hfill\break
Dear Doron, \hfill\break
As far as the alternating sign matrix conjecture is concerned,
I don't think it's just a matter of pedantry, and the second
referee did not think so either.  It won't do to say that the
proof is "robust."  If that were acceptable, then the conjecture
would have been regarded as proved as soon as it was made.
After all, there was numerical evidence for it, and if God
did not want such a beautiful result to be true, why did He
not provide a simple counterexample?  However, mathematics
insists on a higher level of proof than that.  Any respectable
mathematical journal will surely want either a proof that
is verifiable by competent and careful referees, or a clear
statement of what the unproved assumptions are.

Best regards \hfill\break
Andrew
}

Then I got a brilliant idea to make the paper `really solid'.
It had to be `pre-refereed'. So I first fixed the many gaps
(some of them, in fairness to Dave and Andrew, were not so minor),
and then I rewrote the paper (that turned out to be about
seventy-two  pages long) in a {\it structured}, {\it modular},
{\it distributed} fashion, organized into {\it lemmas},
{\it sublemmas},  {\it subsublemmas}, etc. (all the
way to $(sub)^{6}$-lemmas), and asked for volunteers, each of whom
would get one node of the proof-tree, and would only have to check that
the assigned $(sub)^i$-lemma follows from all its children, which are
$(sub)^{i+1}$-lemmas, or in the case of a leaf, just check its proof.
In addition, I wrote a Maple package, {\tt ROBBINS}, that accompanied the
article, that checked {\it empirically} each statement made in the paper.

I sent the solicitation E-mail, that can be looked at:

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/asm/CHECKING} ,

to the $120$ people in my E-mailing list (this was in the
good old, pre-spam days), and got a very good response rate,
more than two thirds. Their reports (on the draft) can be looked at:

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/asm/REPORTS} .

Once I fixed all the numerous (but minor) errors, and implemented
the suggested improvements in exposition, I decided to forget
JAMS, and to submit it to the special issue in honor of Dominique Foata's
60th birthday of the {\it Electronic Journal of Combinatorics}.

So Dave Robbins and Andrew Odlyzko's 
`pedantic' insistence was for the best, since
my ASM proof turned out to be a {\it paradigm} of formal correctness, thanks
to its tree-structure and the many checkers. 
In my humble opinion, this innovative {\it format}, and the pioneering idea
of {\it communal checking}, are even more important than the content of 
my article.
I should also add that
Dave Bressoud served as an independent checker for almost everything.

For the full story, in particular for Greg Kuperberg's shorter
proof, and my proof of the Refined ASM conjecture,
I refer you to Dave Bressoud's masterpiece
{\it Proofs and Confirmations} (Cambridge Univ. Press and Math. Assoc.
of Amer.) .

{\bf PostPostScript}

Other `outside work' (a term used by the IDA spooks to refer to
unclassified math) gems of Dave include

$\bullet$ Continued Fractions over $GF(q)(x)$ \hfill\break
$\bullet$ Expected assignments \hfill\break
$\bullet$ Extension of the classical formulas of Herron and
Brahamgupta to areas of pentagons and beyond.\hfill\break
$\bullet$ Another beautiful explicit conjecture, about volumes
 of certain polytopes (joint with Clara Chan). This
conjecture was also proved by yours truly, but this one
only took one page (but it used the deep Morris-Selberg identity).

{\bf PostPostPostScript}

In addition to the {\it short-term work},  {\it long-term work}, 
and {\it outside work}, Dave also had time to worry about
the well-beings of our children, when he served, to 
almost everyone's satisfaction, on the Princeton Regional
Board of Education for six years, three of them as President.
When he was up for re-election, he asked me to be a signatory
in a campaign ad that appeared in the local Princeton newspapers.
I gladly agreed, and thanks to this, I got my name to be part
of a very impressive list (perhaps the most illustrious list I ever
belonged to). At the risk of sounding like a name-dropper, let me
mention some of the signatories:

{\it Bob Austin, John and Neta Bahcal,
Luis Caffarelli, Freeman and Imre Dyson, Charles and Julie Fefferman,
Chiara Nappi, Deborah Robbins, Miri and Nathan Seiberg, Lee Silver,
Arthur Wightman, Ed Witten}, and last but not least, {\it Doron Zeilberger}.

But my main point is that if all these great people supported Dave,
it must say something, not only about Dave the mathematician, but
about Dave the person.

{\bf Acknowledgement:}  
Many thanks to Andrew Odlyzko for permission to quote
from our E-correspondence, and to
Lynne Butler and
Clara Chan for organizing this great tribute for Dave
while he was still able to enjoy it.

\end







%a(n) = Product(  Binomial(3*j-2, 2*j-1) / Binomial(2*j-3,j-2) , (j=1..n) )

%should be



