Número de rutas óptimas a través de una cuadrícula con una restricción de ruta ordenada

Question

Número de rutas óptimas a través de una cuadrícula con una restricción de ruta ordenada

Matemáticas
Teoría de grafos
combinatoria
Matemáticas discretas

Pariente0

Encontré, pero la genial explicación de Arturo Magidin: Contar número de movimientos en una cuadrícula

el número de caminos para una matriz MxN. Si estoy pensando en esto correctamente (diga algo si me equivoco), pero la cantidad de rutas óptimas/más cortas desde la esquina inferior izquierda @ (0,0) hasta la esquina superior derecha @ (m,n) es cualquier ruta eso se puede hacer en m + n movimientos, ya que tendríamos que mover al menos m espacios a la derecha y n espacios hacia arriba en algún punto. Si no hay "retroceso", es decir, que no hay movimientos permitidos hacia abajo o hacia la izquierda, entonces todos los caminos serán de tamaño m + n. Por lo tanto, el número total de caminos de (0,0) a (m,n) es $\binom{m + n - 1}{m}$ o $\binom{m + n -1}{n}$ como no nos importa el orden y, por lo tanto, podría ser transversal con respecto a m o n, ambos nos llevan al punto final.

La pregunta que estoy tratando de resolver es que cuando decimos que tenemos que movernos hacia arriba (al menos una vez) por cada movimiento hacia la derecha. Por lo tanto, un movimiento a la derecha tiene que ser seguido por uno o se mueve hacia arriba. Ahora veo (o creo que veo) que tendríamos el número total de caminos posibles como arriba (sin ciclos o movimientos hacia abajo o hacia la izquierda) menos aquellos caminos que tienen dos movimientos hacia la derecha RR o hacia arriba seguidos. Así podríamos tener RUURURUUUR, pero nada como RUURR...

No veo cómo hacer esto. Tengo curiosidad tanto por la forma directa (combinatoriamente) como por la solución recursiva si a alguien no le importaría echarme una mano.

Gracias,

Brian

desinst.

Es la restricción de que cada R debe ir seguida de una U, o que el número total de R debe ser menor o igual que el número total de U. Si es lo primero, el análisis anterior se puede modificar para que encaje. Si es lo último, busque Dyck Paths, el artículo de wikipedia sobre números catalanes es un buen lugar para comenzar.

Pariente0

Edité la pregunta para que quede más clara. Sin embargo, en respuesta, cada movimiento hacia la derecha TIENE que ser seguido por una o más subidas. El número de R no tiene que ser menor o igual que las U, todo esto depende de la cuadrícula rectangular, es decir, si la cuadrícula es más larga verticalmente que horizontalmente, las U serán más que el número de R, pero si la cuadrícula es más ancho que alto tendremos más R's.

extraño

¿No debería ser el número de caminos de (0,0) a (m,n) C(m+n,m) o C(m+n,n)? (Maldita sea, no puedo hacer que LaTex funcione para mí).

Respuestas (2)

Número de rutas óptimas a través de una cuadrícula con una restricción de ruta ordenada

Es la restricción de que cada R debe ir seguida de una U, o que el número total de R debe ser menor o igual que el número total de U. Si es lo primero, el análisis anterior se puede modificar para que encaje. Si es lo último, busque Dyck Paths, el artículo de wikipedia sobre números catalanes es un buen lugar para comenzar.
Edité la pregunta para que quede más clara. Sin embargo, en respuesta, cada movimiento hacia la derecha TIENE que ser seguido por una o más subidas. El número de R no tiene que ser menor o igual que las U, todo esto depende de la cuadrícula rectangular, es decir, si la cuadrícula es más larga verticalmente que horizontalmente, las U serán más que el número de R, pero si la cuadrícula es más ancho que alto tendremos más R's.
¿No debería ser el número de caminos de (0,0) a (m,n) C(m+n,m) o C(m+n,n)? (Maldita sea, no puedo hacer que LaTex funcione para mí).

extraño · Answer 1

Envuelva RU con cinta adhesiva y considérelo como un carácter; debe haber m de estos. También debe haber nm U no precedido por una R. (Por lo tanto $n \ge m$ .) Así que hay

(\binom{norte}{metro}) = (\binom{norte}{norte - metro})

$\binom{n}{m} = \binom{n}{n-m}$ arreglos aceptables.

Foo Barrigno · Answer 2

Dejar $m$ Sea la dirección horizontal y $n$ sea la dirección vertical.

Si $m>n+1$ , no existen tales caminos ya que siempre habrá al menos un conjunto de $RR$ s en el camino.

Dado que cada R debe tener una U en el medio, siempre podemos comenzar con al menos $RURU...URUR$ como patrón. Por lo tanto, necesitamos al menos $m-1$ $U$ se mueve

El "excedente" se puede organizar de la forma que mejor nos parezca. Entonces hay $\Big(\binom{n-m+1}{n+1}\Big)$ maneras de organizar su "extra" $U$ se mueve entre el $R$ se mueve - o antes de la primera $R$ mover o después del último $R$ moverse, donde $\Big(\Big(.\Big)\Big)$ es la notación para el coeficiente multiconjunto.

Número de rutas óptimas a través de una cuadrícula con una restricción de ruta ordenada

Pariente0

desinst.

Pariente0

extraño

Respuestas (2)

extraño

calvin lin

Foo Barrigno

Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2

Problema sobre la existencia de un ciclo de Bruijn.

Pregunta sobre una prueba de "El gráfico GGG no tiene ciclos impares ⟹⟹\implica que GGG es bipartito"

probar que para n≥2n≥2n \geq 2 no existe un grafo simple de n-vértices cuyos vértices tengan grados distintos

Para cada n≥2n≥2n \geq 2 existe un grafo simple de n-vértices cuyos vértices tienen grados distintos

Número máximo de ciclos de expansión sin borde común en un gráfico completo

Varias pruebas relacionadas con las definiciones de árboles y bosques.

¿Por qué el problema del vendedor ambulante es "difícil"?

Definición de gráfico bipartito del libro de Murty-Bondy

Demuestre que el tamaño del gráfico de Turan Tr(n)Tr(n)T_r(n) es al menos (1−1r)(n2)(1−1r)(n2)(1 - \frac{1}{r} ) \binom{n}{2}.