Número de maneras de obtener de $(0, 0)$ $(x, y)$con los movimientos $(x+ 1, y + 1)$, $(x - 1, y + 1)$ y restricción adicional.

Question

De cuántas maneras existen para obtener de $(0, 0)$ $(x, y)$en el sistema de coordenadas suponiendo que de $(i, j)$ puede mover a $(i + 1, j + 1)$, $(i - 1, j + 1)$ y si usted hace algunas jugadas del segundo tipo en una fila, entonces usted tiene que hacer al menos la misma cantidad de movimientos del primer tipo en una fila. Por ejemplo, hay $5$ formas de llegar desde $(0, 0)$ $(-1, 5)$ $0$formas de llegar a la $(-2, 5)$. Se puede suponer que la $(x, y)$ se encuentra en un segundo cuadrante.

Lo que he descubierto es que el problema es equivalente a calcular la cantidad de secuencias binarias de longitud $y$ están allí, que no se $x$ más, de ceros y después de cada secuencia contigua de ceros debe ser la secuencia contigua de de longitud de, al menos, el mismo. Por ejemplo, una secuencia correcta es $1111001110101000111000011111$.

Answer 1

Supongamos que sabemos cómo podría decirse que responder a la pregunta más fácil

(Problema 2) ¿cuántas maneras existen para llegar desde el origen (0,0) (x,y) (donde $(x,y) \in \mathbb{Z}^2$) sólo el uso de los movimientos +(1,0), +(0,1)?

Ahora definir el cambio de las variables de $\mathbb{Z}^2 \to \mathbb{Z}^2$ dado por la matriz $T = \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix} $. $T$ tiene la propiedad de que los mapas de los movimientos $+(1,0)$$+(1,1)$$+(0,1)$%#%. Se puede comprobar:

El número de maneras de obtener a partir de (0,0) a (x,y) utilizando mueve +(1,0) y +(0,1) es el mismo que el número de maneras de obtener a partir de T(0,0) = (0,0) T(x,y) = (x-y, x+y) el uso de los movimientos +(1,1), +(-1,1).

Algunas cosas a tener en cuenta:

1. T no es surjective, por lo que no se puede llegar a cada punto (x,y) utilizando +(1,1), +(-1,1), por ejemplo (x,y) = (0,1).

2. T tiene una "izquierda inversa" $+(-1,1)$, es decir,$T^{-1} = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}$, lo que debería ayudar a traducir entre los dos problemas. También se puede utilizar para obtener una condición bajo la cual (x,y) es reacheable.

3. Problema 2 se puede interpretar como contar el número de maneras de organizar $T^{-1}T(x,y) = (x,y)$ ceros y $x$ en un número binario de longitud $y$. También: $x+y$ es el valor de la $x+y$-coordinar después de aplicar el $y$$T$, lo que coincide con tu observación.