Se sabe que el número de caminos de Dyck en un cuadrado es igual a los números catalanes: http://mathworld.wolfram.com/DyckPath.html Pero, ¿y si, en lugar de un cuadrado, hacemos la misma pregunta con un rectángulo? Si uno de sus lados es múltiplo del otro, de nuevo existe una buena fórmula para el número de recorridos por debajo de la diagonal, pero ¿existe una buena fórmula en general? ¿Cuál es el número de trayectorias desde la esquina inferior izquierda de un rectángulo con longitudes de lado a y b hasta su esquina superior derecha que quedan por debajo de la diagonal (excepto su punto final)? También me interesa la asintótica.
Respuestas
¿Demasiados anuncios?
Colin Pickard
Puntos
161
El pasado mes de marzo escuché una charla de Timothy Chow en la Universidad de Indiana. Aquí está su resumen, que parece dar una respuesta negativa a tu pregunta sobre los rectángulos cuyos lados tienen una proporción no entera:
Es un resultado clásico que si k es un número entero positivo, entonces el número de trayectorias de la red desde (0,0) hasta (a+1,b) tomando pasos unitarios hacia el norte o el este que evitan tocar o cruzar la línea x = ky es
(a+b elegir b) - k (a+b elegir b-1).
Lamentablemente, no se conoce una fórmula tan sencilla si k es racional pero no es un número entero (aunque existe una fórmula determinante). Demostramos que si sustituimos la frontera de la línea recta por una frontera periódica en forma de escalera, y si elegimos cuidadosamente nuestros puntos de partida y de llegada, entonces se cumple la generalización natural de la fórmula simple anterior. Variando ligeramente la frontera obtenemos otros casos con fórmulas sencillas, pero sigue siendo un tanto misterioso cuándo se puede esperar una fórmula sencilla. Si el tiempo lo permite, también describiremos algunos trabajos recientes de Irving y Rattan que proporcionan una prueba alternativa de algunos de nuestros resultados.
Este es un trabajo conjunto con Chapman, Khetan, Moulton y Waters.
I probé con (y lo intentó de nuevo ) para mejorar el artículo de Wikipedia, pero las ediciones fueron rápidamente revertidas como si las conocidas soluciones de Lights Out fueran "investigación original", a pesar de proporcionar varias citas.
Si algún miembro de Stack Exchange es wikipedista y puede ayudar a restaurar el artículo, se lo agradecería mucho. Además, dirigiría esta petición de forma más apropiada si pudiera, pero no veo la forma de contactar con John Smith directamente. Siéntase libre de borrarlo.
dsims
Puntos
842
¿Está bien una suma?
Estoy acostumbrado a una rotación diferente de los caminos. Creo que las trayectorias que buscas también pueden describirse como todas las trayectorias sobre el eje x, con pasos (1,1) y (1,-1), que comienzan en (0,0) y terminan en la línea x=y+n para algún (x,y) de (n,0) a (n+m,m).
(Si por el contrario terminan en la línea x=n, obtenemos los caminos de las papeletas).
Sea B(n,k) los números de la boleta, B(n,k)= # caminos de (0,0) a (n,k). Ahora, todos los caminos deben pasar por la línea x=n. A partir de ahí es sólo un camino binomial, por lo que el número de caminos son suma_{k=0,2,4,...,n} B(k,n)*( (n-m-k)/2 elige k/2)
(n elige k)= ¡Coeficiente binomial, n!/(k!(n-k)!)
Jeff Atwood
Puntos
31111
Si he entendido bien tu pregunta, los números que buscas se llaman Números de boleta . El número de caminos de $(0,0)$ a $(m,n)$ (donde $m>n$ ) que quedan por debajo de la diagonal es $\frac{m-n}{m+n}\binom{m+n}{m}$ .
Además, si $m>r \cdot n$ entonces el número de caminos de la red desde $(0,0)$ a $(m,n)$ que se mantienen por debajo de la línea $x=r\cdot y$ es $\frac{m-rn}{m+n}\binom{m+n}{m}$ . (No lo he resuelto, pero Ira Gessel lo dice en Introducción a la enumeración de rutas de celosía )
