How many ways to fill in a square grid with certain restrictions

Question

Suppose I have a 5x5 grid of squares. I would like to fill in 15 checkmarks in the squares such that (1) each of the 25 square cells contains at most one checkmark, (2) each row has exactly 3 checkmarks, and (3) each column has exactly 3 checkmarks. How many ways are there to fill in these 15 checkmarks?

More generally, suppose I have an $n \times n $ square grid, and I would like to fill in $mn$ checkmarks such that (1) each of the $n^2$ square cells contains at most one checkmark, (2) each row has exactly m checkmarks, and (3) each column has exactly m checkmarks. How many ways are there to do so? If $m=1,$ I think the answer is $n!$. But I am not sure about the general case.

Also, if I have an additional restriction that no checkmarks on the diagonal, i.e., no checkmark in the (1,1), (2,2),... (n,n) cells. How many ways are there?

Thanks very much! Wish all very happy new year!

Answer 1

What you are looking for is the number of matrices in the class $\mathcal A(n,m)$ of $(0,1)$-matrices that are $n\times n$ and have each row and column containing exactly $m$ entries equal to $1$. This is a pretty well-studied question, but an exact answer isn't known except in some small cases.

You are right that for $m=1$, the number is $n!$, as then you are counting the $n\times n$ permutation matrices. A sort of generalization of this was obtained in

Wei, Wan-Di. "The class $\mathfrak A(R,S)$ of $(0,1)$-matrices." Discrete Mathematics 39, no. 3 (1982): 301–305. Journal link

where it is given that the number of such matrices is at least

$$\frac{(n!)^m}{(m!)^n}.$$

I say it is “sort of” a generalization because it is only a lower bound. Again, there is no closed form known for the exact number. I think the most frequently-cited asymptotic results are those of McKay and others, for example see

McKay, Brendan D., Wang, Xiaoji. "Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums." Linear Algebra and its Applications. 373 (2003): 273–287. Journal link

and anything that cites it.

There are other results – and other asymptotic results – out there. A good starting point for more details is the book Combinatorial Matrix Classes by Brualdi.

Finally, note that this is the same as counting balanced regular bipartite graphs. For example, your question is the same as this one where the $d_v$ and $d_c$ of that question are taken to be equal. So you may wish to see the answer – provided by McKay! – appearing there.

Answer 2

The problem amounts to counting binary or $0/1$-matrices with restrictions on row/column sums.

In general, let the row sums be $r(n)=(r_1,\dots,r_n)$ and column sums $c(n)=(c_1,\dots,c_n)$. Obviously, $0\leq r_i, c_j\leq n$ for all $i, j$. Further, let $\mathbf{x}=(x_1,\dots,x_n)$ and $\mathbf{y}=(y_1,\dots,y_n)$ with the multi-exponent notation $\mathbf{x}^{u}=x_1^{u_1}\cdots x_n^{u_n}$. Then, there is this generating function $$\prod_{i,j=1}^n(1+x_iy_j)=\sum_{r(n),c(n)} N(r(n),c(n))\mathbf{x}^{r(n)}\mathbf{y}^{c(n)} \tag1$$ for the enumeration $N(r(n),c(n))$ of the number of binary matrices with row sums $r(n)$ and $c(n)$.

To get back to your question, extract the coefficient $N((k,\dots,k),(k,\dots,k))$ of $$\mathbf{x}^{(k,\dots,k)}\mathbf{y}^{(k,\dots,k)}$$ from the above product in (1).