A293820 Number of integer-sided polygons having perimeter n, modulo rotations but not reflections.

1, 1, 3, 5, 11, 19, 43, 75, 155, 287, 567, 1053, 2063, 3859, 7455, 14089, 27083, 51463, 98855, 188697, 362675, 695155, 1338087, 2573235, 4962875, 9571195, 18496407, 35759799, 69240899, 134154259, 260235639, 505163055, 981575759, 1908619755, 3714304167, 7233118641, 14095779055

Offset

3,3

Comments

Rotations are counted only once, but reflections are considered different. For a polygon to be nondegenerate, the longest side must be shorter than the sum of the remaining sides (equivalently, shorter than n/2). These are row sums of A293819.

A formula is given in Section 6 of the East and Niles article.

The same article shows that a(n) is asymptotic to 2^n / n.

Links

Andrew Howroyd, Table of n, a(n) for n = 3..200

James East, Ron Niles, Integer polygons of given perimeter, arXiv:1710.11245 [math.CO], 2017.

Formula

a(n) = (Sum_{d|n} phi(n/d)*2^d)/n - 1 - 2^floor(n/2). - Andrew Howroyd, Nov 21 2017

Example

There are 11 polygons having perimeter 7: 2 triangles (331, 322), 4 quadrilaterals (3211, 3121, 3112, 2221), 3 pentagons (31111, 22111, 21211), 1 hexagon (211111) and 1 heptagon (1111111).

Mathematica

T[n_, k_] := DivisorSum[GCD[n, k], EulerPhi[#]*Binomial[n/#, k/#] &]/n - Binomial[Floor[n/2], k - 1];
a[n_] := Sum[T[n, k], {k, 3, n}]
Table[a[n], {n, 3, 40}] (* Jean-François Alcover, Jun 14 2018, after Andrew Howroyd *)

Prog

(PARI) a(n) = sumdiv(n, d, eulerphi(n/d)*2^d)/n - 1 - 2^floor(n/2); \\ Andrew Howroyd, Nov 21 2017

Crossrefs

Cf. A008742 (triangles), A293818 (reflections allowed), A293821 (quadrilaterals), A293822 (pentagons), A293823 (hexagons).

Row sums of A293819 (k-gon triangle).

Sequence in context: A131887 A045691 A045961 * A281380 A117272 A243616

Adjacent sequences: A293817 A293818 A293819 * A293821 A293822 A293823

Keyword

nonn

Author

James East, Oct 16 2017

Status

approved