How Many Polygons

[davar55]

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.

[retina]

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

[Orgasmic Troll]

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

[Kevin]

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

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

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

[Orgasmic Troll]

Originally Posted by Kevin

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

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

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

yeah, I searched there too :)

[axn]

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.

[axn]

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!

[axn]

Looks like there was a bug in my program. The new numbers are:

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

Can somebody verify these?

[starrynte]

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

[axn]

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:

\__/ ==> \__/
          \/

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

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]

[starrynte]

Originally Posted by axn1

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:

\__/ ==> \__/
          \/

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

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]

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