Number of $n \times n$ binary matrices whose rows and columns sum to at most $m$

How many matrices satisfy the following constraints?

1. $n$ rows
2. $n$ columns
3. Cell values are either $0$ or $1$
4. Sum of any row is at most $m$
5. sum of any column is at most $m$

Is there a formula or an efficient algorithm to solve this problem?

• I can solve the cases $m=0$ and $m=1$. Nov 21 '16 at 7:45
• This is the same as the number of digraphs where the in-degree and out-degree are bounded by $m$. Nov 21 '16 at 7:46
• This has some connection to Latin Squares. In particular, we can take an $n\times n$ Latin Square, set the numbers from 1 to $m$ to be 1, and the numbers from $m+1$ to $n$ to be 0. Good news is that this gives a lower bound on your problem. Two problems: 1. the number of Latin squares of size $n$ is an open problem (known bounds are thought to be fairly weak), and 2. it's not clear to me how tight this bound is. In particular, while every Latin square is a solution to your problem, I'm not sure when a solution to this problem can be turned into a Latin Square.
– SamM
Nov 21 '16 at 10:12

Given $1 \leq m \leq n$, we want to determine the cardinality of the following set

$$\{ \mathrm X \in \{0,1\}^{n \times n} \mid \mathrm X 1_n \leq m 1_n \,\land\, \mathrm 1_n^{\top} \mathrm X \leq m \mathrm 1_n^{\top} \}$$

Vectorizing, $\tilde{\mathrm x} := \mbox{vec} (\mathrm X)$, we obtain

$$\bigg\{ \tilde{\mathrm x} \in \{0,1\}^{n^2} : \begin{bmatrix} 1_n^{\top} \otimes \mathrm I_n\\ \mathrm I_n \otimes \mathrm 1_n^{\top}\end{bmatrix} \tilde{\mathrm x} \leq m \begin{bmatrix} \mathrm 1_n\\ \mathrm 1_n\end{bmatrix} \bigg\}$$

or,

$$\bigg\{ \tilde{\mathrm x} \in [0,1]^{n^2} : \begin{bmatrix} 1_n^{\top} \otimes \mathrm I_n\\ \mathrm I_n \otimes \mathrm 1_n^{\top}\end{bmatrix} \tilde{\mathrm x} \leq m \begin{bmatrix} \mathrm 1_n\\ \mathrm 1_n\end{bmatrix} \bigg\} \cap \mathbb Z^{n^2}$$

Thus, we want to count the number of integer points inside a convex polytope, or, in other words, to count the number of solutions a given integer program (IP) has. Take a look at De Loera's survey [0] and the references therein.

[0] Jesús De Loera, The Many Aspects of Counting Lattice Points in Polytopes, 2005.