Pares de caminos más cortos

Question

Se sabe que el coeficiente binomial $2n \choose n$ es igual al número de caminos de red más cortos desde $(0,0)$ a $(n,n)$ . El número catalán $\frac{1}{n+1} {2n\choose n}$ es igual al número de caminos más cortos de la red que nunca pasan por encima de la diagonal. En este caso, la diagonal puede verse como un camino desde $(0,0)$ a $(n,n)$ .

¿Existe una fórmula para el número de pares $(P_{1},P_{2})$ donde cada $P_{i}$ es un camino de red más corto desde $(0,0)$ a $(n,n)$ tal que $P_{1}$ nunca pasa de $P_{2}\ ?$ Aquí, " $P_{1}$ nunca pasa de $P_{2}$ " significa que $P_{1}$ se encuentra dentro o en el límite de la región determinada por $P_{2}$ El $x$ -y la línea $x=n$ .

Answer 1

¡La respuesta es (2n)! ¡(2n+1)! / (n)!^2 (n+1)!^2 .

Se puede obtener mediante el método Gessel-Viennot sugerido anteriormente. Una de las dificultades es que GV quiere contar los caminos que no se tocan en absoluto, incluso en los vértices, mientras que tú sólo quieres contar los caminos que no se cruzan. Para resolver esto, toma tu camino inferior y deslízalo hacia el sureste. Ahora estás buscando dos caminos, uno de (0,0) a (n,n) y otro de (-1,1) a (n-1,n+1), que no se tocan en absoluto.

El método GV da el determinante

(2n elegir n) (2n elegir n+1)

(2n elegir n-1) (2n elegir n)

Ampliando esto y simplificando da lo anterior, si no me he equivocado.

Answer 2

Si se hace la pregunta análoga sobre p caminos no cruzados en un rectángulo de m x n, se está contando esencialmente particiones planas (si se escribe en cada casilla el número de caminos que tiene encima, entonces todas las filas y columnas son débilmente decrecientes). Existe entonces una hermosa fórmula de MacMahon para el número de éstos: es el producto de (i+j+k-1)/(i+j+k-2) sobre todos los 1<=i<=m, 1<=j<=n, 1<=k<=p.

Answer 3

También deberías buscar el teorema de (Lindström-) Gessel-Viennot para trayectorias no intersecantes, que cuenta, por sorpresa, conjuntos de trayectorias de celosía no intersecantes, y los expresa como un determinante.

Answer 4

A continuación se presenta una idea para expresar la respuesta en términos de suma de números catalanes.

Construya una secuencia de tamaño (2n) para P1 de manera que el término i-ésimo sea 1 si P1 se mueve hacia arriba en el paso i-ésimo, y 0 en caso contrario. Lo mismo ocurre con P2. Por ejemplo, cuando n=4, y P1 es RRURUURU, la secuencia es (0,0,1,0,1,1,0,1); si P2 es UUURRURR, la secuencia es (1,1,1,0,0,1,0,0).

Se considera la secuencia de P2 menos la secuencia de P1. Por ejemplo, en el último párrafo, obtenemos (1,1,1,0,0,1,0,0) - (0,0,1,0,1,1,0,1) = (1,1,0,0,-1,0,0,-1).

La secuencia de diferencia tiene algunas propiedades:

1) Cada término es 1, 0 o -1.

2) La suma parcial nunca es negativa.

Por lo tanto, podemos obtener la respuesta numérica mediante

a) elegir una secuencia catalana de tamaño k (donde n>=k>=0)

b) en la secuencia de diferencia elegir 2k coordenadas para la secuencia catalana

c) en las otras coodinadas, poner ceros

d) los k uno deben corresponder a k arriba en la secuencia de P2. Sin embargo, hay algunos otros (n-k) ups de P2, que está "escondido" en los ceros de la secuencia de diferencia (como la tercera coordenada en el ejemplo que menciono arriba). Así que tenemos que elegir (n-k) ceros correspondientes a los ups de la secuencia de P2

Esto da la respuesta

$sum_{k=0}^n C(2n,2k) C_k C(2n-2k,n-k) = \sum_{k=0}^n (2n)! / (2k)! / ((n-k)!)^2 * C_k,$

donde $C_k$ es el k-ésimo número catalán, y $C(a,b)$ es "a elige b".

La suma puede simplificarse utilizando la función generadora exponencial, pero no estoy seguro en este momento. ¿Algún comentario?

Answer 5

El número de estos pares es (n^2+1)(n^2+2)/2.

Justificación:

Permítanme replantear los pares (P1,P2) de la siguiente manera: tomemos el diagrama de Ferrers trazado por P1, el eje x y la recta x=n; la pregunta es sobre el número de subdiagramas, incluyendo el diagrama nulo trazado por el camino P2 que recorre el eje x y luego la recta x=n.

Para contar el número de pares (P1,P2), añadamos un cuadrado cada vez al diagrama de Ferrers (rellenando las columnas antes que las filas, por ejemplo), y contemos cuántos subdiagramas tiene (delimitados por P2). Mediante este proceso, contamos el diagrama nulo n^2+1 veces, el diagrama con un solo cuadrado n^2 veces, el diagrama con dos cuadrados n^2-1 veces, ..., el diagrama con todos los n^2 cuadrados exactamente una vez.

Por lo tanto, el número de estos pares es \sum_ {k=1}^{n^2+1}k = (n^2+1)(n^2+2)/2.