14
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Side note: The formula is a bit similar to en.wikipedia.org/wiki/Catalan_number#Generalizations the super-Catalan numbers (or one of the super versions). $\endgroup$ – Per Alexandersson Apr 9 '18 at 15:37
  • 1
    $\begingroup$ I've just posted a question inspired by this one here mathoverflow.net/questions/297411/… $\endgroup$ – j.c. Apr 9 '18 at 19:29
  • 3
    $\begingroup$ It may be useful to study $\tilde{g}(m, n, i) = \frac{g(m, n, i)}{m! n!}$, which represents the number of collinear orderings that reach each row and column in order. This satisfies the simpler recursion relation $\tilde{g}(m, n, i+1) = (mn - i) \tilde{g}(m, n, i) + n \tilde{g}(m-1, n, i) + m \tilde{g}(m, n-1, i)$, and also keeps the numbers smaller. The conjecture is then that $\tilde{g}(m, n, mn) = \frac{(mn)!}{(m + n - 1)!}$. $\endgroup$ – user44191 Apr 9 '18 at 20:25
  • 2
    $\begingroup$ I wrote some little code and verified the formula for $nm \le 1000$. $\endgroup$ – Yuzhou Gu Apr 9 '18 at 21:11
  • 2
    $\begingroup$ @SebastienPalcoux Also, I just recognized the sum as a generalized hockeystick. $\sum_{\ell=1}^m \frac{m!}{(m-\ell)!} \ell (2m-\ell-1)! = m! \sum_{\ell=1}^m \frac{(2m-\ell-1)!}{(m-\ell)!} \ell = m! (m - 1)! \sum_{\ell = 1}^m \binom{l}{1} \binom{2m - \ell - 1}{m - 1}$ $= m! (m - 1)! \binom{2m}{m + 1} = m! \frac{(2m)!}{(m + 1)!} = \frac{(2m)!}{m + 1}$ $\endgroup$ – user44191 Apr 9 '18 at 21:24
4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ In your paper, it would be nice to also mention the questioners of the mathoverflow posts you cited. $\endgroup$ – Sebastien Palcoux Sep 28 '18 at 16:15
  • 1
    $\begingroup$ Congratulations, I'm looking forward to reading your paper! $\endgroup$ – j.c. Sep 28 '18 at 21:28
8
$\begingroup$

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)!$?

$\endgroup$
3
$\begingroup$

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: http://web.mit.edu/shopkins/docs/rsk.pdf. 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.

$\endgroup$
2
$\begingroup$

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$:

Labeled picture of Markov chain on R

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.

$\endgroup$
  • $\begingroup$ Should I accept your answer, or should I wait a couple of weeks for a complete answer? $\endgroup$ – Sebastien Palcoux Apr 15 '18 at 17:32
  • $\begingroup$ Unfortunately I haven't managed to make any progress in getting this to the conjectured form. I would keep waiting though; I'm sure a proof is out there somewhere. $\endgroup$ – j.c. Apr 15 '18 at 20:05
  • $\begingroup$ This defines $h_{m, n}(k, l)$ with the recursion relation $h_{m, n}(k, l) = \frac{l (m - k)}{mn - kl} h_{m, n}(k + 1, l) + \frac{k (n - l)}{mn - kl} h_{m, n}(k, l + 1)$, and boundary condition $h_{m, n}(m, n) = 1$, right? $\endgroup$ – user44191 Apr 19 '18 at 0:53
  • $\begingroup$ @user44191 I guess $h_{m,n}(k,l)$ denotes the probability that a walk that has made it to $(k,l)$ survives to reach $(m,n)$, right? Should the multiplicative factors in your recursion be the reciprocals of the weights in my answer, that is, $\frac{mn-kl}{l(m-k)}$ and $\frac{mn-kl}{k(n-l)}$, (since you are effectively moving "backwards" from $(m,n)$ towards (1,1)) or am I missing something? $\endgroup$ – j.c. Apr 19 '18 at 1:16
  • $\begingroup$ @j.c. That description sounds right, and I think my formula mimics what you were trying to do as is - without reciprocals. I could be wrong though. $\endgroup$ – user44191 Apr 20 '18 at 21:12

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.