Notas sobre Rutas y Trayectorias en Rejillas

Rutas y trayectorias en rejillas

• Contexto general: prácticas sobre rutas y trazos de figuras; enfoque en movimientos permitidos a lo largo de una rejilla desde un punto A hasta un punto B, usando únicamente direcciones específicas (por ejemplo, derecha y abajo o izquierda y arriba).
• Enfoque típico: cada ruta desde A a B corresponde a una secuencia de movimientos en una rejilla rectángulo, con un número fijo de pasos en cada dirección.

Conceptos clave

• Trayectoria monotónica en rejilla: recorrido desde A a B moviéndose solo en direcciones que no retroceden respecto a las coordenadas (p. ej., derecha y abajo).
• Coordenadas básicas: si A está en
  • A = (0,0) y B está en (m, n), entonces se requieren exactamente m movimientos hacia la derecha y n movimientos hacia abajo.
• Número de rutas totales de A a B con movimientos permitidos (derecha y abajo):
  • Se trata de contar todas las secuencias de una cadena con m símbolos R (derecha) y n símbolos D (abajo).
  • Fórmula principal:
  • $N = \binom{m+n}{m} = \binom{m+n}{n}$
  • Explicación combinatoria: entre los m+n movimientos, hay que elegir en qué posiciones irán los movimientos hacia la derecha (o, equivalentemente, hacia abajo).
• Relevancia de la simetría: la cantidad es la misma si se intercambian las direcciones (R y D) al invertir la trayectoria de A a B o de B a A.

Movimiento en direcciones opuestas

• Si las direcciones permitidas son izquierda y arriba (en lugar de derecha y abajo) para ir de B a A, el conteo es igual al de A a B, ya que se invierten las direcciones de la misma secuencia de movimientos.
• En general, el conteo depende solo de cuántos movimientos en cada eje son necesarios, no de la orientación exacta de las direcciones.

Pasar por un punto intermedio

• Si la ruta debe pasar por un punto M = (i, j) entre A y B (con A en (0,0) y B en (m,n)), el total se obtiene multiplicando los conteos de cada tramo:
• Número de rutas A → M:
• $N_{A\to M} = \binom{i+j}{i} = \binom{i+j}{j}$
• Número de rutas M → B:
• $N_{M\to B} = \binom{(m-i)+(n-j)}{m-i} = \binom{(m-i)+(n-j)}{n-j}$
• Total pasando por M:
• $N<em>{A\to M\to B} = N</em>{A\to M} \cdot N_{M\to B}$
• Para pasar por varias intermedias M, N en orden monotónico (A → M → N → B), se multiplican los conteos de cada tramo correspondiente.

Ejemplos numéricos (ilustrativos)

• Ejemplo 1: A a B con 3 movimientos a la derecha y 2 movimientos hacia abajo.
  • Conteo: $N = \binom{3+2}{3} = \binom{5}{3} = 10$
• Ejemplo 2: A a B con 4 movimientos a la derecha y 3 movimientos hacia abajo.
  • Conteo: $N = \binom{4+3}{4} = \binom{7}{4} = 35$
• Ejemplo 3: A → M → B con A=(0,0), M=(2,1), B=(4,3).
  • $N_{A\to M} = \binom{2+1}{2} = \binom{3}{2} = 3$
  • $N_{M\to B} = \binom{(4-2)+(3-1)}{4-2} = \binom{4}{2} = 6$
  • Total: $N_{A\to M\to B} = 3 \cdot 6 = 18$

Notación y fórmulas en LaTeX

• Ruta total entre dos puntos (A=(0,0) y B=(m,n)):
• $N = \binom{m+n}{m} = \binom{m+n}{n}$
• Tramo A→M (con M=(i,j)):
• $N_{A\to M} = \binom{i+j}{i}$
• Tramo M→B (con B=(m,n)):
• $N_{M\to B} = \binom{(m-i)+(n-j)}{m-i}$
• Ruta A→B pasando por M:
• $N<em>{A\to M\to B} = N</em>{A\to M} \cdot N_{M\to B}$

Consejos prácticos para resolver las prácticas

• Asegúrate de definir correctamente el destino B y las direcciones permitidas (derecha/abajo o izquierda/arriba).
• Si te piden pasar por puntos intermedios, verifica que estén en orden monotónico compatible con las direcciones permitidas.
• Para grandes valores de m y n, usa la identidad binomial y evita calcular factoriales grandes directamente (puedes usar propiedades de cociente de factoriales).
• Si ves soluciones que calculan productos (por ejemplo, 70 × 56 = 3920) para conteos de rutas, recuerda que el conteo correcto de rutas en una rejilla es un número binomial, no un producto directo de dimensiones; verifica con N = \binom{m+n}{m}.

Aplicación a la práctica dada (contextualizado desde la transcripción)

• En la práctica se piden:
  • 2) De cuántas maneras se puede ir de A a B moviéndose solo hacia la derecha y hacia abajo. Utiliza la fórmula $N = \binom{m+n}{m}$.
  • 4) De cuántas maneras se puede ir de A a B pasando por M y N (en el orden adecuado si aplica). Usa la multiplicación de rutas por tramos: $N = N<em>{A\to M} \cdot N</em>{M\to N} \cdot N_{N\to B}$, siempre que M y N estén coordinadamente en la trayectoria monotónica.
• Observación para revisión: la solución mostrada en la transcripción incluye un cálculo como $170 \times 56 = 3920$; este resultado no representa directamente el conteo binomial de rutas y debe ser verificado con la fórmula correcta $N = \binom{m+n}{m}$ o con el producto de subtramos si corresponde.

Resumen rápido

• El conteo de rutas monotónicas en una rejilla es un problema de combinatoria básico.
• La clave es contar secuencias de movimientos: si se requieren m movimientos en una dirección y n en la otra, el número de rutas es $N = \binom{m+n}{m}$.
• Para rutas que deben pasar por puntos intermedios, multiplicas los conteos de cada tramo entre puntos en orden permitido.
• Al practicar, siempre verifica la consistencia de las direcciones permitidas y la ordenación de puntos intermedios; si no hay monotonicidad, el problema cambia.