# 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
The text passage describes a combinatorial problem involving grid walks and a claim about the expected value of a product over the steps of the walk. It provides an example for specific values of $k$ and $\ell$, and asks if there is a simple proof of the claim or if it is a known result.
single_question_with_answer

the passage contains a single mathematical question asking for a simple proof of the combinatorial summation or a reference if it is known. an answer is provided in the form of a proof sketch using induction.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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
user
The text passage describes a combinatorial problem involving grid walks and a claim about the expected value of a product over the steps of the walk. It provides an example for specific values of $k$ and $\ell$, and asks if there is a simple proof of the claim or if it is a known result.

TYPE: SINGLE_QUESTION_WITH_ANSWER

The passage contains a single mathematical question asking for a simple proof of the combinatorial summation or a reference if it is known. An answer is provided in the form of a proof sketch using induction.