How Many Polygons
 

Start with an equilateral triangle with each side divided into N equal parts.
Draw the N-1 line segments parallel to each of the three sides connecting
the dividing vertices on the other two sides. This divdes the triangle into
N^2 small equilateral triangles. Within this diagram are various convex
polygons composed of contiguous small triangles. The question is, how
many such convex poygons are so formed? Say, for N = 1 through 10.

[spoiler]For N=1 we have Polygons = 1. I've done my part, 1/10th of the puzzle already finished.[/spoiler]

[spoiler]I get 11 for N=2 and 50 for N=3. I think a general form solution will be difficult[/spoiler]

If somebody can show that for n=4 you get 212 or 352, then I have a guess at the general form...

[SPOILER]http://www.research.att.com/~njas/sequences/A026684[/SPOILER]

[SPOILER]http://www.research.att.com/~njas/sequences/A026618[/SPOILER]

[QUOTE=Kevin;146075]If somebody can show that for n=4 you get 212 or 352, then I have a guess at the general form...

[SPOILER]http://www.research.att.com/~njas/sequences/A026684[/SPOILER]

[SPOILER]http://www.research.att.com/~njas/sequences/A026618[/SPOILER][/QUOTE]

yeah, I searched there too :)

[SPOILER]
1 1
2 11
3 50
4 156
5 392
6 854
7 1680
8 3060
9 5247
10 8569
11 13442
12 20384
13 30030
14 43148
15 60656
16 83640
17 113373
18 151335
19 199234
20 259028

From table of differences, a sixth degree polynomial should generate these numbers.
PS:- No guarantees that my program is error free.[/SPOILER]

The polynomial is:

(n^6 + 27*n^5 + 205*n^4 + 405*n^3 + 154*n^2 - 72*n)/6!

which factorizes as:

n*(n+1)*(n+2)*(n+9)*(n^2+15*n-4)/6!

Looks like there was a bug in my program. The new numbers are:
[CODE]1 1
2 11
3 50
4 157
5 398
6 876
7 1742
8 3208
9 5561
10 9179
11 14548
12 22281
13 33138
14 48048
15 68132
16 94728
17 129417
18 174051
19 230782
20 302093
[/CODE]
Can somebody verify these?

can you briefly describe how the program is working? (i'm stuck on this problem)

The program works by extending the convex polygons one layer of triangles at a time.

The program keeps track of the "shape" & "size" of the bottom layer of all polygons.
Based on this, it calculates the shape & size of a new set of polygons formed by extending into
the newly added layer of triangles.

There are three types of shapes -- converging, parallel & diverging. The rules of extension:
[code]
\__/ ==> \__/
\/

/ \ ==> / \ or / \ or / \ or / \
---- / \ \ \ / / \ /
------ ---- ---- --

/ / ==> / / or / /
--- / / \ /
[/code]
A converging extension reduces size by 1. A parallel extension keeps the same size. A diverging extension increases the size by 1.

A converging shape with a zero size in the last layer (i.e. converges to a point), can't be extended to next layer. [Parallel & Diverging shapes can't have zero size]

[quote=axn1;146438]The program works by extending the convex polygons one layer of triangles at a time.

The program keeps track of the "shape" & "size" of the bottom layer of all polygons.
Based on this, it calculates the shape & size of a new set of polygons formed by extending into
the newly added layer of triangles.

There are three types of shapes -- converging, parallel & diverging. The rules of extension:
[code]
\__/ ==> \__/
\/

/ \ ==> / \ or / \ or / \ or / \
---- / \ \ \ / / \ /
------ ---- ---- --

/ / ==> / / or / /
--- / / \ /
[/code]A converging extension reduces size by 1. A parallel extension keeps the same size. A diverging extension increases the size by 1.

A converging shape with a zero size in the last layer (i.e. converges to a point), can't be extended to next layer. [Parallel & Diverging shapes can't have zero size][/quote]
nice pictures, but i'm still confused on one part. which polygons are kept track of (so as to avoid identical shapes) and do you tell the type of a polygon purely by the shape