# How many hexagonal paths?

Here is a hexagonal tiling, borrowed from Wikipedia.

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?

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

74280

Method

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:

The sum of the numbers in the last column is the answer to the question posted.

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

73392?

Reasoning:

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.

• The method seems to be correct, but I'm afraid your calculation is flawed indeed. – elias Oct 30 '18 at 12:22
• @elias yeah, I thought that would be the case. – Excited Raichu Oct 30 '18 at 12:22
• Also I'm sure you meant northwest and southwest instead of northeast. – elias Oct 30 '18 at 12:24
• @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. – Excited Raichu Oct 30 '18 at 12:27

$$83,746$$

Method:

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$$

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