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.

[Example contingency table]
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.