Walking on an infinite grid

Question

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.

Answer 1

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.

Answer 2

First of all, your problem is equivalent to find the number of paths from $(0,0)$ to $(40,0)$. This is what we are going to assume.

Considering $A,B,C$ as vectors, we are in a first step looking for the number of triples $(m,n,p)$ of integers such that $$m\binom{1}{0}+n\binom{1}{1}+p\binom{ \ \ 1}{-1}=\binom{40}{0} \ \iff \ \ \begin{cases}m+n+p&=&40\\n-p&=&0\end{cases}\tag{1}$$

$$\iff \ \ \begin{cases}m+2n&=&40& \ \ \ (a)\\n&=&p& \ \ \ (b)\end{cases}.\tag{2}$$ which amounts to say :

$$\text{Determine (first) the ordered pairs of integers} \ (m,n) \ \text{such that} \ m+2n=40$$

(2) implies that $m=2(20-n)$ is an even number : $m=2k$ for $k=0,1,\cdots 20.$

Therefore, taking (2)(b) into account :

$$(m,n,p)=(2k,20-k,20-k)=(0,20,20),(2,19,19),(4,18,18), etc...$$

As a consequence, each $k$ it remains to constitute a word of $40$ letters $A,B,C$, i.e.

place into $40$ slots : $m=2k$ letters "$A$"s, $(20-k)$ letters "$B$"s, and $(20-k)$ letters "$C$"s as well.

Once the $2k$ "slots" for letters "$A$" have been attributed, we have to place the same amount of letters $B$ and $C$ i.e., $20-k$ letters $B$ and as many letters "$C$". We consider only placement of letters "$B$" (Placing letters "$C$" hasn't to be considered : they occupy the remaining "slots"). This boils down to the following count :

$$\sum_{k=0}^{20} \binom{40}{2k}\binom{40-2k}{20-k}=\sum_{k=0}^{20} \frac{40 !}{(2k)! (20-k) ! (20-k) !}$$

I don't know if one can give a close expression to this sum...