10
$\begingroup$

Let $\gamma$ denote a grid walk from the upper left corner $(1,k)$ to the lower right corner $(\ell,1)$ of the $k\times\ell$ rectangle $\{1,..,k\}\times\{1,..,\ell\}$. There are $\binom{k+\ell-2}{k-1}$ such paths. Denote $$ X_\gamma = \prod_{(i,j)\in\gamma} \frac{1}{i+j-1}\,. $$ Claim:
$$\sum_\gamma X_\gamma = \frac{1}{(k+\ell-1)(k-1)!(\ell-1)!}\,. $$

Equivalently, and more elegantly, for a random path $\gamma$, we have: $\ \Bbb E[X_\gamma] = 1/(k+\ell-1)!$

Example: $k=2$, $\ell=3$. There are $3=\binom{3}{1}$ paths $\,\gamma_1: (1,2) \to (1,1) \to (2,1) \to (3,1)$, $\,\gamma_2: (1,2) \to (2,2) \to (2,1) \to (3,1)$, $\,\gamma_3: (1,2) \to (2,2) \to (3,2) \to (3,1)$. Then: $$ X_1 = \frac{1}{2\cdot 1\cdot 2\cdot 3} \ , \ X_2 = \frac{1}{2\cdot 3\cdot 2\cdot 3} \ , \ X_3 = \frac{1}{2\cdot 3\cdot 4\cdot 3} \ , $$ $$X_1+X_2+X_3 = \frac{1}{12}+\frac{1}{36}+\frac{1}{72} = \frac{1}{8} = \frac{1}{4\cdot 1!\cdot 2!}\,. $$

Question: Is there a simple proof of this combinatorial summation? If it's known, does anyone have a reference?

P.S. I can in fact prove the claim but the proof is incredibly involved for such a simple looking result.

$\endgroup$
5
  • $\begingroup$ Is the upper left corner $(1,1)$, or $(1,k)$? $\endgroup$
    – rkm0959
    Dec 28, 2015 at 11:02
  • $\begingroup$ @Gyumin Roh - usual coordinates, Upper Left = $(1,k)$, Lower Right = $(\ell,1)$ $\endgroup$
    – Igor Pak
    Dec 28, 2015 at 12:07
  • $\begingroup$ What about summing $\prod\limits_{\left(i,j\right) \in \gamma} \dfrac{1}{a_i+b_j}$ ? My feeling is that if there is a nice proof, then it factors through this generalization. $\endgroup$ Dec 28, 2015 at 12:23
  • $\begingroup$ @darij grinberg -- I am not sure. I don't think my (very general) tools give that at all. Let me know if this works (on this page or directly). $\endgroup$
    – Igor Pak
    Dec 28, 2015 at 12:31
  • $\begingroup$ @IgorPak: Now I'm not sure of it myself, as the numerator does not factor for $k=2$ and $\ell=3$. $\endgroup$ Dec 28, 2015 at 14:23

1 Answer 1

3
$\begingroup$

Suppose the start point is $(a,b)$ and the end point is $(c,d)$, where $a\geq c$ and $d\geq b$.
From the general form of $F((k,1),(1,l))$, and the fact that paths from $(k,1)$ go through $(k-1,1)$ or $(k,2)$, you can deduce the general form of $F((k,2),(1,l))$.
Then $F((k,3),(1,l))$ and so on.
I got this formula:
$$F((a,b),(c,d))=\frac{(a+d-b-c)!(b+c-2)!}{(a+d-1)!(a-c)!(d-b)!}$$ The base case of the induction proof is $F((a,b),(a,b))=1/(a+b-1)$ because there is one path of a single vertex.
The recursive equation is $$F((a,b),(c,d))=\frac1{a+b-1}\left[F((a-1,b),(c,d))+F((a,b+1),(c,d))\right]$$ $$=\frac1{a+b-1}\left[\frac{(a+d-b-c-1)!(b+c-2)!}{(a+d-2)!(a-c-1)!(d-b)!}+\frac{(a+d-b-c-1)!(b+c-1)!}{(a+d-1)!(a-c)!(d-b-1)!}\right]\\ =\frac1{a+b-1}\frac{(a+d-b-c-1)!(b+c-2)!}{(a+d-1)!(a-c)!(d-b)!}\cdot\\ \left[(a+d-1)(a-c)+(b+c-1)(d-b)\right]$$ The final factor equals $(a+b-1)(a-b-c+d)$, so the final answer is $F((a,b),(c,d))$ given above, and we only assumed $F((a,b),(c,d))$ was correct for values with a lower value of $a-b$.

$\endgroup$
5
  • $\begingroup$ I don't follow. Paths start at $(1,k)$ and go to $(\ell,1)$. Can you expand? $\endgroup$
    – Igor Pak
    Dec 28, 2015 at 12:46
  • $\begingroup$ Whoops, I had them going the other way. $\endgroup$
    – Empy2
    Dec 28, 2015 at 14:30
  • $\begingroup$ Oh, thank you so much. I didn't expect a simple inductive argument to work. In fact, the final equality is also quite surprising - here it is again: tinyurl.com/hlmbjnk $\endgroup$
    – Igor Pak
    Dec 28, 2015 at 23:50
  • 1
    $\begingroup$ You also have $1/\mathbb{E}(X_{\gamma})=\prod_{j=b+c-1}^{a+d-1}j$ $\endgroup$
    – Empy2
    Dec 29, 2015 at 0:09
  • $\begingroup$ To followup on your comment, here is my new way of phrasing this. The expectation $\Bbb E[X_\gamma]$ for random $\gamma$ from $(a,b)$ to $(c,d)$ is the same as for random $\gamma$ from $(a,d)$ to $(c,b)$. Of course $X_\gamma$ is a constant in one of these cases. $\endgroup$
    – Igor Pak
    Dec 29, 2015 at 12:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .