A293819 Triangle read by rows of the number of integer-sided k-gons having perimeter n, modulo rotations but not reflections, for k=3..n.

1, 0, 1, 1, 1, 1, 1, 2, 1, 1, 2, 4, 3, 1, 1, 1, 6, 6, 4, 1, 1, 4, 10, 13, 10, 4, 1, 1, 2, 12, 21, 21, 12, 5, 1, 1, 5, 20, 37, 41, 30, 15, 5, 1, 1, 4, 23, 51, 74, 65, 43, 19, 6, 1, 1, 7, 35, 84, 126, 131, 99, 55, 22, 6, 1, 1, 5, 38, 108, 196, 239, 216, 143, 73, 26, 7, 1, 1, 10, 56, 166, 314, 422, 428

Offset: 3

Author

James East, Oct 16 2017

Keywords

• nonn
• tabl

Comments

Rotations are counted only once, but reflections are considered different. For a k-gon to be nondegenerate, the longest side must be shorter than the sum of the remaining sides (equivalently, shorter than n/2). Column k=3 is A008742, column k=4 is A293821, column k=5 is A293822 and column k=6 is A293823.

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

Examples

			For polygons having perimeter 7, there are: 2 triangles (331, 322), 4 quadrilaterals (3211, 3121, 3112, 2221), 3 pentagons (31111, 22111, 21211), 1 hexagon (211111) and 1 heptagon (1111111). Note that the quadrilaterals 3211 and 3112 are reflections of each other, but these are not rotationally equivalent.
The triangle begins:
n=3:  1;
n=4:  0,  1;
n=5:  1,  1,  1;
n=6:  1,  2,  1,  1;
n=7:  2,  4,  3,  1,  1;
n=8:  1,  6,  6,  4,  1,  1;
n=9:  4, 10, 13, 10,  4,  1,  1;
...
		

Links

• Andrew Howroyd, Rows n=3..52 of triangle, flattened
• James East, Ron Niles, Integer polygons of given perimeter, arXiv:1710.11245 [math.CO], 2017.

Crossrefs

Columns: A008742 (triangles), A293821 (quadrilaterals), A293822 (pentagons), A293823 (hexagons).

Row sums are A293820.

Same triangle with reflection allowed is A124287.

Programs

Mathematica

T[n_, k_] := DivisorSum[GCD[n, k], EulerPhi[#]*Binomial[n/#, k/#]&]/n - Binomial[Floor[n/2], k - 1];
Table[T[n, k], {n, 3, 16}, {k, 3, n}] // Flatten (* Jean-François Alcover, Jun 14 2018, translated from PARI *)

PARI

T(n,k)={sumdiv(gcd(n,k), d, eulerphi(d)*binomial(n/d,k/d))/n - binomial(floor(n/2), k-1)}
for(n=3, 10, for(k=3, n, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 21 2017

Formula

T(n,k) = (Sum_{d|gcd(n,k)} phi(d)*binomial(n/d, k/d))/n - binomial(floor(n/2), k-1). - Andrew Howroyd, Nov 21 2017