4
$\begingroup$

Determine the number of paths to move from the top-left cell to the bottom-right cell in the $8 \times 6$ (so the height is $6$ units and the length $8$ units) cell grid using a sequence of downwards moves and rightwards moves such that there are an even number of direction changes.

I'm a little lost on this. I know that there are $(8+6)!/(8!\cdot 6!)$ ways to get from the top left corner to the bottom left corner, but otherwise I'm not sure what to do. Of course, I did try to "get my hands dirty" and worked out possible paths that have an even and an odd number of direction changes, but I'm not sure if they have helped me much so far.

$\endgroup$
7
$\begingroup$

Observe that if you first move right, you must end with a move to the right, and if you first move down, you must end with a move down. In the former case, you are left with a grid of $6 \times 6,$ which has $12 \choose 6$ valid moves. In the latter case, you are left with a grid of $8 \times 4,$ which has $12 \choose 8$ valid moves. The number of ways to achieve an even number of direction changes thus equals:

$${12 \choose 6} + {12 \choose 8} = 924 + 495 = 1419$$

$\endgroup$
5
$\begingroup$

Let's generate all lattice paths with $h$ horizontal moves, $v$ vertical moves and $c$ changes in direction. The number of such lattice paths will be the $x^hy^vz^c$ coefficient of some generating function series $f(x,y,z)$.

This function can be further partitioned into a function of all such paths ending with a horizontal move $f_x(x,y,z)$, a function of all such paths ending with a vertical move $f_y(x,y,z)$ and the empty path $1$.

$$f=1+f_x+f_y\, .\tag{1}$$

Now, paths ending in a horizontal move $f_x$ are either

  • a single move $x$,
  • a path ending in a horizontal move $f_x$ followed by another horizontal move $x$,
  • a path ending in a verical move $f_y$ followed by a horizontal move $x$ and therfore also a change in direction $z$.

$$\begin{align} && f_x&=x+f_xx +f_yxz\\[1ex] &\implies & f_x&=\frac{x+f_yxz}{1-x}\, .\tag{2}\end{align}$$

Similarly we can argue for $f_y$:

$$\begin{align} &&f_y&=y+f_yy+f_xyz\\[1ex] &\implies & f_y&=\frac{y+f_xyz}{1-y}\, .\tag{3}\end{align}$$

We can substitute $(3)$ in $(2)$ eliminating $f_y$ to give:

$$\begin{align} &&f_x&=\frac{x}{1-x}+\frac{xyz}{(1-x)(1-y)}+\frac{f_xxyz^2}{(1-x)(1-y)}\\[1ex] &\implies &f_x&=\frac{x(1-y)+xyz}{(1-x)(1-y)-xyz^2}\, .\tag{4}\end{align}$$

Similarly by eliminating $f_x$ we get

$$f_y=\frac{y(1-x)+xyz}{(1-x)(1-y)-xyz^2}\, ,\tag{5}$$

then inputting $(4)$ and $(5)$ into $(1)$ and simplifying gives:

$$f(x,y,z)=\frac{1-xy(1-z)^2}{1-x-y+xy-xyz^2}\, .\tag{6}$$

This is our generating function for lattice paths with direction changes.

We could, at this point, use a computer algebra system such a sage to find the coefficients of all $x^8y^6z^{\text{even}}$ in $(6)$ then add them to get our answer. However, there is a useful trick we can use called the Discrete Fourier Transform (DFT) which will make our answer easy to calculate.

We note that the desired solution would be the $x^8y^6$ coefficient of

$$\begin{align}\tfrac{1}{2}(f(x,y,1)+f(x,y,-1))&=\frac{1-2xy}{1-(x+y)}\\[1ex] &=\sum_{k\ge 0}(x+y)^k-2xy\sum_{k\ge 0}(x+y)^k\end{align}\tag{7}$$

since we are using the square-roots of unity $\{1,-1\}$ odd powers of $z$ cancel and we sum the even coefficients.

So, taking the required $x^8y^6$ coefficient with the operator $[x^8y^6]$ on $(7)$:

$$\begin{align}[x^8y^6]\tfrac{1}{2}(f(x,y,1)+f(x,y,-1))&=[x^8y^6]\sum_{k\ge 0}(x+y)^k-2[x^7y^5]\sum_{k\ge 0}(x+y)^k\\[1ex] &=\binom{8+6}{6}-2\binom{7+5}{5}\\[1ex] &=\binom{14}{6}-2\binom{12}{5}\\[1ex]& =1419\tag{Answer}\end{align}$$

$\endgroup$
  • 1
    $\begingroup$ A very complete answer (+1). I would like to point out, however, that the result in the second to last line can intuitively be reasoned as well: from all possible paths, subtract those in which you start with a downward movement and end with a move towards the right, and those in which you start with a move towards the right and end with a downward movement. $\endgroup$ – jvdhooft Jun 21 '18 at 19:39
  • $\begingroup$ A worthwhile contribution, thank you! Buried in my method as I was, I didn't take a step back to make that observation, but it's as clear as day now you mention it. Thanks for the upvote too! I had already done so for your beautifully succinct answer. :) $\endgroup$ – N. Shales Jun 21 '18 at 19:48

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.