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$

6more comments