How many ways for a beetle to move from bottom left corner to upper right corner in a 6 x 6 grid if it must be done in 14 steps only?

Question

Note: We allow all four directions (up, down, right, left but no diagonal)

The 6 x 6 grid is composed of 7 horizontal lines and 7 vertical lines. We are to calculate how many 14 steps paths are possible where it never returns to the same intersecting point.

The answer given is

$$C(12, 8) \times C(8,7) \times (6/8) \times 2 = 5940$$

where $C(n,r)$ is here is the Binomial Coefficient.

I cannot seem to figure out how this counting was done. Can somebody provide me with the explanation regarding how this counting argument was done please? Any help is appreciated, thank you.

Answer 1

I don't know how that formula was obtained but here is another argument which gives the same result numerically. We generalise to finding paths of length $m+n+2$ on an $m\times n$ grid from $(0,0)$ to $(m,n)$.

It is not hard to see that the path must consist of one of the following mutually exclusive possibilities:

• $m-2$ single moves right, $n+1$ single moves up, $1$ sequence of three moves right-down-right;
• $m+1$ single moves right, $n-2$ single moves up, $1$ sequence of three moves up-left-up.

To count the first type we begin by arranging $m-2$ letters R and $n+2$ letters U: this can be done in $C(m+n,m-2)$ ways. Then we replace one of the letters U by RDR: this can be done for any of the $n+2$ letters U except the first or last, so there are $n$ options. A similar argument for the second case gives the total number of paths as $$n\binom{m+n}{m-2}+m\binom{m+n}{n-2}\ .$$ If $m=n$ this is $$2m\binom{2m}{m-2}\ ,$$ and in particular for the $6\times6$ grid it is $$12\binom{12}{4}=5940\ .$$

Answer 2

Here's one way to explain the given calculation, though I do feel it's a rather awkward way to tackle the problem.

Since moving from the bottom left to the top right in a 6x6 grid would require a minimum of 12 steps, a 14-step sequence of movements must consist of 6 right (R) steps, 6 up(U) steps, plus either one left (L) and one additional right, or one down (D) and one additional up. Since we're not allowed to return to a previous point, we cannot have L & R or U & D appear consecutively, which means that the L would have to be 'sandwiched' between two U's or the D would be between two R's.

Let's assume that we're looking at the former case, with an L and an additional R. Then we can say the path must consist of 12 'blocks': the seven R's, four of the six U's, plus the ULU combination. We want to count the arrangements of these 12 blocks, subject to one additional condition mentioned below.

We start by choosing the eight positions for the R & ULU blocks; this can be done in

$$\binom{12}{8}$$

ways. Then we choose the positions of the seven R's, leaving the ULU in whichever of the eight spots remains; that gives us

$$\binom{12}{8} \times \binom{8}{7}$$

However, note that we cannot have the ULU before or after all the R steps, as we have to move right at least once before we can move left, and at least once after we move left (otherwise the left step would be coming from outside the grid.) So we have to eliminate the $\frac{2}{8}$ of the sequences where ULU comes first or last, leaving us

$$\binom{12}{8} \times \binom{8}{7} \times \frac{6}{8}$$

The four remaining U's would go in the last four empty spots, so they add nothing to the count. Finally we have to account for the possibility of having RDR instead of ULU, so we double our count to arrive at

$$\binom{12}{8} \times \binom{8}{7} \times \frac{6}{8} \times 2$$

Answer 3

Apparently my answer is wrong, but I was thinking of this:
There are four directions: Up, Down, Left and Right.

In order to go from bottom left to upper right, you need 6 U and 6 R, which is a total of 12 movements.

In order to get to 14 movements, you need to take an extra step and one back, so we end up with:

7 U, 1 D and 6 R, or:
6 U, 7 R and 1 L.

The amount of ways to do this is:

$$\frac{(7 + 1 + 6)!}{7! \cdot 1! \cdot 6!} + \frac{(6 + 7 + 1)!}{6! \cdot 7! \cdot 1!}$$

The result of this seems to be 48.048, which is clearly different than the proposed 5940, so something is wrong here. It's not my reasoning (I have correctly found all the ways to travel), so it should be my calculation. Feel free to add comments, I'll edit my answer accordingly.

Remark: my answer is divisible by 13, which is obvious because we are talking about taking 14 steps ($13 + 1$), so I'm wondering what happened to the 13 in the correct result 5940.