Walking on an infinite grid

combinatoricsdiscrete mathematics

I am sure someone has asked a similar question already, but I wasn't able to find it.

So lets get started: We have an infinite grid with coordinates out of $ \mathbb{Z} $. Lets say the first coordinate is the X and the second is the Y. We start at some position on the grid (lets say $ (2, 2) $) and now want to go to an other position (lets say $ (42, 2) $). To do that we could go the following steps (for example):
$$A=(+1, 0)$$
$$B=(+1, +1)$$
$$C=(+1, -1)$$
Now I want to know the number of possible ways using the steps from above.

I already had some ideas – I'll list them here too for inspiration:

  1. The step A has a weight of one and the step B and C has a combined weight of 2. So my mission is to find the number of their combinations to reach 40 (see example from above).
    BUT this doesn't work because combinations like 'BAC' are also valid.

  2. I count the possible ways to perform the steps B and C: If n equals the number of steps into the right direction, so i can go B on $n-1$ steps (the last one is impossible, because for now I start with up only) and it corresponding down step can be on $n-2$ steps and so on…
    This doesn't work, because I could go on $n-1$ steps up and on the n-th all down. Additionally things like 'BCCAB' are with this model also not possible.

  3. Well, I can see a pattern there (n equals steps to the right):

    • 40xA; 0xB+C -> 1 possible way
    • 38xA; 1xB+C -> $ n * (n-1) $ possible ways
    • 36xA; 2xB+C -> $ n * (n-1) * (n-2) * (n-3) $ possible ways
    • 34xA; 3xB+C -> $ n * (n-1) * (n-2) * (n-3) * (n-4) * (n-5) $ possible ways

…so maybe something like this: $ \prod\limits_{i=0}\limits^{n/2-1} ( (n-i*2) * (n-i*2-1) ) $

So, anyone has an idea or hint for me?

EDIT: Added third idea.

Best Answer

We encode the steps with $x$ when going a step horizontally in $x$-direction and with $y$ when going vertically in $y$-direction. This way $A,B,C$ become \begin{align*} &A=(1,0)\quad\to x^1y^0\\ &B=(1,1)\quad \to x^1y^1\\ &C=(1,-1)\ \to x^1y^{-1}\\ \end{align*} To go one step either $A$ or $B$ or $C$ is encoded as \begin{align*} x+xy+\frac{x}{y} \end{align*}

Note the number of paths from $(2,2)$ to $(42,2)$ is due to symmetry equal to the number of paths from $(0,0)$ to $(40,0)$. We need $40$ steps to go from $(0,0)$ to $(40,0)$ and so we consider \begin{align*} [x^{40}y^{0}]\left(x+xy+\frac{x}{y}\right)^{40}\tag{1} \end{align*} where we conveniently use the coefficient of operator $[x^ny^m]$ to denote the coefficient of $x^ny^m$ in a series $A(x,y)$.

We obtain \begin{align*} \color{blue}{[x^{40}y^{0}]}&\color{blue}{\left(x+xy+\frac{x}{y}\right)^{40}}\\ &=[x^{40}y^0]x^{40}\left(1+y+\frac{1}{y}\right)^{40}\\ &=[y^0]\sum_{k=0}^{40}\binom{40}{k}\left(y+\frac{1}{y}\right)^k\tag{2}\\ &=[y^0]\sum_{k=0}^{40}\binom{40}{k}\sum_{j=0}^k\binom{k}{j}y^jy^{-(k-j)}\\ &=\sum_{k=0}^{40}\binom{40}{k}[y^k]\sum_{j=0}^k\binom{k}{j}y^{2j}\tag{3}\\ &=\sum_{k=0}^{20}\binom{40}{2k}[y^{2k}]\sum_{j=0}^{2k}\binom{2k}{j}y^{2j}\tag{4}\\ &\,\,\color{blue}{=\sum_{k=0}^{20}\binom{40}{2k}\binom{2k}{k}}\tag{5} \end{align*} in accordance with the result of @JeanMarie.

Comment:

  • In (2) we apply the rule $[x^p]x^q=[x^{p-q}]$ and apply the binomial theorem to $\left(1+\left(y+\frac{1}{y}\right)\right)^{40}$.

  • In (3) we apply the rule $[y^p]y^q=[y^{p-q}]$ again.

  • In (4) we observe that only even powers $2j$ do contribute. So we need only to consider even indices $2k$.

  • In (5) we finally select the coefficient of $y^{2k}$.

Note: The coefficients of $x^0$ in the expansion of $\left(x+1+x^{-1}\right)^n$ are called central trinomial coefficients. They do not admit a closed formula which is shown in this post.

Related Question