A way to fill a finite grid (one box after the other) is called *collinear* if every newly filled box (the first excepted) is vertically or horizontally collinear with a previously filled box. See the following example:

Let $g(m,n)$ be the number of collinear ways to fill a $m$-by-$n$ grid. Note that $g(m,n) = g(n,m)$.

**Question**: What is an explicit formula for $g(m,n)$?

*Conjecture* (user44191): $g(m,n)=m!n!(mn)!/(m+n-1)!$.

*Definition* (user44191): Let $g(m,n,i)$ be the number of collinear ways to fill $i$ boxes in a $m$-by-$n$ grid such that every row and every column contain at least one filled box.

*Remark*: $g(m,n) = g(m,n,mn)$.

*Proposition* (user44191): Here is a recursive formula for $g(m,n,i)$:

- $g(1,1,1) = 1$.
- If $m=0$ or $n=0$ or $ i< \min(m,n)$, then $g(m,n,i) = 0$.
- $g(m,n,i+1)=(mn-i) g(m,n,i) + mn g(m-1,n,i) + mn g(m,n-1,i).$

*Proof*: The two first points are obvious. We consider the number of collinear ways to fill $i+1$ boxes in a $m$-by-$n$ grid such that every row and every column contain at least one filled box.

There are three cases, corresponding to the three components of the recursive formula:

- The last filled box is not the only filled box in its row and not the only filled box in its column.
- The last filled box is the only filled box in its row.
- The last filled box is the only filled box in its column.

By the collinear assumption, 2. does not overlap 3. $\square$

One way to answer the question is to prove the conjecture using the above recursive formula.

We checked the conjecture for $1\le m \le n \le 5$, using the recursive formula (see below).

*Remark*: This question admits an extension to higher dimensional grids.

*Remark*: This question was inspired by that one.

**Sage program**

```
# %attach SAGE/grid.sage
from sage.all import *
import copy
def grid(m,n,j):
if [m,n,j]==[1,1,1]:
return 1
elif j < min(m,n) or m==0 or n==0:
return 0
else:
i=j-1
return (m*n-i)*grid(m,n,i) + m*n*grid(m-1,n,i) + m*n*grid(m,n-1,i)
def IsFormulaCorrect(m,n):
return grid(m,n,m*n)==factorial(m)*factorial(n)*factorial(m*n)/factorial(m+n-1)
def CheckFormula(M,N):
for m in range(1,M+1):
for n in range(M,N+1):
if not IsFormulaCorrect(m,n):
return False
return True
```

*Computation*

```
sage: CheckFormula(5,5)
True
```