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\}$$\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
    This is correct, thanks. I was fooled by the N=4 case into thinking that all hexagons that touch all three sides must have one side of n-2, which is true for N=4 but not true for higher values of N. For example for N=5 we can have a hexagon that results from chopping off triangles of side 2 removed from each corner of the grid.2012-09-17
  • 0
    Yeah, the law of small numbers strikes again.2012-09-17
  • 1
    Interesting. By a completely different technique I arrived at the less elegant but equally correct solution $$T_n=\frac1{360}(x^6-9x^5+130x^4-1005x^3+4189x^2-9066x+7920)\;.$$ (@user1131467 may also be interested.)2012-09-21
  • 0
    @BrianM.Scott: What was your technique?2012-09-21
  • 0
    I found a reasonable way to count the hexagons with bases on the bottom edge. This gives a recurrence $T_{n+1}=T_n+f(n)$. The function $f(n)$ was a bit messy, but it showed that $T_n$ was polynomial in $n$ of degree at most $6$. The rest was just an application of finite differences, since $f(n)$ allowed easy computation of more than enough values of $T_n$.2012-09-21
  • 0
    @BrianM.Scott: Hm, but you don't have a $(-1)^n$ part, hence our solutions cannot be *equally* correct / at most one of them can be corret ...?2012-09-24
  • 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