Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted
+50

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

share|improve this answer
    
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. –  Andrew Tomazos Sep 17 '12 at 4:31
    
Yeah, the law of small numbers strikes again. –  Hagen von Eitzen Sep 17 '12 at 18:08
    
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.) –  Brian M. Scott Sep 21 '12 at 10:56
    
@BrianM.Scott: What was your technique? –  Andrew Tomazos Sep 21 '12 at 13:02
    
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$. –  Brian M. Scott Sep 21 '12 at 20:21
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.