Ytukyg

(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)

1. 
   $3T_{n-1}$ The three n-1 triangles in each corner


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


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


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


5. 
   $-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?

Starting from your idea: By inclusion-exclusion, for $n>3$
$$tag{1}T_n = X_n +3T_{n-1}-3T_{n-2}+T_{n-3},$$
where $X_n$ is the number of "full-size" hexagons, i.e. those that touch all three sides. A full-size hexagon is determined by three positive integers $a,b,c$ (the sizes of the small triangles chopped off) with $a+b<n, b+c<n, a+c<n$.

How many such triples ($a,b,c)$ with $max{a+b,a+c,b+c}<n$ are there for each $n$?
We shall assume $nge3$.
There are $n-1choose 2$ possibilities to choose $x,yge 1$ such that $x+y<n$ (think of inserting two separators into the $n-1$ gaps between $n$ pebbles, thus gouping them into $xge1$, $yge1$ and $n-x-yge1$ pebbles). Therefore, there are $n-1choose2$ triples each of the forms $(1,b,c)$ and $(a,1,c)$and $(a,b,1)$. We have to subtract the $n-2$ triples each of the forms $(a,1,1)$, $(1,b,1)$, $(1,1,c)$. Then we have to add back the single triple $(1,1,1)$. What remains are triples $(a,b,c)$ with $a,b,cge2$. By mapping these to $(a-1,b-1,c-1)$ we biject them with the $X_{n-3}$ triples $(x,y,z)$ with $max{x+y,x+z.y+z}<n-2$.
Therefore
$$tag{2}X_n = X_{n-2}+3{n-1choose 2}-3(n-2)+1=X_{n-2}+3{n-2choose 2}+1 $$
This would be the correct count of what corresponds to your (4) and (5). Without going into details, we see that $X_n$ is cubic in $n$, not linear as in your count; so that's where your error comes from.

We can eliminate $X_n$ by combinig equation $(1)$ with $n$ and $n-2$:
$$T_n-T_{n-2}=X_n-X_{n-2}+3(T_{n-1}-T_{n-3})-3(T_{n-2}-T_{n-4})+T_{n-3}-T_{n-5},$$
$$tag{3}T_n = 3T_{n-1}-2T_{n-2}-2T_{n-3}+3T_{n-4}-T_{n-5}+3{n-2choose 2}+1.$$
Using this recursion and $T_{-2}=ldots=T_2=0$ as starting values, one finds
$$ T_3=1\
T_4=7\
T_5=29\
T_6=90\
T_7=232\
T_8=524\
T_9=1072\
vdots
$$

The polynomial equation $x^5=3x^4-2x^3-2x^2+3x+1$ has $+1$ as quadruple root and $-1$ as a simple root. This suggests that there is an explicit formula $T_n=a_0+a_1n+a_2n^2+a_3n^3+b(-1)^n$. However, the cubic inhomogenuous part increases the degree so that we shall find an explicit formula
$$tag{4}T_n=a_0+a_1n+a_2n^2+a_3n^3+a_4n^4+a_5n^5+a_6n^6+b(-1)^n.$$
The coefficients can be obtained by plugging $(4)$ into $(3)$ and the inital values. It turns out that
$$ T_n = frac{n^6}{480}-frac{n^4}{192}-frac{n^2}{80}+frac1{128}-frac{(-1)^n}{128}=frac{4n^6 - 10n^4 - 24n^2 + 15-15cdot(-1)^n}{1920}.$$