How many different ways to fill a nonnegative integer matrix with fixed column and row sums

Question

Given an $m$ by $n$ matrix, what is the general, closed-form formula to calculate how many different ways we can fill this matrix with nonnegative integers given the required sums of each row, $r_1, r_2, ..., r_m$ and of each column, $c_1, c_2, ... c_n$?

Example:

╭───┬───┬───╮
│ 1 │ 0 │ 2 │ =3
├───┼───┼───┤
│ 0 │ 2 │ 0 │ =2
└───┴───┴───┘
  =1  =2  =2

is one solution to a 2-by-3 matrix where $c_1=1, c_2=2, c_3=2, r_1=3, r_2=2$

Edit:

I'm looking for some combinatorial properties I can take advantage of from this closed-form formula, similar to the multinomial theorem.

Answer 1

If you insist that the "nonnegative numbers" you fill your matrix with are in fact nonnegative integers, this is a well studied problem. The objects you're describing often go by the name contingency tables (or frequency tables) and we term the specified row and column sums the margins of the table. Computing the number of contingency tables for given margins is an important problem in a lot of different branches of mathematics.

Specifically, we are interested in the following. Given two margin constraints, $r = (r_1,\dots,r_m)$ and $c = (c_1,\dots,c_n)~$ (on the rows and columns respectively) consider the set of all $m \times n$ tables satisfying these constraints: $$ \Sigma_{m,n}(r,c) = \left\{ A = (a_{ij})_{i=1,j=1}^{m,n} : \sum_{i=1}^m a_{ij} = c_j \text{ and } \sum_{j=1}^n a_{ij} = r_i\right\}. $$ The problem is then to find the cardinality $\left| \Sigma_{m,n}(r,c) \right|$.

You can see a brief overview of the problem (and a recursive algorithm to answer your question) in "Counting and Enumerating Frequency Tables with Given Margins" by Francesca Greselin. Therein it is mentioned that exact answers are already known in some very special cases. If we want to do the general calculation efficiently there are (randomized) approximation algorithms known when we impose additional constraints, but one should not hope to find an efficiently computed closed form expression in the general case due to complexity assumptions. I think a good bit of evidence for the the difficulty of the problem is taken from the paper: given margins $r = c = (15,15,15,15,15)$ there are $1,9208 \ldots \times 10^{50}$ tables. There are also constructions relating this computation to other well known combinatorial questions for which we do not expect there to be a computationally efficient answer for.