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

Question

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?

Answer 1

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.