dada la cuadrícula dirigida a continuación de tamaño , me gustaría obtener el número de camino posible de longitud , .
Ejemplo de cuadrícula de tamaño 4 x 4
Te mueves desde abajo a la izquierda (inicio) hasta arriba a la derecha (terminar). Los pasos que puede hacer son subir, ir a la derecha o ir en diagonal. En clase, vimos que el número total de rutas en dicho gráfico viene dado por lo siguiente: .
Mi intuición fue decir que para cada , el número de camino de longitud es definido por . Hice el cálculo a mano para cuadrículas de tamaño 1,2,3,4 y parece funcionar. Posteriormente, el cálculo es demasiado largo para hacerlo a mano.
Mi pregunta es la siguiente, ¿tiene sentido? Y si es así, ¿podría explicarme por qué funciona, por ejemplo, cómo significa en este caso elegir ¿caminos?
Dejar sea el número de movimientos hacia la derecha, hacia arriba y en diagonal, respectivamente.
Entonces tenemos eso y ,
(ya que un movimiento diagonal resulta en un movimiento hacia la derecha y hacia arriba al mismo tiempo),
entonces y .
La cantidad de formas de organizar a nosotros, r, y d's en orden está dada por
,
puesto que hay formas de colocar las u y luego Formas de colocar las r.
