3
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – TMM Mar 26 '17 at 18:38
  • $\begingroup$ 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? $\endgroup$ – TMM Mar 26 '17 at 19:40
  • $\begingroup$ I've edited the question. Now maybe it is clearer a bit. $\endgroup$ – user128409235 Mar 26 '17 at 21:27
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.