Como señala correctamente Joriki en su respuesta, esto ya se ha investigado, y no se conoce ninguna forma cerrada. En cambio, hay estimaciones asintóticas dadas. Sin embargo, sería bueno tener algo elemental aquí en este sitio, así que compartiré un argumento de límite inferior realmente básico que llamaré el argumento de la "serpiente".
Considere un $n \times m$ rejilla, con $n$ impar. Una forma de construir tal camino en esta cuadrícula es serpentear como sigue:
$$(0, 0) \rightarrow (0, 1) \dots \rightarrow (0, m) \rightarrow \\ (1, m) \rightarrow (1, m - 1) \dots \rightarrow (1, 0) \rightarrow \\ \dots \rightarrow \\ (n, 0) \rightarrow (n, 1) \rightarrow dots \rightarrow (n, m)$$
Pero si se "aleja", y se considera todo el $n \times m$ rectángulo como una sola columna de longitud $n$ entonces podemos repetir el proceso de la serpiente, es decir, podemos movernos a lo largo de este rectángulo de tamaño $n \times m$ y luego de vuelta a lo largo de otro de posiblemente un tamaño diferente $n \times m'$ y así sucesivamente.
Ahora, cualquier secuencia de números $m_1, m_2, \dots, m_h$ tal que $\sum_{k =1}^h m_k = n$ corresponde exactamente a un camino serpenteante de este tipo. Así que tenemos un límite inferior en el número de caminos es el número de números que suman a nuestro número en cuestión. Por estrellas y barras, este número es simplemente $2^{n -1}$ que es un límite inferior del número de caminos para el tamaño del cuadrado $n$ . Obviamente esto es patético comparado con el límite conocido $\tau^{O(n^2)}$ pero al menos la derivación es elemental y no completamente trivial: es al menos un límite exponencial en $n$ .
Creo que esta idea podría llevarse mucho más lejos, ya que sólo he considerado un subconjunto muy restringido de estas estructuras "serpenteantes". Además, esto se generaliza fácilmente de un cuadrado a un rectángulo.
Ejemplo de imagen de serpentina a continuación
![Rough Sketch of the Snake Idea]()
Un argumento aproximado de por qué esta función crece como $\tau^{n^2}$ es la siguiente. Sea $A_n$ sea el número de tales caminos desde la esquina inferior izquierda de un cuadrado de lado $n$ a su esquina superior derecha. Consideremos ahora un cuadrado de longitud lateral $n^2$ es decir $n^4$ células en total.
Ahora, podemos "alejarnos" de este cuadrado y observar que tiene $n^2$ subcuadrados, cada uno de ellos de lado $n$ . Entonces es posible construir un camino en este gran cuadrado combinando caminos en cada uno de estos subcuadros. Entonces tenemos la desigualdad de recurrencia $A_{n^2} \geq (A_n)^{n^2}$ . A partir de aquí podemos razonar inductivamente. Suponiendo que $A_n \geq C \tau^{n^2}$ entonces $A_{n^2} \geq C \tau^{n^4}$ . Y así sucesivamente para $n^8, n^{16}, n^{32}, \dots, n^{2^k}, \dots$ Así que se intuye por qué crece a ese ritmo.
