Here is a hexagonal tiling, borrowed from Wikipedia.

hexagonal tiling

I start in any hexagon on the left hand side. I end at any hexagon on the right hand side. I can only travel to the right, not up, down or backwards.

In how many ways can this be done?

  • $\begingroup$ bonus question: if the grid is extended to $2k$ columns in total, what is the sum of the $2k^{th}$ column? $\endgroup$ – JonMark Perry Oct 30 '18 at 12:44

The answer is



Every cell in the first column can be reached 1 way.
Other cells can be reached as many different ways, as the sum of their two left neighbours, giving:
enter image description here
The sum of the numbers in the last column is the answer to the question posted.

  • $\begingroup$ I think I might give this the tick for the presentation aspect and the right answer. The bottom row is A001700. $\endgroup$ – JonMark Perry Oct 30 '18 at 12:49
  • 5
    $\begingroup$ @JonMarkPerry, actually it isn't. The sequences start to differ from the 2*12=24th column, when the diagonal hits the top/bottom. $\endgroup$ – elias Oct 30 '18 at 13:06

The correct answer might be:



Well, I made a Pascal's Triangle-like chart with alternating 11 and 12 columns, and 14 rows, where each number was the sum of the two numbers northwest and northeast of it. I added all of the numbers on the bottom row. It's quite likely I messed up some addition, though.

  • $\begingroup$ The method seems to be correct, but I'm afraid your calculation is flawed indeed. $\endgroup$ – elias Oct 30 '18 at 12:22
  • $\begingroup$ @elias yeah, I thought that would be the case. $\endgroup$ – Excited Raichu Oct 30 '18 at 12:22
  • $\begingroup$ Also I'm sure you meant northwest and southwest instead of northeast. $\endgroup$ – elias Oct 30 '18 at 12:24
  • 1
    $\begingroup$ @elias I did the chart vertically instead of horizontally like the question asked (same result, and easier for me to draw), so for me it was northeast. I see how this could cause a bit of confusion though. $\endgroup$ – Excited Raichu Oct 30 '18 at 12:27




Consider the first 2 columns of this diagram. There are 11 starting positions, and 12 destinations. Each starting position can go to one of 2 destinations, so the number of possible paths is equal to $11 \cdot 2 = 22$.

Now, consider columns 2 and 3 of the diagram. There are 12 starting positions, and 11 destinations. 10 of the starting positions have 2 possible destinations, and 2 of them only have 1 possible destination (the top and bottom ones). This means the total number of possible paths is $(10 \cdot 2) + 2 = 22$.

If we now consider the first 3 columns, it can be seen that each of the internal starting positions has 4 possible paths, and the top and bottom ones have 3. Therefore, in total, there are $(9 \cdot 4) + (2 \cdot 3) = 36 + 6 = 42$ possible paths across the first 3 columns.

In the initial consideration, the inner hexes were each finished on twice, and the outer ones once. Therefore, a second way to work out the number of paths in the third consideration, would be to edit the calculation for consideration 2 to be $((10 \cdot 2) \cdot 2) + (2 \cdot 1) = 40 + 2 = 42$.

Next, considering the first 4 columns, each of the paths already determined for the first 3, has 2 more possible destinations, so the number of paths would total $42 \cdot 2 = 84$.
Using these values, I can determine a formula for calculating the number of paths, where n increases by 1 for every repeating pair of columns.
$\Sigma_n = ((\Sigma_{n-1} - n) \cdot 4) + 2n$

Therefore, we can step through this calculation to determine the results of:
$\Sigma_1 = 22$
$\Sigma_2 = 84$
$\Sigma_3 = 330$
$\Sigma_4 = 1312$
$\Sigma_5 = 5238$
$\Sigma_6 = 20,940$
$\Sigma_7 = 83,746$
As there are 7 pairs of columns in the above image, (if my formula is correct), I believe there to be $83,746$ possible paths.

Bonus Question:

$\Sigma_n = ((\Sigma_{n-1} - n) \cdot 4) + 2n$ where $n=2k$

  • 3
    $\begingroup$ I'm pretty sure @NudgeNudge 's earlier answer of 90112 is an upper bound for the answer. $\endgroup$ – Excited Raichu Oct 30 '18 at 12:19
  • $\begingroup$ @ExcitedRaichu you're right, I think I had an unnecessary factor of n $\endgroup$ – AHKieran Oct 30 '18 at 12:47

Your Answer

