Number of collinear ways to fill a grid

Question

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:

1. The last filled box is not the only filled box in its row and not the only filled box in its column.
2. The last filled box is the only filled box in its row.
3. 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

Answer 1

We managed to obtain a solution via Stanley's comment above and some manipulations of binomial coefficients. See https://arxiv.org/abs/1809.10263

Answer 2

By the method I used to solve Counting "connected" edge orderings (shellings) of the complete graph, I can show the following: $$ g(m,n) = (mn-1)!\,m!\,n!\sum \frac{b_1 b_2\cdots b_{m+n-2}} {b_{m+n-2}(b_{m+n-3}+b_{m+n-2})\cdots(b_1+b_2+\cdots+b_{m+n-2})}, $$ where the sum is over all sequences $a_1 a_2\cdots a_{m+n-2}$ of $m-1$ $0$'s and $n-1$ $1$'s, and where $$ b_i=\#\{1\leq j<i\,\colon\, a_i\neq a_j\}+1. $$ Does anyone see why this is equal to $m!\,n!\,(mn)!/(m+n-1)!$?

Answer 3

Let me give an alternative proof with only finitely many variables used. It also gives some formulae for the following numbers: "when the filling becomes not collinear for the first time, there are $a$ columns and $b$ rows already used in the filling".

Consider a random enumeration $e_1,e_2,\ldots,e_{mn}$ of the edges of the graph $K_{n,m}$ with parts $N=\{v_1,\ldots,v_n\}$ and $M=\{u_1,\ldots,u_m\}$. We look it as a process: the edges $e_1,e_2,\ldots$ are added consecutively. Denote by $G(k)$ the graph formed by $e_1,\ldots,e_k$. For positive integers $a\leqslant n, b\leqslant m$ denote by $f(a,b)$ the probability of the following event $E(a,b)$:

(i) there exists $k$ such that the graphs $G(1),\ldots,G(k)$ are connected and the vertices of $G(k)$ are $v_1,\ldots,v_a;u_1,\ldots,u_b$; and

(ii) the vertices $v_1,v_2,\ldots,v_a$ appear in the sequence of graphs $G(1),G(2),\ldots$ in this order (that is, the first appearance of $v_i$ is before the first appearance of $v_{i+1}$, for each $i=1,\ldots,a-1$); the same for $u_1,\ldots,u_b$.

Clearly the probability of event (i) itself (without assuming (ii)) equals $a!b! f(a,b)$. So we should prove $f(n,m)=\frac1{(n+m-1)!}$. The key point is the following

Recursion. $f(1,1)=1$, also define $f(a,0)=f(0,b)=0$ for $n\geqslant a\geqslant 2$, $m\geqslant b\geqslant 2$. Then for $n\geqslant a\geqslant 1,m\geqslant b\geqslant 1$ and $(a,b)\ne (1,1)$ we have $$ f(a,b)=\frac{a}{nm-a(b-1)}f(a,b-1)+\frac{b}{nm-(a-1)b}f(a-1,b). \,\quad(1) $$

Proof of recursion. If the vertex $v_a$ appears before than $u_b$, then the event $E(a,b-1)$ happened. Consider the first moment after it happened and the new vertex (not $v_1,\ldots,v_a;u_1,\ldots,u_{b-1})$ appeared. It is the vertex $u_b$ with probability $\frac{a}{nm-a(b-1)}$ (there are $a$ admissible edges and $nm-a(b-1)$ edges using the new vertex in total). That's the first summand, the second analogously corresponds to the case when $u_b$ appears before $v_a$.

Now we solve recurrence (1). I do not know how it should be done in a regular way, so I guessed the answer and proved that it works.

Take a variable $t$ and call a double sequence of rational functions $\varphi(a,b)=\varphi(a,b)(t)$ defined for all non-negative integers $a,b$ appropriate if they satisfy a recurrence $$(t-ab)\varphi (a,b)=a\varphi (a,b-1)+b\varphi (a-1,b)\quad \text{for}\,\,a,b\geqslant 1.$$ So admissible double sequences form a linear space.

Observation. For any $i=1,2,3,\ldots$ the function $$\psi_{i}(a,b):=(-1)^{b-i}\binom{a+b}{a+i}\frac1{(\frac{t}i+b)^{\underline{a+b+1}}}$$ is appropriate. Here we use Knuth's notation $x^{\underline{k}}=x(x-1)\ldots (x-k+1)$. The proof is straightforward.

Proposition. Consider the double sequence $$ h(a,b):=\sum_{i=1}^\infty \left(1+\frac{t}{i^2}\right)\psi_i(a,b) $$ (the summation is of course finite, only upto $i=b$, since for $i>b$ we have $\binom{a+b}{a+i}=0$). Then $h$ is an appropriate double sequence, satisfying $h(1,1)=\frac1{t(t-1)},h(a,0)=h(0,b)=0$ for $a,b\geqslant 2$.

Proof of the proposition. $h$ is appropriate by Observation and linearity of the set of appropriate functions. Relations $h(1,1)=\frac1{t(t-1)}$ and $h(a,0)=0$ are clear. For computing $h(0,b)$ we may look at $h(0,b)$ as a rational function of negative degree and check that all residues are equal to 0. The residue at $t=0$ equals $$\sum_{i=1}^b(-1)^{b-i}\binom{b}i\cdot i=b\sum_{i=1}^b(-1)^{b-i}\binom{b-1}{i-1}=0\quad \text{for}\quad b\geqslant 2.$$ The residues at $t=-ij$, $1\leqslant i,j\leqslant b, i\ne j$, for functions $(1+\frac{t}{i^2})\psi_i(0,b)$ and $(1+\frac{t}{j^2})\psi_j(0,b)$ cancel out.

Main formula. $$f(a,b)=(t-ab)h(a,b)\quad \text{where} \quad t=mn$$ for $1\leqslant a\leqslant n, 1\leqslant b\leqslant m$. (For $a=n,b=m$ the function $h(n,m)$ has a pole at $t=mn$, but the product $(t-mn)h(n,m)$ is well-defined as ${\rm res}_{t=mn} h(n,m)$.)

Proof. Both parts satisfy the same initial conditions $f(1,1)=\frac1{mn}=\frac1{t}=(t-1)h(1,1)$, $f(a,0)=f(0,b)=0$ for $a\geqslant 2$ and the same recurrence (1).

Now for $a=n,b=m$ we get $$f(n,m)={\rm res}_{t=mn}\sum_{i=1}^m\left(1+\frac{t}{i^2}\right)\psi_i(a,b) ={\rm res}_{t=mn} (1+\frac{n}m) \psi_m(n,m)=\frac{1}{(n+m-1)!}$$

Answer 4

Here is some further progress on the problem, without a full solution, based on ideas of Alex Postnikov. Alex's idea is to apply the "multivariate" (or "content-weighted") hook-length formula for Standard Young Tableaux. Everything (everything correct, that is) in this post is due to him.

Richard Stanley reduced the conjectured formula $g(m,n) = m!n!(mn)!/(m+n-1)!$ to showing that $$ \sum_{\alpha} \frac{b^\alpha_1b^\alpha_2 \cdots b^\alpha_{m+n-2}}{b^\alpha_{m+n-2} (b^\alpha_{m+n-2}+b^\alpha_{m+n-3})\cdots (b^\alpha_{m+n-2}+b^\alpha_{m+n-3}+\cdots+b^\alpha_1) } = \frac{mn}{(m+n-1)!}$$ where the sum is over all $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_{m+n-2})$ consisting of $m-1$ 0's and $n-1$ 1's and where $$ b^\alpha_i := \#\{1\leq j < i\colon \alpha_i\neq\alpha_j\} +1.$$

I don't know how to evaluate the above sum, but Alex's technique can be used to give a product formula for a very similar weighted sum over the same objects. Let us define $$ c^\alpha_i := \#\{1\leq j \leq i\colon \alpha_i=\alpha_j\}.$$ Observe that $b^\alpha_i =(i+1)-c^\alpha_i$.

The claim is that $$ \sum_{\alpha} \frac{1}{c^\alpha_{m+n-2} (c^\alpha_{m+n-2}+c^\alpha_{m+n-3})\cdots (c^\alpha_{m+n-2}+c^\alpha_{m+n-3}+\cdots+c^\alpha_1) } = \frac{2^{m-1}2^{n-1}}{(2m-2)! (2n-2)!}$$ where the sum is over the same $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_{m+n-2})$.

To see this, we biject such an $\alpha$ to a Standard Young Tableau of hook shape $(m,1^{n-1})$ in the obvious way: $i+1$ is in the arm of the hook iff $\alpha_i=0$. Then $c^\alpha_i$ is the absolute value of the content of the box containing $i+1$. And now we can directly apply the multivariate hook-length formula; see e.g. Theorem 18 of these notes: RSK via local transformations. In the notation of those notes we set $x_i := |i|$ for all $i \in \mathbb{Z}$.

As mentioned, I don't see immediately how this can be used to say anything about the relevant sum involving $b^{\alpha}_i$'s, but maybe someone else will figure out the approrpriate transformation.

Answer 5

Here's an elementary solution to the following equivalent problem: An $n \times m$ matrix is nice if it contains every integer from $1$ to $mn$ exactly once and $1$ is the only entry which is the smallest both in its row and in its column. Prove that the number of $n \times m$ nice matrices is $(nm)!n!m!/(n+m-1)!$.

For ease of reading, we'll switch the roles of $m$ and $n$ in the problem statement.

After making it continuous, taking complements, and flipping signs, the problem is equivalent to the following: For $1 \le i \le m$, $1 \le j \le n$, define a value independently, identically, and at random $x_{ij} \in U[0,1]$, where $U[0,1]$ is the uniform distribution on $[0,1]$. A pair $(i,j)$ is good if both $x_{ij} \ge x_{iv}$ for all $v$ and $x_{ij} \ge x_{uj}$ for all $u$. Then the probability that there are at least two good pairs $(i,j)$ is exactly $1 - \frac{m! n!}{(m+n-1)!}$.

Let $g$ denote the number of good pairs. Observe that, by a generalized form of the Principle of Inclusion-Exclusion, $$\text{Pr}[g \ge 2] = \sum_{(i_1,j_1),(i_2,j_2)\text{ distinct}}\frac{1}{2!}\text{Pr}[(i_1,j_1),(i_2,j_2)\text{ both good}]$$ $$-\sum_{(i_1,j_1),(i_2,j_2),(i_3,j_3)\text{ pairwise distinct}}\frac{2}{3!}\text{Pr}[(i_1,j_1),(i_2,j_2),(i_3,j_3)\text{ all good}]$$ $$+\sum_{(i_1,j_1),(i_2,j_2),(i_3,j_3),(i_4,j_4)\text{ pairwise distinct}}\frac{3}{4!}\text{Pr}[(i_1,j_1),(i_2,j_2),(i_3,j_3),(i_4,j_4)\text{ all good}]$$ $$\pm\cdots$$ $$=\sum_{k \ge 1}\sum_{(i_1,j_1),(i_2,j_2),\cdots,(i_k,j_k)\text{ pairwise distinct}} \frac{(-1)^k (k-1)}{k!}\text{Pr}[(i_1,j_1),(i_2,j_2),\cdots,(i_k,j_k)\text{ all good}].$$ (Indeed, one can check that $\sum_{k\ge 1}\binom{g}{k}(-1)^k(k-1)$ is $0$ for $g=0,1$, and is $1$ for $g \ge 2$.)

Note that if any two of $(i_1,j_1),(i_2,j_2),\cdots,(i_k,j_k)$ share a row or share a column, then $\text{Pr}[(i_1,j_1),(i_2,j_2),\cdots,(i_k,j_k)\text{ all good}] = 0$. Thus we can rewrite the sum $$\text{Pr}[g \ge 2] = \sum_{k \ge 1}\sum_{(i_1,j_1),(i_2,j_2),\cdots,(i_k,j_k)\text{ pairwise distinct rows, pairwise distinct columns}} \frac{(-1)^k (k-1)}{k!}\text{Pr}[(i_1,j_1),(i_2,j_2),\cdots,(i_k,j_k)\text{ all good}]$$ $$=\sum_{k \ge 1}\sum_{\begin{array}{c} i_1,i_2,\cdots, i_k \text{ pairwise distinct} \\ j_1,j_2,\cdots, j_k \text{ pairwise distinct}\end{array}} \frac{(-1)^k (k-1)}{k!}\text{Pr}[(i_1,j_1),(i_2,j_2),\cdots,(i_k,j_k)\text{ all good}]$$ $$=\sum_{k=1}^{\min (m,n)} (-1)^k (k-1) \binom{m}{k} \binom{n}{k} k! \text{ Pr}[(1,1),(2,2),\cdots,(k,k)\text{ all good}]$$ $$=\sum_{k=1}^{\min (m,n)} (-1)^k (k-1) \binom{m}{k} \binom{n}{k} k! p_k,$$ where $p_k$ is the probability that $(1,1),(2,2),\cdots, (k,k)$ are all good.

Lemma 1. $p_k = \frac{(m+n-k-1)!}{(m+n-1)!}$ for all $1 \le k \le \min (m,n)$

Proof. Without loss of generality assume $\min (m,n) = m$. We'll calculate $q_k = \frac{1}{k!}{p_k}$, which is the probability that $(1,1),(2,2),\cdots, (k,k)$ are all good and $x_{11} \le x_{22} \le \cdots \le x_{kk}$. Equivalently, $q_k$ is the probability that, for each $1 \le i \le k$, $x_{ii}$ is the maximum of the $m+n-2i+1$ numbers $x_{mi},x_{(m-1)i}, \cdots, x_{ii},x_{i(i+1)}, x_{i(i+2)}, \cdots, x_{in}$, and $x_{11} \le x_{22} \le \cdots \le x_{kk}$.

The probability distribution of the maximum of $w$ independently identically distributed uniform random variables over $[0,1]$ is $A_w(t) = \text{Pr}[\max = t] = wt^{w-1}$. Thus, $q_k$ is $\prod_{i=1}^k \frac{1}{m+n-2i+1}$ multiplied by the probability that $z_1 \le z_2 \le \cdots \le z_k$, where each $z_i$ is distributed according to the function $A_{m+n-2i+1}$. We can write $$q_k = \prod_{i=1}^k \frac{1}{m+n-2i+1} \int_{z_1 \le z_2 \le \cdots \le z_k} A_{m+n-1}(z_1)A_{m+n-3}(z_2)\cdots A_{m+n-2k+1}(z_k) $$ $$= \prod_{i=1}^k \frac{1}{m+n-2i+1} \int_{z_1 \le z_2 \le \cdots \le z_k} (m+n-1)z_1^{m+n-2} (m+n-3) z_2^{m+n-4} \cdots (m+n-2k+1) z_k^{m+n-2k}$$ $$= \int_{z_1 \le z_2 \le \cdots \le z_k} z_1^{m+n-2} z_2^{m+n-4} \cdots z_k^{m+n-2k}$$ $$= \int_{z_2 \le z_3 \le \cdots \le z_k}\frac{1}{m+n-1} (z_2^{m+n-1}) z_2^{m+n-4} z_3^{m+n-6} \cdots z_k^{m+n-2k} $$ $$= \int_{z_2 \le z_3 \le \cdots \le z_k}\frac{1}{m+n-1} z_2^{2(m+n)-5} z_3^{m+n-6} \cdots z_k^{m+n-2k}$$ $$= \int_{z_3 \le z_4 \le \cdots \le z_k} \frac{1}{m+n-1} \frac{1/2}{m+n-2} (z_3^{2(m+n)-4})z_3^{m+n-6}z_4^{m+n-8} \cdots z_k^{m+n-2k}$$ $$= \cdots$$ $$= \frac{1}{m+n-1}\frac{1/2}{m+n-2}\frac{1/3}{m+n-3} \cdots \frac{1/k}{m+n-k}.$$

Thus $p_k = k!q_k = \frac{1}{m+n-1}\frac{1}{m+n-2}\frac{1}{m+n-3}\cdots \frac{1}{m+n-k} = \frac{(m+n-k-1)!}{(m+n-1)!}$ as desired. $\blacksquare$

Our desired probability is then $$\text{Pr}[g \ge 2] = \sum_{k=1}^{\min (m,n)} (-1)^k (k-1) \binom{m}{k} \binom{n}{k} k! p_k$$ $$=\sum_{k=1}^{\min (m,n)} (-1)^k (k-1) \frac{1}{k!} \frac{m!n!}{(m-k)!(n-k)!} \frac{(m+n-k-1)!}{(m+n-1)!}$$ $$=\frac{m!n!}{(m+n-1)!}\sum_{k=1}^{\min (m,n)} (-1)^k(k-1)\frac{1}{k!} \frac{(m+n-k-1)!}{(m-k)!(n-k)!}$$

We'll use the method of Snake-Oil for evaluating combinatorial sums. Declare formal variables $a,b$ and consider the formal power series $f(a,b) = \sum_{m,n \ge 1}\sum_{k=1}^{\min (m,n)} (-1)^k(k-1)\frac{1}{k!} \frac{(m+n-k-1)!}{(m-k)!(n-k)!} a^m b^n$. Our desired probability is then $\frac{m!n!}{(m+n-1)!}$ times the coefficient of $a^mb^n$ in this power series. However, we can switch the order of summation: $$f(a,b) = \sum_{k \ge 1} (-1)^k (k-1)\frac{1}{k!} \sum_{n \ge k} \frac{1}{(n-k)!} b^n \sum_{m \ge k} \frac{(m+n-k-1)!}{(m-k)!} a^m.$$ Using the fact that $\binom{c}{d} = (-1)^d \binom{-c+d-1}{d}$ and the Generalized Binomial Theorem, we have $$f(a,b) = \sum_{k \ge 1} (-1)^k (k-1)\frac{1}{k!} \sum_{n \ge k} \frac{1}{(n-k)!} b^n \sum_{m \ge k} (n-1)! \binom{m+n-k-1}{m-k} a^m$$ $$=\sum_{k \ge 1} (-1)^k (k-1)\frac{1}{k!} \sum_{n \ge k} \frac{(n-1)!}{(n-k)!} b^n \sum_{m \ge k} \binom{-n}{m-k}(-1)^{m-k} a^m$$ $$=\sum_{k \ge 1} (-1)^k (k-1)\frac{1}{k!} \sum_{n \ge k} \frac{(n-1)!}{(n-k)!} b^n a^k (1-a)^{-n}$$ $$=\sum_{k \ge 1} (-1)^k (k-1)\frac{1}{k!} a^k \sum_{n \ge k} \frac{(n-1)!}{(n-k)!} \left(\frac{b}{1-a}\right)^n $$ $$=\sum_{k \ge 1} (-1)^k (k-1)\frac{1}{k!} (k-1)! a^k \sum_{n \ge k}\binom{n-1}{n-k}\left(\frac{b}{1-a}\right)^n$$ $$=\sum_{k \ge 1} (-1)^k (k-1)\frac{1}{k!} (k-1)! a^k \sum_{n \ge k}\binom{-k}{n-k}(-1)^{n-k}\left(\frac{b}{1-a}\right)^n$$ $$=\sum_{k \ge 1} (-1)^k (k-1)\frac{1}{k!} (k-1)! a^k \left(\frac{b}{1-a}\right)^k \left(1-\frac{b}{1-a}\right)^{-k}$$ $$=\sum_{k \ge 1} (-1)^k (k-1)\frac{1}{k!} (k-1)! a^k \left( \frac{b}{1-a-b} \right)^k$$ $$=\sum_{k \ge 1} (-1)^k (k-1)\frac{1}{k!}(k-1)!\left(\frac{ab}{1-a-b}\right)^k$$ $$=\sum_{k \ge 1} \frac{k-1}{k} \left(\frac{-ab}{1-a-b}\right)^k $$ $$= \frac{\frac{-ab}{1-a-b}}{1-\left(\frac{-ab}{1-a-b}\right)} + \log \left(1 - \left(\frac{-ab}{1-a-b}\right)\right)$$ $$=\frac{-ab}{1-a-b+ab} + \log\left(1 + \frac{ab}{1-a-b}\right)$$ $$=\frac{-ab}{(1-a)(1-b)} + \log \left( \frac{1-a-b+ab}{1-a-b} \right)$$ $$= -\frac{a}{1-a}\frac{b}{1-b} + \log(1-a) + \log(1-b) - \log(1-(a+b))$$ $$=-(a+a^2+a^3+\cdots)(b+b^2+b^3+\cdots) - (a + \frac{1}{2}a^2 + \frac{1}{3}a^3 + \cdots) - (b + \frac{1}{2}b^2 + \frac{1}{3}b^3 + \cdots) + ((a+b) + \frac{1}{2}(a+b)^2 + \frac{1}{3}(a+b)^3 + \cdots)$$ It is readily seen that for $m,n \ge 1$, the coefficient of $a^mb^n$ is $\frac{1}{m+n}\binom{m+n}{m} - 1 = \frac{(m+n-1)!}{m!n!} - 1$, so $\text{Pr}[g \ge 2]$ is equal to $\frac{m!n!}{(m+n-1)!}$ times this coefficient, which is $\boxed{1 - \frac{m!n!}{(m+n-1)!}}$ as desired. $\blacksquare$

Answer 6

Below, I adapt this answer of usul to this problem to derive a different "explicit" formula for $g(m,n)$. Unfortunately, this is not a complete answer; I do not (yet?) see how to simplify the weighted sum over paths below to the conjectured result.

First note that the "collinear grid fillings" are in bijection with shellings of the complete bipartite graph $K_{m,n}$ viewed as a 1D simplicial complex. In this context a shelling is equivalent to an ordering of the edges $e_1,\dots,e_{mn}$ of $K_{m,n}$ so that the graph $G_j$ induced by the edge set $E_j=\{e_i|i\leq j\}$ is connected for all $1\leq j\leq mn$. We will write $V_j$ for the vertex set of $G_j$.

Let $p(m,n)=\frac{g(m,n)}{(mn)!}$ denote the probability that a given ordering of the edges of $K_{m,n}$ is a shelling.

The two vertex partitions of $K_{m,n}$ will be denoted A and B, respectively, so that $|A|=m,|B|=n$. For any valid shelling $(e_j)_{j=1}^{mn}$ of $K_{m,n}$ note that the set of ordered pairs:

$$(\text{number of A vertices in }V_j, \text{number of B vertices in }V_j)$$

as $j$ runs from 1 to $mn$, yields a subset of $\mathbb{Z}^2$ which form a walk on the standard grid graph from $(1,1)$ to $(m,n)$ taking steps only in the (1,0) and (0,1) directions. From now on, the term "walk" will refer to such "North or East" walks on the grid graph.

Let $\mathcal{R}=\{(k,l)\in\mathbb{Z}^2|1\leq k\leq m,1\leq l \leq n\}$ be the set of possible such A, B vertex counts reachable by a shelling of $K_{m,n}$. Let $d$ denote an auxiliary "dead" state.

Then $\mathcal{R}\cup\{d\}$ form the states of a Markov chain which coarse-grain the dynamics of edge addition. In addition to the (1,0) and (0,1) transitions which occur if new vertices are attached one at a time (thus preserving the shelling property), there are also transitions to $d$, which occur if an edge is added which disconnects $G_j$. $d$ and $(m,n)$ are the absorbing states.

We will compute the transition probabilities between states in this Markov chain which are induced by a random edge ordering; then $p(m,n)$ will be the probability that a walk from (1,1) survives to reach (m,n).

Suppose we consider a random edge ordering which is at the state $(k,l)\neq(m,n)$. As we add edges, the state must eventually change for some added edge $e_j$ and there are three possibilities:

1. $e_j$ connects $V_{j-1}$ to A, ($l(m-k)$ choices of $e_j$)
2. $e_j$ connects $V_{j-1}$ to B, ($k(n-l)$ choices)
3. $e_j$ is not adjacent to any vertices in $V_{j-1}$ ($(m-k)(n-l)$ choices)

The total number of ways that we can leave $(k,l)$ is $mn-kl$ (equal to the number of edges of $K_{m,n}$ with at least one endpoint outside the $k$ vertices of A and $l$ vertices of B already reached). Thus the transition probabilities are:

1. $\tilde{p}((k,l),(k+1,l))=\frac{l(m-k)}{mn-kl}$
2. $\tilde{p}((k,l),(k,l+1))=\frac{k(n-l)}{mn-kl}$
3. $\tilde{p}((k,l),d)=\frac{(m-k)(n-l)}{mn-kl}$

Here is an image showing the transition probabilities in the case $m=5,n=3$:

The probability that a random edge ordering induces a given walk $W$ from $(1,1)$ to $(m,n)$ is equal to the product of the transition probabilities $\tilde{p}(a,b)$ for all edges $(W_j,W_{j+1})$ of $W$. So for instance, the walk in the image above which goes north from $(1,1)$ to $(1,3)$ and then east to $(5,3)$ has probability $\frac{1}{7}\times\frac{1}{13}=\frac{1}{1001}$.

Finally, $p(m,n)$ is the sum of these probabilities over all possible walks. This can be written as:

$$p(m,n)=\sum_{W\text{ walk from }(1,1)\text{ to }(m,n)}\prod_{j=1}^{m+n-2}\tilde{p}(W_{j},W_{j+1}).$$

For the example above, $p(5,3)=\frac{1}{1001}+\frac{16}{7007}+\frac{32}{7007}+\frac{8}{1911}+\frac{16}{1911}+\frac{1}{91}+\frac{128}{21021}+\frac{256}{21021}+\frac{16}{1001}+\frac{16}{1001}+\frac{128}{21021}+\frac{256}{21021}+\frac{16}{1001}+\frac{16}{1001}+\frac{1}{91}=1/7.$

I have not yet managed to figure out how to simplify this sum in general; the conjecture gives $p(m,n)=\frac{m+n}{\binom{m+n}{m}}$. Curiously, $\binom{m+n}{n}$ is the number of walks from (0,0) to $(m,n)$.

Here is some SageMath code which implements this "weighted path sum" for $p(m,n)$ to compute $g(m,n)=(mn)!p(m,n)$:

def usulformula(m,n):
    def weightA(k,l):
        return l*(m-k)/(m*n-k*l)
    def weightB(k,l):
        return k*(n-l)/(m*n-k*l)
    def recursewalk(k,l,w):
        if k<m:
            if l<n:
                return (recursewalk(k+1,l,weightA(k,l)*w)
                        +recursewalk(k,l+1,weightB(k,l)*w))
            else:
                return recursewalk(k+1,l,weightA(k,l)*w)
        else:
            if l<n:
                return recursewalk(k,l+1,weightB(k,l)*w)
            else:
                return w
    return recursewalk(1,1,1)*factorial(m*n)

While this code is recursive, it only has two recursions as compared to the three recursions used in the grid function in the question.

The values of $g(m,n)$ from the above code agree with those from the conjectured formula for all values of $m,n$ that I've tried.

Answer 7

Based on Zsombor Fehér's solution. Let $S$ be the set of $n \times m$ matrices that contain every integer from 1 to $nm$ exactly once. Clearly, $|S| = (nm)!$.

Let $A_{s, t} \subset S$ (for $1 \leq s \leq n$, $1 \leq t \leq m$) be the set of matrices $M = \left(m_{i, j}\right) \in S$ where the element $m_{s, t}$ is the smallest in both its row and column. The task is to provide a formula for the number of elements in $S$ that belong to exactly one of the sets $A_{s, t}$. This number can be determined using the inclusion-exclusion principle. For this, we will need the number of elements in the intersections of the $A_{s, t}$ sets, specifically the sums $\sigma_k$ of the sizes of the intersections of $k$ distinct $A$-sets.

Each set $A_{s, t}$ has the same size, $\frac{(nm)!}{n+m-1}$. Indeed, to obtain a matrix $M = \left(m_{i, j}\right) \in A_{s, t}$, we can freely assign distinct elements from $[nm] = {1, 2, \ldots, nm}$ to the $(n-1)(m-1)$ positions outside the $s$-th row and $t$-th column. From the remaining $n+m-1$ elements, the smallest will be $m_{s, t}$, while the remaining positions can be filled with any of the unused numbers. From this, we get that $\sigma_1 = \sum_{s, t}\left|A_{s, t}\right| = nm \cdot \frac{(nm)!}{n+m-1}$.

Next, consider the intersection of two distinct sets $A_{s, t}$ and $A_{s', t'}$. Clearly, the intersection is empty if $s = s'$ or $t = t'$ (so there are $2\binom{n}{2}\binom{m}{2}$ non-empty two-set intersections). The size of the non-empty intersections is the same, $\frac{(nm)!}{(2n + 2m - 4)(n+m-1)}$. Indeed, the matrices $M = \left(m_{i, j}\right) \in A_{s, t} \cap A_{s', t'}$ can be split into two groups based on the relative size of $m_{s, t}$ and $m_{s', t'}$. We only examine the case $m_{s, t} < m_{s', t'}$. We can list such matrices by first filling the positions outside the $s$-th and $s'$-th rows and $t$-th and $t'$-th columns, as before (independently and without repetition), then assigning the smallest unused value to $m_{s, t}$ (a deterministic choice), filling the remaining positions of the $s$-th row and $t$-th column according to the rules, assigning the smallest unused value to $m_{s', t'}$ (another deterministic choice), and finally filling the remaining positions of the $s'$-th row and $t'$-th column. Due to these two deterministic choices, the number of matrices in the first class is $$\frac{(nm)!}{(2n + 2m - 4)(n+m-1)}$$ The sum $\sigma_2$ of the sizes of the two-set intersections is given by

$$\left[2\binom{n}{2}\binom{m}{2}\right] \cdot 2 \cdot \frac{(nm)!}{(2n + 2m - 4)(n+m-1)}.$$

Where the first factor represents the number of possibilities for non-empty intersections corresponding to $s, t, s^{\prime}, t^{\prime}$, and the second factor comes from the two cases.

The sizes of the $k$-set intersections can be determined in a completely similar way. The intersection $A_{s_1, t_1} \cap A_{s_2, t_2} \cap \dots \cap A_{s_k, t_k}$ is empty if, for some $i \neq j$, $s_i = s_j$ or $t_i = t_j$. The non-empty intersections, of which there are $k!\binom{n}{k}\binom{m}{k}$, all have the same size:

\begin{aligned} & k!\cdot \frac{(nm)!}{(kn + km - k^2) \cdot \dots \cdot (2n + 2m - 4) \cdot (n + m - 1)} \\ & = \frac{(nm)!}{(n+m-k) \cdot \dots \cdot (n+m-2) \cdot (n+m-1)}. \end{aligned}

\begin{aligned} \sigma_k & = \left[k! \binom{n}{k} \binom{m}{k}\right] \cdot \frac{(nm)!}{(n+m-k) \cdot \dots \cdot (n+m-2) \cdot (n+m-1)} \\ & = \frac{n!m! \cdot (nm)! \cdot (n+m-k-1)!}{(n-k)!(m-k)!k! \cdot (n+m-1)!} \\ & = \frac{n!m!(nm)!}{(n+m-1)!} \cdot \frac{(n+m-k-1)!}{(n-k)!(m-k)!k!}, \end{aligned}

We note that a non-empty $k$-set intersection exists only if $k \leq \min{n, m}$.

"Beautiful" matrices are those that belong to exactly one set $A_{s, t}$. Indeed, for a matrix $M \in S$, if $s$ is the row of the element '1' and $t$ is the column of the element '1', then $M \in A_{s, t}$. A beautiful matrix cannot belong to any other $A$-set. The number of these matrices is given by a form of the inclusion-exclusion principle:

$\sum_{k=1}^{nm} (-1)^{k-1} k \sigma_k.$

Thus, the number of beautiful matrices is

\begin{aligned} & \sum_{k=1}^{\min\{n, m\}} (-1)^{k-1} k \cdot \frac{n!m!(nm)!}{(n+m-1)!} \cdot \frac{(n+m-k-1)!}{(n-k)!(m-k)!k!} \\ & = \frac{n!m!(nm)!}{(n+m-1)!} \cdot \sum_{k=1}^{\min\{n, m\}} (-1)^{k-1} \frac{(n+m-k-1)!}{(n-k)!(m-k)!(k-1)!}. \end{aligned}

Thus:

$$= \frac{n!m!(nm)!}{(n+m-1)!} \cdot \sum_{k=1}^{\min\{n, m\}} (-1)^{k-1} \frac{(n+m-k-1)!}{(n-k)!(m-k)!(k-1)!}.$$

To complete the proof, we need to see that the value of the last sum is $1$.

\begin{align} \sum_{k=1} (-1)^{k-1} \frac{(n+m-k-1)!}{(n-k)!(m-k)!(k-1)!} &= \sum_{k=1} (-1)^{k-1} \binom{n+m-k-1}{n-k} \binom{m-1}{k-1} \\ &= \sum_{k=1} (-1)^{k-1} (-1)^{n-k} \binom{-m}{n-k} \binom{m-1}{k-1} \\ &= (-1)^{n-1} \sum_{k=1} \binom{-m}{n-k} \binom{m-1}{k-1} \\ &= (-1)^{n-1} \binom{-1}{n-1} \\ &= (-1)^{n-1} (-1)^{n-1} \\ &= 1. \end{align}