(This is from a long finished programming competition)
Consider a triangle grid with side N. How many hexagons can fit into it?
This diagram shows N = 4:
I need a recurrence for it:
I tried the following:
$T_1 = 0$
$T_2 = 0$
$T_3 = 1$
$T_4 = 7$
$T_n = ???$
Using inclusion/exclusion:
$T_n = 3T_{n-1} - 3T_{n-2} + T_{n-3} + 3(n-2) - 2 $
Each part is as follows:
(We consider the count of hexagons that fit in certain sub-triangles of the current triangle)
- $3T_{n-1}$ The three n-1 triangles in each corner
- $-3T_{n-2}$ The three n-2 triangles touching one side each. These are each double counted in (1), so we subtract one of each.
- $T_{n-3}$ The n-3 triangle in the center, this is counted 3-3=0 times from (1) and (2) so we need to add one of them.
- $3(n-2)$ The number of hexagons which take up an entire side (and don't fit in any of the above) is n-2. We count this three times for each side.
- $-2$ The maximum hexagon is counted three times in (4), so we subtract 2 copies.
However it seems I have made a mistake because for $T_7$ I get 140, whereas the expected answer is 232.
Can anyone see where I have gone wrong?
