text: # Curious combinatorial summation
  
  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.
  
  • Is the upper left corner $(1,1)$, or $(1,k)$? Dec 28, 2015 at 11:02
  • @Gyumin Roh - usual coordinates, Upper Left = $(1,k)$, Lower Right = $(\ell,1)$ Dec 28, 2015 at 12:07
  • 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. Dec 28, 2015 at 12:23
  • @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). Dec 28, 2015 at 12:31
  • @IgorPak: Now I'm not sure of it myself, as the numerator does not factor for $k=2$ and $\ell=3$. Dec 28, 2015 at 14:23
  
  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.
  $$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$.
  • I don't follow. Paths start at $(1,k)$ and go to $(\ell,1)$. Can you expand? Dec 28, 2015 at 12:46
  • You also have $1/\mathbb{E}(X_{\gamma})=\prod_{j=b+c-1}^{a+d-1}j$ Dec 29, 2015 at 0:09
  • 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. Dec 29, 2015 at 12:39
explanation: The document presents a combinatorial problem involving grid walks and a specific claim about the sum of a product over all such paths. It includes a detailed example and a question asking for a simple proof or a reference to the claim. The document also contains a discussion in the comments section, where a user provides a proof for the claim.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # Curious combinatorial summation
  
  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.
  
  • Is the upper left corner $(1,1)$, or $(1,k)$? Dec 28, 2015 at 11:02
  • @Gyumin Roh - usual coordinates, Upper Left = $(1,k)$, Lower Right = $(\ell,1)$ Dec 28, 2015 at 12:07
  • 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. Dec 28, 2015 at 12:23
  • @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). Dec 28, 2015 at 12:31
  • @IgorPak: Now I'm not sure of it myself, as the numerator does not factor for $k=2$ and $\ell=3$. Dec 28, 2015 at 14:23
  
  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.
  $$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$.
  • I don't follow. Paths start at $(1,k)$ and go to $(\ell,1)$. Can you expand? Dec 28, 2015 at 12:46
  • You also have $1/\mathbb{E}(X_{\gamma})=\prod_{j=b+c-1}^{a+d-1}j$ Dec 29, 2015 at 0:09
  • 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. Dec 29, 2015 at 12:39
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document presents a combinatorial problem involving grid walks and a specific claim about the sum of a product over all such paths. It includes a detailed example and a question asking for a simple proof or a reference to the claim. The document also contains a discussion in the comments section, where a user provides a proof for the claim.
  
  Label: question-and-answer