Well, I have arrived at $n(1+(n-1)(n+1))$ as the solution. Probably incorrect dough.. I just can't see why

It's $n^3$?!...!?

$n^3$ is correct if you assume the hexagon edges are parallel to the sides of the original figure, but the problem does not make this assumption. Take an arbitrary hexagon. If its center is $P$ and $A,B,C$ are three consecutive vertices, then $ABCP$ is a parallelogram. Since $A,B,C$ all have vertices among the equilateral triangles, we conclude $P$ must as well. Therefore, we can count hexagons by their center vertex. Label every vertex $P$ of a triangle with the number $k$, where $k$ is the minimum number of equilateral triangle edges one must travel on to get from any edge vertex to $P$ (so e.g. all vertices on the edge get labelled with a 0). Then we can draw a 60 degree angle out from $P$ along the gridlines so that all vertices contained in this angle are those we might have travelled on in the minimum length path. A hexagon centered at $P$ either has exactly one vertex contained in the interior of the drawn angle or two vertices on the angle's boundaries. If $P$'s label is $k$, the number of points in the interior is $\binom{k}{2}$, and the number of points on one boundary is $k$. So there are $\binom{k+1}{2}$ hexagons centered at $P$. These hexagons are all valid by the fact that $k$ is the minimum path length to $P$; if one of the hexagons we constructed had an invalid vertex, we could construct a shorter path from the edge to $P$. To finish the problem, we need only sum up the value of $\binom{k+1}{2}$ for each vertex we labelled with $k$. We assigned the center of the hexagon the label $n$, and the points assigned the label $n-k$ are those lying on the edges of a regular hexagon of side length $k$ concentric with the original hexagon. There are $6k$ such points. So the total is \[ \binom{n+1}{2} + 6\sum_{k=1}^n \binom{k}{1}\binom{n-k+1}{2}. \] The sum is another way of counting the number of 4-element subsets of $\{0,1,2,\ldots,n+1\}$ with the $k$ we're summing over being the second element of the subset. So that sum is equal to $\binom{n+2}{4}$. The above then simplifies to \[ \binom{n+1}{2} + 6\binom{n+2}{4} = \frac{(n^2 + n)^2}{4}. \] (This is also the sum of the first $n$ cubes, but I'm not confident there's a nice bijection to that.)

Eh..eh i have a stupid mistake! i also think ...the hexagon edges are parallel to sides of original figure!

I used simple counting argument and ended up with a slightly strange sum which I had to leave as it is because of time was gone. But after the exam I discovered that my sum is indeed $\frac{1}{4} n^2(n+1)^2$. Sketch of my idea was: 1. divide the hexagon into 6 equilateral triangles by its 3 main diagonals 2. find the number of all possible regular hegaxons whose centers are one of the points inside and on the one side of each triangle. 3. multiply the result of 2) to 6 and add $\frac{n(n+1)}{2}$ whic is the number of all possible hegaxons with center at the center of the original hegaxone.

here my solution: Base of idea $ \rightarrow $ barycenter of any hexagon be the point one among vertices equilaterals. Let $ABCDEF$ is given originally hexagon and $A_1B_1C_1D_1E_1F_1$ is hexagon inside of $ABCDEF$ such that the sides are parallel to the sides of $ABCDEF$ and $A_1B_1=B_1C_1=...=F_1A_1=n-1$. Let $f(n)$ is number of regular hexagons for $n$. Then we will prove that $f(n)-f(n-1)=n^3$. (1) We need number of hexagons which the sides are non-parallel to original hexagon and at least one vertex lies outside of $A_1B_1C_1D_1E_1F_1$. It's obviously equal to $ (n-1)^3 $, because the barycenter of the hexagon lies on inside of $A_1B_1C_1D_1E_1F_1$ and we can change this hexagon to another hexagon which the all vertices lie inside of original hexagon $ABCDEF$. (2). The number of hexagons which the sides are parallel to the sides of original hexagon $ABCDEF$ and at least one vertex lies outside of $A_1B_1C_1D_1E_1F_1$ is $n^3-(n-1)^3 $ (see post previous posts '@Nsamardzic'). So we have $f(n)-f(n-1)=[(1)+(2)]=n^3$ ($f(n)$ for $ABCDEF$, $f(n-1)$ for $A_1B_1C_1D_1E_1F_1$ ). Hence \[ f(n)=n^3+(n-1)^3+...+1^3 .\]

mathuz wrote: (1) We need number of hexagons which the sides are non-parallel to original hexagon and at least one vertex lies outside of $A_1B_1C_1D_1E_1F_1$. It's obviously equal to $ (n-1)^3 $, because the barycenter of the hexagon lies on inside of $A_1B_1C_1D_1E_1F_1$ and we can change this hexagon to another hexagon which the all vertices lie inside of original hexagon $ABCDEF$. In other words, you want to establish a bijection between the hexagons with the sides non-parallel to those of the original hexagon and at least one vertex lying outside of $A_1B_1C_1D_1E_1F_1$, and the hexagons with the sides parallel to those of the original hexagon and all vertices lying inside of $A_1B_1C_1D_1E_1F_1$ (I assume this is what you wanted to say, since you want the count to be $(n-1)^3$). It is not clear how you propose to do that - just saying "we can change this hexagon to another hexagon ..." is quite insufficient.

it wasn't clear.. never mind

90% of your post is just repeating what you want to happen; then instead of saying "it's obvious", like in your first post, you say "it's clear by induction". Well, it is not so clear to me ... why won't you just offer a full proof? please!

MellowMelon wrote: $n^3$ is correct if you assume the hexagon edges are parallel to the sides of the original figure, but the problem does not make this assumption. Take an arbitrary hexagon. If its center is $P$ and $A,B,C$ are three consecutive vertices, then $ABCP$ is a parallelogram. Since $A,B,C$ all have vertices among the equilateral triangles, we conclude $P$ must as well. Therefore, we can count hexagons by their center vertex. Label every vertex $P$ of a triangle with the number $k$, where $k$ is the minimum number of equilateral triangle edges one must travel on to get from any edge vertex to $P$ (so e.g. all vertices on the edge get labelled with a 0). Then we can draw a 60 degree angle out from $P$ along the gridlines so that all vertices contained in this angle are those we might have travelled on in the minimum length path. A hexagon centered at $P$ either has exactly one vertex contained in the interior of the drawn angle or two vertices on the angle's boundaries. If $P$'s label is $k$, the number of points in the interior is $\binom{k}{2}$, and the number of points on one boundary is $k$. So there are $\binom{k+1}{2}$ hexagons centered at $P$. These hexagons are all valid by the fact that $k$ is the minimum path length to $P$; if one of the hexagons we constructed had an invalid vertex, we could construct a shorter path from the edge to $P$. To finish the problem, we need only sum up the value of $\binom{k+1}{2}$ for each vertex we labelled with $k$. We assigned the center of the hexagon the label $n$, and the points assigned the label $n-k$ are those lying on the edges of a regular hexagon of side length $k$ concentric with the original hexagon. There are $6k$ such points. So the total is \[ \binom{n+1}{2} + 6\sum_{k=1}^n \binom{k}{1}\binom{n-k+1}{2}. \] The sum is another way of counting the number of 4-element subsets of $\{0,1,2,\ldots,n+1\}$ with the $k$ we're summing over being the second element of the subset. So that sum is equal to $\binom{n+2}{4}$. The above then simplifies to \[ \binom{n+1}{2} + 6\binom{n+2}{4} = \frac{(n^2 + n)^2}{4}. \] (This is also the sum of the first $n$ cubes, but I'm not confident there's a nice bijection to that.) sorry mellowmellon, i have read your solution and the last part of it is not as clear to me can you explain it? I'm talking about this equation \[ \sum_{k=1}^n \binom{k}{1}\binom{n-k+1}{2}=\binom{n+2}{4} \] thank you beforehead

"number of hexagons with vertices in an hexagonal grid with n points in each side." Ignacio Larrosa Cañestro, Oct 15 2006 In OEIS: http://oeis.org/A000537

zaurimeshveliani: I'm doing a double-counting / bijective proof, counting the number of 4-element subsets of $\{0,1,2,\ldots,n+1\}$ in two ways. One way to count it is simply the binomial coefficient $\binom{n+2}{4}$. A second way to count it is to condition on what the second smallest element $k$ is. For any fixed value of $k$, we need to pick two things: the one element of our subset less than $k$ and the two elements of our subset greater than $k$. There are $k$ nonnegative integers less than $k$, so we can pick the 1 element in $\binom{k}{1}$ ways. There are $n-k+1$ nonnegative integers greater than $k$ but at most $n+1$, so we can pick the 2 elements in $\binom{n-k+1}{2}$ ways. The choices are independent, so we take the product of these two binomial coefficients, then sum over all possibilities for $k$. This shows that a second answer to the question is $\sum_{k=1}^n\binom{k}{1}\binom{n-k+1}{2}$. We counted the same thing both times, so the two quantities must be equal. This book, which I really like, is entirely focused on proving things in this manner.

NSamardzic wrote: Well, I have arrived at $n(1+(n-1)(n+1))$ as the solution. Probably incorrect dough.. I just can't see why mathuz wrote: are you sure? It's $n^3$?!...!? Um... $n(1+(n-1)(n+1))=n(1+n^2-1)=n(n^2)=n^3$ But anyway that is the incorrect answer.

Define a p-hexagon as one which has its edges through the vertices of the equilateral triangles, ie. one whose sides are parallel to those of the original hexagon. Within any p-hexagon of side length $m$, there are exactly $m$ regular hexagons whose vertices lie on the perimeter of this p-hexagon. There exist exactly $3(n-m)(n-m+1)$ p-hexagons of side length $m$, since the centre of each p-hexagon lies no more than $n-m$ away from the centre of the original hexagon, and these centres form a hexagon of side length $n-m$: the number of such p-hexagons is therefore the $(n-m+1)^{\text{th}}$ centred hexagonal number, which is $3(n-m)(n-m+1)$. Hence the number we are looking for is: \[\sum_{m=1}^n \left(3(n-m)(n-m+1)+1\right)m = \sum_{m=1}^n (3(n^2 - 2mn + m^2 + n -m)+1)m\] \[= (3n^2 + 3 + 1)\sum_{m=1}^n m - 3(2n+1)\sum_{m=1}^n m^2 + 3\sum_{m=1}^n m^3\] Using the fact that $\sum_{m=1}^n m=\frac{n(n+1)}{2}$, $\sum_{m=1}^n m^2 = \frac{n(n+1)(2n+1)}{6}$ and $\sum_{m=1}^n m^3 =\left(\frac{n(n+1)}{2} \right)^2$ yields the desired result of $\left(\frac{n(n+1)}{2} \right)^2$

Same logic, but slightly different counting. Let S be the number of hexagons that we are counting. Claim 1: If the vertices of the hexagons lies on the grid points then it's center belongs to the grid point. Claim 2: If we pick the center and one of the vertices, then the hexagon is well defined and all of it's vertices lies on the another hexagons surface whose all sides are grid line. Claim 3: Let $x$ be the side of the hexagon whose sides are grid lines. Then the number of hexagons whose center is same as that hexagon and it's vertices lies on it's surface is just $x$. Claim 4: Let $x$ be the side of the hexagon whose sides are grid lines. Then number of these hexagons which inscribed in a original hexagon is equal to $3x^2+3x+1$. Claim 5: By combining all the claims we get that $S=\sum_{x=1}^n x(3(n-x)^2+3(n-x)+1)$, which is eventually become $S=(\frac{n(n+1)}{2})^2$