Curiosa suma combinatoria

Question

Deje $\gamma$ denotar una cuadrícula a pie de la esquina superior izquierda $(1,k)$ a la esquina inferior derecha $(\ell,1)$ de la $k\times\ell$ rectángulo $\{1,..,k\}\times\{1,..,\ell\}$. Hay $\binom{k+\ell-2}{k-1}$ rutas de acceso. Denotar $$ X_\gamma = \prod_{(i,j)\in\gamma} \frac{1}{i+j-1}\,. $$ Reclamo:
$$\sum_\gamma X_\gamma = \frac{1}{(k+\ell-1)(k-1)!(\ell-1)!}\,. $$

De forma equivalente, y más elegante, para una ruta de acceso aleatorio $\gamma$, tenemos: $\ \Bbb E[X_\gamma] = 1/(k+\ell-1)!$

Ejemplo: $k=2$, $\ell=3$. Hay $3=\binom{3}{1}$ rutas $\,\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)$. Entonces: $$ 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!}\,. $$

Pregunta: ¿existe una prueba simple de esta combinatoria de totalización? Si se conoce, ¿alguien tiene una referencia?

P. S. yo, de hecho, puede probar la afirmación, pero la prueba es muy involucrados para un simple resultado de apariencia.

Answer 1

Supongamos que el punto de inicio de la es $(a,b)$ y el punto final es $(c,d)$ donde$a\geq c$$d\geq b$.
A partir de la forma general de la $F((k,1),(1,l))$, y el hecho de que las rutas de $(k,1)$ ir a través de $(k-1,1)$ o $(k,2)$, se puede deducir la forma general de la $F((k,2),(1,l))$.
A continuación, $F((k,3),(1,l))$ y así sucesivamente.
Tengo esta fórmula:
$$F((a,b),(c,d))=\frac{(a+d-b-c)!(b+c-2)!}{(a+d-1)!(a-c)!(d-b)!}$$ El caso base de la inducción es la prueba de $F((a,b),(a,b))=1/(a+b-1)$ porque no es una ruta de acceso de un solo vértice.
La ecuación recursiva es $$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]$$ El último factor es igual a $(a+b-1)(a-b-c+d)$, por lo que la respuesta final es $F((a,b),(c,d))$ anterior, y sólo hemos asumido $F((a,b),(c,d))$ era correcta para los valores con un valor más bajo de $a-b$.