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

Author

James East, Oct 16 2017

Keywords

• nonn

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.

Examples

			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).
		

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.

Crossrefs

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

Row sums of A293819 (k-gon triangle).

Programs

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 *)

PARI

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

Formula

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