# Number of ways to get from $(0, 0)$ to $(x, y)$ with moves $(x+ 1, y + 1)$, $(x - 1, y + 1)$ and additional constraint.

How many ways are there to get from $(0, 0)$ to $(x, y)$ in coordinates system assuming that from $(i, j)$ you can move to $(i + 1, j + 1)$, $(i - 1, j + 1)$ and if you make some moves of the second type in a row then you have to do at least the same amount of moves of the first type in a row. For example, there are $5$ ways to get from $(0, 0)$ to $(-1, 5)$ and $0$ ways to get to $(-2, 5)$. You can assume that $(x, y)$ lies in a second quadrant.

What I've found out is that the problem is equivalent to calculating how many binary sequences of length $y$ are there such that there are $x$ more ones, than zeros and after each contiguous sequence of zeros there must be contiguous sequence of ones of length at least the same. For example, a correct sequence is $1111001110101000111000011111$.

• What's the point of the j variable when you always increase it by one? You're just doing 5 steps of either +/-1 and you want to count the number of ways to get end result -1, with one additional constraint on the allowed steps. – TMM Mar 26 '17 at 18:38
• What is x in your question? Is it a fixed number? If not, how can you express the number of zeros in the binary sequence in terms of x? – TMM Mar 26 '17 at 19:40
• I've edited the question. Now maybe it is clearer a bit. – user128409235 Mar 26 '17 at 21:27

Suppose we know how to answer the arguably easier question

(Problem 2) How many ways are there to get from the origin (0,0) to (x,y) (where $(x,y) \in \mathbb{Z}^2$) only using the moves +(1,0), +(0,1)?

Now define the change of variables $\mathbb{Z}^2 \to \mathbb{Z}^2$ given by the matrix $T = \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}$. $T$ has the property that it maps the moves $+(1,0)$ to $+(1,1)$ and $+(0,1)$ to $+(-1,1)$. You can verify:

The number of ways to get from (0,0) to (x,y) using moves +(1,0) and +(0,1) is the same as the number of ways to get from T(0,0) = (0,0) to T(x,y) = (x-y, x+y) using the moves +(1,1), +(-1,1).

Few things to note:

1. T is not surjective, so you cannot reach every point (x,y) using +(1,1), +(-1,1), for instance (x,y) = (0,1).

2. T has a "left-inverse" $T^{-1} = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}$, i.e. $T^{-1}T(x,y) = (x,y)$, which should help you translate between the two problems. Also you can use this to derive a condition under which (x,y) is reacheable.

3. Problem 2 can be interpreted as counting the number of ways to arrange $x$ zeroes and $y$ ones in a binary number of length $x+y$. Also: $x+y$ is the value of the $y$-coordinate after applying $T$ to $(x,y)$, which matches with your observation.