Counting Hexagons in Triangle Grid Recurrence? (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?
 A: 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 $n\ge3$.
There are $n-1\choose 2$ possibilities to choose $x,y\ge 1$ such that $x+y<n$ (think of inserting two separators into the $n-1$ gaps between $n$ pebbles, thus gouping them into $x\ge1$, $y\ge1$ and $n-x-y\ge1$ pebbles). Therefore, there are $n-1\choose2$ 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,c\ge2$. 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-1\choose 2}-3(n-2)+1=X_{n-2}+3{n-2\choose 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-2\choose 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-15\cdot(-1)^n}{1920}.$$
