A293819 - OEIS

%I #40 Jun 14 2018 04:03:18

%S 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,

%T 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,

%U 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

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

%C 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.

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

%H Andrew Howroyd, <a href="/A293819/b293819.txt">Rows n=3..52 of triangle, flattened</a>

%H James East, Ron Niles, <a href="https://arxiv.org/abs/1710.11245">Integer polygons of given perimeter</a>, arXiv:1710.11245 [math.CO], 2017.

%F 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

%e 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.

%e The triangle begins:

%e n=3:  1;

%e n=4:  0,  1;

%e n=5:  1,  1,  1;

%e n=6:  1,  2,  1,  1;

%e n=7:  2,  4,  3,  1,  1;

%e n=8:  1,  6,  6,  4,  1,  1;

%e n=9:  4, 10, 13, 10,  4,  1,  1;

%e ...

%t T[n_, k_] := DivisorSum[GCD[n, k], EulerPhi[#]*Binomial[n/#, k/#]&]/n - Binomial[Floor[n/2], k - 1];

%t Table[T[n, k], {n, 3, 16}, {k, 3, n}] // Flatten (* _Jean-François Alcover_, Jun 14 2018, translated from PARI *)

%o (PARI)

%o T(n,k)={sumdiv(gcd(n,k), d, eulerphi(d)*binomial(n/d,k/d))/n - binomial(floor(n/2), k-1)}

%o for(n=3, 10, for(k=3, n, print1(T(n, k), ", ")); print); \\ _Andrew Howroyd_, Nov 21 2017

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

%Y Row sums are A293820.

%Y Same triangle with reflection allowed is A124287.

%K nonn,tabl

%O 3,8

%A _James East_, Oct 16 2017