# Number of ways to get from $(0, 0)$ to $(2, 2)$ in coordinates system

I'm in point $\left(0, 0\right)$ of coordinates system:

• I want to konw how many ways are there to the point $(2, 2)$ in at most 6 steps.
• One step is moving up, down, left or right by one cell, so from $\left(0, 0\right)$ in one step I can get to $\left(0, 1\right), \left(1, 0\right), \left(-1, 0\right), \left(0, -1\right)$.
• Of course, the minimum number of steps is $4$ and there are $6$ ways of length $4$. You can't get there in $5$ steps.
• What about ways of length exactly $6$ ?. How can I count them ?.
• Similar question – Wei Zhong Sep 9 '16 at 16:08
• Have you computed how many ways from the origin to $(1,1)$ in 4 steps? – András Salamon Sep 9 '16 at 16:24

We can do the job algebraically. We encode steps in direction $E$ and $W$ by $x^1$ and $x^{-1}$ and similarly we encode steps in direction $N$ and $S$ by $y^1$ and $y^{-1}$.

We obtain the expression \begin{align*} x^1+x^{-1}+y^{1}+y^{-1}\tag{1} \end{align*} with the $+$ sign indicating the alternatives we have for each step.

Let's denote with $[x^j]$ the coefficient of $x^j$ in an expression. This way we can write e.g. \begin{align*} [x^2](1+x)^6=\binom{6}{2} \end{align*}

Since one step is encoded by (1) and we are looking for the number of possibilities to go from $(0,0)$ to $(2,2)$ in $6$ steps, we have to look for the coefficient of \begin{align*} [x^2y^2](x^1+x^{-1}+y^{1}+y^{-1})^6 \end{align*}

For example one of the paths of length $6$ from $(0,0)$ to $(2,2)$ is \begin{align*} E.N.S.N.N.E \qquad \longleftrightarrow\qquad x^1y^1y^{-1}y^{1}y^{1}x^{1}=x^2y^2 \end{align*}

We obtain \begin{align*} [x^2y^2]&(x^1+x^{-1}+y^{1}+y^{-1})^6\\ &=[x^2y^2]\sum_{j=0}^6\binom{6}{j}\left(x+\frac{1}{x}\right)^j\left(y+\frac{1}{y}\right)^{6-j}\tag{2}\\ &=[x^2y^2]\binom{6}{2}\left(x+\frac{1}{x}\right)^2\left(y+\frac{1}{y}\right)^4\\ &\qquad+[x^2y^2]\binom{6}{4}\left(x+\frac{1}{x}\right)^4\left(y+\frac{1}{y}\right)^2\tag{3}\\ &=[x^2y^2]\left(\binom{6}{2}\binom{2}{0}x^2\binom{4}{1}y^2+\binom{6}{4}\binom{4}{1}x^2\binom{2}{0}y^2\right)\tag{4}\\ &=\binom{6}{2}\cdot 4+\binom{6}{4}\cdot 4\\ &=120 \end{align*} and conclude there are $120$ different paths to go from $(0,0)$ to $(2,2)$ in $6$ steps using steps $(1,0),(-1,0),(0,1)$ and $(0,-1)$.

Comment:

• In (2) we group the polynomial $(x^1+x^{-1}+y^{1}+y^{-1})^6=\left(\left(x+\frac{1}{x}\right)+\left(y+\frac{1}{y}\right)\right)^6$ and apply the binomial theorem.

• In (3) we observe only $j=2$ and $j=4$ provide a contribution to $[x^2y^2]$.

• In (4) we select the coefficients of $[x^2y^2]$.

HINT: I will denote the four steps shown in the question by $E$ (east), $N$ (north), $W$ (west), and $S$ (south) in that order. Let $n_E$ be the number of $E$ steps on the path, $n_N$ the number of $N$ steps, and so on. Then you want the number of solutions in non-negative integers to the system

\left\{\begin{align*}&n_E+n_N+n_W+n_S=6\\ &n_E-n_W=2\\ &n_N-n_S=2\;. \end{align*}\right.\tag{1}

From the last two you have $n_E=n_W+2$ and $n_N=n_S+2$; substituting into the first and simplifying, we get $n_W+n_S=1$. This has just two solutions in non-negative integers; how many paths correspond to each of them.

(This is actually more machinery that this specific problem requires, since with a little thought it should be clear that in order to get from $\langle 0,0\rangle$ to $\langle 2,2\rangle$ in exactly $6$ steps you’ll need two $E$ steps, two $N$ steps, and two steps that cancel each other out, and you simply have to count the possible orders of these steps. However, it gives you a general approach that can be applied to all such problems.)

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ As $\texttt{@Markus Scheurer}$ said: "We can do the job algebraically". We'll consider the problem in the Complex Plane such that the possible 'steps' are $\ds{1,\ic,-1,-\ic}$ and the 'end point' is $\ds{2 + 2\ic}$. Lets $$\bbox[5px,border:1px groove navy]{\quad a \equiv 2 + 2\ic\quad \mbox{and}\quad \Omega \equiv \braces{\vphantom{\Large A}1,\ic,-1,-\ic}\quad}$$

The Number of Paths from $\ds{\pars{0 + 0\ic}}$ to $\ds{a = 2 + 2\ic}$ is given by: \begin{align} &\sum_{z_{1}\ \in\ \Omega}\ \sum_{z_{2}\ \in\ \Omega} \cdots \sum_{z_{n}\ \in\ \Omega}\bracks{z_{1} + z_{2} + \cdots + z_{n} = a}\qquad \pars{~\bracks{\cdots}:\ Iverson\ Bracket~} \\[5mm] = &\ \sum_{z_{1}\ \in\ \Omega}\ \sum_{z_{2}\ \in\ \Omega} \cdots \sum_{z_{n}\ \in\ \Omega}\,\,\,\oint_{\verts{z} = 1}\,\,\, {1\over z^{1 - \pars{z_{1}\ +\ z_{2}\ +\ \cdots\ +\ z_{n}\ -\ a}}}\,\,\,\,\,\,\, {\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z} = 1}\,\,{1 \over z^{a + 1}} \pars{\sum_{w\ \in\ \Omega}z^{w}}^{n}{\dd z \over 2\pi\ic} = \oint_{\verts{z} = 1}\,\, {\pars{z + z^{\ic} + z^{-1} + z^{-\ic} }^{n} \over z^{a + 1}} \,{\dd z \over 2\pi\ic} = \\[5mm] = &\ \oint_{\verts{z} = 1}\,\, {1 \over z^{a + 1}}\sum_{p = 0}^{\infty}\ \sum_{q = 0}^{\infty}\ \sum_{r = 0}^{\infty}{n \choose p,q,r,n - p - q - r} z^{p}z^{q\ic}z^{-r}z^{-\ic\pars{n - p - q - r}}\,\,\,\, \,{\dd z \over 2\pi\ic} \\[5mm] = & \sum_{p = 0}^{\infty}\ \sum_{q = 0}^{\infty}\ \sum_{r = 0}^{\infty}{n \choose p,q,r,n - p - q - r}\oint_{\verts{z} = 1} {1 \over z^{3 - p + r}}\,{1 \over z^{\pars{2 - p - 2q - r + n}\ic}} \,\,\,\,\,\,{\dd z \over 2\pi\ic} \\[1cm] = &\ \sum_{p = 0}^{\infty}\ \sum_{q = 0}^{\infty}\ \sum_{r = 0}^{\infty}{n \choose p,q,r,n - p - q - r} \times \\ &\ \bracks{3 - p + r = 1}\bracks{2 - p - 2q - r + n = 0}\,{\dd z \over 2\pi\ic} \label{1}\tag{1} \end{align}
The solution, for $\ds{p\ \mbox{and}\ r}$, of equations $\ds{3 - p + r = 1\quad\mbox{and}\quad 2 - p - 2q - r + n = 0}$ are given by $\ds{p = 2 + n/2 - q\quad\mbox{and}\quad r = n/2 - q}$. Then, $\bbox[#ffb,3px]{\ds{\eqref{1}\ \mbox{vanishes out when}\ n\ \mbox{is an}\ \ul{odd}\ \mbox{number}}}$. We'll consider the case of $\ds{\ul{even}\ n}$. Namely, $\ds{n = 2m}$. \begin{align} &\left.\sum_{z_{1}\ \in\ \Omega}\ \sum_{z_{2}\ \in\ \Omega} \cdots \sum_{z_{n}\ \in\ \Omega}\bracks{z_{1} + z_{2} + \cdots + z_{n} = a} \,\right\vert_{\ n\ =\ 2m} \\[5mm] = &\ \sum_{q = 2}^{m}{2m \choose m + 2 - q,q,m - q,q - 2}\label{2}\tag{2} \end{align}

For $\ds{n = 6\ \implies\ m = 3}$ we'll get: \begin{align} &\sum_{q = 2}^{3}{6 \choose 5 - q,q,3 - q,q - 2} = {6 \choose 3,2,1,0} + {6 \choose 2,3,0,1} = {6! \over 3!\,2!\,1!\,0!} + {6! \over 2!\,3!\,0!\,1!} \\[5mm] = &\ \bbox[5px,border:2px groove navy]{\color{#f00}{120}} \end{align}

Note that expression \eqref{2} has a 'closed form' ( extra-bonus ): $$\sum_{q = 2}^{m}{2m \choose m + 2 - q,q,m - q,q - 2} = {4\Gamma^{\, 2}\pars{2m} \over \Gamma\pars{m - 1}\Gamma^{\, 2}\pars{m}\Gamma\pars{m + 3}}\,,\qquad n = 2m.$$