Número de la forma a la forma de movimiento $(1,1)$ $(n,n)$en un cuadrado de la cuadrícula de tomar exactamente $k$ vueltas

Question

Dado un cuadrado de la cuadrícula de tamaño $n \times n (n>2)$, hallar el número de maneras de mover el formulario de $(1,1)$ $(n,n)$utilizando sólo la derecha y abajo de dirección y tomar exactamente $k$ giros( una vez, es un derecho de mover, seguida de inmediato por una mudanza o un abajo mover seguido inmediatamente por un derecho de moverse $0 < k < 2n-2$).

Si quitamos "exactamente $k$" cláusula, el problema es fácil, pero tenemos que tener cuidado de vueltas también. Una vez, puede ser identificada por las coordenadas de modo que podemos elegir $k/2$ fila y columna de los índices, pero todavía hay algunos problemas.

Puede alguien por favor me ayude a resolver esta cuestión.

Answer 1

Sugerencia: Si hay $k$ vuelve, ¿cuántos segmentos horizontales hay? Cuántos segmentos verticales hay? (WLOG, la dirección de el primer movimiento es horizontal.)

Sugerencia: ¿cuántas maneras hay para escribir $n$ como la suma de $l$ enteros positivos, donde $l\leq n$?

Answer 2

Suponga que empieza en la dirección $d \in \{\text{right}, \text{down}\}$, e $d'$ es la otra dirección.

A continuación, $k$ convierte significa que no se $1 + \lfloor k/2 \rfloor$ segmentos contiguos en la dirección $d$, e $\lceil k/2 \rceil$ segmentos en la dirección $d'$. Toda la secuencia de movimientos se especifica si especificamos cómo muchos movimientos que hay en cada uno de estos segmentos. Es decir, que $x_1, x_2, \dots, x_{1+\lfloor k/2 \rfloor}$ el número de movimientos en los segmentos en la dirección $d$, y cada una de las $y_1, y_2, \dots, y_{\lceil k/2 \rceil}$ el número de movimientos en los segmentos en la dirección $d'$. A continuación, toda la ruta está totalmente determinado por la $x_i$s y $y_j$s.

Como el número de total de número de movimientos en cada dirección es $n-1$, estamos buscando (por cada elección de $d$) para el número de enteros positivos soluciones a $$\begin{align} x_1 + x_2 + \dots + x_{1 + \lfloor k/2 \rfloor} &= n-1 \\ y_1 + y_2 + \dots + y_{\lceil k/2 \rceil} &= n-1 \end{align} $$

Esto le da la respuesta final como $$2\binom{n-2}{\lfloor k/2 \rfloor}\binom{n-2}{\lceil k/2 \rceil - 1}.$$