Recuento de votos en caso de empate $r$ veces

Question

Problema de votación con número fijo de empates:

Planteamiento del problema : En unas elecciones, el candidato A recibe $m$ votos y el candidato B recibe $n$ notas. Dejemos que $m \ge n$ . ¿De cuántas maneras pueden contarse las papeletas para que se produzcan empates exactamente? $r$ veces ( $r \le n$ )?

Ejemplo : $m = 3, n = 2, r = 1$ . Hay 4 escenarios de este tipo: para el orden ABAAB, BAAAB el empate se produce en la 2ª votación; para el orden AABBA, BBAAA el empate se produce en la 4ª votación.

Llame a este número $Z( m,n, r)$ . Mi objetivo práctico es responder a lo siguiente: Dado el número total de votos $N$ de cuántas maneras podemos ordenar las papeletas para tener exactamente $r$ lazos? Es \begin{equation} Z(N,r) = \sum_{n = r}^{N/ 2} Z( N-n, n ,r ) + \sum_{n = r}^{N/ 2} Z( n, N-n ,r ) \end{equation} una vez que averigüemos $Z(m,n,r)$ .

Estaría bien poder conseguir $Z(N,r)$ o su función generadora directamente, pero creo que el " $r$ -tie" es interesante por sí solo.

Asignación a la enumeración de rutas reticulares

He aquí una forma equivalente del problema:

Considere la trayectoria reticular desde $(0,0)$ para señalar $(m,n)$ con sólo $(0,1)$ o derecha $(1,0)$ movimiento en $m +n $ pasos. Excluyendo el punto de partida $(0,0)$ cuántas trayectorias de celosía llegan al (punto de celosía en la) línea diagonal $y = x$ exactamente $r$ ¿tiempos?

La siguiente figura muestra un camino de celosía que llega a (4,3) y su imagen bajo la reflexión de André. Golpea la diagonal 3 veces.

$r = 0$ es la trayectoria estrictamente monótona

En $r = 0$ problema puede resolverse Principio de reflexión de André . (el método utilizado aquí es similar a este Puesto ME )

En primer lugar $m > n$ en caso contrario, el punto final $(n,n)$ será un punto de contacto. Como no se permite tocar la diagonal, el primer paso debe ir a la derecha. Hay ${ m + n - 1 \choose m-1}$ tales caminos pero necesitamos excluir los que tocan la diagonal.

Supongamos que hay un camino de este tipo (el primer paso va hacia la derecha) que toca la diagonal, podemos hacer una reflexión sobre la $ y= x$ para la trayectoria entre el origen y la primera intersección (véase la figura). La trayectoria reflejada es la que comienza con un movimiento hacia arriba. Dado que tales trayectorias cruzarán definitivamente la línea diagonal para llegar a $(m,n)$ es fácil ver que el mapa es uno a uno. Hay ${m+n -1 \choose n - 1}$ tales caminos.

En resumen, el resultado es \begin{equation} Z( m, n, 0) = { m + n - 1 \choose m - 1 } - {m+n -1 \choose n - 1} = { m + n - 1 \choose n } - {m+n -1 \choose n - 1} \quad m > n \end{equation} que es muy similar al teorema de la votación .

---

¿Alguna idea de acercarse al general $r$ ?

Gracias.

---

Actualización 1: $m = n, r = 1$ es la trayectoria de Dyck estrictamente monótona

La única intersección es en el punto final $(n,n)$ así que esto es básicamente un camino Dyck que golpea la diagonal una vez. Este Puesto ME da el resultado general para que una trayectoria Dyck llegue a la diagonal $k$ veces. Ajuste $k$ = 1, el resultado es $\frac{1}{n}{2n - 2 \choose n-1 }$ . Aquí la trayectoria puede estar por encima o por debajo de la línea diagonal, por lo que un factor de $2$ , \begin{equation} Z( n, n, 1 ) = \frac{2}{n}{2n - 2 \choose n-1 } \end{equation}

---

Actualización 2: número de caminos de la red que cruzan la diagonal $k$ veces

Llame a este número $C( m, n, r )$ .

Kern, Malcolm; Walter, Stanley , Teorema de la papeleta y cruces de caminos en celosía , Can. J. Stat. 6, 87-90 (1978). ZBL0387.60018 . da el resultado \begin{equation} C( m,n, r ) = \left\lbrace \begin{aligned} &\frac{2(r+1)}{n} {2n \choose n - r -1 } & m = n \\ &\frac{m - n + 2r + 1}{m + n + 1} { m + n +1 \choose n - r } & m > n \\ \end{aligned} \De acuerdo. \Fin.

Se trata de un problema relevante pero diferente. Fíjese en la diferencia entre "tocar" y "cruzar". Sólo pasando de un lado de $y=x$ a la otra se considera una "cruz". En el problema de las papeletas, se trata de un cambio del candidato principal, no de un empate. Se puede comprobar que $C( n, n, 0 )$ es el doble del número catalán.

Answer 1

Nota: [2017-09-17] Simplificación esencial debido al uso de la fórmula de cambio de variable.

---

Consideramos el problema en términos de trayectorias reticulares con pasos ascendentes $(1,1)$ y bajadas $(1,-1)$ . Utilizamos como bloques de construcción básicos Caminos de Dyck que son trayectorias de longitud $2t (t\geq 0)$ de $(0,0)$ a $(2t,0)$ que no van más allá del $x$ -Eje.

El número de trayectorias Dyck de longitud $2t$ es el _Número catalán $C_t=\frac{1}{t+1}\binom{2t}{t}$ con función generadora \begin{align*} c(z)&=\frac{1}{2z}\left(1-\sqrt{1-4z}\right)\\ &=\sum_{j=0}^\infty C_j z^j=\sum\{j=0}^\infty \frac{1}{j+1}\binom{2j}{j}z^j\\ &=1+z+2z^2+5z^3+14z^4+42z^5+132z^6+429z^7+\cdots \end{align*} Por ejemplo, el coeficiente $[z^5]c(z)=42$ nos dice que hay $42$ caminos de $(0,0)$ a $(10,0)$ que no van más allá del $x$ -Eje.

Queremos contar el número $N(r,m,n)$ de trayectorias que parten de $(0,0)$ con $m$ escalones, $n$ peldaños que tocan (además de $(0,0)$ ) el $x$ -eje $r\geq 1$ veces con \begin{align*} 1\leq r\leq n\leq m \end{align*}

Caso especial: $r=1$ y $n=m$

Desde $m=n$ el número de pasos hacia arriba es igual al número de pasos hacia abajo. Consideramos trayectorias de longitud $2n$ a partir de $(0,0)$ y terminando en $(2n,0)$ que no tocan el $x$ -eje intermedio.

Encontramos una función generadora basada en trayectorias de Dyck:

• Comenzamos con un paso hacia arriba

• entonces tomamos todas las trayectorias Dyck de longitud $2n-2$ y

• termina con un paso hacia abajo,

• o empezamos con un paso descendente, tomamos todos los caminos Dyck de longitud $2n-2$ y terminar con un paso hacia arriba.

De esta forma se garantiza que nunca toquemos o crucemos el $x$ -eje entre el punto inicial y el final.

La función generadora correspondiente es $2zc(z)$ con $z$ que representa el paso inicial ascendente o descendente. El factor $2$ respeta dos posibilidades arriba, resp. abajo. El número $N(1,n,n)$ es por lo tanto \begin{align*} \color{blue}{N(1,n,n)}&=[z^n](2zc(z))=2[z^{n-1}]c(z)=2C_{n-1}\\ &=\frac{2}{n}\binom{2n-2}{n-1}\\ &\color{blue}{=\frac{2}{2n-1}\binom{2n-1}{n}} \end{align*}

Caso especial: $1\leq r\leq n=m$

Concatenación de $r$ como se describe en el paso anterior da rutas de $(0,0)$ a $(2n,0)$ que tocan el $x$ -eje $r$ veces, la última en $(2n,0)$ . Concatenar significa multiplicación de las correspondientes funciones generadoras y obtenemos así

\begin{align*} \color{blue}{N(r,n,n)}&=[z^n](2zc(z))^r=[z^n](1-\sqrt{1-4z})^r\tag{1}\\ \end{align*}

Para derivar los coeficientes de la función generadora en (1) utilizamos lo siguiente

Cambio de fórmula variable: Sea $f(z)$ sea una serie de Laurent y $g(w)$ sea una serie de potencias, $g(w)=g_1w+g_2w^2+\cdots$ donde $g_1\ne 0$ . Entonces \begin{align*} \color{blue}{[z^{-1}]f(z)=[w^{-1}]f(g(w))g^\prime(w)}\tag{2} \end{align*}

Véase, por ejemplo, la página 12 de esta presentación por Ira Gessel.

Utilizamos la transformación \begin{align*} z=\frac{w}{(1+w)^2}\qquad\qquad\frac{dz}{dw}=\frac{1-w}{(1+w)^3} \end{align*} y obtener \begin{align*} 1-\sqrt{1-4z}=\frac{2w}{1+w} \end{align*}

Obtenemos de (2) \begin{align*} \color{blue}{[z^p]\left(1-\sqrt{1-4z}\right)^q} &=[z^{-1}]z^{-p-1}\left(1-\sqrt{1-4z}\right)^q\\ &=[w^{-1}]\left(\frac{w}{(1+w)^2}\right)^{-p-1}\left(\frac{2w}{1+w}\right)^q\frac{1-w}{(1+w)^3}\\ &=2^q[w^{p-q}](1+w)^{2p-q-1}(1-w)\\ &=2^q\left[\binom{2p-q-1}{p-q}-\binom{2p-q-1}{p-q-1}\right]\\ &=2^q\left[\binom{2p-q}{p-q}-2\binom{2p-q-1}{p-q-1}\right]\\ &=2^q\left[\binom{2p-q}{p-q}-2\cdot\frac{p-q}{2p-q}\binom{2p-q}{p-q}\right]\\ &=\color{blue}{\frac{2^qq}{2p-q}\binom{2p-q}{p-q}}\tag{3} \end{align*}

En caso de que $N(r,n,n)$ fijamos en (3) $p=n$ y $q=r$ y obtener

Obtenemos con (2) \begin{align*} \color{blue}{N(r,n,n)}&=[z^n]\left(1-\sqrt{1-4z}\right)^r\\ &=\color{blue}{\frac{2^rr}{2n-r}\binom{2n-r}{n-r}}\tag{4} \end{align*}

Hay que tener en cuenta un aspecto adicional para el caso general.

Caso general: $1\leq r\leq n\leq m$

El caso general $1\leq r \leq n< m$ significa que tenemos $r$ bloques como el anterior que utiliza al menos $r$ pasos ascendentes, uno por cada bloque y como máximo $n$ escalones superiores dentro del $r$ es decir, antes de tocar los bloques $x$ -eje la última vez.

En general, utilizamos $r\leq t\leq n$ escalones superiores dentro del $r$ bloques, dejando $m-t$ escalones y $n-t$ pasos hacia abajo. Desde $m\geq n$ el número $m-t$ de peldaños hacia arriba es mayor o igual que el número de $n-t$ escalones hacia abajo.

En $m-t$ escalones y $n-t$ se utilizan para construir rutas a partir de $(0,0)$ a \begin{align*} (m-t)(1,1)+(n-t)(1,-1)=(m+n-2t,m-n) \end{align*} que comienzan con un paso hacia arriba y se mantienen por encima del $x$ -eje. Según Lema de reflexión de André es el número de caminos desde $(0,0)$ a $(m+n-2t,m-n)$ que no cruzan el $x$ -dado como \begin{align*} \frac{m-n}{m+n-2t}\binom{m+n-2t}{m-t}\tag{5} \end{align*}

En (4) no tenemos un factor $2^{m-n}$ ya que sólo consideramos los caminos que están más allá del $x$ -Eje.

Nota:

• Obsérvese que la estructura del coeficiente binomial en (5) es lo mismo como en (2) con $p=m-t$ y $q=m-n$ .

• Combinatorialmente esto significa el número de caminos de longitud $m+n$ que comienzan en $(0,0)$ con un paso hacia arriba y terminan en $(m,m-n)$ en altura $m-n=r$ y nunca toques el $x$ -es igual al número de trayectorias de longitud $2m$ de $(0,0)$ a $(2n,0)$ que comienzan con un paso hacia arriba nunca van más allá del $x$ -y toque el botón $x$ eje $r$ veces, la última en $(2n,0)$ .

• Alebraicamente esto implica \begin{align*} [z^{m-t}]\left(\frac{1-\sqrt{1-4z}}{2}\right)^{m-n} =\frac{m-n}{m+n-2t}\binom{m+n-2t}{m-t}\tag{6} \end{align*}

Finalmente, concluimos a partir de (4) y (6):

El número $N(r,m,n)$ de trayectorias válidas es \begin{align*} \color{blue}{N(r,m,n)}&=\sum_{t=r}^n[z^t]\left(2zc(z)\right)^r [z^{m-t}](zc(z))^{m-n}\\ &=\frac{1}{2^{m-n}}\sum_{t=r}^n[z^t]\left(2zc(z)\right)^r [z^{m-t}](2zc(z))^{m-n}\\ &=\frac{1}{2^{m-n}}[z^m](2zc(z))^{m-n+r}\\ &=\frac{1}{2^{m-n}}[z^m](1-\sqrt{1-4z})^{m-n+r}\\ &\color{blue}{=2^r\frac{m-n+r}{m+n-r}\binom{m+n-r}{n-r}}\\ \end{align*}

Por ejemplo: $N(1,3,2)$

Calculemos el ejemplo de OP $N(1,3,2)$ contando el número de caminos que tocan el $x$ -eje $r=1$ tiempo consistente en $m=3$ escalones y $n=2$ escalones hacia abajo. Obtenemos de (3) \begin{align*} \color{blue}{N(1,3,2)}&=2\cdot\frac{2}{4}\binom{4}{1} \color{blue}{= 4} \end{align*} Codificación de las subidas con $U$ y bajadas con $D$ las rutas válidas son

\begin{align*} D\ D\ U\ \color{blue}{U}\ U\\ D\ \color{blue}{U}\ U\ U\ D\\ U\ \color{blue}{D}\ U\ U\ D\\ U\ U\ D\ \color{blue}{D}\ U\\ \end{align*}

Los caracteres azules marcan tocar el $x$ -Eje.

Por ejemplo: $N(2,5,3)$

Un ejemplo más con trayectorias formadas por $5$ escalones y $3$ pasos hacia abajo tocando el $x$ -eje dos veces. Obtenemos de (3) \begin{align*} \color{blue}{N(2,5,3)}&=2^2\cdot\frac{4}{6}\binom{6}{1} \color{blue}{= 16} \end{align*}

En $16$ rutas válidas

\begin{align*} \ D\ D\ U\ \color{blue}{U}\ D\ \color{blue}{U}\ U\ U\qquad&\qquad U\ \color{blue}{D}\ D\ D\ U\ \color{blue}{U}\ U\ U\\ D\ D\ U\ \color{blue}{U}\ U\ \color{blue}{D}\ U\ U\qquad&\qquad U\ \color{blue}{D}\ D\ \color{blue}{U}\ U\ U\ D\ U\\ D\ \color{blue}{U}\ D\ D\ U\ \color{blue}{U}\ U\ U\qquad&\qquad U\ \color{blue}{D}\ D\ \color{blue}{U}\ U\ U\ U\ D\\ D\ \color{blue}{U}\ D\ \color{blue}{U}\ U\ U\ D\ U\qquad&\qquad U\ \color{blue}{D}\ U\ \color{blue}{D}\ U\ U\ D\ U\\ D\ \color{blue}{U}\ D\ \color{blue}{U}\ U\ U\ U\ D\qquad&\qquad U\ \color{blue}{D}\ U\ \color{blue}{D}\ U\ U\ U\ D\\ D\ \color{blue}{U}\ U\ \color{blue}{D}\ U\ U\ D\ U\qquad&\qquad U\ \color{blue}{D}\ U\ U\ D\ \color{blue}{D}\ U\ U\\ D\ \color{blue}{U}\ U\ \color{blue}{D}\ U\ U\ U\ D\qquad&\qquad U\ U\ D\ \color{blue}{D}\ D\ \color{blue}{U}\ U\ U\\ D\ \color{blue}{U}\ U\ U\ D\ \color{blue}{D}\ U\ U\qquad&\qquad U\ U\ D\ \color{blue}{D}\ U\ \color{blue}{D}\ U\ U\\ \end{align*}

Los caracteres azules marcan tocar el $x$ -Eje.

Answer 2

¡Ya lo tengo! Se puede resolver utilizando función generadora .

solución(actualizada)

\begin{equation} Z( m,n, r ) = 2^r \frac{m - n + r}{m + n -r} {m + n - r \choose n - r} \quad m \ge n \end{equation}

consulte :

$m = 3, n = 2, r = 1$ , \begin{equation} Z( 3, 2, 1 ) = 2^1 \frac{3 - 2 +1}{3+2-1} {3 + 2 -1 \choose 2 - 1} = 2 \frac{2}{4} { 4 \choose 1 } = 4 \rightarrow \text{correct} \end{equation}

$m = 5, n = 3, r = 2$ Esto ha sido enumerado por @MarkusScheuer (¡gracias!) \begin{equation} Z( 5, 3, 2 ) = 2^2 \frac{5 - 3 + 2}{5 + 3 - 2} { 5 + 3 - 2 \choose 3 - 2} = 4 \frac{4}{6} { 6 \choose 1 } = 16 \rightarrow \text{correct} \end{equation}

caso diagonal

Considere $Z(n,n,2 )$ . Ahora tenemos dos aciertos en la diagonal. Sea el primer acierto $(k,k)$ hay $Z( k, k, 1 ) Z( n-k, n-k, 1)$ posibilidades. Enumerando el primer acierto, tenemos \begin{equation} Z( n,n, 2 ) = \sum_{k=1}^{n-1} Z( k, k ,1 ) Z( n -k, n-k ,1 ) \end{equation} Utilizando la función generadora \begin{equation} f(x) = \sum_{k=0}^{\infty} Z( k, k, 1 ) x^k = \sum_{k=0}^{\infty} 2 \frac{1}{k} {2k -2 \choose k - 1} = 1 - \sqrt{ 1- 4x} \end{equation} tenemos \begin{equation} Z( n, n, 2 ) = \text{coefficient of }x^n \text{ in } [f(x)]^2 \end{equation}

Del mismo modo, $Z( n,n, r )$ es el coeficiente de $x^n$ en $[f(x)]^r$ .

Este resultado es un caso especial del resultado más general de Spivey, Michael Z. , Enumerar los caminos de la red que tocan o cruzan la diagonal en un número dado de puntos de la red Electron. J. Comb. 19, No. 3, Research Paper P24, 6 p. (2012). ZBL1253.05020 ., \begin{equation} Z( n, n, r ) = 2^r \left[{ 2n - r - 1 \choose n - r } - { 2n - r - 1 \choose n - r -1 }\right] = \frac{r 2^r}{2n - r }{ 2n - r \choose n - r } \end{equation}

Déjame comprobarlo con mi resultado. La función generadora para $Z(n ,n, r )$ es \begin{equation} \begin{aligned} f_r(x) &= \sum_{k =0}^{\infty} 2^r \left[{ 2k - r - 1 \choose k - r } - { 2k - r - 1 \choose k - r - 1 }\right] x^k \\ &= 2^r x^r \sum_{k=0}^{\infty} { 2k + r - 1 \choose k } - 2^r x^{r+1} \sum_{k=0}^{\infty} { 2k + r +1 \choose k }\\ &= 2^r x^r [ {}_2 F_1( \frac{r}{2}, \frac{r+1}{2}; r; 4x ) - x {}_2 F_1( \frac{r}{2}+1, \frac{r+3}{2}; r+2; 4x )]\\ &= \left[\frac{4x}{1 + \sqrt{1-4x}} \right]^r \text{ by Mathematica}\\ &= [ 1 - \sqrt{ 1- 4x} ]^r = [f(x)]^r \rightarrow \text{ correct! } \end{aligned} \end{equation} donde utilicé la relación \begin{equation} \sum_{k=0}^{\infty} { 2k + a \choose k } x^k = {}_2 F_1( \frac{a+1}{2}, \frac{a+2}{2}; a+1; 4x ) \end{equation}

caso no diagonal

Para $m >n$ sólo tenemos que enumerar el último punto de impacto \begin{equation} Z( m, n, r ) = \sum_{k= r}^{n} Z( k, k, r ) Z( m -k, n-k , 0 ) \end{equation}

La elección adecuada de la función generadora para el último segmento (sin golpear la diagonal) es \begin{equation} g(x, a) = \sum_{k=0}^{\infty} Z( k, k-a, 0 ) x^k \end{equation} para que $Z( m,n, r) $ es el coeficiente de $x^m$ en $[f(x)]^r g(x, m -n ) $ .

En $g(x, a )$ puede calcularse de forma similar al caso diagonal, \begin{equation} g(x, a ) = \sum_{k = 0}^{\infty} { 2k - a -1 \choose k-a} x^k - \sum_{k = 0}^{\infty} { 2k - a -1 \choose k -a - 1 }x^k = \frac{(1 - \sqrt{ 1- 4x })^a}{2^a } \end{equation} de ahí $Z( m,n, r )$ es el coeficiente de $x^m$ en \begin{equation} \frac{( 1 -\sqrt{ 1- 4x })^{r + m - n} }{2^{m-n}} \end{equation} que puede construirse a partir del caso diagonal $$\begin{equation} \begin{aligned} Z( m,n, r ) &= \frac{1}{2^{m-n} }Z( m, m, r+ m-n ) \\ &= 2^r \left[{m + n - r -1 \choose n - r} - {m + n - r -1 \choose n - r - 1}\right]\\ &= 2^r \frac{m - n + r }{m + n -r} {m + n - r \choose n - r} \end{aligned} \end{equation}$$

Esto también funciona para el caso diagonal.

control elemental

Para el punto fijo $(m, n)$ el número de trayectorias reticulares sin restricción es \begin{equation} \begin{aligned} \sum_{r=0}^{n} Z( m,n,r ) &= \sum_{r=0}^n 2^r \left[{m + n - r -1 \choose n - r} - {m + n - r -1 \choose n - r - 1}\right] \\ &= {m + n -1 \choose n } - {m + n -1 \choose n - 1} + 2 \left[{m + n -2 \choose n-1 } - {m + n -2 \choose n - 2} \right] + \cdots \\ &= {m + n -1 \choose n } + {m + n -2 \choose n-1 } \\ & \quad - 3 {m + n -2 \choose n - 2} + 4 \left[{m + n -3 \choose n-2 } - {m + n -3 \choose n - 4} \right]\\ &= \sum_{r=0}^{n} {m + n -r -1 \choose n - r } = \sum_{k=0}^{n}{ m-1 +k \choose m-1 } = { m \choose n } \rightarrow \text{correct} \end{aligned} \end{equation}

problema de longitud fija

Para simplificar, dejemos que la longitud total $n + m $ ser un número entero impar $2k+1$ . Desde el $ m < n$ caso es el reflejo de $ m > n$ podemos contar el último caso y multiplicar por $2$ . El número de todas las trayectorias de celosía que llegan a la diagonal $r$ veces es \begin{equation} \begin{aligned} Z( 2k+1, r ) &= 2\sum_{n = r}^{k} Z( 2k +1 -n, n, r ) = 2^{r+1} \sum_{n=r}^k\left[ { 2k - r \choose n - r } - { 2k -r \choose n - r -1 } \right] \\ &= 2^{r+1} { 2k -r \choose k - r } \end{aligned} \end{equation}

Answer 3

Se me ocurrió una prueba visual de \begin{equation} Z(m,n, r ) = 2^r \frac{m - n + r}{m + n - r} { m + n - r \choose n- r } \end{equation} que es más fácil que mi enfoque de la función generadora. Creo que merece una respuesta aparte.

En $2^r$ factor

Dividir una trayectoria reticular de $r$ intersecciones con la diagonal en $r$ segmentos en los que el $i$ -El segmento $i$ -y el punto de intersección $i+1$ -th.

Cada segmento es un camino de celosía que se cruza con la diagonal sólo en el punto final y hay dos posibilidades: ir por encima o soplar el $ y = x$ línea. Por lo tanto, podemos considerar sólo la trayectoria de la red por debajo de $y = x$ (se muestra en la figura de la izquierda). Llame al número correspondiente de caminos de celosía a ser $Z_{-}( m,n, r )$ tenemos \begin{equation} Z( m, n, r ) = 2^r Z_{-} ( m, n, r ) \end{equation}

Reducción a $r = 0$

Tomar un camino de celosía por debajo de la línea $ y= x$ . En todos los puntos de intersección, el paso anterior debe ser ascendente (marcado en azul en la figura de la izquierda).

Si eliminamos esos escalones azules, acabamos con un camino en la figura de la derecha que parte de $(0,0)$ y termina en $(m, n - r)$ . Este camino no llegará a la diagonal $y = x$ . Por otro lado, también podemos reconstruir el camino original dibujando hacia atrás y complementando un paso azul al llegar a la diagonal. Para el ejemplo de la figura de la derecha, primero movemos el último paso rojo "yendo hacia la derecha" al lugar entre $(m-1,n)$ y $(m,n)$ . Si llega a la diagonal(lo hace), complementamos un paso azul; si no, retomamos el paso rojo anterior.

Este procedimiento establece un correspondencia individual entre la ruta de $(0,0)$ a $(m,n)$ debajo de $ y= x$ que golpea la diagonal $r$ veces, con la ruta de $(0,0)$ a $( m, n-r)$ que no golpea la diagonal en absoluto.

Equivalentemente, \begin{equation} Z_{-} ( m, n, r ) = Z( m, n -r, 0) \end{equation}

Conclusión

Por lo tanto, concluimos que \begin{equation} Z(m,n, r ) = 2^r Z(m,n-r, 0) = 2^r \left[ { m + n - r - 1\choose n- r }-{m + n -r -1 \choose n- r - 1 }\right] = 2^r \frac{m - n + r}{m + n - r} { m + n - r \choose n- r } \end{equation}