## Algebraic Counting of Contingency Tables

The problem in question is to count how many different ways
are there to fill in the entries of a n by m table with non-negative
entries in such a way that the row sums and column sums equal some
preescribed * margins *. For example, How many ways are
there to fill in the 4-by-4 table in the figure? This example has been
appearing in the literature as a "hard" example. The answer,
1225914276768514. It is computed in a few minutes as an example
in the software we introduce below.

The approach we take here is to
use generating function techniques. The details are contained in
the math programming paper "Algebraic Unimodular Counting" by myself and
Bernd Sturmfels, but roughly speaking we generate a rational function the *
BBKLP generating function *,
that carries all the information about the possible tables. The
generating function can then be evaluated to determine the number of
contingency tables by computing a certain limit at the singularity of
the rational function. For large tables the limit process is actually
the heavy part of the computation. We show two examples of special evaluation.
Here you can access several pieces of software that allow you
to compute the generating functions. This software runs in MAPLE V.5.1.
We have divided them by size of the tables:

For counting
4 by 4 tables . The software
we release includes the evaluation of the functions, which are small enough
to use directly MAPLE's limit functions. In the example above the whole
computation (rational function calculation plus limit evaluation) takes
about 5 minutes. We also present software for
4 by 5 tables , the generating
functions generated are moderately large with 900 terms on average.
Here is an example of how to use the programs:

Read a string with the margins leaving out the last row (column) margin.
Thus for the table above the string is a:=[220, 215, 93, 64, 108, 286, 71]:

Finally, type PolytopeLatticepointseries(U,circuits,a ):
Finally, here are two of the examples of evaluation of the generating
function presented in our paper. The files contain a MAPLE worksheet and
the BBKLP series with some variables set to 1.
Mount's example
and a
BIG 4-by-5 table

Another very interesting application of algebraic-symbolic counting
algorithms is a nice connection to combinatorics and
representation theory via KOSTANT's partition
function . Make sure to visit our online demostration.

*
This research was supported by NSF.
*