11
$\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$
    – Gyumin Roh
    Dec 28 '15 at 11:02
  • $\begingroup$ @Gyumin Roh - usual coordinates, Upper Left = $(1,k)$, Lower Right = $(\ell,1)$ $\endgroup$
    – Igor Pak
    Dec 28 '15 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 '15 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 '15 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 '15 at 14:23
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 '15 at 12:46
  • $\begingroup$ Whoops, I had them going the other way. $\endgroup$
    – Empy2
    Dec 28 '15 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 '15 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 '15 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 '15 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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