Integer polygons of given perimeter
James East and Ron Niles
Abstract

arXiv:1710.11245v2 [math.CO] 14 Nov 2017

A classical result of Honsberger states that the number of incongruent triangles with integer sides and
2
2
perimeter n is the nearest integer to n48 (n even) or (n+3)
(n odd). We solve the analogous problem for
48
m-gons (for arbitrary but fixed m ≥ 3), and for polygons (with arbitrary number of sides). We also show
that the solution to the latter is asymptotic to 2n−1 /n.

1

Introduction and statement of the main results

Several fundamental mathematical theorems involve triangles. The most famous of course is that of Pythagoras: a2 + b2 = c2 if a ≤ b ≤ c are the sides of a right-angled triangle. It is a standard exercise in number
theory to classify all right-angled integer triangles. (By an integer polygon we mean a polygon whose sidelengths are all
p integers.) Lesser known is Heron’s beautiful formula: the area of a triangle with sides a, b, c
is the semi-perimeter. A 1904 result attributed to
is given by s(s − a)(s − b)(s − c), where s = a+b+c
2
Whitworth and Biddle (see [5, p. 199]) states that there are exactly five (incongruent) integer triangles with
perimeter equal to area. Phelps and Fine [13] showed that there is only one with perimeter equal to twice
the area, namely the (3, 4, 5) triangle. Subbarao [15] and Marsden [12] considered analogous problems for
other multiples. Heron’s formula played an important role in the articles [12, 13, 15], in each case reducing
the problem to a simple diophantine equation. Related to these, the following question appears to have
been first asked (and answered) by Jordan, Walch and Wisner [10] in 1979:
Question 1.1. How many incongruent integer triangles have perimeter n?
Several formulations of the answer exist [2,8,10,11,14], and we believe the most elegant is the following:
 2
Theorem 1.2 (Honsberger [8]). The number of incongruent integer triangles with perimeter n is n48 if n

2
is even, or (n+3)
if n is odd.
48

Here, [x] denotes the nearest integer to the real number x (if such exists). A number of proofs of
Theorem 1.2 have been given; see for example [6–9], most of which use recurrence relations and/or generating
functions, sometimes ingeniously.
If the word “triangles” is simply replaced with “quadrilaterals” in Question 1.1, then the answer is not
very interesting: for example, there are infinitely many incongruent rhombuses with edges (1, 1, 1, 1). The
same is true for pentagons, hexagons, and so on. Thus, rather than congruence, we consider two m-gons
to be equivalent if we can obtain one from the other by combinations of rotations, reflections, and gentle
squeezing. In the latter, corners and sides may move relative to each other (without coming apart), but
edges must stay straight, and edge-lengths must be preserved. In Figure 1 for example, the first and second
quadrilaterals are equivalent, the third and fourth are equivalent, but the first and third are inequivalent.
1

2

2

2
1

1

2
1

2

2

1
1

2

2

Figure 1: Several quadrilaterals with edge-lengths 1, 1, 2, 2.
Thus, we would like to answer the following two questions:
Question 1.3. How many inequivalent integer m-gons have perimeter n?
Question 1.4. How many inequivalent integer polygons have perimeter n?
1

1

1

As far as we are aware, neither question has been answered previously, apart from the m = 3 case of
Question 1.3; cf. Theorem 1.2 above. The main purpose of the current article is to give answers to both
questions, and we now state the results that answer them. If d and m are integers, we write d  m to indicate
that d divides m: i.e., that m
d is an integer. We write
 ⌊x⌋ for the floor of the real number x: i.e., the greatest
integer not exceeding x. A binomial coefficient nk has its usual meaning if n, k are non-negative integers
with k ≤ n, and is zero otherwise. Finally, ϕ is Euler’s totient function; so for a positive integer n, ϕ(n) is
the size of the set {d ∈ {1, . . . , n} : gcd(d, n) = 1}.
Theorem 1.5. If 3 ≤ m ≤ n, then the number pm,n of inequivalent integer m-gons with perimeter n is
given by
 
 m
  n   n   n+2 
X
⌊ 2 ⌋ + ⌊ n−m
⌋
⌊4⌋
⌊2⌋
⌊ 4 ⌋
1
ϕ(d) nd
2
−
−
.
− m
pm,n =
m
m +
m
2n
2
m−1
⌊2⌋
⌊2⌋
d
2
dgcd(m,n)

Theorem 1.6. If n ≥ 3, then the number pn of inequivalent integer polygons with perimeter n is given by

n−4
3 · 2⌊ 4 ⌋ if n ≡ 0 or 1 (mod 4)
X ϕ(d) · 2 nd −1
n−3
⌊ 2 ⌋
+2
−
pn =
 ⌊ n+2
n
if n ≡ 2 or 3 (mod 4).
2 4 ⌋
dn

From Theorem 1.5, we may deduce Honsberger’s Theorem 1.2 above as a special case. As an additional
application, we also give an analogous “nearest integer formula” for quadrilaterals in Theorem 5.1 below,
From Theorem 1.6, we will be able to deduce the following elegant asymptotic formula for the pn sequence:

Theorem 1.7. The number of inequivalent integer polygons with perimeter n is asymptotic to 2n−1 /n.
The proofs of Theorems 1.5 and 1.6 follow the same pattern. In both cases, we (i) identify an action of
the dihedral group Dn (defined below) on a certain set of n-tuples, (ii) show that the polygons in question
are in one-one correspondence with the orbits of the action, and (iii) enumerate the orbits using Burnside’s
Lemma (stated in Lemma 2.1 below). We carry out the first two tasks in Section 2, where we also show how
the third reduces to the calculation of certain parameters associated to the elements of Dn . We calculate
these parameters (the bulk of the work) in Section 3, and then complete the proofs in Section 4. Section 5
gives the above-mentioned applications to triangles and quadrilaterals, and Section 6 contains tables of
calculated values, and some concluding remarks.

2

Dihedral group actions

Recall that an action of a group G on a set X is a map G × X → X : (g, x) 7→ g · x, such that idG · x = x
and (gh) · x = g · (h · x) for all x ∈ X and g, h ∈ G. An action induces an equivalence relation on X,
namely (x, y) ∈ X × X : x = g · y (∃g ∈ G) , the equivalence classes of which are the orbits of the action.
The set of orbits is denoted by X/G, and the number of orbits is given by Burnside’s Lemma (see for
example [4, p246] for a proof):
Lemma 2.1. If a finite group G acts on a set X, then the number of orbits of the action is given by
|X/G| =

1 X
fixX (g),
|G|
g∈G

where fixX (g) is the cardinality of the set FixX (g) = {x ∈ X : g · x = x}, for g ∈ G.
In what follows, n generally denotes the perimeter of an integer polygon. Since a polygon has at
least three sides, we will always assume that n ≥ 3. We denote by Sn the symmetric group on the
set {1, . . . , n}, which consists of all permutations of this set. We call a permutation σ ∈ Sn a rotation
if there exists q ∈ {0, 1, . . . , n − 1} such that σ(x) = q + x for all x (reading q + x modulo n where necessary); when q = 0, we obtain the identity map, idn . Similarly, σ is a reflection if there exists q such
that σ(x) = q − x for all x. We write Dn for the set of all rotations and reflections, and Cn for the set of
all rotations. These are subgroups of Sn : the dihedral group of order 2n, and the cyclic group of order n,
respectively. Note that Dn contains n rotations (including the identity), and n reflections. When n is odd,
2

all n reflections fix a single point from {1, . . . , n}; when n is even, n2 of the reflections have two fixed points,
and n2 have none.
Now consider a circular rope of length n units, with n equally spaced points labelled 1, . . . , n, read
clockwise. For any subset A of {1, . . . , n}, we may attempt to create a polygon out of the rope, with corners
at the points from A, by pulling the strings taut between these selected points. With n = 10, for example,
this is possible for A = {1, 3, 4, 8}, but not for B = {3, 4, 8}; for the former, see Figure 2. Obviously,
to create a polygon for such a subset A of {1, . . . , n}, we would need |A| ≥ 3, but there is an additional
restriction coming from the fact that the sides of a polygon must all be less than half the perimeter. Namely,
if A = {x1 , . . . , xm }, where m ≥ 3 and x1 < · · · < xm , then we require
max{x2 − x1 , x3 − x2 , . . . , xm − xm−1 , n + x1 − xm } < n2 .
10

1

9

1

3

2

2

8

2
3

8

3

3
1

1
7

4
6

5

4

4

4

Figure 2: The polygon of perimeter 10 corresponding to the subset A = {1, 3, 4, 8} of {1, . . . , 10}.
The above ideas are easier to work with when formulated in slightly different terms. Write T = {0, 1}.
We identify a subset A of {1, . . . , n} with an n-tuple a = (a1 , . . . , an ) ∈ T n in the usual way: we have
ax = 1 ⇔ x ∈ A. Thus, given a ∈ T n , we may attempt to form a polygon of perimeter n as above. It
turns out that the n-tuples corresponding to polygons in this way may be described very easily.
By a block of 0’s of length l of an n-tuple a ∈ T n , we mean a sequence of l consecutive entries of a
(possibly “wrapping around n”), all of which are 0, that is not contained in any larger such sequence
of consecutive 0’s. Thus, for example, the subsets A and B of {1, . . . , 10} defined above correspond to
the 10-tuples a = (1, 0, 1, 1, 0, 0, 0, 1, 0, 0) and b = (0, 0, 1, 1, 0, 0, 0, 1, 0, 0); here, a has three blocks of 0’s, of
lengths 1, 2 and 3, while b has blocks of lengths 3 and 4; one of the blocks of b wraps around.
Writing k = ⌊ n2 ⌋, so that n = 2k or 2k + 1, we will call a block of 0’s of an n-tuple a ∈ T n bad if its
length is at least k − 1 (n even) or k (n odd). If an n-tuple a ∈ T n had a bad block of 0’s, then it would be
impossible to form a polygon from a, as the bad block would lead to an edge of length at least n2 . Conversely,
if a ∈ T n has no bad blocks, then we can form a polygon from a; for this, note that having no bad blocks
forces a to have at least three 1’s, since n ≥ 3. Accordingly, we call an n-tuple bad if it has at least one bad
block, or good if it has none, and we write
Gn = {a ∈ T n : a is good} and

Bn = {a ∈ T n : a is bad}.

So Gn consists of the n-tuples that correspond
Pto polygons in the manner described above.
For a = (a1 , . . . , an ) ∈ T n , we denote by
a the integer a1 + · · · + an , which is just the number of 1’s
in a. For 0 ≤ m ≤ n, we write

P
Tm,n = a ∈ T n :
a=m
for the set of all n-tuples with exactly m 1’s, and we also write
Gm,n = Gn ∩ Tm,n

and Bm,n = Bn ∩ Tm,n

for the sets of all good and bad such n-tuples, respectively. So Gm,n consists of the n-tuples that correspond
to m-gons in the manner described above. Note that Gm,n = ∅ if m ≤ 2
There is a natural action of the dihedral group Dn on T n given by permuting the coordinates:
σ · (a1 , . . . , an ) = (aσ−1 (1) , . . . , aσ−1 (n) )

for (a1 , . . . , an ) ∈ T n and σ ∈ Dn .

The next result gathers some obvious properties of this action; its proof is routine, and is omitted.
3

(2.2)

Lemma 2.3. If n ≥ 3, a ∈ T n and σ ∈ Dn , then
P
P
(i)
a = (σ · a),
(ii) a ∈ Gn ⇔ σ · a ∈ Gn ,

(iii) a ∈ Bn ⇔ σ · a ∈ Bn .

It follows from part (i) of Lemma 2.3 that Tm,n is closed under the action of Dn ; by parts (ii) and (iii),
so too are the sets Gn and Bn ; by combinations of these facts, it follows that the sets Gm,n and Bm,n are
closed as well. Thus, (2.2) defines actions of Dn on all of the sets T n , Gn , Bn , Tm,n , Gm,n and Bm,n .
Clearly two good n-tuples are in the same orbit of the action if and only if they determine equivalent
polygons in the manner described above. Together with Lemma 2.1, and writing pn (respectively, pm,n ) for
the number of inequivalent integer polygons (respectively, m-gons) of perimeter n, it follows that
1 X
1 X
fixGn (σ) and pm,n = |Gm,n /Dn | =
fixGm,n (σ).
(2.4)
pn = |Gn /Dn | =
2n
2n
σ∈Dn

σ∈Dn

Also, for any σ ∈ Dn , FixT n (σ) = (FixT n (σ) ∩ Gn ) ∪ (FixT n (σ) ∩ Bn ) = FixGn (σ) ∪ FixBn (σ), by Lemma 2.3,
with a similar statement for FixTm,n (σ). Since Gn and Bn are disjoint, it follows that
fixGn (σ) = fixT n (σ) − fixBn (σ)

and

fixGm,n (σ) = fixTm,n (σ) − fixBm,n (σ)

for any σ ∈ Dn .

(2.5)

Equations (2.4) and (2.5) form the basis of our calculation of pn and pm,n . We use (2.5) to calculate the
values of fixGn (σ) and fixGm,n (σ) in Section 3, before showing in Section 4 that these, together with (2.4),
yield the formulae for pn and pm,n stated in Theorems 1.5 and 1.6.

3

Fix sets

As outlined in the previous section, the calculation of pn and pm,n reduces to the calculation of the parameters
fixGn (σ) and fixGm,n (σ) for each σ ∈ Dn . We perform these calculations in this section, proving separate
lemmas for the various forms of elements from Dn . In all the proofs that follow, if a ∈ T k for some k, we
generally assume that a = (a1 , . . . , ak ). We also remind the reader of the convention regarding binomial
coefficients being zero if the arguments fall outside of the usual ranges. We begin with the identity element.
Lemma 3.1. If n ≥ 3, then
⌋
⌊n
2

(i) fixGn (idn ) = 2n − 1 − n · 2

+

(

n
2

0

if n is even
if n is odd,

 
 n 
n
⌊2⌋
(ii) fixGm,n (idn ) =
−n
for any 3 ≤ m ≤ n.
m
m−1

Proof. (i). Clearly fixGn (idn ) = |Gn | = |T n | − |Bn |. Since |T n | = 2n , it therefore suffices to show, writing
k = ⌊ n2 ⌋ for convenience, that
(
−k if n = 2k is even
k
|Bn | = 1 + n · 2 +
0
if n = 2k + 1 is odd.
Certainly (0, . . . , 0) ∈ Bn , so it remains to count the non-zero n-tuples from Bn . By definition, every n-tuple
from Bn has at least one bad block of 0’s. In fact, it is only possible for an n-tuple to have two bad blocks
if n is even, in which case there are exactly n2 such n-tuples (these have two 1’s equally spaced around the
circle). For i ∈ {1, . . . , n}, write πi for the number of non-zero n-tuples a from T n that have a bad block
beginning at position i: i.e.,
ai−1 = 1 and

ai = ai+1 = · · · = ai+l−1 = 0,

where l = k − 1 (n even) or l = k (n odd).

Since the remaining n−(l +1) = k entries ai+l , . . . , ai−2 of such an n-tuple may be chosen arbitrarily from T ,
it follows that πi = 2k for all i. Then π1 + · · · + πn = n · 2k counts the non-zero n-tuples with one bad block
once, but double-counts the non-zero n-tuples with two bad blocks. We have already noted that there are
none of the latter if n is odd, or n2 = k of them if n is even. The result quickly follows.

n
(ii). This time, fixGm,n (idn ) = |Gm,n | = |Tm,n | − |Bm,n | = m
− |Bm,n |. Every element of Bm,n has exactly
⌊n
⌋
2
elements
one bad block of 0’s (since m ≥ 3). As in the proof of (i), one may show that there are m−1
of Bm,n with a bad block beginning at position i, and the result quickly follows.
4

Next we consider the non-trivial rotations. Recall that the order of an element σ ∈ Dn is the least
positive integer k such that g k = idn .
Lemma 3.2. If n ≥ 3, and if σ ∈ Dn is a rotation of order d, where 1 6= d  n, then
(
− n2 if d = 2
n
(i) fixGn (σ) = 2 d − 1 +
0
if d ≥ 3,
n
d
(ii) fixGm,n (σ) = m
for any 3 ≤ m ≤ n.
d

Proof. Let e = nd . Since all rotations of order d are powers of each other, each such rotation fixes the same
set of n-tuples from Gn and Gm,n . Thus, we may assume that σ is defined by σ(x) = x + e for all x. During
both parts of the proof, if a ∈ T n , we will write a∨ = (a1 , . . . , ae ) ∈ T e , while if b ∈ T e , we will write
b∧ = (b1 , . . . , be , b1 , . . . , be , . . . , b1 , . . . , be ) ∈ T n ; note that the entries of b are repeated d times in b∧ .
(i). With the above notation, an element a ∈ FixT n (σ) is completely determined by a∨ (since ax = ax+e
for all x), in which case a = (a∨ )∧ ; cf. Figure 3. It follows that FixT n (σ) = {b∧ : b ∈ T e }, and so
n
fixT n (σ) = 2e = 2 d . By (2.5), it remains to show that
(
n
if d = 2
fixBn (σ) = 1 + 2
0 if d ≥ 3.
Clearly (0, . . . , 0) ∈ FixBn (σ). It b ∈ T e is non-zero, then the longest block of 0’s in b∧ has length at
most e − 1 = nd − 1. If d > 2, then
(
k − 1 if n = 2k is even
n
n
d −1< 2 −1=
k − 12 if n = 2k + 1 is odd,
and so b∧ belongs to Gn for any non-zero b ∈ T e . It follows that fixBn (σ) = 1 if d > 2. If d = 2, then
n = 2k must be even; it is possible for b ∈ T e = T k to be non-zero, but to have b∧ ∈ Bn ; this occurs when b
has exactly one non-zero entry. It follows that fixBn (σ) = 1 + k = 1 + n2 if d = 2.
n
(ii). With the above notation, FixTm,n = {b∧ : b ∈ T md , nd }, and so fixTm,n (σ) = |T md , nd | = md . In the proof
d

of (i), we showed that any non-zero elements of FixBn (σ) have exactly two 1’s, and hence do not belong
to Bm,n (since m ≥ 3). It follows that fixBm,n (σ) = 0. Because of (2.5), this completes the proof.

b4

b1

b6

b3

b2

σ

b2

b1

b5
b3

b2

b4

b3

σ
b1

b4
b4

b3

b1
b3

b4
b2

b2

b5
b1

b6

Figure 3: The rotation σ ∈ Dn and the n-tuple b∧ = (b1 , . . . , be , b1 , . . . , be , . . . , b1 , . . . , be ) ∈ FixT n (σ), from
the proof of Lemma 3.2, in the case n = 12 and d = 3 (left) and d = 2 (right).
For the reflections, we need to consider separate cases according to the parity of n. We begin with the
odd case. Recall that here there are n reflections, each of which fixes a single point of {1, . . . , n}.

5

Lemma 3.3. If n ≥ 3 is odd, and if σ ∈ Dn is a reflection, then
( n+1
n−1
2 2 − 3 · 2 4 + 1 if n ≡ 1 (mod 4)
(i) fixGn (σ) =
n+1
n+5
2 2 −2 4 +1
if n ≡ 3 (mod 4),
 n   n   n+2 
⌊4⌋
⌊2⌋
⌊ 4 ⌋
−
−
for any 3 ≤ m ≤ n.
(ii) fixGm,n (σ) =
m
m
m
⌊2⌋
⌊2⌋
2
Proof. Write n = 2k + 1, and let l = ⌊ k2 ⌋, so that k = 2l or 2l + 1. All reflections fix the same number of
n-tuples from Gn and Gm,n (and from T n , Bn , etc.), so we may assume that the fixed point of σ is n, in
which case σ(x) = n − x for all x. If a ∈ T n , we write a∨ = (a1 , . . . , ak , an ) ∈ T k+1 , while if b ∈ T k+1 , we
write b∧ = (b1 , . . . , bk , bk , . . . , b1 , bk+1 ) ∈ T n .
(i). An element a ∈ FixT n (σ) is completely determined by a∨ , in which case a = (a∨ )∧ ; cf. Figure 4. It
n+1
follows that FixT n (σ) = {b∧ : b ∈ T k+1 }, and so fixT n (σ) = 2k+1 = 2 2 . By (2.5), it remains to show that
(
n−1
3 · 2 4 − 1 if k = 2l
fixBn (σ) =
(3.4)
n+5
if k = 2l + 1.
2 4 −1
To do so, consider some n-tuple a = b∧ ∈ FixT n (σ), where b ∈ T k+1 . Then a ∈ Bn if and only if at least
one of the following holds (cf. Figure 4):
(a) (b1 , . . . , bl , bk+1 ) = (0, . . . , 0), or

(b) (bl+1 , . . . , bk ) = (0, . . . , 0).

There are 2k−l (k + 1)-tuples b satisfying (a), 2l+1 satisfying (b), and one satisfying both (a) and (b). It
follows that fixBn (σ) = 2k−l + 2l+1 − 1; this reduces to the expressions stated in (3.4), by checking separate
cases for k = 2l or 2l + 1.
(ii). Now consider an element a ∈ FixTm,n (σ); again, we have a = b∧ for some b ∈ T k+1 . Since n is the
unique point of {1, . . . , n} fixed by σ, and since an = bk+1 , we must have
(
0 if m is even
bk+1 =
1 if m is odd.
The remaining entries b1 , . . . , bk of b may be chosen arbitrarily from T , as long as ⌊ m
2 ⌋ of them are 1’s. Thus,
⌋
⌋
⌊n
⌊n
⌊ n+2 ⌋
k 
2
4
fixTm,n (σ) = ⌊ m ⌋ = ⌊ m ⌋ . By (2.5), it remains to show that fixBm,n (σ) = ⌊ m ⌋ + m4 . Now, a = b∧
2

2

2

2

as above belongs to Bn if and only if one of (a) or (b) holds, as enumerated in the proof of (i). Now, (b)

⌋
⌊n
l
4
holds if and only if ⌊ m
2 ⌋ of b1 , . . . , bl are 1’s (recall that bk+1 is already fixed), so there are ⌊ m ⌋ = ⌊ m ⌋
2

2

(k + 1)-tuples b, with b∧ ∈ Bm,n , satisfying (b). For b to satisfy (a), m must be even (since bk+1 = 1
⌊ n+2
⌋
k−l
4
=
if m is odd). In this case, m
of
the
entries
b
,
.
.
.
,
b
must
be
1’s;
it
follows
that
there
are
m
m
l+1
k
2
2

2

is not an
(k + 1)-tuples b satisfying (a) when m is even; this is also true when m is odd, since then m
 2 ⌊ n+2 ⌋
⌊n
⌋
integer. Since no b can satisfy both (a) and (b), as m ≥ 3, it follows that fixBm,n (σ) = ⌊ m4 ⌋ + m4 , as
2

required.

Recall that there are two different kinds of reflections when n is even:
and n2 fixing two. We consider these separately.

n
2

fixing no points of {1, . . . , n},

Lemma 3.5. If n ≥ 4 is even, and if σ ∈ Dn is a reflection with no fixed points, then
( n
n+4
2 2 − 2 4 + 1 if n ≡ 0 (mod 4)
(i) fixGn (σ) =
n+6
n
2 2 − 2 4 + 2 if n ≡ 2 (mod 4),
n
 n+2 
⌊ 4 ⌋
2
(ii) fixGm,n (σ) = m − 2
for any 3 ≤ m ≤ n.
m
2

2

6

2

b7

b1

b8

b1

b1

b2

b2

b2

b3

b1
b2

b3

b3

b4

b4

b3

b4

b4
b5
b5

b5
b6

b5
b6

b6

b6

b7

σ

b7

σ

Figure 4: The reflection σ ∈ Dn and the n-tuple b∧ = (b1 , . . . , bk , bk , . . . , b1 , bk+1 ) ∈ FixT n (σ), from the
proof of Lemma 3.3, in the cases n = 13 (left) and n = 15 (right). If condition (a) or (b) from the proof
holds, then the green or blue vertices, respectively, yield a bad block of 0’s in b∧ . If neither (a) nor (b)
holds, then b∧ has no bad blocks.
Proof. Write n = 2k, and let l = ⌊ k2 ⌋. This time we may assume that σ is defined by σ(x) = n + 1 − x. If
a ∈ T n , we write a∨ = (a1 , . . . , ak ) ∈ T k , while if b ∈ T k , we write b∧ = (b1 , . . . , bk , bk , . . . , b1 ) ∈ T n .
n

(i). Again, we have FixT n (σ) = {b∧ : b ∈ T k }, so that fixT n (σ) = 2k = 2 2 . Thus, again by (2.5), it remains
to show that
( n+4
2 4 − 1 if k = 2l
(3.6)
fixBn (σ) =
n+6
2 4 − 2 if k = 2l + 1.
To do so, consider some n-tuple a = b∧ ∈ FixT n (σ), where b ∈ T k . Then a ∈ Bn if and only if at least one
of the following holds (cf. Figure 5):
(a) (b1 , . . . , bl ) = (0, . . . , 0), or

(b) (bk−l+1 , . . . , bk ) = (0, . . . , 0).

There are 2k−l k-tuples b satisfying (a), and also 2k−l satisfying (b). Only one b satisfies both (a) and (b)
if k = 2l, but there are two such b if k = 2l + 1 (compare the left and right diagrams in Figure 5). It follows
that fixBn (σ) = 2 · 2k−l − (1 or 2), as appropriate, which reduces to (3.6).
(ii). Now, FixTm,n (σ) is empty if m is odd (cf. Figure 5), in which case the stated formula for fixGm,n (σ)

k
holds, as m
2 is not an integer. From now on, we assume m = 2h is even. Clearly, fixTm,n (σ) = h . If

a = b∧ ∈ FixTm,n (σ) belongs to Bm,n , then exactly one of (a) or (b) holds, as above. There are k−l
h
k-tuples b satisfying (a), and the same number satisfying (b). Thus, by (2.5),
 

 n
 n+2 
k
k−l
⌊ 4 ⌋
2
fixGm,n (σ) = fixTm,n (σ) − fixBm,n (σ) =
−2
= m
−2
,
m
h
h
2
2
as required.
Lemma 3.7. If n ≥ 4 is even, and if σ ∈ Dn is a reflection with two fixed points, then
( n+2
n+8
2 2 − 2 4 + 1 if n ≡ 0 (mod 4)
(i) fixGn (σ) =
n+2
n+6
2 2 −2 4
if n ≡ 2 (mod 4),
 n 
 n 
⌊4⌋

2

if m is even

 m −2 m
(ii) fixGm,n (σ) =

2

2


 n 
n

−1
⌊4⌋


2 2 m
−2 m
⌊2⌋
⌊2⌋

if m is odd.

7

b1

b1

b1

b1

b2

b2

b2

b2

b3
b3

b3

b3
b4

b4

b4

b4
b5
b5

b5
b6

b5
b6

b6

b6
b7

b7

σ

σ

Figure 5: The reflection σ ∈ Dn and the n-tuple b∧ = (b1 , . . . , bk , bk , . . . , b1 ) ∈ FixT n (σ), from the proof of
Lemma 3.5, in the cases n = 12 (left) and n = 14 (right). If condition (a) or (b) from the proof is satisfied,
then the green or blue vertices, respectively, yield a bad block of 0’s in b∧ . If neither (a) nor (b) hold,
then b∧ has no bad blocks.
Proof. Write n = 2k, and let l = ⌊ k2 ⌋. This time we may assume that the fixed points of σ are 1 and k + 1,
in which case σ is defined by σ(x) = n + 2 − x. If a ∈ T n , we write a∨ = (a1 , . . . , ak+1 ) ∈ T k+1 , while
if b ∈ T k+1 , we write b∧ = (b1 , b2 , . . . , bk , bk+1 , bk , . . . , b2 ) ∈ T n .
(i). As usual, FixT n (σ) = {b∧ : b ∈ T k+1 }, and so fixT n (σ) = 2k+1 = 2
show that
( n+8
2 4 − 1 if k = 2l
fixBn (σ) =
n+6
2 4
if k = 2l + 1.

n+2
2

. Thus, by (2.5), it remains to
(3.8)

To do so, consider some n-tuple a = b∧ ∈ FixT n (σ), where b ∈ T k+1 . Then a ∈ Bn if and only if at least
one of the following holds (cf. Figure 6):
(a) (b1 , . . . , bk−l ) = (0, . . . , 0), or

(b) (bl+2 , . . . , bk+1 ) = (0, . . . , 0), or

(c) b = (1, 0, . . . , 0, 1).

For k = 2l or 2l + 1, respectively, there are 2 · 2l+1 − (2 or 1) elements b ∈ T k+1 satisfying (a) or (b). Since
b = (1, 0, . . . , 0, 1) satisfies neither (a) nor (b), it follows that fixBn (σ) = 2l+1 − (2 or 1) + 1, which reduces
to (3.8).
∧
k+1 . If m = 2h + 1 is
(ii). Write h = ⌊ m
2 ⌋, and consider some n-tuple a = b ∈ FixTm,n (σ), where b ∈ T
odd, then exactly one of b1 , bk+1 must be 1, and h of b2 , . . . , bk must be 1’s. If m = 2h is even, then either
b1 = bk+1 = 1 and h − 1 of b2 , . . . , bk are 1’s, or else b1 = bk+1 = 0 and h of b2 , . . . , bk are 1’s. Thus,
(


k−1
+ k−1
= hk if m = 2h is even
h−1
h

fixTm,n (σ) =
2 k−1
if m = 2h + 1 is odd.
h

By (2.5), and since k =

n
2

and h = ⌊ m
2 ⌋, it remains to show that fixBm,n (σ) = 2

b∧

⌊n
⌋
4
.
⌋
⌊m
2

To do so, consider

an n-tuple a =
∈ FixBm,n (σ). So b satisfies either (a) or (b), as above, and these are mutually exclusive
(since m ≥ 3); note that (c) cannot hold (also since m ≥ 3). Note that b satisfies (a) if and only if bk+1 = 0

⌊n⌋
or 1 (for m = 2h or 2h + 1, respectively), and h of bk−l+1 , . . . , bk are 1’s. There are thus hl = ⌊ m4 ⌋ such
2

(k + 1)-tuples b satisfying (a), and there are the same number satisfying (b).

4

Proofs of the main results

We are now in a position to complete the proofs of our main results, as stated in Section 1.

8

b2

b1

b2

b2

b3

b2

b3

b3

b4

b1

b3

b4

b4

b5

b5

b4

b5

b5
b6

b7

b6

b6

b6
b7

σ

b8

b7

σ

Figure 6: The reflection σ ∈ Dn and the n-tuple b∧ = (b1 , b2 , . . . , bk , bk+1 , bk , . . . , b2 ) ∈ FixT n (σ), from the
proof of Lemma 3.7, in the cases n = 12 (left) and n = 14 (right). If condition (a) or (b) from the proof is
satisfied, then the green or blue vertices, respectively, yield a bad block of 0’s in b∧ . If neither (a) nor (b)
hold, then b∧ has no bad blocks.
1 P
Proof of Theorem 1.5. Equation (2.4) says that pm,n = 2n
σ∈Dn fixGm,n (σ). From Lemmas 3.1 and 3.2,
and the fact that the cyclic group Cn has ϕ(d) elements of order d if d  n, the contribution to (2.4) made
by the rotations from Dn is


 
 n 
n
X
X ϕ(d)  n  1  ⌊ n ⌋ 
X
1  n
⌊2⌋
1
d
d
2

fixGm,n (σ) =
−n
=
+
.
ϕ(d) m
m −
2n
2n
2n
2
m
m−1
m
−
1
d
d
16=dn

σ∈Cn

Since

n
d
m
d



dn

P
P
= 0 if d 6 m, “ dn ” may be replaced by “ dgcd(m,n) ”. It therefore remains to show that the

contribution to (2.4) made by the reflections from Dn is
  n   n+2 
 m
X
⌋
⌊4⌋
⌊ 4 ⌋
1
1
⌊ 2 ⌋ + ⌊ n−m
2
−
−
.
fixGm,n (σ) =
m
m
m
2n
2
⌊2⌋
⌊2⌋
2
σ∈Dn \Cn

n
2

reflections with no fixed points, and n2
⌋
⌊ n+2
4
= 0 if m is
with two fixed points. Combining Lemmas 3.3, 3.5 and 3.7, and keeping in mind that
m
2
odd, we have
  n   n   n+2 
⌊2⌋
⌊4⌋
1
⌊ 4 ⌋



if n is odd
−
−

m
m
m

2
⌊
⌋
⌊
⌋

2
2
2




 1  n  ⌊ n ⌋ ⌊ n+2 ⌋
X
1
2
4
4
fixGm,n (σ) =
−
if n and m are both even
m −
m
m

2n
2

2
2
2

σ∈Dn \Cn


 n
  n   n+2 



1

2 − 1 − ⌊4⌋ − ⌊ 4 ⌋

if n is even m is odd.

m
2
⌊m
⌊m
2
2⌋
2⌋

If n is odd, then Dn has n reflections; if n is even, then Dn has

n−m
It finally remains to observe that ⌊ m
2 ⌋+⌊ 2 ⌋ is equal to
indeed, this may be checked on a case-by-case basis.

n
2 −1

if n is even and m is odd, or to ⌊ n2 ⌋ otherwise;

Proof of Theorem 1.6. With some careful algebra, (2.4) and Lemmas 3.1–3.7 yield

n−4
n−4

3 · 2 2 − 3 · 2 4 + 12 if n ≡ 0 (mod





n−5
n−1


2 2 − 3 · 2 4 + 21
if n ≡ 1 (mod
X ϕ(d) n

n
2 d − 1 − 2⌊ 2 ⌋−1 +
pn =
n+2

2n
3 · 2 n−4
2
− 2 4 + 21
if n ≡ 2 (mod
dn






n+1
2 n−1
2
if n ≡ 3 (mod
− 2 4 + 21
9

4)
4)
(4.1)
4)
4).

(Note that the “ n2 ” from the even P
case of Lemma 3.1(i) cancels out with the “ n2 ” from the d = 2 case of
Lemma 3.2(i).) Using the identity dn ϕ(d) = n, we have
X ϕ(d)

dn

2n

n
X ϕ(d) · 2 nd −1 1
 X ϕ(d) · 2 d
n
1 X
ϕ(d) =
−
− .
2d − 1 =
2n
2n
n
2

dn

dn

n

dn

n−4

n−4

The “ 12 ” here cancels those in (4.1). If n is even, then −2⌊ 2 ⌋−1 +3·2 2 = −2·2 2 +3·2
n
n−1
n−3
n−3
A similar calculation shows that if n is odd, then −2⌊ 2 ⌋−1 + 2 2 = 2 2 = 2⌊ 2 ⌋ .

n−4
2

=2

n−4
2

= 2⌊

n−3
⌋
2

.

Proof of Theorem 1.7. The dominant term in Theorem 1.6 is the d = 1 term of the sum: i.e., 2n−1 /n.
n
All other terms (of which there are at most n) are at most a constant multiple of 2 2 .
The formula pn ∼ 2n−1 /n = 2n /2n given in Theorem 1.7 can be interpreted as saying that: (i) practically
all of the 2n subsets of {1, . . . , n} correspond to polygons (cf. Lemma 3.1(i)); and (ii) practically all such
polygons are completely asymmetric, so that each equivalence class of polygons is counted approximately 2n
times.

5

Triangles and quadrilaterals

Specialising Theorem 1.5 to the case m = 3 allows us to recover Honsberger’s Theorem on triangles, stated
in Section 1 above.
Proof of Theorem 1.2. By Theorem 1.5, the number of inequivalent (i.e., incongruent) integer triangles
of perimeter n is
  n   n 

 
 

1
1 + ⌊ n−3
1 n
1 n3
2 ⌋ − ⌊2⌋ − ⌊4⌋ − 0
+
p3,n =
+
1
2
1
2n 3
n 1
2
⌊ n ⌋(⌊ n2 ⌋ − 1) ⌊ n4 ⌋
n2 − 3n + 2 (0 or 1) 1 + ⌊ n−3
2 ⌋
+
+
− 2
−
12
3
2
4
2
 2
n
−4 + (0 or 4) + (0 or 3)


if n is even

 48 +
12
=

2


 (n + 3) + −4 + (0 or 4) + (0 or 3) if n is even.
48
12
=

4
≤
Since p3,n is an integer, and since − 12 < − 12

integer to

n2
48

or

(n+3)2
48 ,

−4+(0 or 4)+(0 or 3)
12

≤

3
12

< 21 , it follows that p3,n is the nearest

as appropriate.

Specialising Theorem 1.5 to the case m = 4 gives the corresponding result concerning quadrilaterals,
which we have not seen proven elsewhere. For the statement, recall that [x] denotes the nearest integer to
the real number x (if such exists).
Theorem
5.1. For any positive integer n, the number of inequivalent integer quadrilaterals with perimeter n
 n3 −3n2 +20n
3 −7n
if n is even, or n 96
if n is odd.
is
96

Proof. As in the above proof of Theorem 1.2, we use Theorem 1.5 to show, case by case, that
 3
n −3n2 +20n

if n ≡ 0 (mod 4)

96


 n2 −7n+6
if n ≡ 1 (mod 4)
96
p4,n = n2 −3n
2 +20n−36

if n ≡ 2 (mod 4)

96


 n2 −7n−6
if n ≡ 3 (mod 4).
96
3

is an integer,
This clearly completes the proof in the n ≡ 0 (mod 4) case. In the n ≡ 1 case, since n −7n+6
96
3
n3 −7n
6
< 12 , certainly n −7n+6
is
the
nearest
integer
to
.
The
other
cases
are
analogous.
and since 96
96
96
Similar formulae could be obtained for pentagons, hexagons, and so on, although the formulae quickly
become unweildy.
10

6

Calculated values and concluding remarks

Tables 1 and 2 below give calculated values of pm,n and pn , respectively, for 3 ≤ n ≤ 20. Because of the
powers of 2 in Theorem 1.6, the pn sequence is very easy to compute; for example, the millionth term can
be calculated in well under 20 seconds on a standard laptop. The first four rows of Table 1 are Sequences
A005044, A057886, A124285 and A124286, respectively, on the Online Encyclopedia of Integer Sequences [1],
while the whole of Table 1 is Sequence A124287. At the time of writing, the sequence pn (Table 2) did not
appear on [1]; it is now Sequence A293818. Out of all these sequences, as far as we are aware, a formula had
only previously been proven for Sequence A005044 (Honsberger’s Theorem 1.2 concerning triangles, quoted
in Section 1 above).
If we were interested in polygon equivalence under rotations (and gentle squeezing) only, then the inequivalent integer m-gons (respectively, polygons) of perimeter n are in one-one correspondence with the
orbits of Gm,n (respectively, Gn ) under the action of the cyclic group Cn given by (2.2). If we write p′m,n
(respectively, p′n ) for the number of such inequivalent m-gons (respectively, polygons), then
   n 
X
1 X
⌊2⌋
ϕ(d) nd
′
pm,n = |Gm,n /Cn | =
,
fixGm,n (σ) =
m −
m−1
n
n
d
σ∈Cn

p′n

dgcd(m,n)

X ϕ(d) n
X ϕ(d) · 2 nd

n
n
1 X
⌊
⌋
fixGn (σ) =
= |Gn /Cn | =
− 1 − 2⌊ 2 ⌋ .
2d − 1 − 2 2 =
n
n
n
σ∈Cn

dn

dn

The sequence p′3,n (triangles up to rotation) is Sequence A008742 on [1]; curiously, however, A008742 is
listed as the Molien series of a certain three dimensional point group, with no reference to integer triangles.
More computed values may be found in Sequences A293819–A293823 on [1]. (Note that Sequence A124278
of [1] counts |Pm,n /Sm |: i.e., polygons up to arbitrary reorderings of the sides, under which (1, 1, 2, 2) and
(1, 2, 1, 2) are considered equivalent, for example; see also [3].)
Finally, we note that Theorem 1.6 has a seemingly interesting number-theoretic consequence, namely
n −1
P
d
that dn ϕ(d)·2
is an integer for n ≥ 3; cf. Sequences A000031, A053634 and A053635 on [1].
n
m\n
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3
1

4
0
1

5
1
1
1

6
1
2
1
1

7
2
3
3
1
1

8
1
5
4
4
1
1

9
3
7
9
7
4
1
1

10
2
9
13
15
8
5
1
1

11
4
13
23
25
20
10
5
1
1

12
3
16
29
46
37
29
12
6
1
1

13
5
22
48
72
75
57
35
14
6
1
1

14
4
25
60
113
129
125
79
47
16
7
1
1

15
7
34
92
172
228
231
185
111
56
19
7
1
1

16
5
38
109
248
359
435
374
280
147
72
21
8
1
1

17
8
50
158
360
584
745
749
600
392
196
84
24
8
1
1

18
7
54
186
491
868
1261
1382
1281
912
561
252
104
27
9
1
1

19
10
70
258
686
1324
2031
2489
2493
2052
1368
756
324
120
30
9
1
1

20
8
75
296
896
1870
3195
4237
4746
4261
3260
1980
1032
406
145
33
10
1
1

Table 1: The number pm,n of inequivalent integer m-gons with perimeter n, for 3 ≤ m ≤ n ≤ 20.
n

3
1

4
1

5
3

6
5

7
10

8
16

9
32

10
54

11
102

12
180

13
336

14
607

15
1144

16
2098

17
3960

18
7397

19
14022

20
26452

Table 2: The number pn of inequivalent integer polygons with perimeter n, for 3 ≤ n ≤ 20. These are
column sums of Table 1.
11

References
[1] The on-line encyclopedia of integer sequences. Published electronically at http://oeis.org/, 2017.
[2] George E. Andrews. A note on partitions and triangles with integer sides. Amer. Math. Monthly, 86(6):477–478, 1979.
[3] George E. Andrews, Peter Paule, and Axel Riese. MacMahon’s partition analysis. IX. k-gon partitions. Bull. Austral.
Math. Soc., 64(2):321–329, 2001.
[4] Peter J. Cameron. Combinatorics: topics, techniques, algorithms. Cambridge University Press, Cambridge, 1994.
[5] Leonard Eugene Dickson. History of the theory of numbers. Vol. II: Diophantine analysis. Chelsea Publishing Co., New
York, 1966.
[6] Michael D. Hirschhorn. Triangles with integer sides, revisited. Math. Mag., 73(1):53–56, 2000.
[7] Michael D. Hirschhorn. Triangles with integer sides. Math. Mag., 76(4):306–308, 2003.
[8] Ross Honsberger. Mathematical gems. III, volume 9 of The Dolciani Mathematical Expositions. Mathematical Association
of America, Washington, DC, 1985.
[9] Tom Jenkyns and Eric Muller. Triangular triples from ceilings to floors. Amer. Math. Monthly, 107(7):634–639, 2000.
[10] J. H. Jordan, Ray Walch, and R. J. Wisner. Triangles with integer sides. Amer. Math. Monthly, 86(8):686–689, 1979.
[11] Nicholas Krier and Bennet Manvel. Counting integer triangles. Math. Mag., 71(4):291–295, 1998.
[12] Martin J. Marsden. Triangles with integer-valued sides. Amer. Math. Monthly, 81:373–376, 1974.
[13] R. R. Phelps and N. J. Fine. Perfect triangles. Amer. Math. Monthly, 63:43–44, 1956.
[14] David Singmaster. Triangles with integer sides and sharing barrels. College Math. J., 21(4):278–285, 1990.
[15] M. V. Subbarao. Perfect triangles. Amer. Math. Monthly, 78:384–385, 1971.
JE: Centre for Research in Mathematics, Western Sydney University, Sydney, Australia; J.East @ WesternSydney.edu.au
RN: rniles @ yahoo.com

12

