login
Triangle of the number of integer-sided k-gons having perimeter n, for k=3..n.
7

%I #22 Jun 14 2018 04:03:09

%S 1,0,1,1,1,1,1,2,1,1,2,3,3,1,1,1,5,4,4,1,1,3,7,9,7,4,1,1,2,9,13,15,8,

%T 5,1,1,4,13,23,25,20,10,5,1,1,3,16,29,46,37,29,12,6,1,1,5,22,48,72,75,

%U 57,35,14,6,1,1,4,25,60,113,129,125,79,47,16,7,1,1,7,34,92,172,228,231,185

%N Triangle of the number of integer-sided k-gons having perimeter n, for k=3..n.

%C Rotations and reversals are counted only once. 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 A057886, column k=5 is A124285 and column k=6 is A124286. Note that A124278 counts polygons whose sides are nondecreasing.

%H Andrew Howroyd, <a href="/A124287/b124287.txt">Table of n, a(n) for n = 3..1277</a> (terms 3..212 from T. D. Noe)

%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 A formula is given in Theorem 1.5 of the East and Niles article.

%e For polygons having perimeter 7: 2 triangles, 3 quadrilaterals, 3 pentagons, 1 hexagon and 1 heptagon. The triangle begins

%e 1

%e 0 1

%e 1 1 1

%e 1 2 1 1

%e 2 3 3 1 1

%e 1 5 4 4 1 1

%t Needs["DiscreteMath`Combinatorica`"]; Table[p=Partitions[n]; Table[s=Select[p,Length[ # ]==k && #[[1]]<Total[Rest[ # ]] &]; cnt=0; Do[cnt=cnt+Length[ListNecklaces[k,s[[i]],Dihedral]], {i,Length[s]}]; cnt, {k,3,n}], {n,3,20}]

%t (* Second program: *)

%t T[n_, k_] := (DivisorSum[GCD[n, k], EulerPhi[#]*Binomial[n/#, k/#]&]/n + Binomial[Quotient[k, 2] + Quotient[n - k, 2], Quotient[k, 2]] - Binomial[ Quotient[n, 2], k - 1] - Binomial[Quotient[n, 4], Quotient[k, 2]] - If[ OddQ[k], 0, Binomial[Quotient[n + 2, 4], Quotient[k, 2]]])/2;

%t Table[T[n, k], {n, 3, 20}, {k, 3, n}] // Flatten (* _Jean-François Alcover_, Jun 14 2018, after _Andrew Howroyd_ *)

%o (PARI)

%o T(n,k)={(sumdiv(gcd(n, k), d, eulerphi(d)*binomial(n/d, k/d))/n + binomial(k\2 + (n-k)\2, k\2) - binomial(n\2, k-1) - binomial(n\4, k\2) - if(k%2, 0, binomial((n+2)\4, k\2)))/2;}

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

%Y Row sums are A293818.

%Y Cf. A293819.

%K nonn,tabl

%O 3,8

%A _T. D. Noe_, Oct 24 2006