Counting n-gons

[Jonathan Post]

What Tony did is very nice indeed.  What Franklin wrote is certainly
correct.

The partitions can be the same, but the order of edges encountered in a
circuit can differ.

By bow-tie I mean, for instance, for a nonsimple quadrilateral of perimeter
6, the sequence of coordinates (0,0), (0,1), (sqrt 3, 0), (sqrt 3, 1),
(0,0).  The crossing point, not a vertex, is ((sqrt 3)/2, 1/2). Yes, that
can be traversed in other orders, and the quadrilateral can be deformed.
Linkages were much studied until perhaps the 2nd half of the 20th century in
American education.

As well as what I'd call the (1, 2, 1, 2) rectangle (deformable into a
parallelogram), there is a (1, 1, 2, 2) kite and a a (1, 1, 2, 2)  which are
not similar to each other or to the rectangle.  Both kite and dart share a
vertex at (0, 0) , a vertex at (2, 0), and a vertex at (7/4, (sqrt 15)/4).
The coordinates of the other two vertices are elementary and left to the
reader.

Yes, for a general nonsimple n-gon, any of the n edges can be crossed.  The
crossing point has integral coordinates precisely when Pythagorus would want
it.  This relates these sequences to those about Pythagorean triplets.

There are other sequences yet to be mined here, under the various
assumptions that I made, including a count of the number of nonsimple n-gons
of permineter n, under appropriate equivalence classes.  Similarly, the
maximum areas for each edge sequence.

For perimeter 7, we have in the given example (1, 2, 2, 2) and (1, 1, 2,
3).  But the trapezoid I'd denote by edges encountered in circuit (1, 2, 1,
3) is not similar to the irregular convext quadrilateral I'd call (1, 1, 2,
3).  And perimeter 7 can have nonvertex crossings near edges of length 1, 2,
or 3 as desired.

More work here for all of us to share.

-- Jonathan (proud that his 18-year-old son in 5th year of university just
scored 99th percentile on the LSAT, and thus likely to attend one of
America's very best law schools, such as Harvard, Yale, Stanford, Berkeley,
NYU, ... even though that means not immediately going to grad school to
follow on his pending double B.S. in Math and Computer Science)

On 10/24/06, T. D. Noe <noe at sspectra.com> wrote:
>
> At 5:13 PM -0400 10/23/06, franktaw at netscape.net wrote:
> >There's a problem with this formulation.  Triangles are determined up
> >to congruence by their side lenths, but polygons with more sides are
> >not.  (Consider rhombus vs. square.)
> >
> >To make it work, you have to define it purely in terms of edge lengths:
> >sequences of n positive integers, totalling p, whose largest value is
> >less than the sum of the others (equivalently, less than p/2); up to
> >equivalence under rotation and reflection.
> >
> >Franklin T. Adams-Watters
> >
> >
> >-----Original Message-----
> >From: davidwwilson at comcast.net
> >
> >Let f(n,p) be the number of non-congruent integer-sided n-gons with
> >perimeter p. Then f(3,p) = A005044.
> >
> >Can we come up with a general formula/recurrence for f(n, p)?
>
>
> I just submitted A124278, triangle of the number of k-gons having
> perimeter
> n.  Included is a generating function for each column of the triangle.
> There is also a b-file for rows n=3..102 of the triangle.  Here is the
> internal format:
>
> %S A124278 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 3, 2, 2, 1, 1,
> 3, 4, 4, 3, 2, 1, 1, 2, 5, 5, 4, 3, 2, 1, 1, 4, 7, 8, 6, 5, 3, 2, 1, 1, 3,
> 8, 9, 9, 6, 5, 3, 2, 1, 1, 5, 11, 14, 12, 10, 7, 5, 3, 2, 1, 1, 4, 12, 16,
> 16, 13, 10, 7, 5, 3, 2, 1, 1, 7, 16, 23, 22, 19, 14, 11, 7, 5, 3, 2, 1, 1,
> 5, 18, 25, 28, 24, 20, 14, 11, 7, 5, 3, 2, 1, 1, 8, 23, 35, 37, 34, 27,
> 21,
> 15, 11, 7, 5, 3, 2, 1, 1
> %N A124278 Triangle of the number of nondegenerate k-gons having perimeter
> n, for k=3..n.
> %C A124278 For a k-gon to be nondegenerate, the longest side must be
> shorter than the sum of the remaining sides. Column k=3 is A005044, column
> k=4 is A062890, column k=5 is A069906, and column k=6 is A069907.
> %H A124278 G.E. Andrews, P. Paule, and A. Riese, <a
> href="
> http://www.risc.uni-linz.ac.at/publications/download/risc_163/PAIX.pdf
> ">MacMahon's
> Partition Analysis IX: k-Gon Partitions, Bull. Austral. Math. Soc. 64
> (2001), 321-329.</a>
> %H A124278 T. D. Noe, <a
> href="http://www.research.att.com/~njas/sequences/b124278.txt">Rows
> n=3..102 of triangle, flattened</a>
> %F A124278 G.f. for column k is x^k/(product_{i=1..k} 1-x^i) -
> x^(2k-2)/(1-x)/(product_{i=1..k-1} 1-x^(2i))
> %e A124278 For polygons having perimeter 7: 2 triangles, 2 quadrilaterals,
> 2 pentagons, 1 hexagon, and 1 heptagon.  The triangle begins
> 1
> 0 1
> 1 1 1
> 1 1 1 1
> 2 2 2 1 1
> 1 3 2 2 1 1
> %t A124278 Needs["DiscreteMath`Combinatorica`"]; Table[p=Partitions[n];
> Length[Select[p, Length[#]==k && #[[1]]<Total[Rest[#]]&]], {n,3,30},
> {k,3,n}]
> %O A124278 3
>
> Tony
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061024/7354c758/attachment-0002.htm>