6
$\begingroup$

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

1 Answers 1

5

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.

How many such triples ($a,b,c)$ with $\max\{a+b,a+c,b+c\} 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 (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\}. 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}.$

  • 0
    Did I really write *equally*?! Gack. I meant *apparently*. We first disagree at $n=10$, I think. For what you call $X_n$ I get $\sum_{k=1}^{n-2}\left((n-k-1)^2-\sum_{i=1}^{n-2k-1}i\right)\;,$ which for $n=10$ is $154$, if I’ve done my sums correctly.2012-09-24